test/susanita.py

   1 #!/usr/bin/env python
   2
   3 import sys
   4
   5
   6 class Persona:
   7         def __init__(self, nombre = ""):
   8                 # Nombre de la persona, solo con fines de representacion
   9                 self.nombre = nombre
  10
  11                 # Lista de personas que prefiere, la primera de la lista es la
  12                 # que mejor posicionada esta
  13                 self.prefs = []
  14
  15                 # Estado de la persona: puede ser 'soltero', 'declarado' o
  16                 # 'comprometido'
  17                 self.estado = 'soltero'
  18
  19                 # De estar declarado o comprometido, quien es su pareja
  20                 self.pareja = None
  21
  22                 # Lista de la gente que se le declaro
  23                 self.ofertas = []
  24
  25                 # Lista de la gente que lo rechazo
  26                 self.rechazos = []
  27
  28
  29         def __str__(self):
  30                 "Para representacion"
  31                 if not self.pareja:
  32                         pareja = '-'
  33                 else:
  34                         pareja = self.pareja.nombre
  35                 return "<%s: %s - %s>" % (self.nombre, self.estado, pareja)
  36
  37         __repr__ = __str__
  38
  39
  40         def cmp(self, p1, p2):
  41                 """Funcion de comparacion entre dos personas segun nuestras
  42                 preferencias"""
  43                 if self.prefs.index(p1) < self.prefs.index(p2):
  44                         return 1
  45                 elif self.prefs.index(p1) == self.prefs.index(p2):
  46                         return 0
  47                 else:
  48                         return -1
  49
  50
  51         def ordenar_ofertas(self):
  52                 "Ordenamos las ofertas segun nuestras preferencias"
  53                 # este sort es in-place y estable
  54                 def cmp(x, y, obj = self):
  55                         return obj.cmp(x, y)
  56                 self.ofertas.sort(cmp)
  57
  58
  59         def declarar_a(self, p):
  60                 "Nos declaramos a la persona p"
  61                 self.estado = 'declarado'
  62                 self.pareja = p
  63                 p.ofertas.append(self)
  64
  65
  66         def comprometer_con(self, p):
  67                 """Nos comprometemos con la persona p, quien se nos habia
  68                 declarado previamente"""
  69
  70                 # XXX: podriamos usar los decorators de contract para esto
  71                 assert p.estado == 'declarado' and p.pareja == self
  72
  73                 # rompemos el compromiso, si hay
  74                 if self.estado == 'comprometido':
  75                         self.pareja.estado = 'soltero'
  76                         self.pareja.pareja = None
  77                         self.pareja.rechazos.append(self)
  78
  79                 # nos comprometemos
  80                 self.estado = 'comprometido'
  81                 self.pareja = p
  82                 p.estado = 'comprometido'
  83                 p.pareja = self
  84
  85                 # si tenemos ofertas, las rechazamos
  86                 for pretendiente in self.ofertas:
  87                         pretendiente.rechazos.append(self)
  88                 self.ofertas = []
  89
  90
  91 class Hombre (Persona):
  92         pass
  93
  94
  95 class Mujer (Persona):
  96         pass
  97
  98
  99
 100 class Susanita_GS:
 101         def __init__(self):
 102                 # Lista de hombres
 103                 self.hombres = []
 104
 105                 # Lista de mujeres
 106                 self.mujeres = []
 107
 108                 # Diccionario de gente, relaciona nombres con objetos
 109                 self.nombres = {}
 110
 111
 112         def add_persona(self, p):
 113                 assert not self.nombres.has_key(p.nombre)
 114
 115                 self.nombres[p.nombre] = p
 116                 if isinstance(p, Hombre):
 117                         self.hombres.append(p)
 118                 elif isinstance(p, Mujer):
 119                         self.mujeres.append(p)
 120
 121         def get_persona(self, nombre):
 122                 try:
 123                         return self.nombres[nombre]
 124                 except:
 125                         return None
 126
 127
 128         def primera_ronda(self):
 129                 # "En la primera ronda cada hombre se le declara a la mujer que
 130                 # prefiere independientemente de que algun otro se le haya
 131                 # declarado.
 132                 # Entre todas las propuestas que recibio, cada mujer elige al
 133                 # hombre mejor posicionado en su ranking y se compromete con
 134                 # el. Si una mujer no recibe ninguna propuesta, espera hasta
 135                 # la proxima ronda."
 136                 for h in self.hombres:
 137                         m = h.prefs[0]
 138                         h.declarar_a(m)
 139
 140                 for m in self.mujeres:
 141                         if not m.ofertas:
 142                                 continue
 143
 144                         m.ordenar_ofertas()
 145                         h = m.ofertas.pop(0)
 146                         m.comprometer_con(h)
 147
 148
 149         def nesima_ronda(self):
 150                 # "En cada ronda subsiguiente los hombres que ya estan
 151                 # comprometidos no hacen nada. Cada hombre no comprometido se
 152                 # le declara a la mujer mejor posicionada en su ranking que
 153                 # aun no lo rechazo, independientemente de que ella este
 154                 # comprometida o no.
 155                 # Cuando le toca el turno a las mujeres, cada mujer acepta la
 156                 # propuesta del hombre mejor posicionado en su ranking
 157                 # (incluso puede llegar a romper un compromiso; tambien puede
 158                 # suceder que su novio actual este mejor posicionado que todos
 159                 # sus nuevos pretendientes, en cuyo caso se queda con el novio
 160                 # actual). Si una mujer no recibe ninguna propuesta, espera
 161                 # hasta la proxima ronda."
 162                 for h in self.hombres:
 163                         if h.estado == 'comprometido':
 164                                 continue
 165
 166                         for m in h.prefs:
 167                                 if m in h.rechazos:
 168                                         continue
 169                                 break
 170                         else:
 171                                 assert False
 172                         h.declarar_a(m)
 173
 174                 for m in self.mujeres:
 175                         if not m.ofertas:
 176                                 continue
 177
 178                         m.ordenar_ofertas()
 179                         h = m.ofertas.pop(0)
 180                         if m.estado == 'comprometido':
 181                                 if m.cmp(m.pareja, h) < 0:
 182                                         # la oferta es mejor, rompemos el
 183                                         # compromiso
 184                                         m.comprometer_con(h)
 185                                 else:
 186                                         # estamos mejor con nuestra pareja
 187                                         # actual, asi que no hacemos mas que
 188                                         # rechazar a todos (incluyendo el
 189                                         # mejor candidato)
 190                                         for i in m.ofertas + [h]:
 191                                                 i.rechazos.append(m)
 192                                         m.ofertas = []
 193                         else:
 194                                 m.comprometer_con(h)
 195
 196
 197         def todos_h_comprometidos(self):
 198                 "Se fija si todos los hombres estan comprometidos"
 199                 # FIXME: podemos ver de poner esto adentro de nesima_ronda()
 200                 for h in self.hombres:
 201                         if h.estado != 'comprometido':
 202                                 return False
 203                 return True
 204
 205
 206         def mostrar_estado(self):
 207                 for h in self.hombres:
 208                         print h
 209                 print
 210                 for m in self.mujeres:
 211                         print m
 212                 print
 213                 print
 214                 sys.stdout.flush()
 215
 216
 217         def casamentear(self):
 218                 self.primera_ronda()
 219                 while not self.todos_h_comprometidos():
 220                         self.nesima_ronda()
 221
 222
 223
 224 class Parser:
 225         def __init__(self, susanita):
 226                 self.s = susanita
 227                 pass
 228
 229         def input(self, filename):
 230                 f = open(filename)
 231                 sexo = Hombre
 232                 opuesto = Mujer
 233                 for l in f:
 234                         l = l.strip()
 235
 236                         # la linea vacia alterna de sexo
 237                         if not l:
 238                                 sexo = Mujer
 239                                 opuesto = Hombre
 240                                 continue
 241
 242                         # obtenemos el nombre y la lista
 243                         nombre, prefs = l.split(':')
 244                         prefs = prefs.split(',')
 245
 246                         nombre = nombre.strip()
 247                         p = self.s.get_persona(nombre)
 248                         if not p:
 249                                 p = sexo(nombre)
 250                                 self.s.add_persona(p)
 251
 252                         for i in prefs:
 253                                 i = i.strip()
 254                                 t = self.s.get_persona(i)
 255                                 if not t:
 256                                         t = opuesto(i)
 257                                         self.s.add_persona(t)
 258                                 p.prefs.append(t)
 259
 260         def output(self):
 261                 for h in self.s.hombres:
 262                         assert h.estado == 'comprometido'
 263                         print h.nombre, h.pareja.nombre
 264                 print
 265                 for m in self.s.mujeres:
 266                         assert m.estado == 'comprometido'
 267                         print m.nombre, m.pareja.nombre
 268
 269
 270
 271 if __name__ == '__main__':
 272         if len(sys.argv) != 2:
 273                 print "El primer parametro debe ser el archivo de entrada"
 274                 sys.exit(1)
 275
 276         s = Susanita_GS()
 277         p = Parser(s)
 278
 279         p.input(sys.argv[1])
 280         s.casamentear()
 281         p.output()
 282
 283