Encontre o movimento nim ideal

8

O jogo

Nim é um jogo de estratégia matemática, onde 2 jogadores se revezam retirando itens de montes distintos. Por sua vez, você deve pegar pelo menos um item e pode pegar quantos quiser, desde que você pegue apenas um monte. O jogador que pega o último item ganha! Este é um jogo resolvido. Antes de eu entrar na estratégia, você pode tentar jogá-la online aqui .

A estratégia

A estratégia vencedora é explicada com muita clareza e simplicidade aqui neste link. Vou explicar usando termos um pouco mais técnicos. A maneira de ganhar este jogo é sempre levar o máximo de itens possível para que a soma digital-binária seja sempre 0. Considere o seguinte quadro:

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

Para encontrar a soma digital-binária desta placa, você deve:

  1. Converta o número em cada linha para binário. Portanto, temos 001, 010, 011, 100 e 101.

  2. Adicione todos os números juntos e ignore qualquer transporte.

     001
 010
 011
 100
+101
----
 001

    Você também pode bit a bit xor cada número, e isso alcançará o mesmo resultado.

Agora, se a soma nesta configuração atual for 001, então este ainda não é um quadro vencedor. Mas você pode torná-lo um quadro vencedor! Se retirarmos um item das colunas 1, 3 ou 5, a soma será 0. Este é um tabuleiro vencedor, o que significa que, desde que você não cometa um erro, o próximo jogador a perder perderá. Portanto, você deve sempre terminar seu turno com um quadro vencedor. Digamos que você retire um item da coluna 5. Agora o quadro fica assim:

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

Contanto que você não estrague tudo, você tem uma vitória garantida. Não há nada que seu oponente possa fazer para impedi-lo. Vamos dizer que ele pega todos os itens da coluna 5.

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

Onde você iria a seguir? Não role para baixo ainda e tente descobrir por si mesmo.

No momento, a soma é 100. A melhor jogada (e a única jogada vencedora) seria pegar tudo da coluna 4. Isso deixaria o quadro assim:

     * 
   * * 
 * * * 
 1 2 3 4 5

e a soma assim

 001
 010
+011
----
 000

isso significa que você está em um tabuleiro vencedor! Yay!

O desafio

Você deve escrever um programa ou função que, dado um quadro nim, retorne uma jogada vencedora ou um valor falsey se não houver uma jogada vencedora.

Sua entrada:

  • Será o formato de lista nativa do seu idioma, onde cada item da lista corresponde ao número de itens em uma determinada coluna. Por exemplo, a entrada {4, 2, 1, 0, 3} corresponde ao seguinte quadro nim:

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

  • (opcional) O número de linhas. (Para idiomas como C / C ++, onde isso não é conhecido na própria lista.)

Sua saída:

  • Pode ir para STDOUT ou retornar da função

  • Deve haver dois números: 1) a coluna da qual estamos removendo (lembre-se de que as colunas são indexadas em 0) e 2) o número de itens a serem removidos dessa linha. Pode ser uma matriz de dois itens, uma sequência de dois números, etc. Lembre-se de que a resposta pode ter mais de 2 dígitos, portanto, retornar a sequência "111" não é válida porque não está claro se isso significa "Remover um item da coluna onze" ou "Remover onze itens da coluna um". "1,11" ou "11,1" seriam ambos aceitáveis.

  • Se não houver resposta, retorne ou imprima um valor falso. Se o seu idioma puder retornar apenas um tipo de variável (novamente, como C / C ++), um número negativo para a coluna ou 0 ou menos para o número a ser removido serão valores aceitáveis ​​de falsey.

  • Se o número da coluna ou o número a remover for muito grande, isso será visto como uma saída inválida.

Amostras de entradas / saídas

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

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

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

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

Se você optar por executar uma função em vez do programa completo, deverá escrever um programa completo para demonstrar a função em ação. Isso não conta para a sua pontuação completa. Além disso, espera-se que os programas sejam executados em um período de tempo razoável. Não estou planejando inserir entradas excessivamente grandes; portanto, enquanto seu programa não estiver fazendo uma pesquisa de força bruta por toda a árvore do jogo, você deverá ficar bem.

Como de costume, isso é código-golfe, então as lacunas padrão se aplicam e as respostas são contadas em bytes.

Entre os melhores

Aqui está um snippet de pilha para gerar uma classificação regular e uma visão geral dos vencedores por idioma.

Para garantir que sua resposta seja exibida, inicie-a com um título, usando o seguinte modelo de remarcação:

# Language Name, N bytes

onde Nestá o tamanho do seu envio. Se você melhorar sua pontuação, poderá manter as pontuações antigas no título, identificando-as. Por exemplo:

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

Mostrar snippet de código

code-golf game James
fonte
Podemos supor que a lista de entrada contenha pelo menos um número positivo?
Jakube
@ Jakube sim, você pode.
James
Relacionado -ish?
FryAmTheEggman

Respostas:

3

Pitão, 33 22 21 20 19 bytes

eS.e*<JxxFQbb,k-bJQ

Você pode experimentá-lo no compilador online aqui.

Obrigado a Jakube por remover 12 bytes e Maltysen por remover um byte adicional!

Isso imprime um movimento vencedor da posição atual. Se não houver movimentos vencedores, ele não imprime nada.

Eu usei o algoritmo na wikipedia . Aqui está o detalhamento:

  .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
fonte
3

Pitão, 23 bytes

eSs.em*,kd!xxxFQb-bdSbQ

Experimente online: Demonstração

Isso repete todos os movimentos possíveis e até faz a classificação. Portanto, possui uma complexidade de tempo O(N*log(N))e uma memória de O(N), onde Né a soma da lista de entrada ou o número de itens.

Devido à complexidade do tempo ruim, essa pode não ser uma resposta válida. Embora resolva todos os jogos, você pode jogar na vida real com objetos reais instantaneamente.

Explicação:

                          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
fonte
3

CJam, 21 20 bytes

Salvo um byte em comparação com a versão original, e o tratamento de erros também funciona agora:

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

Experimente online

A entrada é uma matriz CJam, por exemplo:

[1 2 3 4 5]

Se nenhuma solução for encontrada, ela será impressa -1 0, o que atenderá ao meu entendimento dos requisitos de saída.

Explicação:

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
fonte
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}

Eu escrevi 2 funções anônimas separadas. A primeira, atribuída fno programa abaixo, imprime todas as soluções, e a segunda g(correspondente à pontuação acima, pois é mais curta e mais compatível com a especificação) retorna apenas a solução que requer a remoção do maior número.

nos dois casos, a soma dos dígitos é totalizada em c. Em seguida, a matriz é repetida e a expressão n=a[i]-(c^a[i])é usada para calcular o número de contadores a serem removidos (obviamente, isso só pode ser feito se exceder zero).

em f, todas as soluções possíveis são impressas (se cfor encontrado 0, errorsão impressas sem loop.) Fiquei surpreso ao ver que as pilhas diferentes podem exigir a remoção de um número bastante diferente de contadores.

na gmatriz de saída ré atualizada apenas se o número de contadores a serem removidos exceder o número anterior. a matriz r = [pile index, number to be removed]é retornada. Se não houver solução, o número de contadores a serem removidos é sempre zero, rpermanece inalterado e o valor inicial de r = [false,0]é retornado.

Economias menores são possíveis se falsepuderem ser alteradas para, por exemplo, "!"e se alguma solução válida, em vez da maior, puder ser retornada (excluindo &&n>r[1].)

Formatado no programa de teste

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
fonte
Na verdade, porque r[1]sempre é pelo menos zero, acho que >0&&n>r[1]pode ser reduzido para>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}&
user202729
fonte
1
O que. O Mathematica não tem um builtin para isso?
Draco18s não confia mais em SE
0

JavaScript (ES6), 54 bytes

Retorna o par [column, number]ou false

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

Experimente online!

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
fonte