Foros del Web » Programando para Internet » Python »

Desafíos 2014 - Semana 4

Estas en el tema de Desafíos 2014 - Semana 4 en el foro de Python en Foros del Web. 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 ...
  #1 (permalink)  
Antiguo 17/02/2014, 18:51
Avatar de razpeitia
Moderador
 
Fecha de Ingreso: marzo-2005
Ubicación: Monterrey, México
Mensajes: 7.321
Antigüedad: 14 años, 3 meses
Puntos: 1360
Desafíos 2014 - Semana 4

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:
Ver original
  1. def max_cycle(a, b):
  2.     return 0
  3.  
  4. if __name__ == '__main__':
  5.     from time import time
  6.     t1 = time()
  7.     assert max_cycle(1, 10) == 20
  8.     assert max_cycle(100, 200) == 125
  9.     assert max_cycle(201, 210) == 89
  10.     assert max_cycle(900, 1000) == 174
  11.     assert max_cycle(113383, 113383) == 248
  12.     assert max_cycle(999999, 1) == 525
  13.     assert max_cycle(20, 20) == 8
  14.     assert max_cycle(9999, 9999) == 92
  15.     assert max_cycle(1, 9999) == 262
  16.     assert max_cycle(340, 3000) == 217
  17.     assert max_cycle(3000, 340) == 217
  18.     assert max_cycle(500, 101) == 144
  19.     assert max_cycle(1, 1) == 1
  20.     assert max_cycle(9999, 9998) == 92
  21.     t2 = time()
  22.     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

Última edición por razpeitia; 18/02/2014 a las 14:22
  #2 (permalink)  
Antiguo 18/02/2014, 08:58
 
Fecha de Ingreso: febrero-2011
Mensajes: 54
Antigüedad: 8 años, 4 meses
Puntos: 18
Respuesta: Desafíos 2014 - Semana 4

Mi intento:
Código Python:
Ver original
  1. cache = {}
  2. def max_cycle(a, b):
  3.            
  4.     def num(n):
  5.         ni = n
  6.         cnt = 1
  7.         if n in cache:
  8.             return cache[n]
  9.         else:
  10.             while not n == 1:
  11.                 cnt += 1
  12.                 if n%2 != 0:
  13.                     n = (3*n)+1
  14.                 else:
  15.                     n = n/2
  16.             cache[ni] = cnt
  17.         return cache[ni]
  18.  
  19.     def sec(a, b):
  20.         maxim = 0
  21.         if a > b: a,b = b,a
  22.         for i in xrange(a,b+1):
  23.             tr = num(i)
  24.             if tr > maxim:
  25.                 maxim = tr
  26.         return maxim
  27.  
  28.     return sec(a,b)
  29.  
  30.  
  31. if __name__ == '__main__':
  32.     from time import time
  33.     t1 = time()
  34.     assert max_cycle(1, 10) == 20
  35.     assert max_cycle(1, 200) == 125
  36.     assert max_cycle(201, 210) == 89
  37.     assert max_cycle(900, 1000) == 174
  38.     assert max_cycle(113383, 113383) == 248
  39.     assert max_cycle(999999, 1) == 525
  40.     assert max_cycle(20, 20) == 8
  41.     assert max_cycle(9999, 9999) == 92
  42.     assert max_cycle(1, 9999) == 262
  43.     assert max_cycle(340, 3000) == 217
  44.     assert max_cycle(3000, 340) == 217
  45.     assert max_cycle(500, 101) == 144
  46.     assert max_cycle(1, 1) == 1
  47.     assert max_cycle(9999, 9998) == 92
  48.     t2 = time()
  49.     print "Tiempo de ejecucion %.3f s" % (t2 - t1)
  50. #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.
  #3 (permalink)  
Antiguo 18/02/2014, 10:49
 
Fecha de Ingreso: febrero-2011
Mensajes: 54
Antigüedad: 8 años, 4 meses
Puntos: 18
Respuesta: Desafíos 2014 - Semana 4

Mucho mejor.
Código Python:
Ver original
  1. def max_cycle(a, b):
  2.  
  3.     cache = {1:1}
  4.    
  5.     def num(cache, n):
  6.         if not n in cache:
  7.             if n % 2:
  8.                 cache[n] = 1 + num(cache, 3 * n + 1)
  9.             else:
  10.                 cache[n] = 1 + num(cache, n / 2)
  11.         return cache[n]
  12.  
  13.     def sec(a, b):
  14.         maxim = 0
  15.         if a > b: a,b = b,a
  16.         for i in xrange(a, b+1):
  17.             tr = num(cache, i)
  18.             if tr > maxim:
  19.                 maxim = tr
  20.         return maxim
  21.  
  22.     return sec(a, b)
  23.  
  24.  
  25. if __name__ == '__main__':
  26.     from time import time
  27.     t1 = time()
  28.     assert max_cycle(1, 10) == 20
  29.     assert max_cycle(100, 200) == 125
  30.     assert max_cycle(201, 210) == 89
  31.     assert max_cycle(900, 1000) == 174
  32.     assert max_cycle(113383, 113383) == 248
  33.     assert max_cycle(999999, 1) == 525
  34.     assert max_cycle(20, 20) == 8
  35.     assert max_cycle(9999, 9999) == 92
  36.     assert max_cycle(1, 9999) == 262
  37.     assert max_cycle(340, 3000) == 217
  38.     assert max_cycle(3000, 340) == 217
  39.     assert max_cycle(500, 101) == 144
  40.     assert max_cycle(1, 1) == 1
  41.     assert max_cycle(9999, 9998) == 92
  42.     t2 = time()
  43.     print "Tiempo de ejecucion %.3f s" % (t2 - t1)
  44. #Tiempo de ejecucion 2.062 s

Saludos.
  #4 (permalink)  
Antiguo 23/02/2014, 10:46
 
Fecha de Ingreso: junio-2008
Ubicación: Seattle, USA
Mensajes: 730
Antigüedad: 11 años, 1 mes
Puntos: 60
Respuesta: Desafíos 2014 - Semana 4

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:
Ver original
  1. def max_cycle(a, b):
  2.  
  3.     cache = {1:1}
  4.  
  5.     def num(cache, n):
  6.         if n in cache: return cache[n]
  7.         if n % 2:
  8.             r = cache[n] = 1 + num(cache, 3 * n + 1)
  9.         else:
  10.             r = cache[n] = 1 + num(cache, n >> 1 )
  11.         return r
  12.  
  13.     def sec(a, b):
  14.         if a == b: return num(cache,a)
  15.         maxim = 0
  16.         if a > b: a,b = b,a
  17.         lowlimit = max(a,b/2,2)
  18.         for i in xrange(b,lowlimit-1,-1):
  19.             if i in cache: continue
  20.             tr = num(cache, i)
  21.             if tr > maxim:
  22.                 maxim = tr
  23.         return maxim
  24.  
  25.     return sec(a, b)
__________________
Visita mi perfil en LinkedIn

Última edición por CalgaryCorpus; 24/02/2014 a las 10:55
  #5 (permalink)  
Antiguo 25/02/2014, 03:02
 
Fecha de Ingreso: febrero-2011
Mensajes: 54
Antigüedad: 8 años, 4 meses
Puntos: 18
Respuesta: Desafíos 2014 - Semana 4

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:
Ver original
  1. cache = {1:1}
  2. def max_cycle(a, b):
  3.  
  4.     def num(cache, n):
  5.         if n in cache: return cache[n]
  6.         if n % 2:
  7.             r = cache[n] = 1 + num(cache, 3 * n + 1)
  8.         else:
  9.             r = cache[n] = 1 + num(cache, n >> 1 )
  10.         return r
  11.  
  12.     def sec(a, b):
  13.         maxim = 0
  14.         if a > b: a,b = b,a
  15.         lowlimit = max(a,b >> 1)
  16.         for i in xrange(lowlimit, b+1):
  17.             tr = num(cache, i)
  18.             if tr > maxim:
  19.                 maxim = tr
  20.         return maxim
  21.  
  22.     return sec(a, b)

Saludos.
  #6 (permalink)  
Antiguo 25/02/2014, 07:24
 
Fecha de Ingreso: junio-2008
Ubicación: Seattle, USA
Mensajes: 730
Antigüedad: 11 años, 1 mes
Puntos: 60
Respuesta: Desafíos 2014 - Semana 4

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.
__________________
Visita mi perfil en LinkedIn

Etiquetas: gui, semana
Atención: Estás leyendo un tema que no tiene actividad desde hace más de 6 MESES, te recomendamos abrir un Nuevo tema en lugar de responder al actual.
Respuesta

SíEste tema le ha gustado a 1 personas




La zona horaria es GMT -6. Ahora son las 03:47.