Perl Weekly Challenge 116: Number Sequence

This is pretty simple to solve. Once we have a starting number N, it's easy to process throught the list:

• Check if the string starts with the number; if not, we have a failure.
• Else, remove N from the beginning of the string, and recurse with N + 1 and the remainder of the string; if this fails, recurse with N - 1 and the remainder of the string. If this fails as well, the entire match fails.

We're the left with picking the starting number. There are only a few possible starting numbers: each of the prefixes of the string.

It's not hard to see the running time is linear in the lenght of the string. Going into recursion twice has the appearance of an exponential time algorithm, but it's impossible for a string to start with both N + 1 and N - 1 — at least one of the recursive calls has to terminate immediately.

First, we create a subroutine make_sequence. It gets two arguments, $string, the string we have to turn into a sequence, and $start, the number the sequence should start with. If we can make a sequence, we return an array with the chunks (in reverse order — this is because it's more efficient to repeatedly push to an array than to unshift). If we cannot make a sequence, we return undef.

In particular, if the starting number equals the whole string, we return an one element array with that starting number:

sub make_sequence ($string, $start) {
    if ($string eq $start) {
        return [$start]
    }
    if (index ($string, $start) == 0) {
        my $tail = substr $string, length $start;
        my $rest;
        if (($rest = make_sequence ($tail, $start + 1)) ||
            ($rest = make_sequence ($tail, $start - 1))) {
            push  @$rest => $start;
            return $rest;
        } 
    }
    return;
}

Now it's a matter of calling this method with each of the possible prefixes of the given input (which we have in $_): we can stop and print the result the first time we get an defined result:

for my $i (1 .. length) {
    #
    # Try to make a sequence with each possible start.
    #
    my  $result = make_sequence $_, substr $_, 0, $i;
    if ($result) {
        say join "," => reverse @$result;
        last;
    }
}

Note that we always find a sequence — in the worst case, it's a one element sequence equal to the entire string. And this is exactly what we should print if no sequence can be made.

Find the full program on GitHub.