Monday, June 23, 2014

Programación lúdica: el juego de NIM


Dice la Wikipedia: "En este juego, dos jugadores a los que llamaremos David y Vicente, colocan un número arbitrario de fichas (cerillas, palillos, guijarros) sobre una superficie, separadas en filas o grupos. Tanto el número de filas como el número de fichas en cada fila son también arbitrarios. El primer jugador, supongamos que es David, toma cualquier número de fichas de una fila, entre uno y el total de la fila, pero sólo de una fila. El jugador Vicente hace su jugada de manera similar, retirando algunos de las fichas que quedan, y los jugadores van alternándose en sus jugadas. Se puede jugar de modo que gane el que retire la última ficha".

Para limitar el problema, pensemos en la siguiente configuración inicial:


Un jugador puede eliminar de una de las cuatro filas, las bolitas que quiera. No importa el orden, es decir, si elimina las tres primeras bolitas de la última fila (la que contiene siete bolitas) o si lo hace salteado, una sí y uno no, alternadamente, da lo mismo. Si quita tres de la última fila, el rival podria, por ejemplo, quitar las cuatro restantes, aunque quedasen en grupos separados dentro de la misma línea.. El objetivo del juego, repito, es que quien tenga que eliminar la última bolita, pierde. Nótese que en cada turno solamente se pueden eliminar bolitas de una sola fila.

Este juego ha sido muy estudiado y se conoce un algoritmo para la solución. Aquí sin embargo, el reto se trata de lo siguiente. Por ejemplo, la configuración 1-2-3 es ganadora (esto quiere decir que en una línea quede una bolita, en la siguiente dos y en la tercera línea tres bolitas) Si hay esta configuración, quien juega pierde. De hecho, 1-2-3 es equivalente a 3-2-1 o 2-1-3, etcétera. Configuraciones que tienen que ver con la mencionada son 2-2 y 1-1-1. Por ejemplo, si llego a tener la configuración 2-2, si el rival quita una bolita de cualquiera de las dos líneas, yo quito dos y mi rival tiene que quitar la última. Si mi rival quita dos bolitas de la línea, yo quito de la línea restante una bolita y de nuevo gano, pues el contrario tiene que eliminar la última.

El reto pues consiste en hallar todas estas configuraciones ganadoras. Ya di algunas:

1-1-1
1-2-3
3-3
2-2
4-4

¿Cuántas configuraciones ganadoras hay? ¿Es 1-3-5-7 una configuración ganadora o perdedora? El resultado del programa que escriban debe dar todas las configuraciones ganadoras en el formato A-B-C-D, por ejemplo:

1-1-1
2-2
3-3
4-4

una configuración en cada línea (pueden omitirse las líneas que no contengan bolitas, que den cero, pues).

¿El premio? Una taza con el logotipo de la Morsa a la mejor solución. Esto solamente aplica a los programadores que vivan en el DF (mandar a provincia o a otros países una taza es estúpidamente costoso). En caso de que los concursantes sean de otros países o de la provincia mexicana, el premio será una memoria USB de al menos 16 GBytes y se les enviará por correo certificado. Y sí, sé que no son los grandes premios pero mientras no tengamos patrocinadores, esto es lo que hay.

Evidentemente quien gane será anunciado en unocero y hasta tendrá sus quince minutos de fama. Sus programas me los pueden mandar a morsa@la-morsa.com y pueden escribirse en cualquier lenguaje. Es importante señalar que hay que mandar el código fuente, el ejecutable (si procede) y el archivo de resultados pedido.

Cabe señalar que este concurso busca simplemente alentar el trabajo de la programación y mostrar que puede ser lúdica. Es un concurso de buena fe. Si hay, por ejemplo, dos o más respuestas satisfactorias, ganará quien la haya mandado primero. El ganador cede su código fuente a la comunidad. Es decir, se promueve el código abierto. Así que “en sus marcas, listos, ¡arrraaaaancan!”

No comments: