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**:

- N = 1692. We have seen the digits 1, 2, 6, and 9.
- 2N = 3384. We have seen the digits 1, 2, 3, 4, 6, 8, and 9.
- 3N = 5076. Now we have seen all ten digits. The answer is thus 5076.

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:

`$b`

is initialized to zero the first time it is used.- I use the idiom
`@{ [ function() ] }`

to embed a function in the double-quoted string. - I use the dollar variables
`$=`

and`$-`

which force the value to a integer and non-negative integer respectively. It looks a bit weird but it works just as well. - I initialize an array of 10 zero elements by creating 10 one element lists which are flattened in one array.
- I use a postfix while loop to bring the core of the calculation down to one line.
- Instead of counting all the elements and checking if they're all true, we inverse our logic and only return the elements that are not true. As said, that means all zero elements in
`@seen`

will be put in a list and returned by grep.`While`

will continue to loop while a non-empty list is returned.

- Instead of counting all the elements and checking if they're all true, we inverse our logic and only return the elements that are not true. As said, that means all zero elements in
- I use map to increment the value of each element in
`@seen`

that was a digit in the number. - I use an implicit return of the wanted value by calculating it as the last statement in the block.

## 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:

- When you flip a stack of pancakes, you invert the order of the pancakes and change the symbol. (
`+`

becomes`-`

and vica versa) - You need to take one continuous chunk (of pancakes) and flip all of them.
- 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:

: If we flip everything we get`+-`

`-+`

and then changing the symbols:`+-`

. Basically, we get the same stack. The solution is to flip the top`+`

pancakes first before flipping the`-`

pancakes as such:`+-`

becomes`--`

(flipping top pancake) and then flip everything:`++`

.: Flip everything, flip top one, don't flip anything (we're one stack of happy pancakes already).`--`

,`-+`

,`++`

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), @_
}
```