No subject

Thu Feb 24 17:58:36 CET 2011

counters, keep counting the length of each wordNumber and "break" to return
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

--0015174c19ea1efa5704a9e36da6
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

Hello Cafe,<br><br>I was trying to solve ITA Software&#39;s &quot;Word Nubm=
ers&quot; puzzle (<a href=3D"http://www.itasoftware.com/careers/puzzle_arch=
ive.html">http://www.itasoftware.com/careers/puzzle_archive.html</a>) using=
 a brute force approach.<br>

<br>Here&#39;s a my version of a quick recap of the problem:<br><br>&gt; A =
wordNumber is defined as<br>&gt; <br>&gt; wordNumber 1 =3D &quot;one&quot;<=
br>&gt; wordNumber 2 =3D &quot;onetwo&quot;<br>&gt; wordNumber 3 =3D &quot;=
onethree&quot;<br>

&gt; wordNumber 15 =3D &quot;onetwothreefourfivesixseveneightninetenelevent=
welvethirteenfourteenfifteen&quot;<br>&gt; ...<br>&gt;<br>&gt; Problem: Fin=
d the 51-billion-th letter of (wordNumber Infinity); assume that letter is =
found at &#39;wordNumber x&#39;, also find &#39;sum [1..x]&#39;<br>

From an imperative perspective, a naive algorithm would be to have 2 co=
unters, keep counting the length of each wordNumber and &quot;break&quot; t=
o return the result. The imperative brute-force approach is implemen=
ted in C# here: <a href=3D"http://ideone.com/JjCb3">http://ideone.com/JjCb3=
</a>. It takes about 1.5 minutes to find the answer on my computer.

Then I implemented a brute-force Haskell version: <a href=3D"http://ide=
one.com/ngfFq">http://ideone.com/ngfFq</a>. It cannot finish the calculatio=
n in 5 minutes on my machine. (Irony: it&#39;s has more lines than the C# v=
ersion)

Here is the `-p` profile of the Haskell program: <a href=3D"http://hpas=
te.org/49934">http://hpaste.org/49934</a> The Question: Are there ob=
vious mistakes I am making? (Note: I am fully aware that brute-forci=
ng it is not the correct solution to this problem. I am mainly interested i=
n 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)<=
br>

(Note 2: It does not seem to be space leaking. The program runs with co=
nstant memory (about 2MB) on my computer) (Note 3: I am compiling wi=
th `ghc -O2 WordNumber.hs) Chris

--0015174c19ea1efa5704a9e36da6--