[pyar] Ordenar horarios - Ejercicio Python

[Juan Rodríguez Monti]

El otro día - hace un tiempo - revisando los mails que no habia leido de la lista ví uno en donde un listero contaba un ejercicio que tomaban en un trabajo en las entrevistas. Me pareció interesante. En especial alguna de las respuestas de algunos listeros. Algunos códigos eran geniales.

Ahora yo voy a hacer lo mismo. Un amigo me contó que toma el siguiente ejercicio para desarrollar en Python ( no me pareció tan simple ) cuando recluta programadores.

Es bastante sencillo, pero para alguien que recién empieza puede ser medio bravo. Lo planteo para ver cómo lo armarian ustedes, y para que compartan su sapiencia con Python.

El ejercicio: Se debe escribir una aplicación en python que permita ingresar por teclado los horarios de cursada disponibles para un alumno ( Esto significa que la Universidad ofrece n horarios posibles; por ejemplo: hay 3 horarios de matemática disponibles con sus día y hora respectivos, 2 de algebra, 5 de programación, etc ), y que dicho programa procese la entrada de datos e imprima en la pantalla todas las posibles combinaciones de horarios de cursada en base a esa entrada.

Ejemplo de horario:

Matemática I - Lunes de 15 a 17 - Miércoles de 20 a 21 - Viernes de 16 a 18.
Algebra II - Martes de 15 a 19
Algoritmos III - Martes de 14 a 18 - Miércoles de 16 a 19

En base a toda la entrada de datos, en donde habrá horarios que se superponen por coincidir parcial o totalmente en hora o día, el sistema deberá construir e imprimir opciones de horarios para que el alumno elija cúal es la ideal para el. Es decir, en base a las n opciones de cursada que se ingresan, el sistema deberá mostrar por pantalla opciones para que el alumno utilice. em donde ninguna materia se superponga con otra, y contemplando que sea posible cursar la mayor cantidad de materias posibles.

Dato aclaratorio: Se ingresará nombre de materia, cantidad de días que se cursa ( generalmente 2, pero pueden ser más ), y horarios. Ayuda: Puede ser de ayuda pedirle al usuario que ingrese por cada día que se cursa hora de inicio y fin de la cursada.

Plus: Si se diseña un algoritmo que optimice las opciones. Es decir, si se determina un criterio a través del cual es mejor cursar 4 hs lunes y 4 hs martes, en lugar de cursar 8 horas un único día. O aquí se puede implementar la optimización que se deseé.

Si les interesa posteen su código que siempre es un placer leerlos.

Un saludo,
Juan

[Gonzalo Sainz Trápaga]

Hola,

2010/7/7 Juan Rodríguez Monti <juanrodri...@gmail.com>:

> Si les interesa posteen su código que siempre es un placer leerlos.

http://blog.gomox.com.ar/2009/02/se-me-pisan-los-horarios.html

Algo así :P
No tiene pretensiones de performance, si estuviera haciendo una
entrevista de laburo y no aprovechando la excusa para escribir sobre
teoría de grafos, trataría de lucirme un poquito más :)

Saludos,

Gonzalo
_______________________________________________
pyar mailing list py...@python.org.ar
http://listas.python.org.ar/listinfo/pyar

PyAr - Python Argentina - Sitio web: http://www.python.org.ar/

[Juan Rodríguez Monti]

El 7 de julio de 2010 12:04, Gonzalo Sainz Trápaga <gomox.ar@gmail.com> escribió:

Hola,

2010/7/7 Juan Rodríguez Monti <juanrodri...@gmail.com>:

> Si les interesa posteen su código que siempre es un placer leerlos.

http://blog.gomox.com.ar/2009/02/se-me-pisan-los-horarios.html

Algo así :P

Muy bueno Gonzalo!. Ahora lo voy a mirar con detenimiento.
 

No tiene pretensiones de performance, si estuviera haciendo una
entrevista de laburo y no aprovechando la excusa para escribir sobre
teoría de grafos, trataría de lucirme un poquito más :)

:) . Es interesante lo que menciona el ejercicio sobre el "plus", y ahí como que le dá lugar al entrevistado a lucirse aún más mejorando la performance o teniendo en cuenta otras cosas que sumen.
 

Saludos,

Gonzalo

Saludos,
Juan

[Juan Pedro Fisanotti]

2010/7/7 Juan Rodríguez Monti <juanrodri...@gmail.com>:

Es un lindo problema para resolver con los métodos de búsqueda de
inteligencia artificial :)
Recomiendo ver en AIMA (Artificial Inteligence, a Modern Approach) la
parte de técnicas para resolver problemas de búsqueda. En especial
porque todo el código de AIMA está implementado en python (
http://code.google.com/p/aima-python/ ), por el mismo Norvig, jeje.

--
fisa - Juan Pedro Fisanotti

[Juan Rodríguez Monti]

Viste, es un lindo problema. Hace tiempo un amigo lo habia implementado en C++. Por eso después yo lo planteé en Python, y bueno después lo pasé a la lista.
 

Recomiendo ver en AIMA (Artificial Inteligence, a Modern Approach) la
parte de técnicas para resolver problemas de búsqueda. En especial
porque todo el código de AIMA está implementado en python (
http://code.google.com/p/aima-python/ ), por el mismo Norvig, jeje.

Buen aporte.

Saludos,
Juan

[Roberto Alsina]

On Wednesday 07 July 2010 12:22:00 Juan Pedro Fisanotti wrote:
> Es un lindo problema para resolver con los métodos de búsqueda de
> inteligencia artificial :)

Pero da para resolverlo exhaustivamente tambien. O sea, no son taaaaaaantas
las combinaciones posibles tampoco (o el ojímetro me falla?)

[Juan Pedro Fisanotti]

El día 7 de julio de 2010 12:29, Roberto Alsina
<ral...@netmanagers.com.ar> escribió:

> On Wednesday 07 July 2010 12:22:00 Juan Pedro Fisanotti wrote:
>> Es un lindo problema para resolver con los métodos de búsqueda de
>> inteligencia artificial :)
>
> Pero da para resolverlo exhaustivamente tambien. O sea, no son taaaaaaantas
> las combinaciones posibles tampoco (o el ojímetro me falla?)

Depende de cuantos datos te cargue, jeje.
Si tiene unas 10 materias que se pueden cursar en 5 horarios distintos
cada una (nada del otro mundo), son unas 9765625 posibilidades :)

--
fisa - Juan Pedro Fisanotti

[Claudio Freire]

2010/7/7 Juan Pedro Fisanotti <fis...@gmail.com>

El día 7 de julio de 2010 12:29, Roberto Alsina
<ral...@netmanagers.com.ar> escribió:

> On Wednesday 07 July 2010 12:22:00 Juan Pedro Fisanotti wrote:
>> Es un lindo problema para resolver con los métodos de búsqueda de
>> inteligencia artificial :)
>
> Pero da para resolverlo exhaustivamente tambien. O sea, no son taaaaaaantas
> las combinaciones posibles tampoco (o el ojímetro me falla?)

Depende de cuantos datos te cargue, jeje.
Si tiene unas 10 materias que se pueden cursar en 5 horarios distintos
cada una (nada del otro mundo), son unas 9765625 posibilidades :)

En realidad no. Si podás combinaciones inválidas (ej: si dos materias cualquiera están superpuestas no necesitás explorar la rama), son menos. No se cuántas menos - potencialmente 9765625 en un caso muy bizarro (ej: es imposible superponer).

Y python es suficientemente rápido como para procesar 9765625 combinaciones en un santiamén.

[Ricardo Daniel Quiroga]

2010/7/7 Juan Rodríguez Monti <juanrodri...@gmail.com>

El otro día - hace un tiempo - revisando los mails que no habia leido de la lista ví uno en donde un listero contaba un ejercicio que tomaban en un trabajo en las entrevistas. Me pareció interesante. En especial alguna de las respuestas de algunos listeros. Algunos códigos eran geniales.

_______________________________________________
pyar mailing list py...@python.org.ar
http://listas.python.org.ar/listinfo/pyar

PyAr - Python Argentina - Sitio web: http://www.python.org.ar/

-- hola
eso parece mas algo que tenga que resolverse mediante un modelo de Programacion Lineal....

saludos

---------------------------------------------------------
        Wyrven no L2Radamanthys
          Ricardo Daniel Quiroga
---------------------------------------------------------
  msn:
         l2rada...@gmail.com
         ricard...@hotmail.com
  mails:
          l2rada...@gmail.com
          l2rada...@saltalug.org.ar
          ricardoqu...@gmail.com
          ricardo...@aprenderpython.com
  sitio Web:
         http://www.l2radamanthys.com.ar
  Facebook:
         http://es-la.facebook.com/L2Radamanthys
  Twitter:
        @l2Radamanthys

---------------------------------------------------------

[Ricardo Daniel Quiroga]

Opcionalmente se puede resolver mediante el algoritmo Hungaro, que es para resolver ese tipo de problemas...

[Hernan Olivera]

En mi facultad un alumno quiso hacer un programa similar para una escuela, y descubrió que aunque optimizara el código nunca llegaba a dar resultados. De ahi, terminó en una tesis de grado, en el cual este problema denominado timetable se resuelve con un sat-solver, previa reescritura en lógica proposicional. Parece trivial, pero no lo es.

saludos

2010/7/7 Ricardo Daniel Quiroga <l2rada...@gmail.com>

--
Hernan Olivera

[Sebastian Bassi]

2010/7/7 Claudio Freire <klauss...@gmail.com>:

> Y python es suficientemente rápido como para procesar 9765625 combinaciones
> en un santiamén.

Seguro, pero es "fuerza bruta", no te sirve para demostrar muchos
conocimientos (pensando que el problema no es solo para ser resuelto,
sino para evaluar la manera de resolverlo).

[Claudio Freire]

2010/7/7 Sebastian Bassi <sba...@clubdelarazon.org>

2010/7/7 Claudio Freire <klauss...@gmail.com>:

> Y python es suficientemente rápido como para procesar 9765625 combinaciones
> en un santiamén.

Seguro, pero es "fuerza bruta", no te sirve para demostrar muchos
conocimientos (pensando que el problema no es solo para ser resuelto,
sino para evaluar la manera de resolverlo).

Backtracking con poda y orden heurístico no es fuerza bruta.

Furza bruta es:


def cartesian(collections):
    if len(collections) == 0:
        raise StopIteration
    elif len(collections) == 1:
        for item in collections[0]:
            yield (item,)
    else:
        for item in collections[0]:
            for stuple in cartesian(*collections[1:]):
                yield (item,) + stuple

def superponen(horarios):
   ...

for horarios in cartesian([ horarios[m] for m in materias ]):
    if not superponen(horarios):
        print horarios



Backtracking con poda es... fuerza informada?

;-)

[Roberto Alsina]

On Wednesday 07 July 2010 13:20:54 Sebastian Bassi wrote:
> 2010/7/7 Claudio Freire <klauss...@gmail.com>:
> > Y python es suficientemente rápido como para procesar 9765625
> > combinaciones en un santiamén.
>
> Seguro, pero es "fuerza bruta", no te sirve para demostrar muchos
> conocimientos (pensando que el problema no es solo para ser resuelto,
> sino para evaluar la manera de resolverlo).

Depende si estás contratando para ingeniería o para ciencia de la computación.
Si se resuelve con fuerza bruta más fácil, entonces la fuerza bruta es lo
correcto, porque te garantiza un resultado óptimo global.

Distinguir cuando la solución pasa por la dinamita es un talento.

[SAn]

2010/7/7 Roberto Alsina <ral...@netmanagers.com.ar>:
[...]

> Distinguir cuando la solución pasa por la dinamita es un talento.

como el chiste del ing. que cobra 5001 pesos por un trabajo
y el cliente indignado le dice
-- pero cómo puede ser!, si solo le diste un martillazo!.
y el ing responde
-- por eso, 1 peso por el martillazo y 5 mil por saber donde pegarle.

perdon for el OT
SAn

[Juan Pedro Fisanotti]

2010/7/7 Claudio Freire <klauss...@gmail.com>:

Pero precisamente backtracking es uno de los algoritmos que está en
AIMA, o sea, de los que yo proponía...
No necesariamente había que irse a los no informados.

--
fisa - Juan Pedro Fisanotti

[Juan Rodríguez Monti]

El 7 de julio de 2010 12:43, Juan Pedro Fisanotti <fis...@gmail.com> escribió:

El día 7 de julio de 2010 12:29, Roberto Alsina
<ral...@netmanagers.com.ar> escribió:

> On Wednesday 07 July 2010 12:22:00 Juan Pedro Fisanotti wrote:
>> Es un lindo problema para resolver con los métodos de búsqueda de
>> inteligencia artificial :)
>
> Pero da para resolverlo exhaustivamente tambien. O sea, no son taaaaaaantas
> las combinaciones posibles tampoco (o el ojímetro me falla?)

Depende de cuantos datos te cargue, jeje.
Si tiene unas 10 materias que se pueden cursar en 5 horarios distintos
cada una (nada del otro mundo), son unas 9765625 posibilidades :)

Mirá que lindo thread que se armó. Jeje. Esto es lo que me encanta de PyAr.

Está faltando que alguien haga sus magias negras y muestre más código. :)

Me sorprendió eso de que a alguien se le terminó transformando en una tésis.

Les cuento que éste ejercicio que mi amigo tom a surgió de que una vez inscribiendonos a unas materias en una universidad teniamos que ir anotando a mano y estabamos medio cansados de hacerlo, ya que no proponia opciones armadas. Alli salió la versión en c++ y luego la idea de tomarlo como posible entrada a un trabajo.

Salutes!,
Juan 

[Juan Rodríguez Monti]

2010/7/7 Hernan Olivera <lhol...@gmail.com>

En mi facultad un alumno quiso hacer un programa similar para una escuela, y descubrió que aunque optimizara el código nunca llegaba a dar resultados. De ahi, terminó en una tesis de grado, en el cual este problema denominado timetable se resuelve con un sat-solver, previa reescritura en lógica proposicional. Parece trivial, pero no lo es.

Hernán, y este alumno ha publicado su trabajo al respecto?. Su investigación, código, todo el trabajo que realizó?.

Slds.,
Juan

[Hernan Olivera]

2010/7/7 Juan Rodríguez Monti <juanrodri...@gmail.com>

2010/7/7 Hernan Olivera <lhol...@gmail.com>

En mi facultad un alumno quiso hacer un programa similar para una escuela, y descubrió que aunque optimizara el código nunca llegaba a dar resultados. De ahi, terminó en una tesis de grado, en el cual este problema denominado timetable se resuelve con un sat-solver, previa reescritura en lógica proposicional. Parece trivial, pero no lo es.

Hernán, y este alumno ha publicado su trabajo al respecto?. Su investigación, código, todo el trabajo que realizó?.

Averiguo, deberia ser público entiendo.
 

Slds.,
Juan

_______________________________________________
pyar mailing list py...@python.org.ar
http://listas.python.org.ar/listinfo/pyar

PyAr - Python Argentina - Sitio web: http://www.python.org.ar/

--
Hernan Olivera

[Juan Rodríguez Monti]

2010/7/7 Hernan Olivera <lhol...@gmail.com>

2010/7/7 Juan Rodríguez Monti <juanrodri...@gmail.com>

2010/7/7 Hernan Olivera <lhol...@gmail.com>

En mi facultad un alumno quiso hacer un programa similar para una escuela, y descubrió que aunque optimizara el código nunca llegaba a dar resultados. De ahi, terminó en una tesis de grado, en el cual este problema denominado timetable se resuelve con un sat-solver, previa reescritura en lógica proposicional. Parece trivial, pero no lo es.

Hernán, y este alumno ha publicado su trabajo al respecto?. Su investigación, código, todo el trabajo que realizó?.

Averiguo, deberia ser público entiendo.

Dale. Acabo de investigar un poco en internet, y nunca pense que hubiera tanta teoria, papers, y analisis de un ejercicio tan sencillo. Realmente me impresiono.

Hay de todo dando vueltas por ahi, mucho material academico, inteligencia artificial como dijeron algunos chicos, y diferentes formas de afrontar el problema.

Saludos,
Juan

[Martin Cerdeira]

2010/7/7 Juan Rodríguez Monti <juanrodri...@gmail.com>

Dale. Acabo de investigar un poco en internet, y nunca pense que hubiera tanta teoria, papers, y analisis de un ejercicio tan sencillo. Realmente me impresiono.

Quizá no sea tan sencillo. =)

A veces, hay problemas que son "sencillos" desde su definición, pero no desde su resolución. El problema del viajante de comercio es un buen ejemplo.

Saludos
-------------------------------------
Martín Cerdeira - Software Developer
[web] http://www.codmacs.blogspot.com/
()  ascii ribbon campaign
/\  www.asciiribbon.org  

[Matigro]

2010/7/7 Martin Cerdeira <martinc...@gmail.com>:

> A veces, hay problemas que son "sencillos" desde su definición, pero no
> desde su resolución. El problema del viajante de comercio es un buen
> ejemplo.
>
> Saludos

O el del Huevo y la Gallina :D

Quizás en lenguajes de programación Lógicos, tipo Prolog, debe ser mas
simple manejar este tipo de problemas debido al buen manejo del
universo de soluciones.

Muy interesante el hilo este.

--
http://www.linkedin.com/in/matigro

[Juan Rodríguez Monti]

2010/7/7 Martin Cerdeira <martinc...@gmail.com>

2010/7/7 Juan Rodríguez Monti <juanrodri...@gmail.com>

Dale. Acabo de investigar un poco en internet, y nunca pense que hubiera tanta teoria, papers, y analisis de un ejercicio tan sencillo. Realmente me impresiono.

Quizá no sea tan sencillo. =)

Totalmente :) . Pero entendés que lo primero que pensé fué que era una gilada. No lo es en absoluto, evidentemente.

Nosotros lo resolvimos de una forma medio a los golpes cuando se hizo en C++. Pero yo ni sabia de que era un problema conocido ( timetabling problems, si alguien quiere buscar ) y que hay toda una serie de papers y topicos academicos en torno a algo que como bien decis, parece sencillo.

 

A veces, hay problemas que son "sencillos" desde su definición, pero no desde su resolución. El problema del viajante de comercio es un buen ejemplo.

Claro. Pero en este a veces pareceria estar escondida la complejidad, je.  Es hasta que empezas a profundizar un poco.

Saludos

Saludos,

Juan 

-------------------------------------
Martín Cerdeira - Software Developer
[web] http://www.codmacs.blogspot.com/
()  ascii ribbon campaign
/\  www.asciiribbon.org  

[Alejandro Santos]

2010/7/7 Juan Rodríguez Monti <juanrodri...@gmail.com>:

>
> El ejercicio: Se debe escribir una aplicación en python que permita ingresar
> por teclado los horarios de cursada disponibles para un alumno ( Esto
> significa que la Universidad ofrece n horarios posibles; por ejemplo: hay 3
> horarios de matemática disponibles con sus día y hora respectivos, 2 de
> algebra, 5 de programación, etc ), y que dicho programa procese la entrada
> de datos e imprima en la pantalla todas las posibles combinaciones de
> horarios de cursada en base a esa entrada.
>
> Ejemplo de horario:
>
> Matemática I - Lunes de 15 a 17 - Miércoles de 20 a 21 - Viernes de 16 a 18.
> Algebra II - Martes de 15 a 19
> Algoritmos III - Martes de 14 a 18 - Miércoles de 16 a 19
>
> En base a toda la entrada de datos, en donde habrá horarios que se
> superponen por coincidir parcial o totalmente en hora o día, el sistema
> deberá construir e imprimir opciones de horarios para que el alumno elija
> cúal es la ideal para el. Es decir, en base a las n opciones de cursada que
> se ingresan, el sistema deberá mostrar por pantalla opciones para que el
> alumno utilice. em donde ninguna materia se superponga con otra, y
> contemplando que sea posible cursar la mayor cantidad de materias posibles.
>

> Plus: Si se diseña un algoritmo que optimice las opciones. Es decir, si se
> determina un criterio a través del cual es mejor cursar 4 hs lunes y 4 hs
> martes, en lugar de cursar 8 horas un único día. O aquí se puede implementar
> la optimización que se deseé.
>

Tiene toooda la onda a un ejercicio de programación dinámica:
maximizar el horario de cursada minimizando el horario por dia y el
horario libre entre dos cursadas.

--
Alejandro Santos
http://www.alejandrosantos.com.ar

[Martin Cerdeira]

Totalmente de acuerdo. También pasa mucho lo que les pasó a uds, uno, sin saberlo, lo "resuelve" en la práctica (como uds en C++), quizá no de forma perfecta, pero, de forma funcional y útil. Muchas veces con eso, un acercamiento a la perfección, alcanza.

Saludos

[Marcelo Fernandez]

El día 7 de julio de 2010 16:55, Matigro <mat...@gmail.com> escribió:
> 2010/7/7 Martin Cerdeira <martinc...@gmail.com>:
>> A veces, hay problemas que son "sencillos" desde su definición, pero no
>> desde su resolución. El problema del viajante de comercio es un buen
>> ejemplo.
>>
>> Saludos
>
> O el del Huevo y la Gallina :D
>
> Quizás en lenguajes de programación Lógicos, tipo Prolog, debe ser mas
> simple manejar este tipo de problemas debido al buen manejo del
> universo de soluciones.

Si aunque es el mismo acercamiento planteado anteriormente en el hilo;
en los lenguajes lógicos se usa el backtracking debajo del capó, hacia
arriba lo que el programador maneja es la abstracción de una prueba
deductiva. Digamos que es un problema que es más elegante de resolver
con algún motor de estos.

http://en.wikipedia.org/wiki/Prolog#Evaluation

Saludos

> Muy interesante el hilo este.

Adhiero. :-)

Saludos
--
Marcelo F. Fernández
Buenos Aires, Argentina
Licenciado en Sistemas - CCNA

E-Mail: marcelo.fid...@gmail.com
Blog: http://blog.marcelofernandez.info
Twitter: http://twitter.com/fidelfernandez