Monthly Archives: July 2008

Google Code (Peanut Butter and) Jam

Last Friday, I participated in the Google Code Jam, a programming puzzle contest sponsored by Google. It was the first qualification round, and I was very happy with how I did, coming in 74th in my heat (there were three heats, and mine had almost 3000 participants).

There were three problems, each with two data sets. The last problem was really more of a math problem, which I figured would have given me more of an edge because most of the time when I cheat on my second love, computers, it’s with my first love, math. However, I couldn’t complete it in the time allotted. But I also couldn’t stop thinking about it. I eventually came up with a solution which I’ll share here.

It’s problem C in round 1A (start here), but essentially, you have to find the last three digits before the decimal point for the number (3 + √5)n where n is a whole number that can be very large (up to two billion).

This means you cannot calculate the whole thing; it would contain several hundred million digits, which would use most of RAM just to hold the representation. So you have to figure out a trick.

Here’s what I came up with (too late to submit). Let An = (3 + √5)n and Bn = (3 – √5)n. Observe that An = Xn + Yn√5 for some series X0, X1, … and Y0, Y1, … where each of Xn and Yn are whole numbers. You can show this easily by induction. You can show a similar thing for Bn; in fact, Bn = Xn – Yn√5.

This means that An+Bn = 2Xn.

Notice that (3 – √5) < 1, so Bn < 1 for n>1, and goes towards 0 very quickly. Since An = 2Xn – Bn, we can calculate An by calculating 2Xn and subtracting a “small” number… that is, the last three digits of An are the same as the last three digits of 2Xn-1.

So all we need to do is figure out Xn!

We know that X0 = 1, Y0 = 0. An+1 = An(3 + √5), so

Xn+1 + Yn+1√5 = An+1 = An(3 + √5) = (Xn + Yn√5)(3 + √5) = (3Xn+5Yn)+√5(Xn+3Yn)

so separating rational and irrational parts yields the pretty recurrence relation Xn+1 = 3Xn + 5Yn and Yn+1 = Xn+3Yn.

That means Xn+1 and Yn+1 depend only upon Xn and Yn. Since we only care about the last three digits, that means that there are only 1000*1000=a million different combinations of Xn, Yn, and thus, the series must repeat in fewer than a million iterations. It shouldn’t be too hard to find a repeat.

Here’s the Python code to find the cycle length:

def _a_b_n(n):
    if n == 0:
        return 3,1
    a,b = a_b_n(n-1)
    return ((3*a+5*b) % 1000, (a+3*b) % 1000)

def a_b_n(n):
    if not CACHE.has_key(n):
    CACHE[n] = _a_b_n(n)
    return CACHE[n]

for i in xrange(int(1e6)):
    k = (Xn, Yn) = a_b_n(i)
    #print i, a, b, (2*a-1)%1000
    if F.has_key(k):
    #print "repeat: %d, %d" % (i,F[k])
    F[k] = i

cycle_length = i-F[k]
print "cycle length is", cycle_length

When you run this, it takes less than a tenth of a second to figure out that the cycle length is 500, and A503, B503 = A3, B3. So now it’s easy! Calculating the first 503 terms is enough.

Here is the rest of the code:

def do_trial(f):
    n = int(f.readline())
    if n>cycle_length:
        n %= cycle_length
        n += cycle_length
    t = a_b_n(n-1)
    return (2*t[0]-1) % 1000

f = sys.stdin
count = int(f.readline())
for i in xrange(count):
v = do_trial(f)
print "Case #%d: %03d" % (i+1, v)

It runs in pretty much no time at all, thanks to the excessive caching.

Aquatic Agism

When in Vancouver, I live in an apartment on campus at the University of British Columbia (UBC), one of the largest universities in Canada. The aquatic centre on campus has a huge indoor pool, as big as I’ve ever seen. It’s so large that every time I see it I can’t believe how big it is, even though I’ve been there many times. In fact, it’s so big, I can’t believe they could make a building large enough to contain it. Of course, I’m sure if you ever come see it, you will not be impressed since I’ve massively oversold it. I don’t care though. I will always think it’s big.

The pool has a three meter diving board and a five meter platform. The three meter is plenty high enough. The five meter platform is just plain scary. The one time I did go up there, I realized that even if no one seems to be paying attention, climbing back down really is not an option. It’s just too humiliating. I had to jump. And it was not good. It’s scary enough just being up there; jumping down and landing is… well, shall I say, “unpleasant”. So I don’t go up there anymore. Nothing good can come of it.

Anyway, I was at the pool recently and saw a bunch of kids jumping from the five meter platform over and over. I guess they didn’t get the same impression I did. Maybe they even found it fun. I thought that was pretty amazing. These kids are so brave.

I walked by the bottom of the ladder where one of the kids, a skinny gangly girl with arms and legs everywhere, was about to go up again. Here I am a grown man, too scared to go up there, when this kid of… hmm, how old do you suppose she is? I needed this information to continue my internal self-beratement.

So I said “What are you, twelve years old?” With a snarly sneer, she shot back “No… thirteen.” I could tell from the look on her face that she was insulted to the point of disgust.

Oh brother. “Oh c’mon,” I said. “That was pretty close. C’mon, you try: guess how old I am.” Being much older, even a small percentage error would likely yield an answer off by much more than a year.

Of course, she takes a quick look at me, pauses a beat, then carelessly guesses exactly the age I turned on my most recent birthday. Not even a friendly underguess, like the kind you offer friends to assure them that they look much younger than they are. Spot on.

I was taken aback. What could I say? “Hm. On the nose. Touché.” A meek offering.

How a twelve year old guessed the age of an adult, I know not. She could very well have a career at the county fair at a guess-your-age booth. Or maybe not (accuracy there ain’t really a premium when the value of the $1 prize you win for an incorrect guess is greatly exceeded by the $3 fee).

I got the last laugh though. Shortly after, the lifeguard came over and chased her gang away because the “Adult Swim” started. “Ha ha! Maybe thirteen is more than twelve, but it’s still less than eighteen!” I taunted to her from the cowardly safety of inside my head.