Solving ITA's Word Numbers Puzzle
nathan.ca
Solving ITA's Word Numbers Puzzle
1–10 of 25 posts
Re: Solving ITA's Word Numbers Puzzle
#2http://conway.rutgers.edu/~ccshan/wiki/blog/posts/WordNumber... I read this write-up of the problem years ago that takes a different approach.
Re: Solving ITA's Word Numbers Puzzle
#3This is pretty cool. It's a shame they haven't retired the problem I solved to get an interview there.
Re: Solving ITA's Word Numbers Puzzle
#4Hint: 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
Re: Solving ITA's Word Numbers Puzzle
#5http://conway.rutgers.edu/~ccshan/wiki/blog/posts/WordNumber... I read this write-up of the problem years ago that takes a different approach.
Ken and Dylan's solution is brilliant, and readable, but has a lot of magic. Don't be surprised if you read (and run!) their solution end-to-end, understanding each piece, but still don't believe that the whole thing works!
(Note, the solution is in 4 parts, but Part 4 is not in the table of contents.)
First, understand that it relies on Haskell's built-in (implicit/invisible) theorem-prover, lazines, and purity to work. It is not possible to directly translate their code into (much uglier) code in C/Python/Java and expect is to work.
Second, while they tersely explain all the math they use, like "automatic (formal) differentiation", "seminearring", it really helps if you are already familiar with these concepts from a college "modern algebra" class, in order to maintain the intuition in your head to follow the exposition.
Third, a lot of the magic of Haskell isn't explicitly explained in their blog post, such as:
0. Where is the, um, "execution" ("main" function)? When not using the IO monad or other explicitly sequential operations, Haskell programs do not have any instructions (loops or command statement), only declarations and definitions/assigments. The only "instruction" in the program is the command to print the value of a function on the console. Haskell's built-in call-by-need need-resolution engine then does all the work of deciding which functions need to be called in which order to compute and print the one top-level function.
1. why differentiation works to solve this problem (Part 2). (The reason is not hard to see if you play with the functions, but is hard to see just by reading: The concrete examples of string lists are all in section 1, but differentiation is defined in section 2, and they don't show any examples of differentiation applied to concrete lists of strings.)
2. Why summing over vast trees is efficient. (Part 2 and Part 3) Each node in the tree contains a reference to (basically) a small function, describing how to combine its branches. That function is collapsed to a value the first time it's value is needed (Haskell's lazy call-by-need semantics).
Note that the tree is extremely redundant! It contains something like (but not quite) log (n) distinct nodes in a tree of n total nodes representing n integeres. The use of indirection, which is implicit in Haskell (like Java!), means that by computing the a sum over part of the tree, we get many other computations for free, even though the code superficially appears to copying values.
Haskell's purity (and therefore, equivalence between functions and their results), means that each function call (including arguments is only ever evaluated more than once, without any explicit visible coding of that evaluation+memoization (not like Java).
3. Why sorting is efficient. The reason is basically the same as why summing is efficient (above).
Re: Solving ITA's Word Numbers Puzzle
#6Hint: 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
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
endRe: Solving ITA's Word Numbers Puzzle
#7This is a fun puzzle. Here's my take on it. I stopped reading the article after the introduction so I could attack the problem fresh, so hopefully this isn't the same as what the author did.
The trick is working backwards. We want to quickly count the number of occurrences of each letter in the list of number words. Knowing how to do that, we just have to do a linear scan over the cumulative counts for A, B, C, ... to find the interval into which the query index fits. If it helps prime your intuition, my inspiration is counting sort with the counts evaluated partly analytically.
Number words can be divided into a fixed set of recurring components: one, two, three, four, ..., ten, eleven, twelve, thirteen, ..., twenty, thirty, ..., hundred, thousand, million, billion. Build an inverse index that maps each letter to the set of all component words that contain the letter, paired with an occurrence count. For example, the inverse index would map T to {(two, 1), (three, 1), (ten, 1), (twelve, 1), (thirteen, 2), ...}.
With this in hand, the problem is reduced to counting the number of each component word in the string.
Let's consider that subproblem for the component 'nine' ('nineteen' and 'ninety' are separate components) for numbers with up to n digits. Numbers with the digit pattern xxx...xxx9 each contribute one occurrence of 'nine', and there are 10^(n-1) such numbers ('... nine'). Likewise each xxx...xxx9xx contributes an occurrence, and there are again 10^(n-1) such numbers ('... nine hundred ...'), the pattern xxx...xxx9xxx has 10^(n-1) members ('... nine thousand ...'), etc.
This same analysis applies to all ones components (one, two, three, ..., nine), and an analogous analysis applies to other components.
Re: Solving ITA's Word Numbers Puzzle
#8couldn't you just use "sort" to sort the file on disk and then offset into the file to find the answer? i would expect sort to work fine for files larger than memory (and if it doesn't i bet there is some tool that does - merge sort with tapes is not so old...)
[edit: you'd need to add, then strip, carriage returns between numbers, i guess]
Re: Solving ITA's Word Numbers Puzzle
#9couldn't you just use "sort" to sort the file on disk and then offset into the file to find the answer? i would expect sort to work fine for files larger than memory (and if it doesn't i bet there is some tool that does - merge sort with tapes is not so old...) [edit: you'd need to add, then strip, carriage returns between numbers, i guess]
You could, but that's incredibly slow.
Re: Solving ITA's Word Numbers Puzzle
#10couldn't you just use "sort" to sort the file on disk and then offset into the file to find the answer? i would expect sort to work fine for files larger than memory (and if it doesn't i bet there is some tool that does - merge sort with tapes is not so old...) [edit: you'd need to add, then strip, carriage returns between numbers, i guess]
You could, but that's incredibly slow.
really? for what value of incredibly? i bet it's way faster than writing all that code.
[edit: to save people reading below i missed the sum requirement, which this wouldn't do, and a rough back of the envelope calculations suggests it would take about the same length of time as the code took. so i was wrong, sorry...]