z.facultad/75.29/susanita.git
16 years agotagged entrega1 master darcs_import entrega1
Leandro Lucarella [Wed, 9 Nov 2005 16:08:29 +0000 (16:08 +0000)]
tagged entrega1

16 years agoBugfix (generador de código imprimible decía TP1).
Leandro Lucarella [Wed, 9 Nov 2005 16:07:45 +0000 (16:07 +0000)]
Bugfix (generador de código imprimible decía TP1).

16 years agoAgrega script para hacer imprimible al código.
Leandro Lucarella [Wed, 9 Nov 2005 16:02:58 +0000 (16:02 +0000)]
Agrega script para hacer imprimible al código.

16 years agoTermina informe.
Leandro Lucarella [Wed, 9 Nov 2005 15:58:26 +0000 (15:58 +0000)]
Termina informe.

16 years agoAcomodar un poco el código para hacerlo mas imprimible
Alberto Bertogli [Wed, 9 Nov 2005 15:55:13 +0000 (15:55 +0000)]
Acomodar un poco el código para hacerlo mas imprimible

16 years agoAcomodar comentarios acerca del orden del GS.
Alberto Bertogli [Wed, 9 Nov 2005 15:32:59 +0000 (15:32 +0000)]
Acomodar comentarios acerca del orden del GS.

16 years agoAgrega graficos bien y corrige/agrega analisis de orden de GS y BT.
Leandro Lucarella [Wed, 9 Nov 2005 07:10:58 +0000 (07:10 +0000)]
Agrega graficos bien y corrige/agrega analisis de orden de GS y BT.

16 years agoAgrega gráficos de orden y otras correcciones mínimas al informe.
Leandro Lucarella [Wed, 9 Nov 2005 05:02:38 +0000 (05:02 +0000)]
Agrega gráficos de orden y otras correcciones mínimas al informe.

16 years agoBugfix (estaba eligiendo a la persona menos preferida =)
Leandro Lucarella [Tue, 8 Nov 2005 18:40:27 +0000 (18:40 +0000)]
Bugfix (estaba eligiendo a la persona menos preferida =)

16 years agoConvierte informe a RTF sin comprimir.
Leandro Lucarella [Tue, 8 Nov 2005 03:16:56 +0000 (03:16 +0000)]
Convierte informe a RTF sin comprimir.
No sé si estaba comprimido o en algún formato binario raro, pero al estar en
"ASCII" el RTF es mucho más amistoso con el darcs y hasta incluso puede
sobrevivir a un merge.

16 years agoAgrega script para correr pruebas.
Leandro Lucarella [Tue, 8 Nov 2005 03:10:51 +0000 (03:10 +0000)]
Agrega script para correr pruebas.
Este parche agrega un script para correr pruebas fácilmente.
Uso: ./corridas.sh gs|bt [series] [hasta]
Ejecuta 'series' veces una tanda de pruebas que consiste en resolver archivos
generados aleatoriamente con 1 a 'hasta' parejas (N).

16 years agoCambia formato del comando ejecutable.
Leandro Lucarella [Tue, 8 Nov 2005 00:48:16 +0000 (00:48 +0000)]
Cambia formato del comando ejecutable.
Este parche hace que sea obligatorio especificar el algoritmo a usar y agrega
una opción para ejecutarlo silencioso (sólo devolviendo el tiempo que tardó)
para hacer pruebas más rápido. Nueva forma de uso:
./tdatp2 gs|bt archivo [-q]

16 years agoAgrega pruebas para la tabla hash y el heap.
Leandro Lucarella [Mon, 7 Nov 2005 17:53:44 +0000 (17:53 +0000)]
Agrega pruebas para la tabla hash y el heap.

16 years agoActualiza comentarios de orden.
Leandro Lucarella [Mon, 7 Nov 2005 07:50:11 +0000 (07:50 +0000)]
Actualiza comentarios de orden.

16 years agoAgrega cuanto tardó a la salida.
Leandro Lucarella [Mon, 7 Nov 2005 07:47:39 +0000 (07:47 +0000)]
Agrega cuanto tardó a la salida.
Esto lo hacía en algún momento, parece que alguien lo había pisado. Ahora la
salida es un poco más linda (aunque menos parser-friendly, pero nada grave).
Siempre el tiempo se escupe por stderr.

16 years agoUsa heap para las ofertas.
Leandro Lucarella [Mon, 7 Nov 2005 07:41:46 +0000 (07:41 +0000)]
Usa heap para las ofertas.
Este parche agrega 2 funciones básicas para manejo de heap (push y pop), basado
en las de la STL (pero son legibles =).
Con esto el GS está en el aclamado O(N^2)!

16 years agoCambia nombre del informe para que no denote una revisión en particular.
Leandro Lucarella [Mon, 7 Nov 2005 03:11:31 +0000 (03:11 +0000)]
Cambia nombre del informe para que no denote una revisión en particular.

16 years agoinforme_v0.01.rtf
Ezequiel [Mon, 7 Nov 2005 02:23:20 +0000 (02:23 +0000)]
informe_v0.01.rtf

16 years agoAcomodar susanita.py para usar el mismo formato de salida que el de C++.
Alberto Bertogli [Mon, 7 Nov 2005 02:53:45 +0000 (02:53 +0000)]
Acomodar susanita.py para usar el mismo formato de salida que el de C++.
En este punto, el GS de C++ y el de Python dan exactamente lo mismo para los
casos de prueba mas grandes. Eeeeeeeeeeeeeee =)

16 years agoEliminar printf() de debug en main().
Alberto Bertogli [Mon, 7 Nov 2005 02:48:41 +0000 (02:48 +0000)]
Eliminar printf() de debug en main().

16 years agoHacer que todos_h_comprometidos() sea O(1).
Alberto Bertogli [Mon, 7 Nov 2005 02:27:35 +0000 (02:27 +0000)]
Hacer que todos_h_comprometidos() sea O(1).
Usamos una variable propia del GS para contar la cantidad de hombres
comprometidos, y cuando esta alcanza a la capacidad, ya estamos.

16 years agoAgregar la capacidad como un atributo de Susanita.
Alberto Bertogli [Mon, 7 Nov 2005 02:25:51 +0000 (02:25 +0000)]
Agregar la capacidad como un atributo de Susanita.

16 years agoMover el cálculo del tamaño de la tabla a HashTable.
Alberto Bertogli [Mon, 7 Nov 2005 02:19:28 +0000 (02:19 +0000)]
Mover el cálculo del tamaño de la tabla a HashTable.
El cálculo de cuanto tiene que tener la tabla pertenece a la lógica de la
tabla y no al main().

Aparte esto nos sirve porque vamos a usar la capacidad en otros patches que
vienen, y es un problema tenerla multiplicada por 4.

16 years agoActualizar comentarios de los ordenes.
Alberto Bertogli [Mon, 7 Nov 2005 01:52:03 +0000 (01:52 +0000)]
Actualizar comentarios de los ordenes.
Dado que ahora el orden del sort y la comparacion mejoraron, cambiaron varios
ordenes en el GS.

16 years agoAgregar una tabla de hash para las preferencias.
Alberto Bertogli [Mon, 7 Nov 2005 01:14:12 +0000 (01:14 +0000)]
Agregar una tabla de hash para las preferencias.
Ademas de la lista de preferencias, agregar una tabla hash que relacione el
nombre de la persona con el numero de preferencia, arrancando de 0.

Esto nos permite comparar en O(1) y asi bajar significativamente los ordenes
de varios algoritmos.

En un patch subsecuente se actualizaran los comentarios con los ordenes donde
corresponda.

16 years agoIncluir cassert en backtracking.h
Alberto Bertogli [Mon, 7 Nov 2005 01:13:22 +0000 (01:13 +0000)]
Incluir cassert en backtracking.h

16 years agoAgregar método get() a HashTable.
Alberto Bertogli [Mon, 7 Nov 2005 01:07:35 +0000 (01:07 +0000)]
Agregar método get() a HashTable.
Este método es igual al operator[], solo que no agrega y es const (lo que nos
va a permitir usarlo dentro del comparador en el futuro).

16 years agoGuarda resultados del BT para hacer la salida igual que el GS.
Leandro Lucarella [Mon, 7 Nov 2005 00:10:51 +0000 (00:10 +0000)]
Guarda resultados del BT para hacer la salida igual que el GS.
Este parche hace que el BT guarde los resultados (las parejas) cuando encuentra
una solución, así al hacer el unwind puede volver a recuperarlo y hacer la
salida consistente con la del GS.

16 years agoParametriza hash.
Leandro Lucarella [Mon, 7 Nov 2005 00:07:20 +0000 (00:07 +0000)]
Parametriza hash.
Este parche parametriza el valor guardado en el hash (no así su clave).

16 years agoHacer que cmp devuelva int y no bool, como corresponde.
Alberto Bertogli [Sun, 6 Nov 2005 23:16:23 +0000 (23:16 +0000)]
Hacer que cmp devuelva int y no bool, como corresponde.

16 years agoHacer que Persona.rechazos sea una HashTable y no una deque.
Alberto Bertogli [Sun, 6 Nov 2005 22:39:20 +0000 (22:39 +0000)]
Hacer que Persona.rechazos sea una HashTable y no una deque.

Esto elimina el orden O(N) en partes de la nesima_ronda().

16 years agoGeneralizar HashTable para almacenar void * como valores.
Alberto Bertogli [Sun, 6 Nov 2005 22:36:24 +0000 (22:36 +0000)]
Generalizar HashTable para almacenar void * como valores.

Esto elimina la restriccion de usar personas para la tabla hash. El motivo es
que vamos a querer usar hashes _dentro_ de la clase persona, y sino tenemos
una referencia circular molesta. Aparte en el futuro podemos querer usarla
para almacenar otras cosas.

16 years agoEliminar pregunta-comentario que ya esta resuelto.
Alberto Bertogli [Sun, 6 Nov 2005 22:05:42 +0000 (22:05 +0000)]
Eliminar pregunta-comentario que ya esta resuelto.

16 years agoBugfix.
Leandro Lucarella [Sun, 6 Nov 2005 22:49:54 +0000 (22:49 +0000)]
Bugfix.

16 years agoMerge del BT con el timer.
Leandro Lucarella [Sun, 6 Nov 2005 21:32:13 +0000 (21:32 +0000)]
Merge del BT con el timer.

16 years agoda_distinto_bt_que_gs
Ezequiel [Sun, 6 Nov 2005 21:11:26 +0000 (21:11 +0000)]
da_distinto_bt_que_gs

16 years agofuentes_backtracking
Ezequiel [Sun, 6 Nov 2005 21:08:43 +0000 (21:08 +0000)]
fuentes_backtracking

16 years agocambios_para_backtracking
Ezequiel [Sun, 6 Nov 2005 21:06:01 +0000 (21:06 +0000)]
cambios_para_backtracking

16 years agoAgrega comentarios anotando el orden de cada función.
Leandro Lucarella [Sun, 6 Nov 2005 21:13:35 +0000 (21:13 +0000)]
Agrega comentarios anotando el orden de cada función.

16 years agoAgrega timer y muestra lo que tardó (en useg) por stderr.
Leandro Lucarella [Sun, 6 Nov 2005 21:13:25 +0000 (21:13 +0000)]
Agrega timer y muestra lo que tardó (en useg) por stderr.

16 years agoConvierte nombres de home del generador de pruebas a iso-8859-1
Leandro Lucarella [Fri, 4 Nov 2005 06:31:45 +0000 (06:31 +0000)]
Convierte nombres de home del generador de pruebas a iso-8859-1

16 years agoAgrega y usa tabla hash.
Leandro Lucarella [Fri, 4 Nov 2005 06:17:41 +0000 (06:17 +0000)]
Agrega y usa tabla hash.
Este parche agrega una tabla hash de hashing abierto _MUY_ simple, de tamaño
inmutable (elegido al construirla). Sólo se pueden obtener elementos del hash,
no eliminar (total la población de claves no cambia en todo el programa). En
fin, bien específica para este problema.
La implementación consiste en un vector donde cada elemento es una lista donde
cada elemento es una tupla (clave, valor). Si la lista está vacía, entonces esa
posición del hash está vacía, si tiene un elemento obtenerlo es O(1) y si tiene
más (colisión) es O(colision) (no está ordenada ni nada porque podemos
garantizar MUY fácil que casi no haya colisiones dandole una capacidad apropiada
a la tabla hash).
Como para construir la tabla de hash necesitamos saber la cardinalidad de la
población de antemano, hice un hack medio feo pero útil que lee la 1ra línea del
archivo y cuenta la cantidad de nombres en la lista de preferencias de la 1ra
persona, con eso basta para obtener el N del problema. La tabla de hash la crea
con capacidad N * 2 (así tiene un factor de ocupación de 50% como decían en la
práctica).
Por último, uso el hash para Susanita::nombres, cosa que no sé si es del todo
útil (se usa sólo en el parser, calculo que para que el algoritmo sea O(N^2)
deberíamos usar el hash en la resolución). Pero bueno, tenía que ponerlo en
algún lado para probarlo =)

16 years agoImplementa destructor de susanita.
Leandro Lucarella [Thu, 3 Nov 2005 16:25:41 +0000 (16:25 +0000)]
Implementa destructor de susanita.
Ahora libera toda la memoria, así nadie nos puede molestar por esto ;)

16 years agoAgregar el generador de testcases y dos listas con nombres mexicanos.
Alberto Bertogli [Thu, 3 Nov 2005 07:20:04 +0000 (07:20 +0000)]
Agregar el generador de testcases y dos listas con nombres mexicanos.

16 years agoMisma correccion de comprometer_con(), pero para la version en Python.
Alberto Bertogli [Thu, 3 Nov 2005 07:18:57 +0000 (07:18 +0000)]
Misma correccion de comprometer_con(), pero para la version en Python.

16 years agoAcomodar rechazos en comprometer_con().
Alberto Bertogli [Thu, 3 Nov 2005 07:14:54 +0000 (07:14 +0000)]
Acomodar rechazos en comprometer_con().

Hoy estamos agregando a la persona con quien nos comprometemos a la lista de
rechazos de nuestros pretendientes. Esto esta mal.

Nosotros deberiamos agregarnos a la lista de gente que rechazo a cada uno de
nuestros pretendientes, porque precisamente los estamos rebotando.

16 years agoArregla _el_ bug.
Leandro Lucarella [Thu, 3 Nov 2005 07:07:30 +0000 (07:07 +0000)]
Arregla _el_ bug.
Muere maldito! Muere!!!!

16 years agoAgregar el listado de prioridades a mostrar_estado().
Alberto Bertogli [Thu, 3 Nov 2005 06:42:42 +0000 (06:42 +0000)]
Agregar el listado de prioridades a mostrar_estado().

16 years agoSaltar los nombres vacios.
Alberto Bertogli [Thu, 3 Nov 2005 06:32:55 +0000 (06:32 +0000)]
Saltar los nombres vacios.

16 years agoMover el mostrar_estado() mas arriba para que no sea protected.
Alberto Bertogli [Thu, 3 Nov 2005 06:29:12 +0000 (06:29 +0000)]
Mover el mostrar_estado() mas arriba para que no sea protected.

16 years agoMover mostrar_estado() de GaleShapley a Susanita.
Alberto Bertogli [Thu, 3 Nov 2005 05:37:45 +0000 (05:37 +0000)]
Mover mostrar_estado() de GaleShapley a Susanita.

16 years agoCorregir el strip()
Alberto Bertogli [Thu, 3 Nov 2005 05:29:18 +0000 (05:29 +0000)]
Corregir el strip()

16 years agoVersión inicial portada desde python (no funciona).
Leandro Lucarella [Thu, 3 Nov 2005 05:16:27 +0000 (05:16 +0000)]
Versión inicial portada desde python (no funciona).
Esta es la versión inicial portada desde python. Tiene algunos problemas y muere
en un loop infinito, pero para poder arreglarlo sincronizadamente optamos por
subirlo al repo en este estado.
En test/ están los ejemplos de prueba y el programa en python que anda.