Lattice paths 20x20 grid

problem15_EULER.py

#!/usr/bin/env python
# -*- coding: utf-8 -*- 
# En una grilla de 20x20 tenemos desde (0,0) hasta (20,20) es decir 20² combinaciones.
# lo que significa que para abarcar todas las posiciones tenemos que hacer 2 bucles anidados
# unit testing :
#		1*1 : 2
#		2*2 : 6
#		3*3 : 20
#		4*4 : 70
# (x,y)
import pprint
rutas = []
completado = []
MAX_VALUE = 20 # Igual al tamaño de la grilla

def generar_ruta(xy = [0,0]):
	global MAX_VALUE
	x = xy[0]
	y = xy[1]
	rutas.append([])
	ruta_a_trabajar = rutas[len(rutas)-1]
	ruta_a_trabajar.append([x,y]) # si no ponemos esto se pierde el valor inicial
	while True:
		if x<MAX_VALUE:
			x+=1
			ruta_a_trabajar.append([x,y])
		if y<MAX_VALUE:
			y+=1
			ruta_a_trabajar.append([x,y])
		else:
			break

	#pprint.pprint( rutas ,None, 0, 800,None )
	

def ruta_alternativa(desde,hasta):
	if (hasta[0] - desde[0]) > (hasta[1] - desde[1]):
		# Es mas la diferencia horizontal
		resultado = [desde[0],desde[1]+1]
	else:
		#Es mas la diferencia vertical
		resultado = [desde[0]+1,desde[1]]
	# en el caso de por ej: desde (2,1) hasta(2,2) siendo MAX_VALUE = 2
	if resultado == hasta or resultado[0]>MAX_VALUE or resultado[1]>MAX_VALUE : 
		raise Exception(resultado)
	else:
		return resultado
	
# guardar las posibilidades de rutas y luego evaular las que siguen
# generar la primera ruta
generar_ruta()
# generar la segunda
generar_ruta(ruta_alternativa(rutas[0][0],rutas[0][1]))
completado.append([0,0]) # significa que cubrimos la otra opción de la 1era ruta en el primer movimiento

a = 1 # para empezar por la segunda posición de los completados (ya hay un espacio ocupado)
b = 0 # para empezar por la primera posición de los completados (ya hay un espacio ocupado)
cant_de_excepciones = 0
while True:
	print len(rutas)
	try:
		generar_ruta(ruta_alternativa ( rutas[b][a],rutas[b][a+1] ) )
		a +=1 
		cant_de_excepciones = 0
	except Exception, e:
		#print e
		b+=1
		a = 0
		cant_de_excepciones += 1
	if cant_de_excepciones>500:
		break