Hey, I've stolen this challenge from some website, it's pretty easy but I know most of you will fuck it up.
A sequence is defined by:
n -> n/2 (n is even)
n -> 3n + 1 (n is odd)
Find the longest sequence, with a starting number under one million.
Bonus points when you find the solution for ten million.
Name:
Anonymous2007-09-05 12:41 ID:N3V2WcCD
Oh, ten million.
Ok that doesn't overflow on the brute force one with longs (and it takes 72.4 seconds), but it does cause Java to run out of heap pretty quickly on my Hashtable one. I can't seem to find the necessary combination of switches to give the JVM more memory to work in though.
Here's some more code (longs+hashtable):
import java.util.Hashtable;
public class World4ChProgPuzzleOpt2 {
static Hashtable<Long, Integer> LengthCache = new Hashtable<Long, Integer>();
private static int calculateSequenceLength(int start) {
switch(start) {
case 1:
case 2:
case 4:
return 3;
default:
{
int Length = 1;
Integer CachedLength = null;
long n = start;
while (!(n==1||CachedLength!=null)) {
CachedLength = LengthCache.get(n);
if (CachedLength != null) {
Length = Length + CachedLength - 1;
} else {
if (n%2==0) {
n /= 2;
} else {
n = 3*n+1;
}
++Length;
}
}
LengthCache.put((long)start, Length);
return Length;
}
}
}
public static void main(String[] args) {
int UpperLimit = 1000000;
int LongestSequenceLength = 0;
int CurrentSequenceLength;
long StartTime = System.currentTimeMillis();
for (int n=1; n<=UpperLimit; n++) {
CurrentSequenceLength = calculateSequenceLength(n);
if (CurrentSequenceLength > LongestSequenceLength) {
LongestSequenceLength = CurrentSequenceLength;
}
}
long ElapsedTime = System.currentTimeMillis()-StartTime;
System.out.println("Longest sequence for numbers up to " + UpperLimit + " is " + LongestSequenceLength);
System.out.println("(took "+ElapsedTime+"ms to run)");
I just realised how stupid I was using a hashtable. I mean, what the fuck? Completely retarded data structure for this application. This next one just allocates a huge array instead.
Average 0.34 seconds for one million items and 4.0 seconds for ten million. Here's the code:
public class World4ChProgPuzzleOpt3 {
static int[] LengthCache;
static final int UpperLimit = 1000000;
private static int calculateSequenceLength(int start) {
switch(start) {
case 1:
case 2:
case 4:
return 3;
default:
{
int Length = 1;
int CachedLength = 0;
long n = start;
while (!(n==1||CachedLength!=0)) {
if (n<=UpperLimit) {
CachedLength = LengthCache[(int)n-1];
}
if (CachedLength != 0) {
Length = Length + CachedLength - 1;
} else {
if (n%2==0) {
n /= 2;
} else {
n = 3*n+1;
}
++Length;
}
}
LengthCache[start-1] = Length;
return Length;
}
}
}
public static void main(String[] args) {
int LongestSequenceLength = 0;
int CurrentSequenceLength;
long StartTime = System.currentTimeMillis();
LengthCache = new int[UpperLimit];
for (int n=1; n<=UpperLimit; n++) {
CurrentSequenceLength = calculateSequenceLength(n);
if (CurrentSequenceLength > LongestSequenceLength) {
LongestSequenceLength = CurrentSequenceLength;
}
}
long ElapsedTime = System.currentTimeMillis()-StartTime;
System.out.println("Longest sequence for numbers up to " + UpperLimit + " is " +
LongestSequenceLength);
System.out.println("(took "+ElapsedTime+"ms to run)");