My Last Day

Tomorrow is my last day in the office at BigPark, the Vancouver company that I work for. The jet-setting lifestyle between Vancouver and California has been pretty interesting, but it seems that it may be coming to an end.

I have a lot of hope for the company, and remain a big supporter financially and intellectually. We have a great team and some great products in the pipeline. I expect I will be doing a fair bit of consulting in the coming months for our initial product launch and transition network operations.

What’s next? I will be in Vancouver another month, enjoying the rest of the summer and packing up my apartment, then heading back to California. For the first time in years, I do not have a job. And this is intentional. My goal is to take at least a year off having a day job so I can relax, travel, and work on a few personal projects.

I’m nervous about this big change, and a little sad about this transition. I know there will be a lot of things I will miss. Yet, I’m excited with anticipation about what the future will bring. And we’ll see if having free time makes me lazy or drives me crazy.

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)

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

F={}
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])
    break
    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.

Code to Automate Posting to a MySpace Blog

I’ve kept a blog on my website for quite some time now. But since most of my readers were on MySpace when I started my own-branded blog, I had to copy the posts from one blog to the next. This gets old in a hurry, so I wrote a little Python code to automatically copy posts from WordPress to MySpace. It should be easy to extend since the MySpace posting code is separated out.

I’ve made this code publicly available with the hope that others may find it useful. It’s on github. Check it out. It’s not perfect, but it works.

Big Park Dot Com

Our corporate web finally went live this week. I have been at this company for over six months, joining shortly after its inception.

So what took so long? Well, for one thing, we didn’t have a name until very recently. We were going by the temporary name “Funny Fox Games”, but didn’t want to waste any time branding us by the temporary name. We struggled over a final name for quite a while, and just a few weeks ago settled on BigPark, Inc. I actually think the name is quite good (kind of a relief… I thought some of the ideas were not that great).

So check out our quite pretty (and vague) web site at http://bigpark.com/ and see what you think. We have a few jobs openings, so if you like computers and/or games, take a look!

With a little luck, we will release our first game Real Soon Now™.

A Word (Spelled) Uniquely Canadian

Canadian English is a hybrid… on one hand, with political roots in the Commonwealth and historical ties to Britain; on the other hand, its geographic and economic influences from the US.

In spelling, like so many other cultural aspects, it’s hard to think of something that is uniquely Canadian and not just borrowed or outright filched from some other nation. When British and American English do not agree on a spelling, the Canadian version is usually just one or the other.

However, this endless indecisiveness yields a word spelled in a uniquely Canadian way:colourize

The Brits spell this “colourise”, the Americans “colorize”. There are two rules at work here: Canadians keep the “u” in words like “color” and “flavor” that does nothing but take up space and reinforce, (in our minds at least), the massive differences between Canada and the US.

But when it comes to the suffix that makes nouns into verbs, we for some reason have settled on the American “-ize” rather than the British “-ise”.

Maybe like “foetus” (a fantastically ugly British spelling), we’ve decided that it’s just a bit too… provincial?

Travel Tips: Fly Clear

I have a Clear card, so security at San Francisco airport (SFO) is very quick. If you want one, use my Refer-A-Friend code SCA52693 to get us both a free month. There are some surprising things about this program. At SFO, you plug the card into a machine, then it scans your irises to confirm your identity. Then the Clear employees ask for ID. That’s right. Reading your irises isn’t enough… they need picture ID. This is in case someone steals your irises without taking your driver’s license. Yes, they know it’s stupid (they called it “illogical” in an email to members). But the government requires it.

After your ID has been confirmed, the valet helps you by carrying some of your stuff, and, chanting “excuse me” repeated while budding in front of everyone else who is standing in own line. That’s right, you don’t get your own line. You don’t get any special rules (you still have to take off your shoes and take your laptop out of its case). You just get butt in front of the same line everyone else is in. It always makes me feel like a self-important jerk. Not in a completely bad way though. All I can ever manage is a meek smile.

And what happens when everyone is in this program? The lines will be much slower because there will now be an extra step (the iris scanning), and the security screening won’t be any different. So what the hell??

I figure that what happened was it was a compromise between privacy versus security. A law was passed for frequent travelers to be pre-screened (and the TSA digs into your background before you’re approved) in exchange for a expedited security process. And they could never decide on exactly how the screening would be expedited… so instead of changing the process, they just bud you to the head of the line.

“TSA-approved and prescreened butthead coming through!”

Line-jumping: the compromise of bureaucracy.

On Living in Two Places

It’s been several months now since I’ve worked in Vancouver while living in California and having a place in both locations. I am getting used to the disorientation and have a few observations.

Currency

The money always seems native. I have a hard time telling which coins and bills are foreign. When I first moved to the US, it was easy: the foreign-looking money was native and vice-versa. As I spent more time there, the feeling gradually switched. During the switch, it was a little confusing as my brain swapped out “native” versus “foreign”, but that happened long ago.

Now when I go back and forth, I swap out the contents of my wallet and change pockets. It seems pretty arbitrary to me, especially now that the US and Canadian dollar are pretty much interchangeable on financial markets (on any given day it’s anyone’s guess which one is worth one or two percent more than the other). I’m a little irritated, really, and am very tempted to try to pass the other country’s money. Of course, that would work fine in Canada and horribly in the US. (This is a nice allegorical of the relationship between the two countries.)

Metric

Oddly, the switch between miles, kilometers, Celsius, Fahrenheit… none of that causes any problem. I am fully bi-unitarian.

Going Home

Another thing that’s odd is that I’m always going home. I’m at home, I get a ride to the airport, fly away, get my ride from the airport to… home.

I pack a small carry on bag. No clothes. No toothbrush. No pills. No deodorant. If the plane ever has to make an unscheduled overnight stop in some other city, I could be in for a bit of a pickle (and this almost happened once when Vancouver was fogged over).

This also means if a fellow traveller asks me “Going home?” I just smile and say “Yes.”

Aww… You So Entertaining!

I went down to the Gallery Lounge on campus at UBC tonight to checkout the karaoke contest that was supposed to be going on (yeah, yeah, I know). I was surprised to see how sparsely attended it was, so I found a book and put in Louis Armstrong’s “What a Wonderful World”, which I do in a pretty decent croaky impression. It went over pretty well.

As the night slowly wore on, it was pretty clear not too many people were interested in singing, so I went up and asked how many songs were left. They said there was one opening left, so I pounced on it and signed myself up for “The Bad Touch” by The Bloodhound Gang. This song is somewhat edgy, slightly rude, and I have it memorized. I also have a little outrageous dance/act-out which is rather of amusing to watch.

I did it, and it went over pretty well too. Immediately following, the crowd voted for “Best Singer” and “Most Entertaining”. I thought I might actually have a chance since I was fresh in people’s minds. Sure enough, I was voted “Most Entertaining”, so they called me up to congratulate me.

I have never advanced in any comedy contest after over three years of doing stand-up. Yet here I won. At least I’m entertaining compared to a layman.

The DJ asked me to do my Louis Armstrong impression, so I plugged my web site in the low throaty voice. If that’s why you’re here now, well… hi. Why not sign up to be my Facebook fan?