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