Code Jam Quals 2016 - Counting sheep and Revenge of the pancakes

After noticing yesterday that the Google Code Jam Quals was happening, I decided that it would be a productive activity to solve them. :) So here's my solution for the first two problems. I'll cover the other two problems in a later blog post.

Counting sheep

Simplified problem statement: Given a number N, create the sequence N, 2N, 3N, ... and return the element at which you have seen all digits pass. If it is impossible to get all the digits, print "INSOMNIA".

Example:

My original solution was this:

use strict;
use warnings;

use Data::Printer;

main(@ARGV);

sub main {
    chomp(my $n = <>);
    my $c = 1;
    while($n--) {
        chomp(my $input = <>);
        print "Case #" . $c++ . ": " . case($input) . "\n";
    }
}


sub case {
    my $number = shift;
    return 'INSOMNIA' if $number == 0;
    my @seen = (0) x 10;
    my $multiplier = 1;

    while(!seenAllNumbers(@seen)) {
        my $new_number = $number * $multiplier++;
        foreach(split //, $new_number) {
            $seen[$_] += 1;
        }
    }

    return $number * --$multiplier;
}

sub seenAllNumbers {
    my @seen = @_;
    my $s = 0;
    map {$s++ if $_} @seen;
    return $s == 10;
}

We create an array of size 10 and initialize each value to zero. Each time we see a digit, we increment the element of the array at the position of the digit. When all elements in the array are "true" (0 is false in Perl), we stop the loop and print the last number in the sequence.

Because I like to simplify things to its core, I refactored the script to take use of some of Perl's built-in mechanisms to write shorter code (more one-liner like).

my $a = <>;
while($b++ != $a) {
    chomp(my $input = <>);
    print "Case #$b: @{ [ case($input) ] }$/";
}

sub case {
    ($=, $-, @seen) = (1, pop, (0) x 10);
    return 'INSOMNIA' if ! $-;
    map { ++$seen[$_] } split //, $- * $=++ while grep{ !$_ } @seen;
    $- * --$=;
}

Here's a list of some Perl quirks I took advantage off:

Revenge of the pancakes

Simplified problem statement: Given a string containing + and - symbols. How many flips does it take to convert the string to all + symbols when you are given the following constraints:

  1. When you flip a stack of pancakes, you invert the order of the pancakes and change the symbol. (+ becomes - and vica versa)
  2. You need to take one continuous chunk (of pancakes) and flip all of them.
  3. You always flip from the first pancake (index 0) to some pancake i with index i greater or equal to zero.

Example: If we start with --+-, we flip all pancakes, so the symbol changes (++-+) and the order reverses, giving +-++. We then flip the top pancake: --++ and now flip the top two pancakes: ++++. We thus needed three flips.

My original solution was this:

use strict;
use warnings;

use Data::Printer;

main(@ARGV);

sub main {
    chomp(my $n = <>);
    my $c = 1;
    while($n--) {
        chomp(my $input = <>);
        print "Case #" . $c++ . ": " . case($input) . "\n";
    }
}


sub case {
    my $s = shift;
    my @stack = split //, $s;
    my $flip_until_index = $#stack; # We start by checking everything...
    my $flips_done = 0;

    while(!everythingHappy(@stack)) {
        # Check from $flip_until_index upwards (so lower indexes) what's all happy,
        # we don't have to flip that...
        while($stack[$flip_until_index] eq '+') {
            $flip_until_index--;
        }

        if($flip_until_index < 0) {
            # My job is done here!
        } else {
            if($stack[0] eq '+') { # infinite loop anders
                # Flip the positive pancakes on top...
                my $p = 0;
                while($stack[$p] eq '+') {
                    $p++;
                }
                @stack = flip_until_index(@stack, $p-1);
            } else { # Flip everything from top to $flip_until_index
                @stack = flip_until_index(@stack, $flip_until_index);
            }
            $flips_done++;
        }

    }

    return $flips_done;
}

sub everythingHappy {
    my @stack = @_;
    my $happy = 1;
    foreach(@stack) {
        $happy = 0 if $_ eq '-';
    }
    return $happy;
}

sub flip_until_index {
    my $end_index = pop;
    my @stack = @_;

    my @reversed_top = reverse splice @stack, 0, $end_index + 1;
    my $joined = join('', @reversed_top);
    $joined =~ tr/+-/-+/;
    @reversed_top = split(//, $joined); 
    return (@reversed_top, @stack);
}

If we consider all posibilities of a stack of 2 pancakes, we notice two groups:

Now we work from the bottom of the stack and gradually make everything happy and reducing the size of our flips. If everything at the bottom is happy, we don't need to flip it anymore.

As before, we can simplify the code a lot. My initial solution is always a mess...

We can turn everythingHappy() into a one-liner by grepping for -:

sub everythingHappy {
    grep /-/, @_
}

Because of the constraints of the problem (maximum size of the stack of pancakes is only 100), we can use built-in functions to create new arrays of our stack. If the maximum size of the stack of pancakes would have been significantly bigger, I would have preferred to do in array modifications without creating copies of the array.

The original code can be optimized by not converting the array to a string and back, but by using map and "translating" each character at its turn:

sub flip_until_index {
    ((map { tr/+-/-+/;$_ } reverse splice @_, 0, pop() + 1), @_)
}

The big while loop in the case subroutine can also be simplified. We notice that $flip_until_undex is only important when the top pancake is happy. If this is the case and $flip_until_index is -1 then we are done with flipping (all pancakes are happy).

while(grep /-/, @stack) {
    $flip_until_index-- while $stack[$flip_until_index] eq '+';

    if($stack[0] eq '+' && $flip_until_index >= 0) {
        @stack = flip_until_index(@stack, shift [grep { $stack[$_] eq '-' } 0..$flip_until_index]);
    } else {
        @stack = flip_until_index(@stack, $flip_until_index + 1);
    }

    $flips_done++;
}

Let me explain what is going on at line 5. Remember that in this case, we want to flip all happy pancakes on top until we get a sad pancake. We can get the index of the first sad pancake by creating a list of the indexes of sad pancakes and then taking the first one (which is what the shift function does).

Note: I also changed the function flip_until_index() at this point to not increment the number passed by 1, which is why i do not need the + 1 at line 5 and the - 1 at line 7.

We thus get something like this:

my $a = <>;
while($b++ != $a) {
    chomp(my $input = <>);
    print "Case #$b: @{ [ case($input) ] }$/";
}

sub case {
    my @stack = split //, shift;
    my $i = $#stack; # Bottom pointer
    my $flips_done = 0;

    while(grep /-/, @stack) {
        $i-- while $stack[$i] eq '+';

        if($stack[0] eq '+' && $i >= 0) {
            @stack = flip_until_index(@stack, shift [grep { $stack[$_] eq '-' } 0..$i]);
        } else {
            @stack = flip_until_index(@stack, $i + 1);
        }

        $flips_done++;
    }

    return $flips_done;
}

sub flip_until_index {
    (map { tr/+-/-+/;$_ } reverse splice @_, 0, pop), @_
}

*****
Written by Adriaan Dens on 10 April 2016