Greatest letter and

mashed arrays

Weekly challenge 264 — 8 April 2024

;

Task 2

You are given two arrays of integers, @source and @indices. The @indices can only contains integers 0 <= i < size of @source. Write a script to create target array by inserting at index $indices[i] the value $source[i].

Example 1Input: @source = (0, 1, 2, 3, 4) @indices = (0, 1, 2, 2, 1) Output: (0, 4, 1, 3, 2) @source @indices @target 0 0 (0) 1 1 (0, 1) 2 2 (0, 1, 2) 3 2 (0, 1, 3, 2) 4 1 (0, 4, 1, 3, 2)Example 2Input: @source = (1, 2, 3, 4, 0) @indices = (0, 1, 2, 3, 0) Output: (0, 1, 2, 3, 4) @source @indices @target 1 0 (1) 2 1 (1, 2) 3 2 (1, 2, 3) 4 3 (1, 2, 3, 4) 0 0 (0, 1, 2, 3, 4)Example 3Input: @source = (1) @indices = (0) Output: (1)

This is a somewhat challenging task to interpret in detail. If `@indices`

contains each of the digits `0 .. scalar @indices - 1`

just once, in any order, then it is clear that
we can simply set `$target[$i] = $source[$indices[$i]]`

. That's the easy case.

However, if `@indices`

contains repetitions - say (0, 1, 2, 2, 1) as per example 1 -
then we have to interpret 'insert' in the task description to mean: put it into `$target[$i]`

,
but if that is already occupied, move previously inserted numbers from `$target[$i]`

and upwards to the right by
one place. For example, you can see that when the 4 is inserted in Example 1 above, the 1, 3 and 2 have
been moved one place to the right.

But that isn't always going to work so neatly. Suppose `@indices`

contains
4, 4, 4, 4, 4, which is apparently allowed by the statement of the task. Applying the 'shift right'
strategy described above we will end up with a `@target`

of (?, ?, ?, ?, 1, 2, 2, 1, 0), where
? is an undefined value.

For `@target`

to be a fully-populated array the same length as `@indices`

(and `@source`

)
the requirements are that:

- one of the indices must be zero,
- another one must be 0 or 1,
- another one must be 0, 1 or 2,
- and so on.

The indices following the above rules can be in any order.

So how do we code this? Perl doesn't give us much support for inserting an element into
the middle of an
array, but it could be done using `push`

and the array slice feature, something like:

push $new_target, $target[0 .. 2]; push $new_target, $source[$indices[$i]]; push $new_target, $target[3 .. 4]; $target = $new_target;

But that's quite messsy, because either of the two array slices could be zero-length, and in any case it might not be necessary to move the entire right hand end of the target if there are still unoccupied elements there.

My next thought was a linked list, which is a data structure where each element has a value and a pointer to the next element. To insert a new element N between existing elements A and B you set N's pointer to the value of A's pointer and set A's pointer to point at N. No mass copying of elements is needed, but you do have to traverse the list multiple times. For the purist, that's probably the 'right' answer.

But I came up with a solution where, if the place in `@target`

for an item in `@indices`

is already occupied, I move the blocking item to the right one place, and use the same logic
to move subsequent items to the right until the next place in `@target`

is unoccupied. That
is relatively straightforward to code, though it is
perhaps not immediately obvious to understand.

I have included a fourth example where the rules listed above are not followed, and that
demonstrates a solution with a gap in `@target`

because the rules above are not followed.

This task is a good example of one that is easy to state, but quite challenging to code in a transparent and scalable fashion.

#!/usr/bin/perl # Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge use v5.26; # The Weekly Challenge - 2024-04-08 use utf8; # Week 264 - task 2 - Target array use warnings; # Peter Campbell Smith binmode STDOUT, ':utf8'; target_array([0, 1, 2, 3, 4], [0, 1, 2, 2, 1]); target_array([1, 2, 3, 4, 0], [0, 1, 2, 3, 0]); target_array([1], [0]); target_array([0, 1, 2, 3, 4], [3, 0, 4, 3, 2]); target_array([11, 12, 13, 14, 15, 16, 17, 18, 19, 20], [9, 4, 2, 7, 5, 8, 1, 0, 3, 6]); target_array([11, 12, 13, 14, 15, 16, 17, 18, 19, 20], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]); sub target_array { my (@source, @indices, @target, $i, $j, $k, $hold, $value); @source = @{$_[0]}; @indices = @{$_[1]}; # loop over indices for $i (0 .. @indices - 1) { $j = $indices[$i]; $value = $target[$j]; # if the place in @target is occupied, move it and subsequent ones right $k = $j; while (defined $value) { $hold = $target[$k]; $target[$k] = $value; $value = $hold; $k ++; } $target[$j] = $source[$i]; } # show results (with '?' for undefined - see analysis) for ($j = 0; $j < @target; $j ++) { $target[$j] = '?' unless defined $target[$j]; } say qq[\nInput: \@source = (] . join(', ', @source) . ')'; say qq[ \@indices = (] . join(', ', @indices) . ')'; say qq[Output: (] . join(', ', @target) . ')'; }

Input: @source = (0, 1, 2, 3, 4) @indices = (0, 1, 2, 2, 1) Output: (0, 4, 1, 3, 2) Input: @source = (1, 2, 3, 4, 0) @indices = (0, 1, 2, 3, 0) Output: (0, 1, 2, 3, 4) Input: @source = (1) @indices = (0) Output: (1) Input: @source = (0, 1, 2, 3, 4) @indices = (3, 0, 4, 3, 2) Output: (1, ?, 4, 3, 0, 2) Input: @source = (11, 12, 13, 14, 15, 16, 17, 18, 19, 20) @indices = (9, 4, 2, 7, 5, 8, 1, 0, 3, 6) Output: (18, 17, 13, 19, 12, 15, 20, 14, 16, 11) Input: @source = (11, 12, 13, 14, 15, 16, 17, 18, 19, 20) @indices = (0, 0, 0, 0, 0, 0, 0, 0, 0, 0) Output: (20, 19, 18, 17, 16, 15, 14, 13, 12, 11)

Any content of this website which has been created by Peter Campbell Smith is in the public domain