Bob Lied

Posted on Oct 23

PWC 344, Task 2: Pick Up the Pieces

#perl #pwc #perlweeklychallenge

Task 2: Array Formation

The Task

You are given two lists: @source and @target.

Write a script to see if you can build the exact @target by putting these smaller lists from @source together in some order. You cannot break apart or change the order inside any of the smaller lists in @source.

Example 1:

Input: @source=([2,3], [1], [4]), @target=(1, 2, 3, 4)
Output: true
Use in the order: [1], [2,3], [4]

Example 2:

Input: @source=([1,3], [2,4]), @target=(1, 2, 3, 4)
Output: false

Example 3:

Input: @source=([9,1], [5,8], [2]), @target=(5, 8, 2, 9, 1)
Output: true
Use in the order: [5,8], [2], [9,1]

Example 4:

Input: @source=([1], [3]), @target=(1, 2, 3)
Output: false
Missing number: 2

Example 5:

Input: @source=([7,4,6]), @target=(7, 4, 6)
Output: true
Use in the order: [7, 4, 6]

The Thought Process

The musical selection for our programming journey is the funky disco-adjacent Pick Up the Pieces, by Average White Band. It was a number one hit in 1974, a time when it was still possible for an instrumental tune to make the charts. Fun personal anecdote: in my high school, the English department partnered with a local radio station (KYVA AM 1230 in Gallup, New Mexico) to put on a 15-minute show on Thursday evenings, and "Pick Up the Pieces" was our intro music.

Nostalgia aside, with a small number of lists in @source, it's tempting to just plow through all the possible combinations and see if any work, but factorial complexity is scary.

There's a little bit of ambiguity in the description. Although the examples imply it, it's not clear if we need to use all the substrings in @source, or if we can accept a solution that only uses some of them. I'm going with not necessarilly using all of the lists in @source if we don't need them.

What about reusing them? I'm going to say no to that.

The solution I lean toward is to use a stack of possibilities and backtrack if we can't satisfy the @target.

The Code

Does it blend?

Let's start with the sub-problem of checking if one of the lists in @source is a prefix of @target. I want a predicate function that answers whether a list p is a leading prefix of a list t.

sub isPrefix($p, $t)
{
    return false if @$p > @$t;
    my $match = true;
    for my ($i, $n) ( indexed $p->@* )
    {
        $match &&= ($n == $t->[$i]);
    }
    return $match;
}

Notes:

Our arguments are array references, so we'll be de-referencing them a lot.
If $p is longer than $t, then it can't possibly be a prefix.
Start by assuming that the answer is yes.
The indexed builtin in Perl is a convenient way to get variables for the index and the thing at the index in a simple syntax. Love it.
For each element in the prefix, $match continues to be true if the same position $t matches. We could bail from the loop as soon as $match becomes false, but with expected short lists, it might be faster to complete the loop than to insert more logic into each execution. No, I'm not going to benchmark for it.

Does it match?

On to the main event. I want to pick lists from @source that match the beginning of @target. Then, I remove that from consideration, both from @source and from the front of @target. Repeat.

If we hit a dead end, I want to be able to backtrack to an earlier point, so I'll stack my possibilities.

sub canMake($source, $target)
{
    my @stack = ( [ [ $source->@* ], [ $target->@*] ] );
    while ( @stack )
    {
        my ($s, $t) = pop(@stack)->@*;

        for my ($i, $p) (indexed $s->@* )
        {
            next unless isPrefix($p, $t);

            my @t = $t->@*;     # Make a copy of remaining target.
            splice(@t, 0, @$p); # Remove prefix from target.

            # Have we completely matched the target?
            if ( @t == 0 )
            {
                return true;
            }

            my @s = $s->@*;     # Make a copy of remaining source.
            splice(@s, $i, 1);  # Remove the segment we used.

            push @stack, [ \@s, \@t ];  # Try again with smaller sets.
        }
    }
    return false;
}