PWC 269 Two of Us Distributing Elements

You and I have memories, longer than the road that stretches out ahead. Remember when refactoring was a Big Deal? Let's do some of that this week.

Two of Us Lyrics Music

Task 2: Distribute Elements

You are given an array of distinct integers, @ints.

Write a script to distribute the elements as
described below:

1) Put the 1st element of the given array to
a new array @arr1.
2) Put the 2nd element of the given array to
a new array @arr2.

Once you have one element in each arrays,
@arr1 and @arr2, then follow the rule below:

If the last element of the array @arr1 is greater
than the last element of the array @arr2, then
add the first element of the given array to @arr1,
otherwise to the array @arr2.

When done distribution, return the concatenated
arrays, @arr1 and @arr2.

Example 1

• Input: @ints = (2, 1, 3, 4, 5)

• Output: (2, 3, 4, 5, 1)

  • 1st operation: Add 2 to @arr1 = (2)
  • 2nd operation: Add 1 to @arr2 = (1)
  • 3rd operation: Now the last element of @arr1 is greater than the last element of @arr2, so add 3 to @arr1 = (2, 3).
  • 4th operation: Again the last element of @arr1 is greater than the last element of @arr2, add 4 to @arr1 = (2, 3, 4)
  • 5th operation: Finally, the last element of @arr1 is again greater than the last element of @arr2, add 5 to @arr1 = (2, 3, 4, 5)
  • Now we have two arrays: @arr1 = (2, 3, 4, 5) and @arr2 = (1)
  • Concatenate the two arrays and return the final array: (2, 3, 4, 5, 1).

Phase 1, in which Doris gets her oats

That's a very prescriptive specification and example. We could hardly do anything else.

sub distElem(@ints) 
{
    my @arr1 = shift @ints; 
    my @arr2 = shift @ints; 
    while ( defined(my $n = shift @ints) )
    {
        if ( $arr1[-1] > $arr2[-1] ) {
            push @arr1, $n;
        } else {
            push @arr2, $n;
        }
    }
    return [ @arr1, @arr2 ];
}

Perl notes:

• We're using up the @ints array by shifting off one element at a time. Numbers could be zero, and we don't want that interpreted as false, so the accurate check is to look for the undef when the array becomes empty.
• Perl can index from the end by using negative offsets. We don't have to do any bookkeeping about the lengths of the arrays.

Sunday driving, not arriving

It irks me to have the two variables named arr1 and arr2. What is this, BASIC? It's a list of two arrays, so let's do that refactoring.

sub distElem(@ints) 
{
    my @arr = ( [shift @ints], [shift @ints] );
    while ( defined(my $n = shift @ints) )
    {
        if ( $arr[0][-1] > $arr2[1][-1] ) {
            push @{$arr[0]}, $n;
        } else {
            push @{$arr[1]}, $n;
        }
    }
    return [ $arr[0]->@*, $arr[1]->@* ];
}

Perl notes:

• We now have an array of two references to arrays, so we see array de-referencing syntax. The first argument to push needs to be an array, so the @{...} turns the reference into an array. In the return statement, I use newer-style postfix de-referencing.

Burning matches, lifting latches

Now I'm annoyed by that if statement. We only have to choose between 0 and 1, and we have a condition that will be either true or false. Zero, one; false, true. Po-tay-to, po-tah-to. Let's use that condition to make an index.

sub distElem(@ints) 
{
    my @arr = ( [shift @ints], [shift @ints] );
    while ( defined(my $n = shift @ints) )
    {
        my $which = ( $arr[0][-1] <= $arr[1][-1] );
        push @{$arr[$which]}, $n;
    }
    return [ $arr[0]->@*, $arr[1->@*} ];
}

Perl notes:

• True and false values will be interpreted as 1 and zero, respectively, when used in an arithmetic context.
• I changed the test from > to <= so that the array order is the same.

Chasing paper, getting nowhere

Introducing the $which variable seems arbitrary. Let's put that in-line.

sub distElem(@ints) 
{
    my @arr = ( [shift @ints], [shift @ints] );
    while ( defined(my $n = shift @ints) )
    {
        push @{$arr[ $arr[0][-1] <= $arr[1][-1 ]}, $n;
    }
    return [ $arr[0]->@*, $arr[1->@*} ];
}

Wearing raincoats, standing solo

Why am I chewing up the @ints array with shifts? Let's just iterate over it.

sub distElem(@ints) 
{
    my @arr = ( [shift @ints], [shift @ints] );
    push @{$arr[ $arr[0][-1] <= $arr[1][-1 ]}, $_ for @ints;
    return [ $arr[0]->@*, $arr[1->@*} ];
}

We're on our way home, we're going home

One last thing: can we make it do reasonable things when the @ints array has 0 or 1 elements? Currently, that inital shift to initialize @arr would put an undef value into the lists. Let's account for the possibility.

sub distElem(@ints)
{
    my @arr = ( [ (shift @ints) // () ], [ (shift @ints) // () ] );

    push @{$arr[ ( $arr[0][-1] <= $arr[1][-1] ) ]}, $_ for @ints;

    return [ $arr[0]->@*, $arr[1]->@* ];
}

Perl notes:

• shift on an empty array will yield undef, but we want an empty list in that case.
• The // operator is really useful for checking defined-ness. In the old days, code was littered with if (defined(...)) tests.

The long and winding road (oops, wrong song)

That was the process I used to get from 11 lines to 3. Of course, there were unit tests executed at every step. The final code, including tests is in GitHub