From a86e26ae42584c979262de7f6ddefa815ac7c625 Mon Sep 17 00:00:00 2001 From: Leandro Lucarella Date: Thu, 3 Nov 2005 05:16:27 +0000 Subject: [PATCH] =?utf8?q?Versi=C3=B3n=20inicial=20portada=20desde=20pytho?= =?utf8?q?n=20(no=20funciona).=20Esta=20es=20la=20versi=C3=B3n=20inicial?= =?utf8?q?=20portada=20desde=20python.=20Tiene=20algunos=20problemas=20y?= =?utf8?q?=20muere=20en=20un=20loop=20infinito,=20pero=20para=20poder=20ar?= =?utf8?q?reglarlo=20sincronizadamente=20optamos=20por=20subirlo=20al=20re?= =?utf8?q?po=20en=20este=20estado.=20En=20test/=20est=C3=A1n=20los=20ejemp?= =?utf8?q?los=20de=20prueba=20y=20el=20programa=20en=20python=20que=20anda?= =?utf8?q?.?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit --- src/Makefile | 39 ++++++ src/galeshapley.cpp | 131 ++++++++++++++++++++ src/galeshapley.h | 52 ++++++++ src/main.cpp | 25 ++++ src/parser.cpp | 104 ++++++++++++++++ src/parser.h | 27 +++++ src/persona.cpp | 143 ++++++++++++++++++++++ src/persona.h | 68 +++++++++++ src/susanita.cpp | 39 ++++++ src/susanita.h | 43 +++++++ test/sample1 | 9 ++ test/sample2 | 7 ++ test/susanita.py | 283 ++++++++++++++++++++++++++++++++++++++++++++ 13 files changed, 970 insertions(+) create mode 100644 src/Makefile create mode 100644 src/galeshapley.cpp create mode 100644 src/galeshapley.h create mode 100644 src/main.cpp create mode 100644 src/parser.cpp create mode 100644 src/parser.h create mode 100644 src/persona.cpp create mode 100644 src/persona.h create mode 100644 src/susanita.cpp create mode 100644 src/susanita.h create mode 100644 test/sample1 create mode 100644 test/sample2 create mode 100644 test/susanita.py diff --git a/src/Makefile b/src/Makefile new file mode 100644 index 0000000..d31fe56 --- /dev/null +++ b/src/Makefile @@ -0,0 +1,39 @@ + +# Opciones para el compilador C++. +CXXFLAGS = -Wall -ansi -pedantic + +ifdef DEBUG +CXXFLAGS += -ggdb -DDEBUG -fno-inline +else +CXXFLAGS += -O2 -DNDEBUG +endif + +target = tdatp2 + +objetos = persona.o susanita.o galeshapley.o parser.o main.o + +all: $(target) + +persona.o: persona.cpp persona.h + +susanita.o: susanita.cpp susanita.h persona.h + +galeshapley.o: galeshapley.cpp galeshapley.h susanita.h persona.h + +parser.o: parser.cpp parser.h persona.h susanita.h + +main.o: main.cpp parser.h susanita.h galeshapley.h + +$(target): $(objetos) + $(CXX) $(LDFLAGS) $(objetos) $(LOADLIBES) $(LDLIBS) -o $(target) + +#main.o: number.h + +# REGLAS +######### + +.PHONY: clean + +clean: + @$(RM) -fv $(objetos) $(target) + diff --git a/src/galeshapley.cpp b/src/galeshapley.cpp new file mode 100644 index 0000000..d76bb1b --- /dev/null +++ b/src/galeshapley.cpp @@ -0,0 +1,131 @@ +#include "galeshapley.h" +#include +#include +#include +#include +#include +#include + +GaleShapley:: +GaleShapley() +{ +} + +void +GaleShapley:: +primera_ronda() +{ + for (personas_type::iterator ih = hombres.begin(); + ih != hombres.end(); ++ih) + { + (*ih)->declarar_a(*((*ih)->prefs[0])); + } + for (personas_type::iterator im = mujeres.begin(); + im != mujeres.end(); ++im) + { + Persona& m = **im; + if (m.ofertas.empty()) + continue; + m.ordenar_ofertas(); + m.comprometer_con(*(m.ofertas.front())); + m.ofertas.pop_front(); + } +} + +void +GaleShapley:: +nesima_ronda() +{ + for (personas_type::iterator ih = hombres.begin(); + ih != hombres.end(); ++ih) + { + Persona& h = **ih; + if (h.estado == Persona::COMPROMETIDO) + continue; + + Persona* pm = 0; + for (personas_type::iterator im = h.prefs.begin(); + im != h.prefs.end(); ++im) + { + pm = *im; + if (std::find(h.rechazos.begin(), h.rechazos.end(), pm) + != h.rechazos.end()) // Si está + continue; + break; + } + assert(pm); + h.declarar_a(*pm); + } + + for (personas_type::iterator im = mujeres.begin(); + im != mujeres.end(); ++im) + { + Persona& m = **im; + if (m.ofertas.empty()) + continue; + + m.ordenar_ofertas(); + Persona* ph = m.ofertas.front(); + m.ofertas.pop_front(); + if (m.estado == Persona::COMPROMETIDO) + { + if (m.cmp(*(m.pareja), *ph) < 0) + { + // la oferta es mejor, rompemos el compromiso + m.comprometer_con(*ph); + } + else + { + // estamos mejor con nuestra pareja actual, asi + // que no hacemos mas que rechazar a todos + // (incluyendo el mejor candidato) + for (Persona::ofertas_type::iterator i + = m.ofertas.begin(); + i != m.ofertas.end(); ++i) + (*i)->rechazos.push_back(&m); + ph->rechazos.push_back(&m); + m.ofertas.clear(); + } + } + else + { + m.comprometer_con(*ph); + } + } +} + +bool +GaleShapley:: +todos_h_comprometidos() const +{ + // FIXME: podemos ver de poner esto adentro de nesima_ronda() + for (personas_type::const_iterator ih = hombres.begin(); + ih != hombres.end(); ++ih) + if ((*ih)->estado != Persona::COMPROMETIDO) + return false; + return true; +} + +void +GaleShapley:: +mostrar_estado() const +{ + for (personas_type::const_iterator ih = hombres.begin(); + ih != hombres.end(); ++ih) + std::cout << **ih << "\n"; + std::cout << "\n"; + for (personas_type::const_iterator im = mujeres.begin(); + im != mujeres.end(); ++im) + std::cout << **im << "\n"; + std::cout << "\n" << std::endl; +} + +void +GaleShapley:: +casamentear() +{ + primera_ronda(); + while (!todos_h_comprometidos()) + nesima_ronda(); +} + diff --git a/src/galeshapley.h b/src/galeshapley.h new file mode 100644 index 0000000..f80b1b0 --- /dev/null +++ b/src/galeshapley.h @@ -0,0 +1,52 @@ +#ifndef _GALESHAPLEY_H_ +#define _GALESHAPLEY_H_ + +#include "persona.h" +#include "susanita.h" +#include +#include +#include + +struct GaleShapley: Susanita +{ + + /// Constructor + GaleShapley(); + + /// Empieza a emparejar gente + void casamentear(); + + private: + + /** + * 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 él. Si una + * mujer no recibe ninguna propuesta, espera hasta la proxima ronda. + */ + void primera_ronda(); + + /** + * 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. + */ + void nesima_ronda(); + + /// Se fija si todos los hombres estan comprometidos + bool todos_h_comprometidos() const; + + /// Muestra estados + void mostrar_estado() const; + +}; + +#endif // _GALESHAPLEY_H_ diff --git a/src/main.cpp b/src/main.cpp new file mode 100644 index 0000000..7376740 --- /dev/null +++ b/src/main.cpp @@ -0,0 +1,25 @@ +#include "galeshapley.h" +#include "parser.h" +#include + +int main(int argc, char* argv[]) +{ + if (argc != 2) + { + std::cerr << "Uso: " << argv[0] << " [archivo_entrada]\n"; + return 1; + } + + GaleShapley gs; + Parser p(gs); + + if (!p.input(argv[1])) + { + std::cerr << "Error al abrir el archivo '" << argv[1] << "'\n"; + return 2; + } + gs.casamentear(); + p.output(); +} + + diff --git a/src/parser.cpp b/src/parser.cpp new file mode 100644 index 0000000..f15b9c7 --- /dev/null +++ b/src/parser.cpp @@ -0,0 +1,104 @@ +#include "parser.h" +#include +#include +#include +#include +#include +#include + +Parser:: +Parser(Susanita& s): + susanita(s) +{ +} + +// Para no exportar los símbolos (uso interno de este módulo) +namespace +{ + /// Saca espacios de una palabra + std::string strip(std::string s) + { + std::istringstream ss(s); + ss >> s; + return s; + } + + /// Devuelve palabra hasta el caracter indicado + std::string get_hasta(std::istream& is, char hasta) + { + std::string s; + std::getline(is, s, hasta); + return strip(s); + } +} + +bool +Parser:: +input(const std::string& filename) +{ + std::ifstream f(filename.c_str()); + if (!f) + return false; + Persona::sexo_type sexo = Persona::M; + Persona::sexo_type opuesto = Persona::F; + std::string l; + while (std::getline(f, l)) + { + l = strip(l); + // la linea vacia alterna de sexo + if (l.empty()) + { + sexo = Persona::F; + opuesto = Persona::M; + continue; + } + + // obtenemos el nombre y la lista + std::istringstream ss(l); + std::string nombre = get_hasta(ss, ':'); + Persona* pp = susanita.get_persona(nombre); + if (!pp) + { + pp = new Persona(nombre, sexo); + susanita.add_persona(pp); + } + + Persona::prefs_type prefs; + while (ss) + { + std::string nombre = get_hasta(ss, ','); + Persona* ppp = susanita.get_persona(nombre); + if (!ppp) + { + ppp = new Persona(nombre, opuesto); + susanita.add_persona(ppp); + } + pp->prefs.push_back(ppp); + } + } + return true; +} + +void +Parser:: +output() const +{ + for (Susanita::personas_type::const_iterator ih + = susanita.hombres.begin(); + ih != susanita.hombres.end(); ++ih) + { + Persona& h = **ih; + assert(h.estado == Persona::COMPROMETIDO); + std::cout << h.nombre << ", " << h.pareja->nombre << "\n"; + } + std::cout << "\n"; + for (Susanita::personas_type::const_iterator im + = susanita.mujeres.begin(); + im != susanita.mujeres.end(); ++im) + { + Persona& m = **im; + assert(m.estado == Persona::COMPROMETIDO); + std::cout << m.nombre << ", " << m.pareja->nombre << "\n"; + } +} + diff --git a/src/parser.h b/src/parser.h new file mode 100644 index 0000000..984ac78 --- /dev/null +++ b/src/parser.h @@ -0,0 +1,27 @@ +#ifndef _PARSER_H_ +#define _PARSER_H_ + +#include "persona.h" +#include "susanita.h" +#include + +struct Parser +{ + + /// Constructor + Parser(Susanita& s); + + /// Obtiene la entrada cargando a nuestra casamentera + bool input(const std::string& filename); + + /// Genera la salida de nuestros casamientos + void output() const; + + private: + + /// Nuestro objeto casamentero + Susanita& susanita; + +}; + +#endif // _PARSER_H_ diff --git a/src/persona.cpp b/src/persona.cpp new file mode 100644 index 0000000..ca121a4 --- /dev/null +++ b/src/persona.cpp @@ -0,0 +1,143 @@ +#include "persona.h" +#include +#include + +/// Constructor +Persona:: +Persona(const std::string& nombre, sexo_type sexo): + nombre(nombre), estado(SOLTERO), sexo(sexo), pareja(0) +{ +} + +/// Para representación +std::ostream& +operator<< (std::ostream& os, const Persona::estado_type e) +{ + switch (e) + { + case Persona::SOLTERO: + return os << "soltero"; + case Persona::DECLARADO: + return os << "declarado"; + case Persona::COMPROMETIDO: + return os << "comprometido"; + default: + assert("Estado de la persona desconocido"); + return os << "desconocido"; + } +} + +/// Para representación +std::ostream& +operator<< (std::ostream& os, const Persona::sexo_type s) +{ + switch (s) + { + case Persona::M: + return os << "M"; + case Persona::F: + return os << "F"; + default: + assert("Sexo de la persona desconocido"); + return os << "desconocido"; + } +} + +/// Para representación +std::ostream& +operator<< (std::ostream& os, const Persona& p) +{ + std::string pareja = "-"; + if (p.pareja) + { + pareja = p.pareja->nombre; + } + os << "<" << p.nombre << " (" << p.sexo << "): " << p.estado << " - " + << pareja << ">"; + return os; +} + +/// Función de comparación entre dos personas según nuestras preferencias +bool +Persona:: +cmp(const Persona& p1, const Persona& p2) const +{ + prefs_type::const_iterator pos_p1 + = std::find(prefs.begin(), prefs.end(), &p1); + prefs_type::const_iterator pos_p2 + = std::find(prefs.begin(), prefs.end(), &p2); + if (pos_p1 < pos_p2) + return 1; + if (pos_p1 == pos_p2) + return 0; + return -1; +} + +// Para que no se exporte el símbolo, es de uso interno de este módulo +namespace +{ + /// Functor de ordenamiento auxiliar + struct PersonaCmp + { + Persona& p; + PersonaCmp(Persona& p): p(p) {} + /// devuelve true si p1 < p2 + bool operator ()(const Persona* const p1, const Persona* const p2) + { + return p.cmp(*p1, *p2) < 0; + } + }; +} + +/// Ordenamos las ofertas segun nuestras preferencias +void +Persona:: +ordenar_ofertas() +{ + // este sort es in-place y O(N.log(N)) + // Más info en: http://www.sgi.com/tech/stl/sort.html + std::sort(ofertas.begin(), ofertas.end(), PersonaCmp(*this)); +} + +/// Nos declaramos a la persona p +void +Persona:: +declarar_a(Persona& p) +{ + estado = DECLARADO; + pareja = &p; + p.ofertas.push_back(this); +} + +/// Nos comprometemos con la persona p, quien se nos habia declarado previamente +void +Persona:: +comprometer_con(Persona& p) +{ + assert(p.estado == DECLARADO); + assert(p.pareja == this); + + // rompemos el compromiso, si hay + if (estado == COMPROMETIDO) + { + assert(pareja != 0); + pareja->estado = SOLTERO; + pareja->pareja = 0; + pareja->rechazos.push_back(&p); + } + + // nos comprometemos + estado = COMPROMETIDO; + pareja = &p; + p.estado = COMPROMETIDO; + p.pareja = this; + + // si tenemos ofertas, las rechazamos + for (ofertas_type::iterator pretendiente = ofertas.begin(); + pretendiente != ofertas.end(); ++pretendiente) + { + (*pretendiente)->rechazos.push_back(&p); + } + ofertas.clear(); +} + diff --git a/src/persona.h b/src/persona.h new file mode 100644 index 0000000..925cdff --- /dev/null +++ b/src/persona.h @@ -0,0 +1,68 @@ +#ifndef _PERSONA_H_ +#define _PERSONA_H_ + +#include +#include +#include +#include + +struct Persona +{ + /// Tipos de listas + typedef std::deque< Persona* > prefs_type; + typedef std::deque< Persona* > ofertas_type; + typedef std::deque< Persona* > rechazos_type; + + /// Estados posibles de una persona + enum estado_type { SOLTERO, DECLARADO, COMPROMETIDO }; + + /// Sexo + enum sexo_type { M, F }; + + /// Constructor + Persona(const std::string& nombre, sexo_type sexo); + + /// Nombre de la persona, sólo con fines de representación + std::string nombre; + + /// Lista de personas que prefiere, la primera de la lista es la + /// que mejor posicionada esta + prefs_type prefs; + + /// Estado de la persona + estado_type estado; + + /// Sexo + sexo_type sexo; + + /// De estar declarado o comprometido, quien es su pareja + Persona* pareja; + + /// Lista de la gente que se le declaro + ofertas_type ofertas; + + /// Lista de la gente que lo rechazo + rechazos_type rechazos; + + /// Función de comparación entre dos personas según nuestras prefs + bool cmp(const Persona& p1, const Persona& p2) const; + + /// Ordenamos las ofertas según nuestras preferencias + void ordenar_ofertas(); + + /// Nos declaramos a la persona p + void declarar_a(Persona& p); + + /// Nos comprometemos con la persona p, quien se nos habia declarado + /// previamente + void comprometer_con(Persona& p); + +}; + +/// Para representación +std::ostream& operator<< (std::ostream& os, const Persona::estado_type e); + +/// Para representación +std::ostream& operator<< (std::ostream& os, const Persona& p); + +#endif // _PERSONA_H_ diff --git a/src/susanita.cpp b/src/susanita.cpp new file mode 100644 index 0000000..12cba02 --- /dev/null +++ b/src/susanita.cpp @@ -0,0 +1,39 @@ +#include "susanita.h" +#include + +Susanita::~Susanita() +{ +} + +void +Susanita:: +add_persona(Persona* pp) +{ + // XXX cual sería el problema que agregue una persona repetida? + // Reemplazaría a la anterior nomás + assert(nombres.find(pp->nombre) == nombres.end()); + + nombres[pp->nombre] = pp; + switch (pp->sexo) + { + case Persona::M: + hombres.push_back(pp); + break; + case Persona::F: + mujeres.push_back(pp); + break; + default: + assert("Una persona no es ni mujer ni hombre!"); + } +} + +Persona* +Susanita:: +get_persona(const std::string& nombre) const +{ + nombres_type::const_iterator ip = nombres.find(nombre); + if (ip == nombres.end()) // No está + return 0; + return ip->second; +} + diff --git a/src/susanita.h b/src/susanita.h new file mode 100644 index 0000000..85bc8ba --- /dev/null +++ b/src/susanita.h @@ -0,0 +1,43 @@ +#ifndef _SUSANITA_H_ +#define _SUSANITA_H_ + +#include "persona.h" +#include +#include +#include + +/// Interfaz para nuestra clases casamenteras +struct Susanita +{ + + /// Tipos + typedef std::deque< Persona* > personas_type; + + /// Destructor + virtual ~Susanita(); + + /// Agrega persona + virtual void add_persona(Persona* p); + + /// Obtiene una persona + virtual Persona* get_persona(const std::string& p) const; + + /// Empieza a emparejar gente + virtual void casamentear() = 0; + + /// Lista de hombres + personas_type hombres; + + /// Lista de mujeres + personas_type mujeres; + + protected: + /// Tipos + typedef std::map< std::string, Persona* > nombres_type; + + /// Mapa de gente, relaciona nombres con objetos + nombres_type nombres; + +}; + +#endif // _SUSANITA_H_ diff --git a/test/sample1 b/test/sample1 new file mode 100644 index 0000000..51e55ac --- /dev/null +++ b/test/sample1 @@ -0,0 +1,9 @@ +Alberto: Ana,Betina,Carla,Dalma +Bato: Dalma,Carla,Betina,Ana +Carlos: Dalma,Carla,Betina,Ana +Demian: Betina,Ana,Carla,Dalma + +Ana: Alberto,Carlos,Bato,Demian +Betina: Demian,Bato,Carlos,Alberto +Carla: Alberto,Demian,Bato,Carlos +Dalma: Carlos,Demian,Alberto,Bato diff --git a/test/sample2 b/test/sample2 new file mode 100644 index 0000000..5fc587e --- /dev/null +++ b/test/sample2 @@ -0,0 +1,7 @@ +Juan: Sofia,Carla,Lucia +Jose: Carla,Sofia,Lucia +Luis: Lucia,Carla,Sofia + +Sofia: Juan,Jose,Luis +Carla: Jose,Juan,Luis +Lucia: Luis,Jose,Juan diff --git a/test/susanita.py b/test/susanita.py new file mode 100644 index 0000000..afe3c4a --- /dev/null +++ b/test/susanita.py @@ -0,0 +1,283 @@ +#!/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() + + -- 2.43.0