probleme_14.groovy

def max = 1000000L;


def next=[1:1];
def length = [1:1];

def getNext(number) {
    if(number%2==0) {
        return (number/2).toBigInteger().longValue();
    } else {
        return (3*number+1).toBigInteger().longValue();
    }
}

def getSequence(numbers, number) {
	def returned = [];
	returned << number;
	if(number!=1) {
		returned.addAll(getSequence(numbers, numbers.get(number)));
	}
	return returned;
}

def getLength(next, length, i) {
	def size = 1G;
	def number = i;
	while(number!=1) {
		number = next[number];
		if(length.containsKey(number)) {
			size+=length[number];
			break;
		} else {
			size++;
		}
	}
	return size;
}

long start = System.currentTimeMillis();
def toCompute = [];
toCompute+=1L..max;
int index=0L;
while(toCompute.size()>0) {
    def current = toCompute.remove(0);
    if(!next.containsKey(current)) {
        next[current]=getNext(current);
        if(!next.containsKey(next[current])) {
            toCompute << next[current];
        }
		index++;
    }
}
println "all values computed";

index=0L;
for(i in next.keySet()) {
	length[i] = getLength(next, length, i);
	index++;
}

def maxLength = length.values().max();
def key = length.find {it.value==maxLength }?.key;
println "max length = "+maxLength;
println "for "+getSequence(next, key).join(" -> ");
long end = System.currentTimeMillis();
println "duration "+((end-start)/1000.0)+" s";