Desafíos 2014 - Semana 4

[razpeitia]

Problema
Vamos a probar una de las series mas populares en matemáticas. Toma en cuenta el siguiente algoritmo.

Código:

1  entrada n
2  imprime n
3  Si n = 1 termina
4  Si n es impar n = 3n + 1
5  si no n = n / 2
6 ve a 2

Por ejemplo para n=22 generaría la siguiente salida 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 y cuya longitud seria de 16 porque produce 16 números.

Entrada
Dado 2 números a y b, que representan un rango inclusive en ambos extremos.

Salida
La longitud mas larga que existe entre el rango a, b.

Plantilla para resolver el problema

Código Python:

def max_cycle(a, b):
    return 0
 
if __name__ == '__main__':
    from time import time
    t1 = time()
    assert max_cycle(1, 10) == 20
    assert max_cycle(100, 200) == 125
    assert max_cycle(201, 210) == 89
    assert max_cycle(900, 1000) == 174
    assert max_cycle(113383, 113383) == 248
    assert max_cycle(999999, 1) == 525
    assert max_cycle(20, 20) == 8
    assert max_cycle(9999, 9999) == 92
    assert max_cycle(1, 9999) == 262
    assert max_cycle(340, 3000) == 217
    assert max_cycle(3000, 340) == 217
    assert max_cycle(500, 101) == 144
    assert max_cycle(1, 1) == 1
    assert max_cycle(9999, 9998) == 92
    t2 = time()
    print "Tiempo de ejecucion %.3f s" % (t2 - t1)
 

PD: El score estará dado por tiempo de ejecución.

Score:
1. sukoy 21.416s 2.221s

[sukoy]

Mi intento:

Código Python:

cache = {}
def max_cycle(a, b):
            
    def num(n):
        ni = n
        cnt = 1
        if n in cache:
            return cache[n]
        else:
            while not n == 1:
                cnt += 1
                if n%2 != 0:
                    n = (3*n)+1
                else: 
                    n = n/2
            cache[ni] = cnt
        return cache[ni]
 
    def sec(a, b):
        maxim = 0
        if a > b: a,b = b,a
        for i in xrange(a,b+1):
            tr = num(i)
            if tr > maxim: 
                maxim = tr
        return maxim
 
    return sec(a,b)
 
 
if __name__ == '__main__':
    from time import time
    t1 = time()
    assert max_cycle(1, 10) == 20
    assert max_cycle(1, 200) == 125
    assert max_cycle(201, 210) == 89
    assert max_cycle(900, 1000) == 174
    assert max_cycle(113383, 113383) == 248
    assert max_cycle(999999, 1) == 525
    assert max_cycle(20, 20) == 8
    assert max_cycle(9999, 9999) == 92
    assert max_cycle(1, 9999) == 262
    assert max_cycle(340, 3000) == 217
    assert max_cycle(3000, 340) == 217
    assert max_cycle(500, 101) == 144
    assert max_cycle(1, 1) == 1
    assert max_cycle(9999, 9998) == 92
    t2 = time()
    print "Tiempo de ejecucion %.3f s" % (t2 - t1)
#Tiempo de ejecucion 23.939 s
 

Hice lo que pude...
Cachear los resultados de cada numero no parece que sirva de mucho...

Saludos y gracias.

[sukoy]

Mucho mejor.

Código Python:

def max_cycle(a, b):
 
    cache = {1:1}
    
    def num(cache, n):
        if not n in cache:
            if n % 2:
                cache[n] = 1 + num(cache, 3 * n + 1)
            else:
                cache[n] = 1 + num(cache, n / 2)
        return cache[n]
 
    def sec(a, b):
        maxim = 0
        if a > b: a,b = b,a
        for i in xrange(a, b+1):
            tr = num(cache, i)
            if tr > maxim:
                maxim = tr
        return maxim
 
    return sec(a, b)
 
 
if __name__ == '__main__':
    from time import time
    t1 = time()
    assert max_cycle(1, 10) == 20
    assert max_cycle(100, 200) == 125
    assert max_cycle(201, 210) == 89
    assert max_cycle(900, 1000) == 174
    assert max_cycle(113383, 113383) == 248
    assert max_cycle(999999, 1) == 525
    assert max_cycle(20, 20) == 8
    assert max_cycle(9999, 9999) == 92
    assert max_cycle(1, 9999) == 262
    assert max_cycle(340, 3000) == 217
    assert max_cycle(3000, 340) == 217
    assert max_cycle(500, 101) == 144
    assert max_cycle(1, 1) == 1
    assert max_cycle(9999, 9998) == 92
    t2 = time()
    print "Tiempo de ejecucion %.3f s" % (t2 - t1)
#Tiempo de ejecucion 2.062 s
 

Saludos.

[CalgaryCorpus]

Muestro unas pequeñas optimizaciones al programa mostrado por sukoy, basado en la observacion que en el rango (a,b) es posible que exista un rango (a..lowlimit) en que cada indice sea la mitad de otro indice dentro del rango (lowlimit+1,b) y por tanto cada uno de los num[i] sera menor que los num[j] con i en el primer rango y j en el segundo y como se busca el valor mayor resulta superfluo revisar ese rango.

Ademas, si al recorrer hacia atras, se encuentran elementos en el cache, quiere decir que pertenecen a un recorrido previo y por tanto el indice actual no puede ser el maximo y se puede descartar de manera segura.

Aqui van:

Código Python:

def max_cycle(a, b):
 
    cache = {1:1}
 
    def num(cache, n):
        if n in cache: return cache[n]
        if n % 2:
            r = cache[n] = 1 + num(cache, 3 * n + 1)
        else:
            r = cache[n] = 1 + num(cache, n >> 1 )
        return r
 
    def sec(a, b):
        if a == b: return num(cache,a)
        maxim = 0
        if a > b: a,b = b,a
        lowlimit = max(a,b/2,2)
        for i in xrange(b,lowlimit-1,-1):
            if i in cache: continue
            tr = num(cache, i)
            if tr > maxim:
                maxim = tr
        return maxim
 
    return sec(a, b)
 

[sukoy]

El mejor resultado que obtengo, teniendo en cuenta las optimizaciones de CalgaryCorpus, es sacando el cache de la función, de esta forma no se destruye en cada llamada.

Código Python:

cache = {1:1}
def max_cycle(a, b):
 
    def num(cache, n):
        if n in cache: return cache[n]
        if n % 2:
            r = cache[n] = 1 + num(cache, 3 * n + 1)
        else:
            r = cache[n] = 1 + num(cache, n >> 1 )
        return r
 
    def sec(a, b):
        maxim = 0
        if a > b: a,b = b,a
        lowlimit = max(a,b >> 1)
        for i in xrange(lowlimit, b+1):
            tr = num(cache, i)
            if tr > maxim:
                maxim = tr
        return maxim
 
    return sec(a, b)
 

Saludos.

[CalgaryCorpus]

Edité el codigo en mi comentario previo varias veces con sucesivas optimizaciones.
Sugiero aplicar estas al código final y medir. Solo se aplicaron algunas.

Algunas optimizaciones suponen un cache local, no global.