Task — Target array

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].

Examples

Example 1
Input: @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 2
Input: @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 3
Input: @source  = (1)
       @indices = (0)
Output: (1)

Analysis

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.

Try it 

#!/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) . ')';
}

Output

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)