CientoSeis

Como es 1 de Agosto, y por tanto queda un mes exacto para el 1 de Septiembre, voy a proponer un concurso de programación. Al mismo podéis apuntaros o incluso invitar amigos de fuera. Será simplemente code-for-fun, no hay premio, salvo que alguien encuentre algún patrocinador, yo miraré por mi lado.

Las reglas son las siguientes:

1. Se puede utilizar cualquier lenguaje de programación que uno prefiera.
2. Las aplicaciones serán modo consola. Se busca la realización del algoritmo, no interfaces bonitos.
3. Debe ser capaz de generar un ejecutable válido para Windows. Esto no es un handicap, todos los lenguajes más usados son capaces de ello. Pero así todas las aplicaciones se medirán en el mismo baremo y SO.
4. El concurso comenzará el día 1 de septiembre. Constará de 3 pruebas a superar en 5 días cada una.
5. El sistema de puntuaciones será objetivo:
- Para cada algoritmo se pasarán 10 tests unitarios, cada uno de 5 puntos. Con lo cual una aplicación que supere todo obtendrá 50 puntos. Así se premia la robustez de la aplicación. Si una aplicación no pasa al menos 5 tests unitarios, se invalidará.
- El primero en enviar cada algoritmo obtendrá 25 puntos extra. El segundo 12 puntos extra. El tercero 5. Para así premiar la velocidad de codificación.
- El que envíe el algoritmo más veloz obtendrá 25 puntos extra. El segundo más veloz 12 puntos extra. El tercero 5. Para así premiar la performance.
6. Para cada prueba se enviará el código fuente junto con el ejecutable en formato zip.



Yo me voy de vacaciones hasta el día 20. Así que, no estaré para ver si os habéis apuntado. Si conocéis gente que no sea del foro interesada en competir, que se apunte. En mi ausencia, hablad (si es que esto llega a algún lado y alguien se apunta) o incluso proponed cambios de fecha (a futuro) o de normas.

Lista de apuntados:
Faerindel
Ydrojen
Aserercoff
Thylzos
Ynteror
Shadark

Primera Prueba:
http://www.cientoseis.es/index.php?topic=84047.msg770887#msg770887 (http://www.cientoseis.es/index.php?topic=84047.msg770887#msg770887)

Dije que me amputaba, ¿no? Pues venga.

He modificado las normas en dos puntos:
1. 3 pruebas, una cada 5 días. Para que todos reciban el enunciado de la prueba al mismo tiempo, y exista más tiempo para los que programan poco o trabajan.
2. Si no se supera el 50% de los tests unitarios se invalidará. Porque fijo que algún listo manda un zip vacío para ganar los 25 puntos de velocidad y los 25 de performance.

Yo me amputo también.

Cita de: Ydrojen en 01 de Agosto de 2012, 19:51
Yo me amputo también.

Y de paso pásate por el hilo de programación de juegos, que a lo mejor hay un post que puede resultar interesante.

Me uno, pero aviso que dispongo de poco tiempo. Puede que no entregue alguna prueba.

Me uno.

+yo

De los que os habéis unido, ¿cuántos saben programar con cierta habilidad? Quiero saber el nivel que hay.

Cita de: Aserercoff en 04 de Agosto de 2012, 19:36
De los que os habéis unido, ¿cuántos saben programar con cierta habilidad? Quiero saber el nivel que hay.

El nivel de un concurso lo ponen sus preguntas y no los concursantes. Y ya aviso que las preguntas serán variaciones de preguntas existentes en concursos de programación, la diferencia es que en lugar de tener un par de horas para resolverlas, tenéis una semana. Creo que es bastante ventaja como para que todos puedan participar.

Yo, intentaré a ver si saco algo :gñe:

Actualizado el primer post con la lista de participantes.

Para los que quieran "calentar", les sugiero ir aquí:

http://codility.com/ (http://codility.com/)

Debajo del botón "Certify yourself!" encontraréis un enlace al demo test. Sacar un 100 en ese es sencillo.

momento, creo que debo salir por motivos ajenos a mi voluntad, no soy muy bueno tampoco pero el tiempo no lo tendre :/

Bueno, tú verás, al final es posible que exista un premio de 100 euros para el ganador. Unos 123 dólares. Aunque para eso tendría que conseguir más gente.

Y contando con que yo es posible que no pueda, pero hago bulto :lol:.

Si saco un poco mas de tiempo vuelvo y te lo aviso, y si va de gente buscare un par de "hamijos" que tengo en el medio a ver si se animan, pero por ahora estoy out.

Igual gracias.

si necesitas a alguien para hacer bulto y tal, apuntame, pero no creo que gane nada xDD

Muy interesante. Me será imposible por tiempo pero me apuntaré a la próxima si puedo.

De todos modos, si van a ser ejercicios públicos me gustaría saber si se pueden enviar aunque no participes, just for fun. No me gustaría competir porque sé seguro que no cumpliré los plazos, por sencillos que sean los ejercicios, por varios motivos laborales y personales.

A ver si me puedo apuntar al próximo. Aunque la programación no me apasione ni realmente sea lo mio, he de reconocer que a veces te entran unas ganas locas de programar algo.

Can I has some participant?

2 days to go.... Mentira, doy el Go mañana porque me piro a Granada y no tendré internec. Así que pongo la primera prueba mañana.

Go go go go go!!

Prueba 1:

Descripción

Una compañía bancaria tiene un sistema de seguridad online muy curioso. Ofrece a sus usuarios una tarjeta con una contraseña muy larga, de caracteres alfanuméricos, en la que no se repiten caracteres dentro de la contraseña. Pedir la contraseña al usuario tendría dos problemas: que el usuario tendría que meter muchos caracteres, y que además al enviar la contraseña crea una debilidad en el sistema. Por ello, la web online del banco lo que hace es pedirle 3 caracteres de la contraseña, indicándole las posiciones de los mismos (las tres diferentes). Pero han cometido un error, y es que los piden en orden.

Has instalado un keylogger en la máquina de un cliente, y te llegan los conjuntos de 3 letras. Ahora solamente te falta realizar un programa que te devuelva las posibles contraseñas, en orden alfabético.

Notas:

Caracteres válidos: [A..Z, a..z, 0..9]
Dar por supuesto que se han tomado suficientes muestras como para poseer todos los caracteres posibles de la contraseña.
Las contraseñas estarán en un fichero "input.txt" en el mismo directorio que el ejecutable.
Las respuestas se guardarán en un fichero "output.txt" en el mismo directorio que el ejecutable.
No se aceptará ningún ejecutable que no pase al menos los unit tests adjuntos en la prueba.
Es posible que no exista solucion, en cuyo caso el output.txt deberá estar vacío.
Tenéis de tiempo hasta el viernes 7 de agosto a las 23:59.
El código debe adjuntarse en un zip junto con el ejecutable generado, y enviadme por MP un link para descargarme el zip. Una vez enviado, es el definitivo, no hay posibilidad de cambios o volver a enviar.

Unit Tests

Citar
Unit Test 1

Input:

CSe
iEo
ToS
nTo
iEn
Cie
SeI
iEe
ESe
ToI
EIs

Output:

CiEnToSeIs

Citar
Unit Test 2

Input:

Eos
SeI
CEs
EnT
iEI
Cie
Tes
ToS

Output:

CiEnToSeIs
CiEnToSesI

Citar
Unit Test 3

Input:

Cos
Eoe
Ces
iEn
nTS
Cin
SeI

Output:

CiEnoTSeIs
CiEnoTSesI
CiEnToSeIs
CiEnToSesI
CiEnTSoeIs
CiEnTSoesI
CiEonTSeIs
CiEonTSesI

Citar
Unit Test 4

Input:

MaN
zAn
NzO

Output:

MaNzAnO
MaNzAOn
MaNzOAn

Citar
Unit Test 5

Input:

B2C
a1b
1Dd
BcD
1Cc
1Bd
a2D
1b4
Aa2
Aab
3d4
ADd
Ab3

Output:

Aa1B2b3CcDd4
Aa1B2bC3cDd4
Aa1B2bCc3Dd4
Aa1B2bCcD3d4
Aa1B2Cb3cDd4
Aa1B2Cbc3Dd4
Aa1B2CbcD3d4
Aa1B2Ccb3Dd4
Aa1B2CcbD3d4
Aa1B2CcDb3d4
Aa1b3B2CcDd4
Aa1Bb23CcDd4
Aa1Bb2C3cDd4
Aa1Bb2Cc3Dd4
Aa1Bb2CcD3d4
Aa1Bb32CcDd4

No entiendo como va algunos output, me explicas por ejemplo este como va?

Citar
Unit Test 4

Input:

MaN
zAn
NzO

Output:

MaNzAnO
MaNzAOn
MaNzOAn

Según entiendo deberían ser 2 out: MaNZOzAn y zAnMaNZO

EDIT: Nop, me liao y las dos zetas son minusculas asi que tampoco serian esos out que he dicho

Supón que la contraseña original era "MaNzAnO".

1234567
MaNzAnO

Al usuario le han pedido la contraseña 3 veces, y las has capturado, en concreto:
1) Letras 1, 2 y 3 => capturas MaN
2) Letras 4, 5 y 6 => capturas zAn
3) Letras 3, 4 y 7 => capturas NzO

Tú estás suponiendo que siempre piden letras consecutivas, y no es así. Eso sería demasiado fácil.

¿Se supone que es un jueguecillo simple de adivinar cual es la letra que va antes que otra, no?

Me he entretenido en ver este hilo por curiosidad, y me surge una duda.

Peluche, estás intentando desmontar el sistema de seguridad del Santander o que?  :gñe:

Perdón por la intromisión.

El sistema CES del santander está más que desmontado  :lol: Solamente es un poquito de seguridad más para el comercio electrónico, pero es inseguro a tope. Son más seguras las tarjetas de coordenadas, por ejemplo LaCaixa usa este sistema, te envía una tarjeta con 60 coordenadas de 4 cifras cada una.

En cuanto al concurso, solamente está participando Ydrojen, así que supongo que el viernes le tendré que declarar ganador del concurso por abandono de todos los demás participantes  :lol:

Cita de: Mike en 02 de Septiembre de 2012, 00:12
¿Se supone que es un jueguecillo simple de adivinar cual es la letra que va antes que otra, no?

Sí y no. Sería un jueguecillo simple si la solución a ofrecer fuese única. Al no ser una solución única, tienes que calcular además las permutaciones de soluciones posibles. Pero vamos, si es simple, entonces estoy esperando tu solución a mi MP ;)

Hombre, espero que alguno más sea capaz de hacer algo, que ganar tan pronto es aburrido :lol:

Estamous en ellou. Que me estoy enrollando como una persiana y seguramente esté mirando 11k métodos más complicados, pero bueno. :lol:

Han pasado tres días y por ahora Ydrojen sigue siendo el único participante  :gñe:

Eso me hará más sencillo calcular el ganador  :amo:

Desde que estudio administración de sistemas no tengo ningún compilador instalado y lo poco o nada que pude llegar a entender en C y en Visual se me han ido a tomar por culo.

¿Soy un desastre de informático?

Yo es que estoy de exámenes y no tengo tiempo a hacerlo... De todas máneras, tengo alguna duda.. En los ejemplos que pusiste, en el Output, solo hay palabras que empiezan por la misma letra, no hay la posibilidad de que empiecen por otra letra?

Cita de: Genki en 04 de Septiembre de 2012, 23:24
en el Output, solo hay palabras que empiezan por la misma letra, no hay la posibilidad de que empiecen por otra letra?

Dependerá del input que te den... si hay suficiente información cómo para saber la letra inicial de la contraseña entera...

Se supone que no. Y se supone que los inputs son suficientes y que pueden conformar la contraseña completa, en alguna de todas las Outputs.

Además, eso se ve a ojo, si te paras un poco y miras en los Inputs cual va antes que cual, ves que algunas van delante de la palabra a la fuerza.

Claro que pueden empezar por letras diferentes. Ejemplo:

Aa1
Ba1

A simple vista ya se ve que las posibles soluciones son
ABa1
BAa1

Lo he dicho por deducción, lamentablemente no tengo tiempo para ponerme.

Lo que dice el enunciado es que los inputs contienen la totalidad de los carácteres que conforman la contraseña. Entiendo que no tienen porqué ser suficientes para ordenar totalmente la contraseña (como es evidente en los ejemplos proporcionados). Por lo tanto de igual modo que la parte final tiene varias opciones entiendo que la parte inicial podría también tener "dudas".

EDIT: ya contestó bill.

pero si:

a1b
1Bd
Aab

¿Como puede ir B delante de A?

Cita de: Bill en 03 de Septiembre de 2012, 20:33
Han pasado tres días y por ahora Ydrojen sigue siendo el único participante  :gñe:

Eso me hará más sencillo calcular el ganador  :amo:

Bueno, pero la fecha de entrega es el viernes. Me juego un brazo a que el 7 a las 23:58 recibes el resto de los trabajos (entre los que estará el mío xD).

Por cierto, ¿podrías poner una posible solución luego de cada prueba o la mejor de las presentadas o algo así? Me interesa participar para aprender un poco más y así puedo ver mejores implementaciones que la mía.

Cuando leí el enunciado tuve un flashback con mi nefasto profesor de grafos :(.

Citar
pero si:

a1b
1Bd
Aab

¿Como puede ir B delante de A?

En tu ejemplo, sencillamente no puede. Tu ejemplo tiene dos soluciones:
Aa1bBd
Aa1Bdb

Tu ejemplo no tengo ni puta idea de dónde ha salido.

Pero es que yo no te puse ese ejemplo. Te puse este, que es el más sencillo que contestaba a la duda de Genki:

Aa1
Ba1

Eso implica que hay 4 posiciones y 4 letras: [A, a, 1, B]

"Aa1" =>
A no puede ir en posición 3 ni 4, le quedan 1 y 2
a no puede ir en posición 1 ni 4, le quedan 2 y 3
1 no puede ir en posición 1 ni 2, le quedan 3 y 4.

"Ba1" =>
B no puede ir en posición 3 ni 4, le quedan 1 y 2
a no puede ir en posición 1 ni 4, le quedan 2 y 3
1 no puede ir en posición 1 ni 2, le quedan 3 y 4.

Juntando ambas informaciones, sabemos que la "A" y la "B" tienen de posibilidades las posiciones 1 y 2, eso fuerza que la "a" no puede estar en la posición 2 porque estaría ocupada por la "A" o la "B", con lo cual la "a" está en la posición 3. Y eso fuerza que el "1" está en posición 4. Con lo cual las posiciones de "a" y "1" están forzadas, pero las de "A" y "B" no, así que tiene dos soluciones:

ABa1 y BAa1.

Sí, algo así queria saber, porque en los ejemplos no vi ningún caso así, aunque tambien hay muchos imputs para que no se presenten estos casos xD

Es un extracto del último ejemplo de la prueba.

Par de preguntas:

CitarEs posible que no exista solucion, en cuyo caso el output.txt deberá estar vacío.

Según cómo entendí el problema, no es posible que haya un output.txt vacío (salvo que el input tenga algún error y no siga las normas que has estipulado).

CitarEl código debe adjuntarse en un zip junto con el ejecutable generado, y enviadme por MP un link para descargarme el zip. Una vez enviado, es el definitivo, no hay posibilidad de cambios o volver a enviar.

Tengo pensado escribirlo en Python, por lo que necesitarías tener la máquina virtual de Python instalada. ¿Hay algún problema con eso o prefieres que lo escriba en otro lenguaje?

Ejemplo de input que no tiene solución:

Aa1
1aA

Como ves, es imposible, ergo.. output vacío.

Otro ejemplo:

AA1
Aa2

Hijo mío, las soluciones yo las escribo en python, con eso te lo digo todo.

Debería de empezar a darme de hostias con python o no es tan necesario?

Con tu java tienes más futuro profesional.
Con tu python tienes más jugueteo.

Quédate con tu java, además no se te da mal del todo.

Por darte resultados, con la prueba complicada (que no está entre las que puse ahí) tu solución tarda 12 segundos y 360 milésimas. Y tienes un bug, prueba a meter un input con una línea en blanco, ya sea en el medio o al final.

No decías nada de que los input podían cometer errores :llori: Cuando trabajo en algo tengo en cuenta cualquier "cosa rara" que pueda ocurrir pero en un ejercicio así no lo vi necesario.

Y sin tener otro que comparar no se si 12 seg es mucho o poco :lol:

Cita de: Bill en 05 de Septiembre de 2012, 21:50
Ejemplo de input que no tiene solución:

Aa1
1aA

Como ves, es imposible, ergo.. output vacío.

Otro ejemplo:

AA1
Aa2

Hijo mío, las soluciones yo las escribo en python, con eso te lo digo todo.

Ah, vale, creí que decías se podía dar el caso en entradas que siguiesen las "normas". Perfecto entonces. Gracias.

Ydrogen, yo uso mucho Python, pero para cosas como estas, pequeños programas rápidos que necesito hacer o para interiorizar algún procedimiento de la carrera (diagonalizar una matriz, buscar bases de un espacio o cosas por el estilo) escribiendo un programa de prueba que lo ejecute o para automatizar pequeñas tareas... En fin, como solución rápida y que no requiera pensar mucho. Como dice Bill, pa algo más serio siempre suele haber una mejor alternativa.

Queda poco más de un día. Ydojen sigue siendo el vencedor, y no tendré que hacer más pruebas porque habrá ganado  :lol:

Cita de: Bill en 06 de Septiembre de 2012, 20:58
Queda poco más de un día. Ydojen sigue siendo el vencedor, y no tendré que hacer más pruebas porque habrá ganado  :lol:

Si ya las tienes pensadas puedes ponerlas igualmente, a modo de ejercicio manquesea. :gñe:

Yo ya te aviso de que no vas a recibir el mío. Me da una pereza horrible terminarlo ahora, aunque me ha servido para desoxidarme un poquito. :$

Pues nada. Ydrojen, vencedor por abandono de todos los demás.  :gñe:

Ey, ya que solo se ha presentado uno haz un análisis chulo, di cuantos test he superado y esas cosas *.*

Nah, ando decepcionado. No contigo, con el resto. Pensaba que la chispa de talento del foro sería algo más grande, pero vamos, error mío... no hay más que ver cómo se os dan las matemáticas para algoritmica, como los juegos que puse en la sección de juegos de lógica  :lol: El talento se demuestra enfrentándose a retos. Es como los juegos de rol, si no te enfrentas al bicho enorme y pasas dificultades, porque además quieres hacerlo, no consigues experiencia y no mejoras.

Este problema era de nivel bajo. Tú fuiste el primero en enviar respuesta, tu tiempo de respuesta fue muy bueno. En cuanto a performance también eres el ganador, pero porque eras el único participante. De los unit tests pasaste 9 de 10, uno está fallido porque era el del enter extra al final del input.

El input para probar la performance es:



Tu forma de resolver es correcta y rápida de programar, pero su performance sufre un poco porque no eliminas posibilidades. Construyes el TreeMap para representar al grafo, y haces el backtracking, pero olvidas que algunas aristas no tienen por qué existir.

Al grano, vamos a ver cómo sería una solución construyendo el grafo, algo más óptima, con un ejemplo:

(http://img705.imageshack.us/img705/5322/paso1q.png)

Es a partir de ahora dónde viene lo divertido:
(http://img17.imageshack.us/img17/5191/paso2du.png)

Te he puesto dos aristas en rayado. Una es C->e, que no llega a insertarse al grafo, porque ya hay un camino más largo para llegar de "C" a "e". La otra es o->s, que se elimina, porque al añadir o->e->s ya existe un camino más largo para llegar. Esto es lo que no tiene tu solución, la eliminación de esos caminos.

Pongo ya todos los pasos hasta el grafo final:

(http://img543.imageshack.us/img543/2593/paso2b.png)
(http://img687.imageshack.us/img687/7381/paso3g.png)
(http://img685.imageshack.us/img685/6523/paso3b.png)
(http://img684.imageshack.us/img684/9067/paso4b.png)
(http://img690.imageshack.us/img690/5473/paso5k.png)
(http://img140.imageshack.us/img140/4278/paso5b.png)
(http://img687.imageshack.us/img687/9831/paso6g.png)

A partir de aquí es recorrer el grafo para dar las soluciones, que creo que está claro. Se clona el grafo, y se escoge cada nodo para cada disyuntiva, para recorrer todas las posibilidades, bien sea dentro de una recursiva o usando una pila para soluciones.

Bueno, yo no llego a "montar" el grafo, con la información que almaceno se puede montar pero no monto la estructura como tal.

Primero recorro el input almacenando para cada letra las letras que se que van delante. Luego para montar la solución miro en ese momento las posibles candidatas, que son las que no tengan ninguna delante, clono el mapa para cada candidato eliminando esa letra del mapa y de la lista de anteriores de las demás y vuelvo a mirar las que no tienen ninguna delante.

Lo único que podría mejorarse es que cuando cojo X candidato tengo que recorrerme las listas de anteriores de los demás para eliminar X si lo tiene. Si cuando recorro el input me fijo en no guardar las aristas esas que tu quitas, a la hora de recorrer la lista para eliminar X tendrían menos elementos cada lista y lo haría más rápido, aunque tienes mas operaciones al recorrer el input así que al final tampoco es tanta mejora...