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
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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe