3n+1

ACM (Association for Computing Machinery) organiza unas competencias de programación llamadas ICPC (International Collegiate Programming Contest). En esta dirección hay muchos problemas de las competencias: http://acm.uva.es/problemset/.

Este es el enunciado del primer problema de la guía: http://acm.uva.es/p/v1/100.html

El fin de semana hice esta solución:

(nota: los lenguajes soportados por las competencias son C y Java, mi solución está escrita en Python por que me resulta más ágil. De todas formas importa más el algoritmo que el lenguaje.)

def odd(n):
    return not (n%2 == 0)

def tnu(n=1):
    print n
    if (n == 1): return
    elif (odd(n)): n = 3*n+1
    else: n = n/2
    tnu(n) # la recursividad por la cola es evitable

>>> tnu(22)
22
11
34
17
52
26
13
40
20
10
5
16
8
4
2
1

La longitud del ciclo para un n dado es la cantidad de valores que la función tnu() develve (incluido el 1 final)

El problema pide leer un archivo con pares i,j y para cada par devolver la mayor longitud de ciclo para todos los enteres enter i y j incluyendo a i y a j.

Solución Exaustiva

Una solución exaustiva podría consistir en calcular para cada par i,j todos las longitudes de ciclo asociadas y devolver la mayor.

Redefino tnu para que en lugar de imprimir los sucesivos valores de n devulva una lista con los valores, el segundo argumento de la función es una lista vacía.

def tnu(n,l):
    #print n
    l.append(n)
    if (n == 1): return l
    elif (odd(n)): n = 3*n+1
    else: n = n/2
    return tnu(n,l) # la recursividad por la cola es evitable

Suponiendo que ya se leyeron los pares del archivo correspondiente y se tienen en una lista llamada pairs:

def solv1(pairs):
    for i,j in pairs:
        maxc = 0
        for n in range(i,j+1):
            maxc = max(len(tnu(n,[])),maxc)
        print i, j, maxc

>>> pairs = [(1,10),(88,123),(7,1),(55,455),(10000,10003)]
>>> solv1(pairs)
1 10 20
88 123 119
7 1 0
55 455 144
10000 10003 180
>>> pairs = [(1,10),(100,200),(201,210),(900,1000)]
>>> solv1(pairs)
1 10 20
100 200 125
201 210 89
900 1000 174

Bien, esta solución ANDA, pero no es óptima. De hecho probablemente sea la solución menos eficiente la de la fuerza bruta.

Solución Dinámica

La idea es almacenar los resultados ya calculados para no tener que hacerlos una y otra vez. Si se pide la máxima longitud de ciclo (mlc) enter 100 y 200 y obtengo 125 y luego se pide la máxima longitud de ciclo enter 1 y 300, voy a calcular la mlc para el par 1,100, luego lo haré para 200,300 y luego compararé los resultados con 125 quedándome con el mayor de los 3.

Pero.. que pasa si ya he calculado la mlc para los valores entre 2 y 99?

def solv1din(pairs,dic):
    for i,j in pairs:
        maxc = f_maxc(i,j,dic)
        print i, j, maxc
        dic[i,j]=maxc

def f_maxc(i,j,dic):
    wide = 0
    for a,b in dic.keys():
        if a == i and b == j: return dic[a,b]
        if (i<=a and b<=j and b-a > wide):
            f,g = a,b
            wide = b-a
    if (wide == 0): #ningún rango del diccionario estaba dentro de i,j
        maxc = 0
        for n in range(i,j+1):
            maxc = max(len(tnu(n,[])),maxc)
        return maxc
    else:
        return max(f_maxc(i,f,dic),dic[f,g],f_maxc(g,j,dic))

>>> solv1din(pairs,{})
1 10 20
100 200 125
201 210 89
900 1000 174

Una versión no recursiva de tnu podría ser algo como esto:

def tnu(n):
    l = []
    while(n != 1):
        l.append(n)
        if (odd(n)): n = 3*n+1
        else: n = n/2
    l.append(1)
    return l

Download

• Una implementación completa que resuelve el problema: 3n+1.py
• Un archivo de entrada de ejemplo: input100.txt

Ejemplo de uso

juanjo@sarge:~/problemas$ ./3n+1.py input100.txt
1 10 20
100 200 125
201 210 89
900 1000 174
88 123 119
7 1 0
55 455 144
10000 10003 180