shimweasel

Pretty happy about my showing this year - just scraped into the top 1000 at 991, thereby earning a shirt :)

http://code.google.com/codejam/contest/scoreboard?c=1150486#sp=981

The expensive friend problem in particular broke my noodle - I managed to get a solution to the small case by realising that it's really asking about the difference between the number of primes under n and the number of prime powers under n. A naive solution computes this directly, but the large solution includes inputs up to 10^12.  even computing the primes under that's not feasible, so I turned to Ben Smith for guidance. (It's good to have friends who are smarter than you.) He pointed out that if the prime factor p is more than sqrt(n), then p^2 is more than n, so that prime can make no difference to the spread.

This simple optimisation (plus some simple parallelisation) brought the runtime down to about 11 seconds, but being a nerd, I had no choice but to optimise it even further. Some fiddling with bang patterns, a bit of core inspection, and one algorithmic change (computing integer logs directly rather than with logBase), and the whole large problem set runs in under a second on my 4-core machine. Happiness.

Of course, the codejam and associated hacking left me a bit bare on #projectaweek - I've added some stuff to the website and OAuth is almost ready to be deployed, but it's not a big project, or even a strictly separate one. I hope my fellow hackers will afford me some leniency.

never quite got around to announcing it, but I released the http://projectaweek.heroku.com site the week before last. Albert Scheiner gave me heaps of help making it look schmick, and once I've pushed the oauth features I'll be comfortable calling it done and getting on with whatever new project I'm doing this week.