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's "Word Nubm=
ers" 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's a my version of a quick recap of the problem:<br><br>> A =
wordNumber is defined as<br>> <br>> wordNumber 1 =3D "one"<=
br>> wordNumber 2 =3D "onetwo"<br>> wordNumber 3 =3D "=
onethree"<br>
> wordNumber 15 =3D "onetwothreefourfivesixseveneightninetenelevent=
welvethirteenfourteenfifteen"<br>> ...<br>><br>> Problem: Fin=
d the 51-billion-th letter of (wordNumber Infinity); assume that letter is =
found at 'wordNumber x', also find 'sum [1..x]'<br>
<br>From an imperative perspective, a naive algorithm would be to have 2 co=
unters, keep counting the length of each wordNumber and "break" t=
o return the result.<br><br>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.<br>
<br>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's has more lines than the C# v=
ersion)<br>
<br>Here is the `-p` profile of the Haskell program: <a href=3D"http://hpas=
te.org/49934">http://hpaste.org/49934</a><br><br>The Question: Are there ob=
vious mistakes I am making?<br><br>(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>
<br>(Note 2: It does not seem to be space leaking. The program runs with co=
nstant memory (about 2MB) on my computer)<br><br>(Note 3: I am compiling wi=
th `ghc -O2 WordNumber.hs)<br><br>Chris<br><br>
--0015174c19ea1efa5704a9e36da6--
More information about the Haskell-Cafe
mailing list