Here's part 2. :)

## Coin Jam

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

- Every digit is either 0 or 1.
- The first digit is 1 and the last digit is 1.
- If you interpret the string in any base between 2 and 10, inclusive, the resulting number is not prime.

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.

- Each L in the sequence will be replaced with the original sequence of K tiles.
- Each G in the sequence will be replaced with K gold tiles.

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.

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.