Activa las notificaciones para estar al tanto de lo más nuevo en tecnología.

tona-nim00

Tonatihu Sánchez, quien estudió Ciencia de la Computación en la Facultad de Ciencias de la UNAM, ganó el reto que propusimos sobre encontrar todas las configuraciones para ganar en el juego de NIM. Su programa está escrito en Python, cosa que lleva ya siendo una extraña moda en la facultad enseñar este lenguaje, pero desde luego, tendrán sus razones y Tonatihu tuvo, para entender lo que tenía que hacer, buscar en Internet cómo se jugaba y se resolvía este problema (ver los dos enlaces en su código fuente).

Dice el autor: “La estrategia consistió en entender bien el juego, jugarlo incluso antes de codificar. En el código fuente vienen las dos referencias principales que consulté. Ahí fue donde aprendí sobre la nim-suma y su equivalencia con la operación “xor”, así como las estrategías que se siguen para ganar el juego. Ya a la hora de codificar puse atención en no repetir posiciones equivalentes y aunque la primera vez traté de hacerlo lo más general posible (aunque no te gustó mi solución), el que el problema estuviera acotado de esa manera facilitó mucho resolverlo.”

He aquí el archivo de soluciones del ganador:

Hay 18 posiciones ganadoras
1-3-5-7 es una posición ganadora
Las posiciones ganadoras son las siguientes:
7-5-3-1
7-5-2
7-4-3
7-4-2-1
6-5-3
6-5-2-1
6-4-3-1
6-4-2
5-5-1-1
5-5
5-4-1
4-4-1-1
4-4
3-3-1-1
3-3
3-2-1
2-2-1-1
2-2
1-1-1

Tonatihu nos aclara: “Adjunto código fuente y archivo de soluciones. La forma recomendada de ejecutar el programa es la siguiente:

$ python nim4.py [bolitas]

Donde [bolitas] es el número máximo de bolitas que se quiera que tenga el juego. De manera predeterminada se establece dicho valor en 7.

y añade:

  • El programa fue probado con el interprete de Python versión 2.7.3
  • El programa imprime el resultado en consola por lo que el archivo de resultados fue generado con una redirección de la salida estándar.

He aquí su programa:

#!/usr/bin/python
# -*- coding: utf-8 -*-
"""
nim4.py: Encuentra todas las configuraciones ganadoras(1) para NIM de 4 filas, 
con una configuración inicial de 7-5-3-1.
[1] Tocandole el turno al oponente y en modo 'miseria' [http://es.wikipedia.org/wiki/Nim_(juego)]
"""
__version__ =  "2.0"
__author__  = "Tonatihu Sánchez - [email protected]"
__license__ = "GPL 2.0"

ganadoras = 0 #Contará el número de configuraciones ganadoras
posiciones = '' #Guardará las posiciones ganadoras
for A in xrange(7,1,-1):
for B in xrange(5,0,-1):
for C in xrange(3,-1,-1):
for D in xrange(1,-1,-1):
if (D<=C and C<=B and B<=A): 
#Para evitar repeticiones innecesarias debido a que es equivalente 1-2-3 que 1-3-2, 3-1-2 etc.
if(A^B^C^D == 0): #Referencia: http://www.archimedes-lab.org/How_to_Solve/Win_at_Nim.html
ganadoras += 1
aux = str(A)+"-"+str(B)
if(C != 0):
aux += "-"+str(C)
if(D != 0):
aux += "-"+str(D)
posiciones += aux+"\n"
posiciones += "1-1-1\n" #Caso especial debido al "modo miseria"

print "Hay " + str(ganadoras) + " posiciones ganadoras"
print "1-3-5-7 es una posición ganadora"
print "Las posiciones ganadoras son las siguientes:"
print posiciones
Desde la Red…
Comentarios