With all the stores closed and cold and damp weather outside, yesterday was the perfect day to work through a programming puzzle. I skimmed down ITA’s puzzle archive and thought Word Numbers seemed interesting. It was retired in September of 2008, so I don’t feel bad publishing my solution publicly. I’ve seen this puzzle before briefly, but had not actually made an attempt at solving it until yesterday.
The gist of the problem is to determine what number is completed at the 51 billionth byte when you concatenate the numbers 1 through 999,999,999 written out in words, such as “onemilliontwohundredthousandthreehundredfortyfive”, sorted alphabetically. What seems like an easy problem at first glance becomes dramatically more difficult with those last two words; sorting the word numbers alphabetically is what makes things interesting. The problem also asks for the sum of the numbers up-to-and-including that number ending at the 51 billionth byte in the sorted order.
With infinite resources, this problem is trivial: write out all billion numbers, run it through
sort, and walk through the file until we get to the 51 billion byte mark, tallying up the values along the way. Unfortunately, my infinite supercomputer is stuck in an infinite loop from a few years back and I haven’t been able to make use of it since, so we’re going to have to approach this the old-fashioned way and use our brains. Full solution after the fold.