+#!/usr/bin/env python
+
+import sys
+
+
+class Persona:
+ def __init__(self, nombre = ""):
+ # Nombre de la persona, solo con fines de representacion
+ self.nombre = nombre
+
+ # Lista de personas que prefiere, la primera de la lista es la
+ # que mejor posicionada esta
+ self.prefs = []
+
+ # Estado de la persona: puede ser 'soltero', 'declarado' o
+ # 'comprometido'
+ self.estado = 'soltero'
+
+ # De estar declarado o comprometido, quien es su pareja
+ self.pareja = None
+
+ # Lista de la gente que se le declaro
+ self.ofertas = []
+
+ # Lista de la gente que lo rechazo
+ self.rechazos = []
+
+
+ def __str__(self):
+ "Para representacion"
+ if not self.pareja:
+ pareja = '-'
+ else:
+ pareja = self.pareja.nombre
+ return "<%s: %s - %s>" % (self.nombre, self.estado, pareja)
+
+ __repr__ = __str__
+
+
+ def cmp(self, p1, p2):
+ """Funcion de comparacion entre dos personas segun nuestras
+ preferencias"""
+ if self.prefs.index(p1) < self.prefs.index(p2):
+ return 1
+ elif self.prefs.index(p1) == self.prefs.index(p2):
+ return 0
+ else:
+ return -1
+
+
+ def ordenar_ofertas(self):
+ "Ordenamos las ofertas segun nuestras preferencias"
+ # este sort es in-place y estable
+ def cmp(x, y, obj = self):
+ return obj.cmp(x, y)
+ self.ofertas.sort(cmp)
+
+
+ def declarar_a(self, p):
+ "Nos declaramos a la persona p"
+ self.estado = 'declarado'
+ self.pareja = p
+ p.ofertas.append(self)
+
+
+ def comprometer_con(self, p):
+ """Nos comprometemos con la persona p, quien se nos habia
+ declarado previamente"""
+
+ # XXX: podriamos usar los decorators de contract para esto
+ assert p.estado == 'declarado' and p.pareja == self
+
+ # rompemos el compromiso, si hay
+ if self.estado == 'comprometido':
+ self.pareja.estado = 'soltero'
+ self.pareja.pareja = None
+ self.pareja.rechazos.append(p)
+
+ # nos comprometemos
+ self.estado = 'comprometido'
+ self.pareja = p
+ p.estado = 'comprometido'
+ p.pareja = self
+
+ # si tenemos ofertas, las rechazamos
+ for pretendiente in self.ofertas:
+ pretendiente.rechazos.append(p)
+ self.ofertas = []
+
+
+class Hombre (Persona):
+ pass
+
+
+class Mujer (Persona):
+ pass
+
+
+
+class Susanita_GS:
+ def __init__(self):
+ # Lista de hombres
+ self.hombres = []
+
+ # Lista de mujeres
+ self.mujeres = []
+
+ # Diccionario de gente, relaciona nombres con objetos
+ self.nombres = {}
+
+
+ def add_persona(self, p):
+ assert not self.nombres.has_key(p.nombre)
+
+ self.nombres[p.nombre] = p
+ if isinstance(p, Hombre):
+ self.hombres.append(p)
+ elif isinstance(p, Mujer):
+ self.mujeres.append(p)
+
+ def get_persona(self, nombre):
+ try:
+ return self.nombres[nombre]
+ except:
+ return None
+
+
+ def primera_ronda(self):
+ # "En la primera ronda cada hombre se le declara a la mujer que
+ # prefiere independientemente de que algun otro se le haya
+ # declarado.
+ # Entre todas las propuestas que recibio, cada mujer elige al
+ # hombre mejor posicionado en su ranking y se compromete con
+ # el. Si una mujer no recibe ninguna propuesta, espera hasta
+ # la proxima ronda."
+ for h in self.hombres:
+ m = h.prefs[0]
+ h.declarar_a(m)
+
+ for m in self.mujeres:
+ if not m.ofertas:
+ continue
+
+ m.ordenar_ofertas()
+ h = m.ofertas.pop(0)
+ m.comprometer_con(h)
+
+
+ def nesima_ronda(self):
+ # "En cada ronda subsiguiente los hombres que ya estan
+ # comprometidos no hacen nada. Cada hombre no comprometido se
+ # le declara a la mujer mejor posicionada en su ranking que
+ # aun no lo rechazo, independientemente de que ella este
+ # comprometida o no.
+ # Cuando le toca el turno a las mujeres, cada mujer acepta la
+ # propuesta del hombre mejor posicionado en su ranking
+ # (incluso puede llegar a romper un compromiso; tambien puede
+ # suceder que su novio actual este mejor posicionado que todos
+ # sus nuevos pretendientes, en cuyo caso se queda con el novio
+ # actual). Si una mujer no recibe ninguna propuesta, espera
+ # hasta la proxima ronda."
+ for h in self.hombres:
+ if h.estado == 'comprometido':
+ continue
+
+ for m in h.prefs:
+ if m in h.rechazos:
+ continue
+ break
+ else:
+ assert False
+ h.declarar_a(m)
+
+ for m in self.mujeres:
+ if not m.ofertas:
+ continue
+
+ m.ordenar_ofertas()
+ h = m.ofertas.pop(0)
+ if m.estado == 'comprometido':
+ if m.cmp(m.pareja, h) < 0:
+ # la oferta es mejor, rompemos el
+ # compromiso
+ m.comprometer_con(h)
+ else:
+ # estamos mejor con nuestra pareja
+ # actual, asi que no hacemos mas que
+ # rechazar a todos (incluyendo el
+ # mejor candidato)
+ for i in m.ofertas + [h]:
+ i.rechazos.append(m)
+ m.ofertas = []
+ else:
+ m.comprometer_con(h)
+
+
+ def todos_h_comprometidos(self):
+ "Se fija si todos los hombres estan comprometidos"
+ # FIXME: podemos ver de poner esto adentro de nesima_ronda()
+ for h in self.hombres:
+ if h.estado != 'comprometido':
+ return False
+ return True
+
+
+ def mostrar_estado(self):
+ for h in self.hombres:
+ print h
+ print
+ for m in self.mujeres:
+ print m
+ print
+ print
+ sys.stdout.flush()
+
+
+ def casamentear(self):
+ self.primera_ronda()
+ while not self.todos_h_comprometidos():
+ self.nesima_ronda()
+
+
+
+class Parser:
+ def __init__(self, susanita):
+ self.s = susanita
+ pass
+
+ def input(self, filename):
+ f = open(filename)
+ sexo = Hombre
+ opuesto = Mujer
+ for l in f:
+ l = l.strip()
+
+ # la linea vacia alterna de sexo
+ if not l:
+ sexo = Mujer
+ opuesto = Hombre
+ continue
+
+ # obtenemos el nombre y la lista
+ nombre, prefs = l.split(':')
+ prefs = prefs.split(',')
+
+ nombre = nombre.strip()
+ p = self.s.get_persona(nombre)
+ if not p:
+ p = sexo(nombre)
+ self.s.add_persona(p)
+
+ for i in prefs:
+ i = i.strip()
+ t = self.s.get_persona(i)
+ if not t:
+ t = opuesto(i)
+ self.s.add_persona(t)
+ p.prefs.append(t)
+
+ def output(self):
+ for h in self.s.hombres:
+ assert h.estado == 'comprometido'
+ print h.nombre, h.pareja.nombre
+ print
+ for m in self.s.mujeres:
+ assert m.estado == 'comprometido'
+ print m.nombre, m.pareja.nombre
+
+
+
+if __name__ == '__main__':
+ if len(sys.argv) != 2:
+ print "El primer parametro debe ser el archivo de entrada"
+ sys.exit(1)
+
+ s = Susanita_GS()
+ p = Parser(s)
+
+ p.input(sys.argv[1])
+ s.casamentear()
+ p.output()
+
+
projects / z.facultad / 75.29 / susanita.git / commitdiff