So if we were to emulate your Java solution, we'd do
import Data.Array
cacheSize :: Int
cacheSize = 65536
table :: Array Int Integer
table = listArray (1,cacheSize) (1 : map go [2..cacheSize]) where
go n
| even n = 1 + lookup (n `div` 2)
| otherwise = 1 + lookup (3 * n + 1)
lookup :: Integer -> Integer
lookup n
| n < cacheSize = table ! (fromInteger n)
| even n = 1 + lookup (n `div` 2)
| otherwise = 1 + lookup (3 * n + 1)
The rest of the code is just some simple i/o.
The table is filled up lazily as you request values from it.
On Thu, Apr 14, 2011 at 3:29 AM, Dmitri O.Kondratiev <[email protected]>wrote:
> 3n+1 is the first, "warm-up" problem at Programming Chalenges site:
>
> http://www.programming-challenges.com/pg.php?page=downloadproblem&probid=110101&format=html
>
> (This problem illustrates Collatz conjecture:
>
> http://en.wikipedia.org/wiki/3n_%2B_1#Program_to_calculate_Collatz_sequences
> )
>
> 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.
>
> *** 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.
>
> To illustrate my question I add the problem description and my Java
> solution at the end of this message.
> Thanks!
>
> *** Problem
>
> Consider the following algorithm to generate a sequence of numbers. Start
> with an integer *n*. If *n* is even, divide by 2. If *n* is odd, multiply
> by 3 and add 1. Repeat this process with the new value of *n*, terminating
> when *n* = 1. For example, the following sequence of numbers will be
> generated for *n* = 22:
> 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
> It is *conjectured* (but not yet proven) that this algorithm will
> terminate at *n* = 1 for every integer *n*. Still, the conjecture holds
> for all integers up to at least 1, 000, 000.
>
> For an input *n*, the *cycle-length* of *n* is the number of numbers
> generated up to and *including* the 1. In the example above, the cycle
> length of 22 is 16. Given any two numbers *i* and *j*, you are to
> determine the maximum cycle length over all numbers between *i* and *j*, *
> including* both endpoints.
>
> Input The input will consist of a series of pairs of integers *i* and *j*,
> one pair of integers per line. All integers will be less than 1,000,000 and
> greater than 0.
>
> OutputFor each pair of input integers *i* and *j*, output *i*, *j* in the
> same order in which they appeared in the input and then the maximum cycle
> length for integers between and including *i* and *j*. These three numbers
> should be separated by one space, with all three numbers on one line and
> with one line of output for each line of input.
>
> Sample Input
>
> 1 10
> 100 200
> 201 210
> 900 1000
>
> Sample Output
>
> 1 10 20
> 100 200 125
> 201 210 89
> 900 1000 174
>
> *** my Java solution
>
> import java.io.BufferedReader;
> import java.io.InputStreamReader;
> public class Main {
> final static BufferedReader reader_ = new BufferedReader(new
> InputStreamReader(System.in));
> /**
> * @param args
> */
> public static void main(String[] args) {
> new Problem().run();
> }
> static String[] ReadLn() {
> String[] tokens = null;
> try {
> String line = reader_.readLine();
> String REGEX_WHITESPACE = "\\s+";
> String cleanLine =
> line.trim().replaceAll(REGEX_WHITESPACE, " ");
> tokens = cleanLine.split(REGEX_WHITESPACE);
>
> } catch (Exception e) {}
> return tokens;
> }
> }
>
> class Problem implements Runnable {
> long CACHE_SIZE = 65536;
> private final long[] cache_ = new long[(int) CACHE_SIZE];
> /**
> * Compute cycle length for a single number
> *
> * @param n number for which we find cycle length
> * @return cycle length
> */
> long cycleLen(long n) {
> long len = 1;
> if (n != 1) {
> len = getFromCache(n);
> if (len == 0) { //not yet in cache
> // Recursively compute and store all
> intermediate values of cycle length
> if ((n & 1) == 0) {
> len = 1 + cycleLen(n >> 1);
> } else {
> len = 1 + cycleLen(n * 3 + 1);
> }
> putInCache(n, len);
> }
> }
> return len;
> }
>
> void putInCache(long n, long len) {
> if(n < CACHE_SIZE) {
> cache_[(int)n] = len;
> }
> }
>
> long getFromCache(long n) {
> long result = 0;
> if(n < CACHE_SIZE) {
> result = cache_[(int)n];
> }
> return result;
> }
>
> /**
> * Find max cycle on interval
> *
> * @param from interval start
> * @param to interval end
> * @return max cycle
> */
> Long maxCycle(Long from, Long to) {
> Long result = 0L;
> Long cycle = 0L;
> // Get all values of cycle length on the interval and put these
> values into a sorted set
> for (long i = from; i <= to; i++) {
> cycle = cycleLen(i);
> if (cycle > result)
> result = cycle;
> }
> return result;
> }
>
> public void run() {
> String[] tokens = null;
> long from, to, result = 0;
> long arg1, arg2 = 0;
> while ((tokens = Main.ReadLn()) != null) {
> if (tokens.length == 2) {
> arg1 = new Long(tokens[0]).longValue();
> arg2 = new Long(tokens[1]).longValue();
> from = (arg1 <= arg2) ? arg1 : arg2;
> to = (arg2 >= arg1 ) ? arg2 : arg1;
> result = maxCycle(from, to);
> out(arg1+" "+arg2+" "+result);
> }
> }
> }
>
> static void out(String msg) {
> System.out.println(msg);
> }
>
> }
>
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
