Solving ITA's Word Numbers Puzzle • Hacker News Board

Re: Solving ITA's Word Numbers Puzzle

#21

Post by lurker17 » Fri, Dec 30, 2011, 10:10 PM UTC

darkane wrote: post #20

mukyu wrote: post #2

http://conway.rutgers.edu/~ccshan/wiki/blog/posts/WordNumber... I read this write-up of the problem years ago that takes a different approach.

Interesting that this and the OP's solutions result in different answers.

That's because you missed the hidden Part 4 where Shan&Thurston finish their solution:

http://conway.rutgers.edu/~ccshan/wiki/blog/posts/WordNumber...

Re: Solving ITA's Word Numbers Puzzle

#22

Post by darkane » Fri, Dec 30, 2011, 10:27 PM UTC

lurker17 wrote: post #21

darkane wrote: post #20

Earlier quoted context omitted.

Interesting that this and the OP's solutions result in different answers.

That's because you missed the hidden Part 4 where Shan&Thurston finish their solution: http://conway.rutgers.edu/~ccshan/wiki/blog/posts/WordNumber...

Ah, good call. Very easy to miss that link.

Re: Solving ITA's Word Numbers Puzzle

#23

Post by anonymoushn » Sat, Dec 31, 2011, 2:16 AM UTC

lurker14 wrote: post #11

anonymoushn wrote: post #3

This is pretty cool. It's a shame they haven't retired the problem I solved to get an interview there.

Why is it a shame that they haven't retired something cool?

If they had retired it, then we could discuss it :)

Re: Solving ITA's Word Numbers Puzzle

#24

Post by strags » Sat, Dec 31, 2011, 10:35 PM UTC

I have a ruby solution that takes 20s to run on a machine that's about 5 years old.

I just brute-force generate the strings from 1-999999, as well as "million-prefix" strings of the form "(1-999)million". These are then sorted in the same array. Also compute the sum of the length of the strings from 1-999999 while we're at it.

Then, run through the sorted array, keeping a running total of the length. Each time you hit a "million-prefix" string, it's easy to compute the total length of all the numbers that start with the prefix - it's just the sum of the string lengths from 1-999999 plus 999999*prefix-length.

If this subtotal doesn't push you past the 51B limit, then keep going. If it does, then run through the 1-999999 numbers only, adding each one to the total individually, until you reach the magic 51B mark.

The practical upshot is that you can skip millions of numbers at a time.

Ugly code here: http://codepuppies.com/ben/ita/t2.txt

Re: Solving ITA's Word Numbers Puzzle

#25

Post by danielharan » Wed, Jan 04, 2012, 11:09 PM UTC

lurker14 wrote: post #6

danielharan wrote: post #4

Hint: Gauss. Sum of numbers 1 to 100. Using Gauss's insight, Ruby can solve 10,000 times faster than a naive C solution. I solved this a while back, while high on drugs my dentist gave me. Blog post is down, but code is here: http://refactormycode.com/codes/8-integer-puzzle

What of the magic numbers in this solution? ThousandRange: def child_values @thousands * 1_000_000 + 499500 end def child_sizes NumberWriter.write(@thousands * 1_000).size * 1_000 + 18440 end MillionRange: def child_values @millions * 1_000_000_000_000 + 499_999_500_000 end def child_sizes NumberWriter.write(@millions * 1_000_000).size * 1_000_000 + 44_872_000 end

The size of the strings for that range of numbers. So, e.g. all of the strings starting with "twenty" will have that length of string (here, 6) * 10, plus the "one" in "twentyone", etc. The "one", "two", "three", etc have the same length whether they're preceded by "twenty" or "thirty".

Account for the repeated strings "hundred", "thousand" or "million" and what follows them and you'll get the magic numbers above.