On Thu, Apr 14, 2011 at 4:29 AM, Dmitri O.Kondratiev <span dir="ltr"><<a href="mailto:dokondr@gmail.com">dokondr@gmail.com</a>></span> wrote:<br><div class="gmail_quote"><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
<div>3n+1 is the first, "warm-up" problem at Programming Chalenges site:</div><div><a href="http://www.programming-challenges.com/pg.php?page=downloadproblem&probid=110101&format=html" target="_blank">http://www.programming-challenges.com/pg.php?page=downloadproblem&probid=110101&format=html</a></div>
<div><br>
</div><div>(This problem illustrates Collatz conjecture:</div><div><div><a href="http://en.wikipedia.org/wiki/3n_%2B_1#Program_to_calculate_Collatz_sequences" target="_blank">http://en.wikipedia.org/wiki/3n_%2B_1#Program_to_calculate_Collatz_sequences</a>)</div>
</div><div><br></div><div>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 problem.</div>
<div><br></div><div>*** 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.</div></blockquote><div><br>This is the exact problem data-memocombinators was written to solve. <a href="http://hackage.haskell.org/packages/archive/data-memocombinators/0.4.1/doc/html/Data-MemoCombinators.html">http://hackage.haskell.org/packages/archive/data-memocombinators/0.4.1/doc/html/Data-MemoCombinators.html</a><br>
<br>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 <br>
<br> switch (<10^6) integral id<br><br>Luke<br></div></div>