Encuentra el movimiento óptimo de nim

8

El juego

Nim es un juego de estrategia matemática, donde 2 jugadores se turnan para tomar elementos de montones distintos. En su turno, debe tomar al menos un artículo, y puede tomar tantos como desee, siempre que solo tome de un montón. ¡El jugador que tome el último elemento gana! Este es un juego resuelto. Antes de entrar en la estrategia, puedes intentar jugarla en línea aquí .

La estrategia

La estrategia ganadora se explica muy claramente y simplemente aquí en este enlace. Lo explicaré con un poco más de términos técnicos. La forma de ganar este juego es tomar siempre tantos elementos como sea posible para que la suma digital binaria sea ​​siempre 0. Considere el siguiente tablero:

         *
       * *
     * * *
   * * * *
 * * * * *
 1 2 3 4 5

Para encontrar la suma binaria-digital de esta placa, debe:

  1. Convierta el número en cada fila a binario. Entonces tenemos 001, 010, 011, 100 y 101.

  2. Sume todos los números juntos e ignore cualquier carga.

     001
 010
 011
 100
+101
----
 001

    También puede hacer bit-xor cada número, y esto logrará el mismo resultado.

Ahora, si la suma en esta configuración actual es 001, entonces esto no es (todavía) una tabla ganadora. ¡Pero puedes convertirlo en una tabla ganadora! Si quitamos un elemento de las columnas 1, 3 o 5, la suma será 0. Este es un tablero ganador, lo que significa que, siempre que no se equivoque, el siguiente jugador en moverse perderá. Así que siempre debes terminar tu turno con una tabla ganadora. Digamos que quitas un elemento de la columna 5. Ahora el tablero se ve así:

       * *
     * * *
   * * * *
 * * * * *
 1 2 3 4 5

Mientras no lo arruines, tienes una victoria garantizada. No hay nada que tu oponente pueda hacer para detenerte. Digamos que toma todos los elementos de la columna 5.

       *
     * *
   * * *
 * * * *
 1 2 3 4 5

¿A dónde irías después? No se desplace hacia abajo todavía e intente resolverlo usted mismo.

En este momento, la suma es 100. El mejor movimiento (y el único movimiento ganador) sería tomar todo de la columna 4. Eso dejaría el tablero así:

     * 
   * * 
 * * * 
 1 2 3 4 5

y la suma como esta

 001
 010
+011
----
 000

eso significa que estás en una tabla ganadora! ¡Hurra!

El reto

Debe escribir un programa o función que, dado un tablero de nim, devolverá un movimiento ganador o un valor falsey si no hay un movimiento ganador.

Tu aportación:

  • Será el formato de la lista nativa de su idioma, donde cada elemento de la lista corresponde al número de elementos en una columna determinada. Por ejemplo, la entrada {4, 2, 1, 0, 3} corresponde a la siguiente placa nim:

    *
*           *
*  *        *
*  *  *     *
1, 2, 3, 4, 5

  • (opcional) El número de filas. (Para lenguajes como C / C ++ donde esto no se conoce de la lista misma).

Su salida:

  • Puede ir a STDOUT o ser devuelto desde la función

  • Deben ser dos números, 1) la columna de la que estamos eliminando (recuerde que las columnas están indexadas en 0) y 2) el número de elementos que se eliminarán de esa fila. Esto podría ser una matriz de 2 elementos, una cadena de los dos números, etc. Tenga en cuenta que la respuesta puede tener más de 2 dígitos, por lo que devolver la cadena "111" no es válida porque no está claro si esto significa "Eliminar un elemento de la columna once" o "Eliminar once elementos de la columna uno". "1,11" u "11,1" serían aceptables.

  • Si no hay respuesta, devuelva o imprima un valor falso. Si su idioma solo puede devolver un tipo de variable (de nuevo, como C / C ++), un número negativo para la columna, o 0 o menos para el número a eliminar serían valores de falsey aceptables.

  • Si el número de columna o el número a eliminar son demasiado grandes, esto se considera una salida no válida.

Entradas / salidas de muestra

[1, 2, 3, 4, 5]---> [0, 1]o [4, 1]o[2, 1]

[1, 3, 5, 6]---> [0, 1]o [1, 1]o[2, 1]

[1, 2, 0, 0, 5] ---> [4, 2]

[1, 2, 3] ---> ERROR

Si elige hacer una función en lugar de un programa completo, debe escribir un programa completo para demostrar la función en acción. Esto no contará para su puntaje completo. Además, se espera que los programas se ejecuten en un período de tiempo razonable. No planeo ingresar entradas excesivamente grandes, por lo tanto, siempre que su programa no esté haciendo una búsqueda de fuerza bruta en todo el árbol del juego, debería estar bien.

Como de costumbre, este es el código de golf, por lo que se aplican agujeros de bucle estándar , y las respuestas se cuentan en bytes.

Tabla de clasificación

Aquí hay un fragmento de pila para generar una tabla de clasificación regular y una descripción general de los ganadores por idioma.

Para asegurarse de que su respuesta se muestre, comience con un título, usando la siguiente plantilla de Markdown:

# Language Name, N bytes

¿Dónde Nestá el tamaño de su envío? Si mejora su puntaje, puede mantener los puntajes antiguos en el título, tachándolos. Por ejemplo:

# Ruby, <s>104</s> <s>101</s> 96 bytes

Mostrar fragmento de código

code-golf game James
fuente
¿Podemos suponer que la lista de entrada contiene al menos un número positivo?
Jakube
@Jakube sí, puedes.
James
Relacionado -ish?
FryAmTheEggman

Respuestas:

3

Pyth, 33 22 21 20 19 bytes

eS.e*<JxxFQbb,k-bJQ

Puedes probarlo en el compilador en línea aquí.

¡Gracias a Jakube por eliminar 12 bytes y a Maltysen por eliminar un byte adicional!

Esto imprime un movimiento ganador desde la posición actual. Si no hay movimientos ganadores, no imprime nada.

Usé el algoritmo en wikipedia . Aquí está el desglose:

  .e              Q    While enumerating every element in the input:
      J                    Assign variable J to:
        xFQ                 Every element of the input bitwise xor'ed together,
       x   b                bitwise xor'ed with the current element of the input
             ,             Create a tuple containing:
              k             The index of the current element, and
               -bJ          the difference between the current element and J
    *<J     b              Put that tuple into a list if J < b, otherwise put an empty tuple
 S                     Sort the list
e                      Print the last element of the list
Mike Bufardeci
fuente
3

Pyth, 23 bytes

eSs.em*,kd!xxxFQb-bdSbQ

Pruébelo en línea: demostración

Esto itera sobre todos los movimientos posibles e incluso ordena. Por lo tanto, tiene una complejidad de tiempo O(N*log(N))y una complejidad de memoria de O(N), donde Nes la suma de la lista de entrada o el número de elementos.

Debido a la complejidad del mal tiempo, esta podría no ser una respuesta válida. Aunque resuelve todos los juegos, puedes jugar en la vida real con objetos reales, al instante.

Explicación:

                          implicit: Q = input list
   .e                 Q   map each (index k, item b) of Q to:
     m              Sb      map each d of [1, 2, ..., b] to:
       ,kd                      the pair (k, d)
      *                       multiplied by
             xFQ                xor of all numbers in Q
            x   b               xor with b
           x     -bd            xor with b-d
          !                     not (1 if xor==0 else 0)

So the input [1, 2, 0, 0, 5] gives [[[]], [[], []], [], [], [[], [4, 2], [], [], []]]

  s                       add all lists to one big list
 S                        sort

Now it looks like this: [[], [], [], [], [], [], [], [4, 2]]

e                         pick the last element and print
Jakube
fuente
3

CJam, 21 20 bytes

Guardado un byte en comparación con la versión original, y el manejo de errores también funciona ahora:

l~__:^f^.-_:g1#_@=S\

Pruébalo en línea

La entrada es una matriz CJam, por ejemplo:

[1 2 3 4 5]

Si no se encuentra una solución, se imprime -1 0, lo que cumple con mi comprensión de los requisitos de salida.

Explicación:

l~      Get input.
__      Make two copies for following operations.
:^      Reduce with xor operator, producing xor of all columns.
f^      xor all input values with the result. For each column, this calculates
        the value that the column would have to change to make the overall
        xor zero. Consider this the "target values".
.-      Subtract the target values from the input values.
_:g     Per element signum of difference between target value and input value.
1#      Find index with value 1, which is the first positive value.
_@=     Get the value at the index.
S\      Put a space between index and value.
Reto Koradi
fuente
1

Ruby, 95

->(a){r=[false,c=0]
a.each{|e|c^=e}
a.each_index{|i|(n=a[i]-(c^a[i]))>0&&n>r[1]?(r=[i,n]):0}
r}

Escribí 2 funciones anónimas separadas. El primero, asignado fen el programa a continuación, imprime todas las soluciones, y el segundo g(correspondiente a la puntuación anterior, ya que es más corto y más compatible con la especificación) devuelve solo la solución que requiere eliminar el mayor número.

en ambos casos, la suma de dígitos se totaliza en c. Luego, la matriz se repite y la expresión n=a[i]-(c^a[i])se usa para calcular el número de contadores que se eliminarán (obviamente, esto solo se puede hacer si excede cero).

en f, todas las soluciones posibles se imprimen (si cse encuentra 0, errorse imprime sin bucle). Me sorprendió ver que las diferentes pilas pueden requerir un número bastante diferente de contadores para eliminarse.

en gla matriz de salida rsolo se actualiza si el número de contadores que se eliminarán excede el número anterior. [pile index, number to be removed]se devuelve la matriz r = . Si no hay solución, el número de contadores que se eliminarán es siempre cero, rpermanece sin cambios y [false,0]se devuelve el valor inicial de r = .

Los ahorros menores son posibles si falsese pueden cambiar a, por ejemplo, "!"y si se puede devolver alguna solución válida en lugar de la más grande (eliminando &&n>r[1]).

Formateado en programa de prueba

f=->(a){
  c=0
  a.each{|e|c^=e}
  c<1?(p "error"):(a.each_index{
     |i|(n=a[i]-(c^a[i]))>0?(p"#{i},#{n}"):0
   })
}

g=->(a){
  r=[false,c=0]
  a.each{|e|c^=e}
  a.each_index{
     |i|(n=a[i]-(c^a[i]))>0&&n>r[1]?(r=[i,n]):0
  }
  r
}

#Change the following two lines according to the number of values youj want to use for testing.
t=[rand(15),rand(15),rand(15),rand(15)] #Generate some random numbers for testing.
t=[gets.to_i,gets.to_i,gets.to_i]       #User input. Delete this line if you want to test with random numbers.
print t,"\n"

f.call(t)
puts g.call(t)
Level River St
fuente
En realidad, porque r[1]siempre es al menos cero, creo que >0&&n>r[1]se puede acortar a>r[1]
Level River St
0

Mathematica, 73 bytes

{f=BitXor;p=Position[#,x_/;BitAnd[x,a=f@@#]==a][[1,1]],(n=#[[p]])-n~f~a}&
usuario202729
fuente
1
Qué. ¿Mathematica no tiene una construcción para esto?
Draco18s ya no confía en SE
0

JavaScript (ES6), 54 bytes

Devuelve el par [column, number]o falso

a=>a.some((n,i)=>r=(n-=n^eval(a.join`^`))>0&&[i,n])&&r

Pruébalo en línea!

Comentado

a =>                        // a[] = input array
  a.some((n, i) =>          // for each value n at position i in a[]:
    r = (                   //   save the result of the iteration in r
      n -=                  //   subtract from n:
        n ^ eval(a.join`^`) //     n XOR (all values in a[] XOR'ed together)
    ) > 0                   //   if the above value is positive:
    && [i, n]               //     yield the solution [i, n] and exit the some() loop
                            //   (otherwise: yield false and go on with the next value)
  ) && r                    // end of some(); return r
Arnauld
fuente