fundo

No jogo de Nim , os jogadores alternam a remoção de "pedras" de "pilhas": em cada turno, um jogador deve remover entre uma e todas as pedras de uma única pilha. O objetivo de Nim é pegar a última pedra ou, na variante errada, forçar seu oponente a fazê-lo - no entanto, as estratégias são quase idênticas.

Nim faz um divertido jogo de bar. Você pode usar palitos de fósforo ou moedas para as "pedras" e as "pilhas" normalmente dispostas em uma linha. Abaixo está uma configuração clássica com pilhas de 1, 3, 5 e 7:

Se você nunca jogou Nim antes, tente sua mão antes de tentar este desafio. Aqui está uma versão chamada "Pearls Before Swine" .

Estratégia

A estratégia ideal em Nim é complicada o suficiente para que a maioria dos leigos perca consistentemente para um especialista, mas simples de descrever com aritmética binária .

Fazer operações binárias mentais de XOR, no entanto, é difícil, por sorte existe uma maneira equivalente de visualizar a estratégia correta que é mais fácil de implementar em tempo real, mesmo quando está bêbado.

Existem apenas três etapas:

1. Agrupe mentalmente as "pedras" em cada linha em subgrupos cujos tamanhos são potências de 2, começando com o maior tamanho possível: 8, 4, 2 e 1 são suficientes para a maioria dos jogos.
2. Tente combinar cada grupo com um gêmeo em outra linha, para que cada grupo tenha um par.
3. Se isso não for possível, remova "pedras" não emparelhadas de uma única linha (isso sempre será possível - consulte o link da Wikipedia para saber o porquê) para que a etapa 2. se torne possível.

Ou, disse de outra maneira: "Remova algumas pedras de uma única pilha, de modo que, se você agrupar as pilhas em potências de 2, todos os grupos poderão ser emparelhados com um grupo em outra pilha". Com a ressalva de que você não pode dividir potências maiores de 2 em potências menores - por exemplo, você não pode agrupar uma linha com 8 pedras em dois grupos de 4.

Por exemplo, veja como você visualizaria o quadro acima:

Este tabuleiro é perfeitamente equilibrado, então você quer que seu oponente se mova primeiro.

O desafio

Dada uma lista de números inteiros positivos que representam o tamanho das "pilhas" de Nim, retorne uma visualização em texto sem formatação do painel Nim, conforme visto por um especialista.

O que constitui uma visualização válida é melhor explicado pelo exemplo, mas você deve:

1. Designe um caractere distinto para cada "subgrupo de potência de 2" e seu par (subgrupos não emparelhados não se qualificam) e use esse caractere para representar as "pedras" no subgrupo e no par.
2. Representam qualquer "pedras" desemparelhados (ou seja, aqueles especialista iria remover quando se joga normais - não misere - Nim) usando um hífen: -.

Haverá várias maneiras de obter uma visualização válida e todas são válidas. Vamos trabalhar com alguns casos de teste:

Casos de teste

Entrada: 1, 3, 5, 7

Saída possível 1:

A
BBA
CCCCD
CCCCBBD

Opcionalmente, você pode incluir espaços entre os caracteres, bem como linhas em branco entre as linhas:

Saída possível 2:

A

B B A

C C C C D

C C C C B B D

Entrada: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

A ordem e a escolha dos caracteres podem ser o que você quiser:

Saída possível 1:

G
E E
E E G
C C C C
C C C C F
B B B B D D
B B B B D D F
H H I - - - - -
A A A A A A A A I
A A A A A A A A H H

Os símbolos Unicode também estão ok:

Saída possível 2:

◎
◈  ◈
◈  ◈  ◎
△  △  △  △
△  △  △  △  ◉
◐  ◐  ◐  ◐  ◀  ◀
◐  ◐  ◐  ◐  ◀  ◀  ◉
▽  ▽  ◒  -  -  -  -  -
▥  ▥  ▥  ▥  ▥  ▥  ▥  ▥  ◒ 
▥  ▥  ▥  ▥  ▥  ▥  ▥  ▥  ▽  ▽  

Entrada: 7

Das regras, segue-se que qualquer "pilha única" deve ser completamente removida.

Saída possível 1:

-------

Saída possível 2:

- - - - - - -

Entrada: 5, 5

Saída possível:

A A A A B
A A A A B

Regras adicionais

• Este é o código de golfe com regras padrão. O menor código vence.
• A entrada é flexível e pode ser feita em qualquer forma de lista conveniente para você.
• A saída também é flexível, como ilustram os exemplos acima. As variações mais razoáveis ​​serão permitidas. Pergunte se você não tiver certeza sobre alguma coisa.

Ruby, 169 164 148 bytes

->a{s=eval a*?^
c=?@
m={}
a.map{|x|z=x-(x^s);[$><<?-*z,x-=z,s=0]if z>0
n=1
eval'x&1>0?[$><<(m[n]||c.next!)*n,m[n]=!m[n]&&c*1]:0;n*=2;x/=2;'*x
puts}}

Experimente online!

Primeiro, inicializamos

• o nim-sum com s=eval a*?^(que é menor que a.reduce:^)
• a variável c, que armazena o primeiro caractere exclusivo não utilizado
• um mapa mque mapeia dois comprimentos para caracteres usados ​​para representá-los

Em seguida, percorrendo cada pilha, executamos o seguinte:

z=x-(x^s);[$><<?-*z,x-=z,s=0]if z>0

De acordo com a estratégia da Wikipedia , se a pilha XOR de nim-sum for menor que a pilha , devemos remover pedras dessa pilha para que seu comprimento se torne uma pilha XOR de nim-soma . Armazenando a diferença na variável z, podemos testar para ver se essa diferença é positiva e, em caso afirmativo, 1.) imprimir muitos traços, 2.) subtraí-la da pilha e 3.) definir a variável nim-sum como zero para evitar mais remoção de pedras.

n=1
eval'[...];n*=2;x/=2;'*x

Agora nós "laço" sobre cada bit e manter o controle de seus valores dividindo-se repetidamente xpor 2e multiplicando o acumulador npor 2. O loop é, na verdade, um xtempo avaliado de string , que é muito maior do log2(x)que o necessário, mas nenhum dano é causado (além da ineficiência). Para cada bit, executamos o seguinte se o bit for 1 ( x&1>0):

$><<(m[n]||c.next!)*n

Imprima um caractere nvezes. Se já imprimimos um grupo não pareado dessas muitas pedras, use esse caractere; caso contrário, use o próximo caractere não utilizado (avançando cno local devido ao !).

m[n]=!m[n]&&c*1

Se m[n]existir (ou seja, acabamos de concluir um par), então m[n]é redefinido. Caso contrário, apenas começamos um novo par, então defina m[n]o personagem que usamos ( *1é uma maneira curta de fazer uma cópia c).

Python 2 , 150 196 206 bytes

def f(p):
 c=48;s=[l*'.'for l in p];m=2**len(bin(l))
 while m:
  if sum(m*'.'in l for l in s)>1:
   for i,l in enumerate(s):s[i]=l.replace('.'*m,chr(c)*m,`s`.count(chr(c)*m)<2)
   c+=1
  else:m/=2
 return s

Experimente online!

JavaScript (ES6), 215 bytes

f=
(a,c=0,x=eval(a.join`^`),i=a.findIndex(e=>(e^x)<e),b=a.map(_=>``),g=e=>(d=e&-e)&&a.map((e,i)=>e&d&&(a[i]-=d,b[i]=(c++>>1).toString(36).repeat(d)+b[i]))&&g(e-d))=>g(eval(a.join`|`),b[i]='-'.repeat(a[i]-(a[i]^=x)))||b

<textarea oninput=o.textContent=/\d/.test(this.value)?f(this.value.match(/\d+/g)).join`\n`:``></textarea><pre id=o>

Visualiza apenas até 36 caracteres diferentes. Estou aliviado por isso funcionar 1, 3, 4, 5.

Limpo , 454 bytes

ainda jogando golfe

import StdEnv,Text,Data.List
$p=join"\n"[{#toChar c+'-'\\c<-e}\\e<-[take i(e++[0,0..])\\e<-r[[~c\\c<-reverse e,_<-[1..c]]\\e<-hd[q\\q<-foldr(\h t=[[a:b]\\a<-h,b<-t])[[]][[c\\c<-subsequences(takeWhile((>=)k)(iterate((*)2)1))|sum c<=k]\\k<-p]|sum[1\\a<-q&b<-p|sum a<>b]<2&&foldr(bitxor)0(flatten q)==0]]1&i<-p]]
r[]_=[]
r[h:t]n|all((<)0)h=[h:r t n]
#[m:_]=removeDup[e\\e<-h|e<0]
#(a,[x:b])=span(all((<>)m))t
=r([[if(e==m)n e\\e<-k]\\k<-[h:a]++[x]]++b)(n+1)

Experimente online!

Define a função $ :: [Int] -> String, pegando o tamanho da pilha e retornando uma sequência na qual -denota pedras a serem removidas, e os grupos são representados por caracteres ASCII ascendentes de -. Se grupos suficientes forem necessários, os personagens retornarão eventualmente, e devido aofoldr fato, requer mais de um gigabyte de memória para executar o segundo caso de teste.

Versão recuada da compreensão gigante:

$p=join"\n"[
    {#
        toChar c+'-'
        \\c<-j
    }
    \\j<-[
        take i(e++[0,0..])
        \\e<-r[
            [
                ~c
                \\c<-reverse e
                ,_<-[1..c]
            ]
            \\e<-hd[
                q
                \\q<-foldr(\h t=[
                    [a:b]
                    \\a<-h
                    ,b<-t
                ])[[]][
                    [
                        c
                        \\c<-subsequences(takeWhile((>=)k)(iterate((*)2)1))
                        |sum c<=k
                    ]
                    \\k<-p
                ]
                |sum[
                    1
                    \\a<-q
                    &b<-p
                    |sum a<>b
                ]<2&&foldr(bitxor)0(flatten q)==0
            ]
        ]1
        &i<-p
    ]
]