[Haskell-cafe] Programming Chalenges: The 3n+1 problem
lrpalmer at gmail.com
Thu Apr 14 20:02:48 CEST 2011
On Thu, Apr 14, 2011 at 4:29 AM, Dmitri O.Kondratiev <dokondr at gmail.com>wrote:
> 3n+1 is the first, "warm-up" problem at Programming Chalenges site:
> (This problem illustrates Collatz conjecture:
> As long as the judge on this site takes only C and Java solutions, I
> submitted in Java some add-hock code (see at the end of this message) where
> I used recursion and a cache of computed cycles. Judge accepted my code and
> measured 0.292 sec with best overall submissions of 0.008 sec to solve the
> *** Question: I wonder how to implement cache for this problem in Haskell?
> At the moment, I am not so much interested in the speed of the code, as in
> nice implementation.
This is the exact problem data-memocombinators was written to solve.
For this problem, it is too slow to memoize everything; you have to use a
bounded memo table. That's why I use a combinator-based memo approach as
opposed to the type-directed approach used in eg. MemoTrie. The memo table
you need is something like
switch (<10^6) integral id
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Haskell-Cafe