Coin Jam - What I Did (Google CodeJam 2016)

In my quest to learn more about this competition that I just recently discovered, I came across this page where the Google Code Jam problem authors discuss their process for creating well-designed competition problems.  The whole thing was an enlightening read, but I mention it here to reference the section where they discuss problem difficulty, which ends with this:

This is (very roughly) what we aim for in Code Jam's qualification round: easy; easy, but insight required; medium-hard.

When I read this it made perfect sense to me in the context of the Qualification Round problems I've been documenting here.  The first problem was easy.  The second problem was easy, once you had the right insight about how to optimally flip the pancakes.  With that said, we now move onto the third problem where the difficulty definitely ramps up.

In particular, the third problem seems designed to foil the trusty tool I (and probably most beginning programmers/puzzlers) use: brute force.  I figured I'd need to be more clever to solve this one:

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.

When sending someone a jamcoin, it is polite to prove that the jamcoin is legitimate by including a nontrivial divisor of that jamcoin's interpretation in each base from 2 to 10.

Can you produce J different jamcoins of length N, along with proof that they are legitimate?

As it turns out, my solution really was just brute force, although I did put a little thought into it so it would actually run and produce output in a reasonable amount of time.  I didn't come close to the more elegant, analytical solution that this problem was presumably designed to elicit.  In this post I'll talk about what I did, and in a separate post I'll look at what I should have done.

After deciding that I was going to try to brute-force this problem, I broke it down into several steps:

  1. Generate potential jamcoins.
  2. Convert each jamcoin into each of the bases from 2 through 10.
  3. Check if any of these conversions are prime.
  4. If it's composite in every base, output the jamcoin with a list of divisors.

There are a variety of ways to do step 1.  I settled on what seemed like a quick and straightforward approach: generate binary numbers in succession, prepending as many leading zeros as necessary and adding 1s to the beginning and end to create a jamcoin of the desired length:

Now we have a function to generate strings of 1s and 0s.  We need to convert this representation into decimal for each base so we can test if it's prime.  This isn't very complicated:

So far so good, but now comes the harder part.  We need to check if any of these conversions is prime, and these are really big numbers.  For smaller numbers I could implement a basic sieve of Eratosthenes to check for compositeness but that would just take too long - we only have 8 minutes to submit a solution for the large variant of the problem, in which we have to successfully generate 500 different 32-digit jamcoins.

What I opted for instead was a probabilistic algorithm known as the Miller-Rabin primality test.  This test won't technically tell us for certain if a number is prime, though if we run it a sufficient number of times it will tell us with a very high degree of confidence.  I used this Python implementation of the algorithm (which is the function

probably_prime()

you'll see in end result below).

This will allow us to quickly test if our jamcoins are composite in every base.  When we've found one, we also need to output a list of divisors, which I did separately:

For this step I just tried to find a divisor less than 10,000.  If it didn't find one, I'd subsequently throw this jamcoin out as if it failed the compositeness test.  This means we're potentially throwing out valid jamcoins but I assumed there would be more than enough that we could afford to skip over some valid candidates.

Finally I put it all together, and ran it for the given parameters of the problem:

As the title of this post indicates, that's what I did.  This is not to be confused with what I should have done (which I'll go over in the next post).  Admittedly, this solution just brute-forces the answer and is not even very efficient at doing that.  I made a number of suboptimal and even redundant choices above, so this should not be construed as THE way to solve the problem.  But it is A way to solve the problem, which goes to show that there is more than one way to skin a cat.

Leave a Reply