A wordNumber is defined as
wordNumber 1 = "one" wordNumber 2 = "onetwo" wordNumber 3 = "onethree" wordNumber 15 = "onetwothreefourfivesixseveneightnineteneleventwelvethirteenfourteenfifteen" ...
Problem: Find the 51-billion-th letter of (wordNumber Infinity); assume
From an imperative perspective, a naive algorithm would be to have 2 counters, keep counting the length of each wordNumber and "break" to return
Hello Cafe, I was trying to solve ITA Software's "Word Nubmers" puzzle ( http://www.itasoftware.com/careers/puzzle_archive.html) using a brute force approach. Here's a my version of a quick recap of the problem: that letter is found at 'wordNumber x', also find 'sum [1..x]' the result. The imperative brute-force approach is implemented in C# here: http://ideone.com/JjCb3. It takes about 1.5 minutes to find the answer on my computer. Then I implemented a brute-force Haskell version: http://ideone.com/ngfFq. It cannot finish the calculation in 5 minutes on my machine. (Irony: it's has more lines than the C# version) Here is the `-p` profile of the Haskell program: http://hpaste.org/49934 The Question: Are there obvious mistakes I am making? (Note: I am fully aware that brute-forcing it is not the correct solution to this problem. I am mainly interested in making the Haskell version perform comparatively to the C# version. Right now it is at least 5x slower so obviously I am missing something obvious) (Note 2: It does not seem to be space leaking. The program runs with constant memory (about 2MB) on my computer) (Note 3: I am compiling with `ghc -O2 WordNumber.hs) Chris