Contexte

Dans le jeu de Nim , les joueurs alternent en retirant les "pierres" des "piles": à chaque tour, un joueur doit retirer entre une et toutes les pierres d'une seule pile. Le but de Nim est de prendre la dernière pierre ou, dans la variante misere, de forcer votre adversaire à le faire - cependant, il s'avère que les stratégies sont presque identiques.

Nim fait un jeu de bar amusant. Vous pouvez utiliser des allumettes ou des pièces pour les "pierres" et les "piles" sont généralement disposées en ligne. Vous trouverez ci-dessous une configuration classique avec des piles de 1, 3, 5 et 7:

Si vous n'avez jamais joué à Nim auparavant, vous pouvez vous y essayer avant de tenter ce défi. Voici une version appelée "Pearls Before Swine" .

Stratégie

La stratégie optimale dans Nim est suffisamment délicate pour que la plupart des profanes perdent systématiquement face à un expert, mais simple à décrire avec l' arithmétique binaire .

Cependant, effectuer des opérations XOR binaires mentales est difficile, donc heureusement, il existe un moyen équivalent de visualiser la bonne stratégie qui est plus facile à mettre en œuvre en temps réel, même lorsqu'il est ivre.

Il n'y a que trois étapes:

1. Regroupez mentalement les "pierres" de chaque ligne en sous-groupes dont les tailles sont des puissances de 2, en commençant par la plus grande taille possible: 8, 4, 2 et 1 suffisent pour la plupart des jeux.
2. Essayez de faire correspondre chaque groupe avec un jumeau d'une autre ligne, afin que chaque groupe ait une paire.
3. Si ce n'est pas possible, supprimez les "pierres" non appariées d'une seule ligne (ce sera toujours possible - voir le lien Wikipedia pour savoir pourquoi) afin que l'étape 2. devienne possible.

Ou, a dit une autre façon: "Retirez des pierres d'une seule pile de sorte que si vous regroupez ensuite les piles en pouvoirs de 2, tous les groupes peuvent être associés à un groupe dans une autre pile." Avec la mise en garde que vous ne pouvez pas diviser des pouvoirs plus grands de 2 en plus petits - par exemple, vous ne pouvez pas grouper une ligne avec 8 pierres en deux groupes de 4.

Par exemple, voici comment vous visualisez le tableau ci-dessus:

Ce plateau est parfaitement équilibré, vous voudrez donc que votre adversaire bouge en premier.

Le défi

Étant donné une liste d'entiers positifs représentant la taille des "piles" Nim, renvoyez une visualisation en texte brut de la carte Nim vue par un expert.

Ce qui constitue une visualisation valide est mieux expliqué par l'exemple, mais vous devez:

1. Attribuez un caractère distinct à chaque "sous-groupe power-of-2" et à sa paire (les sous-groupes non appariés ne sont pas qualifiés), et utilisez ce caractère pour représenter les "pierres" du sous-groupe et de la paire.
2. Représenter les « pierres » non appariés (c. -à ceux d' un expert supprimerait lors de la lecture normale - pas misere - Nim) à l' aide d' un trait d' union: -.

Il y aura plusieurs façons d'obtenir une visualisation valide, et toutes sont valides. Passons en revue quelques cas de test:

Cas de test

Entrée: 1, 3, 5, 7

Résultat possible 1:

A
BBA
CCCCD
CCCCBBD

Vous pouvez éventuellement inclure des espaces entre les caractères, ainsi que des lignes vides entre les lignes:

Résultat possible 2:

A

B B A

C C C C D

C C C C B B D

Entrée: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

L'ordre et le choix des personnages peuvent être ceux que vous aimez:

Résultat possible 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

Les symboles Unicode sont également corrects:

Résultat possible 2:

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

Entrée: 7

Il résulte des règles que toute "pile unique" doit être complètement supprimée.

Résultat possible 1:

-------

Résultat possible 2:

- - - - - - -

Entrée: 5, 5

Sortie possible:

A A A A B
A A A A B

Règles supplémentaires

• C'est du golf de code avec des règles standard. Le code le plus court gagne.
• La saisie est flexible et peut être effectuée sous la forme de liste qui vous convient.
• La sortie est également flexible, comme l'illustrent les exemples ci-dessus. Les variations les plus raisonnables seront autorisées. Demandez si vous n'êtes pas sûr de quelque chose.

Rubis, 169 164 148 octets

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

Essayez-le en ligne!

Tout d'abord, nous initialisons

• la somme nim avec s=eval a*?^(qui est plus courte que a.reduce:^)
• la variable c, qui stocke le premier caractère unique inutilisé
• une carte mqui mappe des longueurs de puissance de deux aux caractères utilisés pour les représenter

Ensuite, en bouclant sur chaque pile, nous exécutons ce qui suit:

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

Selon la stratégie de Wikipedia , si la pile XOR à somme nim est inférieure à la pile , nous devons retirer les pierres de cette pile de sorte que sa longueur devienne une pile XOR à somme nim . En stockant la différence dans la variable z, nous pouvons tester pour voir si cette différence est positive, et si c'est le cas 1.) imprimer autant de tirets, 2.) la soustraire de la pile, et 3.) définir la variable nim-sum sur zéro pour empêcher un retrait ultérieur de la pierre.

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

Maintenant, nous "bouclons" sur chaque bit et gardons une trace de leurs valeurs en divisant xpar 2et en multipliant l'accumulateur npar 2. La boucle est en fait une chaîne évaluée xfois, ce qui est bien plus long que log2(x)nécessaire, mais aucun mal n'est fait (à part l'inefficacité). Pour chaque bit, nous exécutons ce qui suit si le bit est 1 ( x&1>0):

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

Imprimer un caractère nfois. Si nous avons déjà imprimé un groupe non apparié de ces nombreuses pierres, utilisez ce caractère; sinon, utilisez le prochain caractère inutilisé (avancement csur place en raison du !).

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

S'il m[n]existait (c'est-à-dire que nous venons de terminer une paire), il m[n]est réinitialisé. Sinon, nous venons de commencer une nouvelle paire, donc définissez m[n]le caractère que nous avons utilisé ( *1c'est un moyen rapide de faire une copie de c).

Python 2 , 150 196 206 octets

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

Essayez-le en ligne!

JavaScript (ES6), 215 octets

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>

Visualise uniquement jusqu'à 36 caractères différents. Je suis soulagé que cela fonctionne 1, 3, 4, 5.

Nettoyer , 454 octets

toujours au golf

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)

Essayez-le en ligne!

Définit la fonction $ :: [Int] -> String, en prenant les tailles de pile et en retournant une chaîne où -dénoter les pierres à retirer, et les groupes sont représentés par des caractères ASCII ascendants -. Si suffisamment de groupes sont nécessaires, les personnages finiront par revenir en arrière et, à cause de foldrcela, il nécessite plus d'un gigaoctet de mémoire pour exécuter le deuxième cas de test.

Version en retrait de la compréhension géante:

$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
    ]
]