]> git.llucax.com Git - z.facultad/75.29/susanita.git/blob - test/susanita.py
da_distinto_bt_que_gs
[z.facultad/75.29/susanita.git] / 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