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.