Code Jam Quals 2016 - Coin Jam and Fractiles

Here's part 2. :)

Coin Jam

(Simplified) problem statement: A jamcoin is a string of N ≥ 2 digits with the following properties:

Generate J jamcoins with a non-trivial divisor for each base for a jam coin of length N.

Example: If N = 4 and J = 1, then 1001 is a jam coin. Interpreting from base 2 to 10: 9, 28, 65, 126, 217, 344, 513, 730, and 1001. None of these are prime since we can generate a non-trivial divisor for each of them: 3, 7, 5, 6, 31, 8, 27, 5, and 77.

My original solution was this:

use strict;
use warnings;

use Data::Printer;
use Math::Prime::XS qw(primes is_prime);

main(@ARGV);

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


sub case {
    my ($n, $j) = split / /, shift;
    my $generated = 0;
    my %jamcoins = ();
    while($j) {
        my $jam_coin = generate_possible_jamcoin($n, $generated++);

        # Interpret the number as base 2..10
        my @bases = ();
        my $theres_a_prime = 0;
        foreach(2..10) {
            my $number_in_base = base_converter($jam_coin, $_);
            push @bases, $number_in_base;
            if(is_prime($number_in_base)) {
                $theres_a_prime = 1;
                last;
            }
        }
        next if $theres_a_prime;

        # Ok, all numbers are definitely not prime, now find divisors for each...
        my @divisors = ();
        foreach my $b (@bases) {
            foreach my $i (2..$b-1) {
                if($b % $i == 0) {
                    push @divisors, $i;
                    last;
                }

            }
        }

        print "$jam_coin @divisors\n";

        $j--;
    }
}

sub generate_possible_jamcoin {
    my ($n, $g) = @_;
    my $bin = to_base2($g, $n - 2); # -2 because first and last bit are 1 anyway.
    return '1' . $bin . '1';
}

sub to_base2 {
    my ($n, $l) = @_;
    return sprintf("%0${l}b", $n);
}

sub base_converter {
    my ($jam_coin, $base) = @_;

    my $number = 0;
    my $powah = 0;
    foreach(reverse(split //, $jam_coin)) {
        $number += $_ * $base**$powah;
        $powah++;
    }
    return $number;
}

My generator for jam coins is quite easy. I use a variable that increments by 1 each time and convert it to a base 2 string representation. To satisfy the condition that jam coins always start and end with a '1', I just prepend and append '1' to the base 2 string. I use sprintf to generate the base 2 string of length N - 2 (because I append and prepend a '1', I need a shorter string).

To check if a number is prime, I used an XS Perl module called Math::Prime::XS. This actually resulted in a problem on the big input provided by Google since the library apparently cannot handle very large numbers. :( So sadly, I didn't solve the big input during the Quals.

But anyway, let's refactor a bit.

Generating jam coins

This can actually be done in a one-liner in the main function.

my $jam_coin = '1' . sprintf('%0' . ($n - 2) . 'b', $generated++) . '1';

If you try to put this in a separate subroutine, but still in a one-liner, you loose the meaning of the arguments passed to the function. So it's more obvious to put this in the case() function where you have the $n and $generated variables.

Base converter

We can simplify this into two lines:

sub base_converter {
    my ($number, $powah) = (0, 0);
    pop [ map { $number += $_ * $_[1]**$powah++ } reverse split //, $_[0] ];
}

First foreach loop

We can convert primes for each base shorter with map:

my @bases = map { base_converter($jam_coin, $_) } 2..10;

And going to the next jam coin if one of the numbers is prime:

next if grep { is_prime($_) } @bases;

This once again exploits the fact that an empty array resolves to false in a boolean context.

Second foreach loop

I've kept it the same as before since map and grep are not effected by loop control mechanisms such as last and next. This means that we would not be able to break out of the inner loop when we found a divisor, when using map.

Problems with Math::Prime::XS

When I tried running it with the large input, I was greeted with the following error:

$ perl sol_min.pl < C-large.in > output.txt
Cannot isprime() on 4.65661e+21 at sol_min.pl line 18, <> line 2.

This problem can be solved by using the BigNum modules that Perl offers. base_converter() would be rewritten as:

sub base_converter {
    my ($number, $powah, $jam_coin, $base) = (Math::BigInt->new(0), -1, $_[0], Math::BigInt->new($_[1]));
    pop [ map { ++$powah;$number->badd( $base->copy()->bpow($powah)->bmul($_) ) } reverse split //, $jam_coin ];
}

And the second loop would become:

# Find divisors for each number
my @divisors = (); my $too_much_work = 0;
STAPH: foreach my $b (@bases) {
    foreach my $i (2..1000) {
        if($b->copy()->bmod($i)->is_zero()) { # Yeah, we found a non-trivial divisor
            push @divisors, $i;
            last;
        } elsif($i == 1000) {
            $too_much_work = 1;
            last STAPH;
        }
    }
}
next if $too_much_work;

With some effort and efficiency loss, we can rewrite it to the following:

my @divisors = grep { $_ } map { my $b = $_; pop [ grep { $b->copy()->bmod($_)->is_zero() } 2..100 ]; } @bases;
next if @divisors != 9;

Let's quickly go through it: We loop through all the numbers using map and return the first non-trivial divisor or false if there is none. Then we grep for true values with grep. If we got nine divisors, meaning we found a divisor for each number, then we can say we found a jam coin.

To improve efficiency, I lowered the upper bound to one hundred. I had to do this because we can't use loop control functions as explained before.

Shorter version

So in the end, we get this:

use Math::BigInt lib => 'GMP';
use Math::Prime::Util qw(is_prime);

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

sub case {
    my ($generated, $n, $j) = (0, split / /, shift);
    while($j) {
        my $jam_coin = '1' . sprintf('%0' . ($n - 2) . 'b', $generated++) . '1';
        my @bases = map { base_converter($jam_coin, $_) } 2..10;
        next if grep { is_prime($_) } @bases;
        my @divisors = grep { $_ } map { my $b = $_; pop [ grep { $b->copy()->bmod($_)->is_zero() } 2..100 ]; } @bases;
        next if @divisors != 9;
        print "$jam_coin @divisors\n"; $j--;
    }
}

sub base_converter {
    my ($number, $powah, $jam_coin, $base) = (Math::BigInt->new(0), -1, $_[0], Math::BigInt->new($_[1]));
    pop [ map { ++$powah;$number->badd( $base->copy()->bpow($powah)->bmul($_) ) } reverse split //, $jam_coin ];
}

So note to self: Next time start using Math::BigInt from the beginning. :)

Fractiles

(Simplified) problem statement: We have an unknown sequence consisting of K tiles. Each tile is either L (lead) or G (gold). The original sequence of K tiles can grow like a fractal with the following rules.

When we apply these rules, we say that the complexity C has increased by one. Given K, C and a number S, the number of tiles we can ask the state of, can we know if there was a gold tile in the original sequence?

Remark: The easy case always has K = S.

Example: K = 2, C = 3 and S = 2. The four begin sequences are: LL, LG, GL and GG. With complexity C = 3, they produce respectively: LLLLLLLL, LGGGGGGG, GGGGGGGL, GGGGGGGG. If we can ask the state of any two tiles, we can pick tile 2 to 7 to know if there was a gold tile in the original sequence.

The easy case is literally solved in 5 minutes. Since K = S, we can just ask for the first K tiles. If the leftmost tile at complexity C - 1 was 'L', then the first K tiles are equal to the original sequence. If the leftmost tile at complexity C - 1 was 'G', then the first K tiles are all gold and we thus know that we have a gold tile in the original sequence.

use strict;
use warnings;

main(@ARGV);

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


sub case {
    my ($k, $c, $s) = split / /, shift;
    return join(' ', 1..$k) 
}

For the difficult case, we have to be a bit smarter. As with the small case, we basically want to find positions in the sequence of complexity C where we know we can find a G in 2^K - 1 cases. If we can't do that, we cannot say with certainty that there was a gold tile in the original sequence.

Three weeks later

I'm sad to say that this post had become some kind of road block where I wasn't feeling like doing anything because I should be finishing this blog post. So here I am, three weeks after writing most of it (except for the hard part), saying that I won't finish it. In the mean time, I did some cool stuff on other projects (Raspberry Pi cluster anyone?) and spent a few hours on some CTF challenges that I would rather write on. So I'll just leave you a link to the official solution and I see you again in a new blog post.

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