Problemas de lógica mediante genéticos (Einstein y avenida complicada)

gen.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# genetico_logica.py
# Author: Overxfl0w13 #

from random import shuffle,randint,uniform
#from premisas_avenida import PREMISAS
from premisas_einstein import PREMISAS

MAX_PREMISES = 0

""" Búsqueda completa intratable O((n!)^m) / n es el número de casas y m es el número de atributos 
		(5!)^5 = 24883200000 combinaciones inicialmente (se reducen con las premisas dadas) 
"""
def genetico():
	poblacion   = generar_inicial()
	evaluacion  = evaluacion_genetico(poblacion)
	while convergencia_genetico(evaluacion)==False:
		poblacionaux = poblacion[:]
		poblacion    = []
		for x in xrange(len(poblacionaux)/2):
			padres          = seleccion(poblacionaux,evaluacion)
			padre_1,padre_2 = padres[0],padres[1]
			hijos           = cruce_2_puntos(padre_1,padre_2)
			hijo_1,hijo_2   = hijos[0],hijos[1]
			hijo_1,hijo_2   = mutacion(hijo_1),mutacion(hijo_2)
			poblacion.append(hijo_1)
			poblacion.append(hijo_2)
		evaluacion = evaluacion_genetico(poblacion)
	print "Solucion -> ", poblacion[evaluacion.index(len(PREMISAS))]

def generar_inicial():
	""" Genera una población inicial de individuos (|poblacion| € [l,2l] / l = |cromosoma|) """
	pob,longpob = [],randint(25,50)
	print longpob
	for x in xrange(50):
		rand = [[x for x in xrange(0,5)] for i in xrange(0,5)]
		for cgen in rand: shuffle(cgen)
		pob.append(sum(([]+rand),[]))
	return pob


def weighted_choice(choices):
   total = sum(w for c, w in choices)
   r = uniform(0, total)
   upto = 0
   for c, w in choices:
      if upto + w > r:
         return c
      upto += w
   
def seleccion(poblacion,evaluacion):
	fevaltotal = sum(evaluacion)
	pobaux     = poblacion[:]
	choices    = [(i,float(evaluacion[i])/fevaltotal) for i in xrange(len(evaluacion))]
	c1,c2      = pobaux[weighted_choice(choices)],pobaux[weighted_choice(choices)]
	return (c1,c2)
	
	
def mutacion(cromosoma):
	""" Mutacion por permutación entre 2 genes dentro de rangos [n,n+5] / n%5==0 """
	""" P(mutacion) = |cromosoma|**-1 = 0.04 """
	l = [x for x in xrange(len(cromosoma))]
	shuffle(l)
	p1,p2,p3,p4,p5 = cromosoma[0:5],cromosoma[5:10],cromosoma[10:15],cromosoma[15:20],cromosoma[20:25]
	p   = [p1,p2,p3,p4,p5]
	res = []
	for part in p:
		for i in xrange(len(part)):
			rand = l[randint(0,len(l)-1)] # P(rand==x / x€l | l) = |cromosoma|**-1 = 0.04
			if rand==1:
				pos = randint(0,len(part)-1)
				part[i],part[pos] = part[pos],part[i]
		res += part
	return res
	
def cruce_2_puntos(padre_1,padre_2):
	""" Puntos de cruce solo posibles si el indice es multiplo de 5 """
	puntos_posibles = [5,10,15,20]
	shuffle(puntos_posibles)
	p1,p2           = puntos_posibles.pop(randint(0,len(puntos_posibles)-1)),puntos_posibles.pop(randint(0,len(puntos_posibles)-1))
	p1,p2           = min(p1,p2),max(p1,p2)
	h1              = padre_1[0:p1]+padre_2[p1:p2]+padre_1[p2:]
	h2              = padre_2[0:p1]+padre_1[p1:p2]+padre_2[p2:]
	return (h1,h2)
	
def evaluacion_complete(cromosoma): 
	feval = 0
	for premisa in PREMISAS:
		if premisa(cromosoma): feval += 1
	return feval

def evaluacion_genetico(poblacion):
	feval,c = [],0
	for cromosoma in poblacion:
		c = 0
		for premisa in PREMISAS:
			try:
				if premisa(cromosoma): c+=1
			except: # Evitar ajustar las comprobaciones en los limites, y si se excede se cuenta como False (sin pérdida de generalidad) #
				continue
		feval.append(c)
	return feval
	
def convergencia_genetico(evaluacion): return True if len(PREMISAS) in evaluacion else False
				
if __name__ == "__main__": 
	genetico()

###############################################################################################################################
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# premisas_avenida.py
# Author: Overxfl0w13

VERDE,GRIS,BLANCA,AZUL,ROJA = 0,1,2,3,4
FORD,MERCEDES,VOLKSWAGEN,CADILLAC,CHEVROLET = 0,1,2,3,4
PINYA,LIMONADA,PEPSI,COCACOLA,CAFE = 0,1,2,3,4
CACHORRO,GATO,CONEJOS,CABALLO,VACA = 0,1,2,3,4
ARGENTINO,PERUANO,BRASILENYO,CHILENO,MEXICANO = 0,1,2,3,4
COLOR  		 = [VERDE,GRIS,BLANCA,AZUL,ROJA]
COCHE  		 = [FORD,MERCEDES,VOLKSWAGEN,CADILLAC,CHEVROLET]
BEBIDA 		 = [PINYA,LIMONADA,PEPSI,COCACOLA,CAFE]
ANIMAL 		 = [CACHORRO,GATO,CONEJOS,CABALLO,VACA]
PROPIETARIO  = [ARGENTINO,PERUANO,BRASILENYO,CHILENO,MEXICANO]

"""          801 803 805 807 809
color         0   1   2   3   4
coche         5   6   7   8   9
bebida        10  11  12 13  14
animal        15  16  17 18  19
propietario   20  21  22 23  24

Individuo -> V € {0,1,2,3,4}^25

"""

def all_index(l,el): 						return [i for i,val in enumerate(l) if val==el]
def get_casa(cromosoma,color):              return all_index(cromosoma,color)[0]
def get_coche(cromosoma,coche): 			return all_index(cromosoma,coche)[1]
def get_bebida(cromosoma,bebida): 			return all_index(cromosoma,bebida)[2]
def get_animal(cromosoma,animal): 			return all_index(cromosoma,animal)[3]
def get_propietario(cromosoma,propietario): return all_index(cromosoma,propietario)[4]

def premisa_1(cromosoma):
	""" Mexicano vive en la casa roja """
	mexicano  = get_propietario(cromosoma,MEXICANO)
	return True if cromosoma[mexicano-20]==ROJA else False


def premisa_2(cromosoma):
	""" Peruano tiene un mercedes """
	peruano   = get_propietario(cromosoma,PERUANO)
	return True if cromosoma[peruano-15]==MERCEDES else False
	
def premisa_3(cromosoma):
	""" Argentino tiene un cachorro """
	argentino = get_propietario(cromosoma,ARGENTINO)
	return True if cromosoma[argentino-5]==CACHORRO else False
	
def premisa_4(cromosoma):
	""" Chileno toma coca-cola """
	chileno  = get_propietario(cromosoma,CHILENO)
	return True if cromosoma[chileno-10]==COCACOLA else False

def premisa_5(cromosoma):
	""" Conejos misma distancia cadillac y limonada """
	conejo   = get_animal(cromosoma,CONEJOS)
	if conejo==19 or conejo==15: return False
	if conejo==16 or conejo==18:
		if cromosoma[conejo-11]==CADILLAC and cromosoma[conejo-4]==LIMONADA: return True
		if cromosoma[conejo-9]==CADILLAC and cromosoma[conejo-6]==LIMONADA: return True
	if conejo==17:
		if cromosoma[conejo-11]==CADILLAC and cromosoma[conejo-4]==LIMONADA: return True
		if cromosoma[conejo-9]==CADILLAC and cromosoma[conejo-6]==LIMONADA: return True
		if cromosoma[conejo-12]==CADILLAC and cromosoma[conejo-3]==LIMONADA: return True
		if cromosoma[conejo-8]==CADILLAC and cromosoma[conejo-7]==LIMONADA: return True 	
	return False

def premisa_6(cromosoma):
	""" Gato no toma cafe ni vive en la casa azul """
	gato      = get_animal(cromosoma,GATO)
	return True if (cromosoma[gato-5]!=CAFE) and (cromosoma[gato-15]!=AZUL) else False

def premisa_7(cromosoma):
	""" En la casa verde se toma zumo de piña """
	casa_verde = get_casa(cromosoma,VERDE)
	return True if (cromosoma[casa_verde+10])==PINYA else False

def premisa_8(cromosoma):
	""" La vaca es vecina de la casa donde se toma coca-cola """
	vaca = get_animal(cromosoma,VACA)
	if vaca==15:
		if cromosoma[vaca-4]==COCACOLA: return True
	elif vaca==19:
		if cromosoma[vaca-6]==COCACOLA: return True
	else:
		if cromosoma[vaca-6]==COCACOLA or cromosoma[vaca-4]==COCACOLA: return True
	return False

def premisa_9(cromosoma):
	""" La casa verde tiene como vecina a la derecha a la casa gris """
	casa_verde = get_casa(cromosoma,VERDE)
	return True if cromosoma[casa_verde+1]==GRIS else False

def premisa_10(cromosoma):
	""" El peruano y el argentino son vecinos """
	peruano    = get_propietario(cromosoma,PERUANO)
	return True if (peruano>20 and cromosoma[peruano-1]==ARGENTINO) or (cromosoma[peruano+1]==ARGENTINO) else False

def premisa_11(cromosoma):
	""" El propietario del volkswagen cria conejos """
	volkswagen = get_coche(cromosoma,VOLKSWAGEN)
	return True if (cromosoma[volkswagen+10]==CONEJOS) else False
	
def premisa_12(cromosoma):
	""" El chevrolet pertenece a la casa roja """
	casa_roja = get_casa(cromosoma,ROJA)
	return True if (cromosoma[casa_roja+5]==CHEVROLET) else False

def premisa_13(cromosoma):
	""" Se toma pepsi-cola en la tercera casa """
	return True if cromosoma[12]==PEPSI else False

def premisa_14(cromosoma):
	""" El brasileño es vecino de la casa azul """
	brasilenyo = get_propietario(cromosoma,BRASILENYO)
	if brasilenyo==20:
		if cromosoma[brasilenyo-19]==AZUL: return True
	elif brasilenyo==24:
		if cromosoma[brasilenyo-21]==AZUL: return True
	else:
		if cromosoma[brasilenyo-19]==AZUL: return True
		if cromosoma[brasilenyo-21]==AZUL: return True
	return False

def premisa_15(cromosoma):
	""" El propietario del ford toma limonada """
	ford       = get_coche(cromosoma,FORD)
	return True if cromosoma[ford+5]==LIMONADA else False

def premisa_16(cromosoma):
	""" El propietario de la vaca es vecino del dueño del cadillac """
	vaca       = get_animal(cromosoma,VACA)
	if vaca==15:
		if cromosoma[vaca-9]==CADILLAC: return True
	elif vaca==19:
		if cromosoma[vaca-11]==CADILLAC: return True
	else:
		if cromosoma[vaca-9]==CADILLAC: return True
		if cromosoma[vaca-11]==CADILLAC: return True
	return False

def premisa_17(cromosoma):
	""" El propietario del chevrolet es vecino del dueño del caballo """
	chevrolet = get_coche(cromosoma,CHEVROLET)
	if chevrolet==5:
		if cromosoma[chevrolet+11]==CABALLO: return True
	elif chevrolet==9:
		if cromosoma[chevrolet+9]==CABALLO: return True
	else:
		if cromosoma[chevrolet+11]==CABALLO: return True
		if cromosoma[chevrolet+9]==CABALLO: return True
	return False
	
def premisa_18(cromosoma):
	""" La casa blanca es del brasileño """
	casa_blanca = get_casa(cromosoma,BLANCA)
	return True if (cromosoma[casa_blanca+20]==BRASILENYO) else False
	

PREMISAS = [premisa_1,premisa_2,premisa_3,premisa_4,premisa_5,premisa_6,
			premisa_7,premisa_8,premisa_9,premisa_10,premisa_11,premisa_12,
			premisa_13,premisa_14,premisa_15,premisa_16,premisa_17,premisa_18]

###############################################################################################################################
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
#  premisas_einstein.py
#  
#  Author: Overxfl0w13
#  

ROJA,VERDE,AMARILLA,BLANCA,AZUL = 0,1,2,3,4
PALLMALL,DUNHILL,BRENDS,BLUEMASTERS,PRINCE = 0,1,2,3,4
TE,CAFE,LECHE,CERVEZA,AGUA = 0,1,2,3,4
PERRO,PAJARO,GATO,PEZ,CABALLO = 0,1,2,3,4
BRITANICO,SUECO,NORUEGO,DANES,ALEMAN = 0,1,2,3,4

"""          801 803 805 807 809
color         0   1   2   3   4
fuma          5   6   7   8   9
bebida        10  11  12 13  14
animal        15  16  17 18  19
propietario   20  21  22 23  24

Individuo -> V € {0,1,2,3,4}^25

"""

def all_index(l,el): 						return [i for i,val in enumerate(l) if val==el]
def get_casa(cromosoma,color):              return all_index(cromosoma,color)[0]
def get_fuma(cromosoma,fuma): 			    return all_index(cromosoma,fuma)[1]
def get_bebida(cromosoma,bebida): 			return all_index(cromosoma,bebida)[2]
def get_animal(cromosoma,animal): 			return all_index(cromosoma,animal)[3]
def get_propietario(cromosoma,propietario): return all_index(cromosoma,propietario)[4]


def premisa_1(cromosoma):
	""" Britanico en la casa roja """
	britanico = get_propietario(cromosoma,BRITANICO)
	return True if cromosoma[britanico-20]==ROJA else False
	
def premisa_2(cromosoma):
	""" El sueco tiene un perro """
	sueco = get_propietario(cromosoma,SUECO)
	return True if cromosoma[sueco-5]==PERRO else False

def premisa_3(cromosoma):
	""" El danes toma te """
	danes = get_propietario(cromosoma,DANES)
	return True if cromosoma[danes-10]==TE else False
	
def premisa_4(cromosoma):
	""" La casa verde esta a la izquierda de la blanca """
	casa_blanca = get_casa(cromosoma,BLANCA)
	if casa_blanca==0: return False
	else:
		if cromosoma[casa_blanca-1]==VERDE: return True
	return False

def premisa_5(cromosoma):
	""" El dueño de la casa verde toma cafe """
	casa_verde = get_casa(cromosoma,VERDE)
	return True if cromosoma[casa_verde+10]==CAFE else False


def premisa_6(cromosoma):
	""" La persona que fuma pallmall tiene un pajaro """
	pallmall = get_fuma(cromosoma,PALLMALL)
	return True if cromosoma[pallmall+10]==PAJARO else False

def premisa_7(cromosoma):
	""" El dueño de la casa amarilla fuma dunhill """
	casa_amarilla = get_casa(cromosoma,AMARILLA)
	return True if cromosoma[casa_amarilla+5]==DUNHILL else False
	
def premisa_8(cromosoma):
	""" El que vive en la casa del centro toma leche """
	return True if cromosoma[12]==LECHE else False
	
def premisa_9(cromosoma):
	""" El noruego vive en la primera casa """
	return True if cromosoma[20]==NORUEGO else False

def premisa_10(cromosoma):
	""" La persona que fuma brends vive junto a la persona que tiene un gato """
	brends = get_fuma(cromosoma,BRENDS)
	if brends==5:
		if cromosoma[brends+11]==GATO: return True
	elif brends==9:
		if cromosoma[brends+9]==GATO: return True
	else:
		if cromosoma[brends+11]==GATO: return True
		if cromosoma[brends+9]==GATO: return True
	return False

def premisa_11(cromosoma):
	""" La persona que tiene un caballo vive junto a la que fuma dunhill """
	dunhill = get_fuma(cromosoma,DUNHILL)
	if dunhill==5:
		if cromosoma[dunhill+11]==CABALLO: return True
	elif dunhill==9:
		if cromosoma[dunhill+9]==CABALLO: return True
	else:
		if cromosoma[dunhill+11]==CABALLO: return True
		if cromosoma[dunhill+9]==CABALLO: return True
	return False

def premisa_12(cromosoma):
	""" El que fuma bluemasters bebe cerveza """
	bluemasters = get_fuma(cromosoma,BLUEMASTERS)
	return True if cromosoma[bluemasters+5]==CERVEZA else False

def premisa_13(cromosoma):
	""" El aleman fuma prince """
	aleman = get_propietario(cromosoma,ALEMAN)
	return True if cromosoma[aleman-15]==PRINCE else False


def premisa_14(cromosoma):
	""" El noruego vive junto a la casa azul """
	noruego = get_propietario(cromosoma,NORUEGO)
	if noruego==20:
		if cromosoma[noruego-19]==AZUL: return True
	elif noruego==24:
		if cromosoma[noruego-21]==AZUL: return True
	else:
		if cromosoma[noruego-19]==AZUL: return True
		if cromosoma[noruego-21]==AZUL: return True
	return False

def premisa_15(cromosoma):
	""" El que fuma brends tiene un vecino que bebe agua """
	brends = get_fuma(cromosoma,BRENDS)
	if brends==5:
		if cromosoma[brends+6]==AGUA: return True
	elif brends==9:
		if cromosoma[brends+4]==AGUA: return True
	else:
		if cromosoma[brends+6]==AGUA: return True
		if cromosoma[brends+4]==AGUA: return True
	return False

PREMISAS = [premisa_1,premisa_2,premisa_3,premisa_4,premisa_5,premisa_6,
			premisa_7,premisa_8,premisa_9,premisa_10,premisa_11,premisa_12,
			premisa_13,premisa_14,premisa_15]