Saturday, July 17, 2010

Mini-Competencia de programación: Feudalismo

Hoy, volviendo de la facu, me quedé casi literalmente sin plata encima (tenía nada más ni nada menos que 15 centavos en la billetera), así que tuve que caminar desde el tren a casa en vez de tomarme el bondi. Durante esa caminata se me ocurrió hacer esta competencia.  Y quizá cada tanto organice más de estas mini-competencias, dependiendo de la respuesta que tenga.

Estuve pensando un rato los detalles del problema, pero lo que más tiempo me llevó es pensar cómo hacerla accesible a la mayor cantidad de gente posible. Al final se me ocurrió cómo hacerlo independiente del sistema operativo e independiente del lenguaje de programación. Casi lo limito a Java para hacerme la vida más fácil al evaluar soluciones, pero sabía que muchos iban a salir corriendo jaja. En fin, vamos al problema:



Supongamos que sos el jefe de una familia campesina en la edad feudal. Estás en una zona donde hay 2 castillos, pertenecientes a los señores feudales A y B. Ambos son señores feudales muy bondadosos, por lo que aceptan a cualquier familia que se quiera unir a su feudo, prometiendo pagarles a todas distribuyendo uniformemente una parte de sus ingresos. El señor feudal A gana 700 piezas de oro por año, y el B gana 300 piezas de oro por año. Esto es independiente de la cantidad de familias pertenecientes al feudo de cada señor. Al final de cada año, el señor feudal divide sus ganancias equitativamente entre todas las familias que le fueron leales ese año, y les da la opción de quedarse o de marcharse. 
Así, si hay 10 familias trabajando en el feudo del señor A y 3 en el feudo del señor B, a fin de año las que están con el señor A ganarán 70 piezas de oro cada una, y las que están con el señor B 100.
El objetivo es hacer un programa que decida a qué feudo ir cada año buscando maximizar las piezas de oro ganadas luego de 80 años. Los únicos datos con los que se cuenta en cada año es  la cantidad de familias en cada feudo del año pasado.

Especificación del programa a realizar:

  1. Se puede usar cualquier lenguaje de programación mientras se pueda compilar y correr en Linux.
  2. Para la simulación, las únicas familias participantes serán los programas que envíen los concursantes, por lo que la cantidad de familias se mantendrá constante durante los 80 años (lo que varía es en qué feudo está cada familia cada año).
  3. El programa debe respetar estrictamente un protocolo basado en entrada/salida. Al comenzar su corrida, debe imprimir en salida estándar una línea con un único carácter indicando en qué castillo se desea empezar(una ´A´ o una ´B´). Luego, sucesivamente, debe leer una línea de entrada estándar de la que recibirá los datos de la simulación y volver a outputtear una línea con un único carácter indicando la opción para el año siguiente. La línea de datos que recibirá serán 2 numeros enteros separados por un espacio que indican la cantidad de familias en el castillo de A y la cantidad de familias en el castillo de B, respectivamente.
  4. Notar que los intercambios input/output son en forma interactiva. El programa debe leer los datos, escribir su opción, luego vovler a leer los datos, y escribir su nueva opción, sucesivamente, hasta terminar los 80 años (no es necesario que el programa termine al pasar los 80 años).
  5. Ejemplo de intercambio input/output:
    A
    5 2
    A
    3 4
    B
    1 6
    A
    etc...
  6. Un programa simple en python que descarta los datos de la simulación y, empezando por el castillo A, va siempre cambiando de castillo, podría ser este: ver código. (sketch, sin testear)
  7. Para evitar problemas en la simulación, sería bueno que luego de imprimir a salida estándar cada línea con la decisión, el programa se ocupara de flushear el buffer de salida (en caso de existir). Notar que aunque el programa no usa los datos de la entrada, igualmente debe leerlos para respetar el protocolo input/output.
Bueno, creo que eso es todo. Espero que se haya entendido. Para participar manden su código fuente a feudalismo@7cerebros.com.ar. Cada participante puede mandar hasta 5 estrategias diferentes. En el mail incluir tu nombre, un nombre para la estrategia, y de ser necesario instrucciones para compilar y correr el programa, o cualquier aclaración que se crea necesaria. Si tenés ganas, también dejá un comentario en este post avisando que estás participando para que los demás lo sepan. 
Otra opción: si te da fiaca hacer el programa o no tenés conocimientos de programación, podés mandar por mail una explicación de la estrategia y yo hago el programa!

En una semana, el 24/7/2010, si se llega a una buena cantidad de estrategias participantes, voy a correr la simulación, y postear los resultados. El martes 27/07/2010 voy a correr la simulación y postear los resultados. La estrategia que consiga más monedas de oro luego de los 80 años se gana un gran aplauso (?). Gracias!

saludos,
Manu

pd: cualquier pregunta dejen un comentario así la aclaración le sirve a todos!

12 comments:

  1. Muy buena onda che! Siempre quise participar de competencias de este estilo.

    Lo voy a pasar! Esperá mi solución en esta semana!!

    ReplyDelete
  2. Gracias Esteban! Contale a los chicos que andan en esta onda si los ves!! quiero tener varios algoritmos compitiendo ferozmente jaja. Ah! Y acordate que vale mandar más de uno por persona.

    abrazo!

    ReplyDelete
  3. ¡Muy buena idea! Me voy a poner a pensar algo para resolver el desafío. Sale RT y otros.

    ReplyDelete
  4. Sumándome en 3... 2... 1

    Vale Objective-C ? :D

    ReplyDelete
  5. Paul: genial!
    Mr. Smith: sí, vale todo! Lo único, fijate de no usar librerías propietarias de Apple, o cosas que me impidan la compilación en linux. Ante la duda incluí instrucciones para ayudarme a no tener problemas. gracias!

    ReplyDelete
  6. Muy bueno man! Ya lo estoy pensando.

    ReplyDelete
  7. Cambié la fecha de finalización porque el sábado no iba a poder! Espero sus estrategias :D

    ReplyDelete
  8. ¡Excelente iniciativa!
    ¿Se permiten "mafias", es decir, presentar varios algoritmos que se ayuden mutuamente, o que ayuden a uno solo del grupo para que su autor gane?

    ReplyDelete
  9. Hola Marcos, sí, eso está permitido, mientras se mantenga el formato especificado en el enunciado. Gracias!

    ReplyDelete
  10. Debido a la poca participación agrego un tiempo más para mandar soluciones!

    Sólo recibí 4 estrategias, de sólo 2 participantes (esteban y marcos). Correr la simulación así no tiene gracia, así que decidí posponer un poco más el fin del concurso a ver si más gente se entusiasma.

    El sábado 7/8/10, si hay una cantidad interesante de estrategias, se correrá la simulación. Perdón a los que ya mandaron por la espera! Si mandaste tu estrategia y no te mencioné chiflá!

    saludos,
    Manuel

    ReplyDelete
  11. Ya están los resultados, mirá acá: http://i.t4z.com.ar/0cY

    ReplyDelete