Votre but est d'écrire un joueur parfait pour le jeu de Wythoff's Nim .

Les règles du Nim de Wythoff

Le Nim de Wythoff est un jeu déterministe à deux joueurs joué avec deux piles de jetons identiques. Les joueurs alternent les tours, au cours desquels ils effectuent l'une de ces actions:

1. Retirez un ou plusieurs jetons de la première pile
2. Retirez un ou plusieurs jetons de la deuxième pile
3. Retirez un nombre égal de jetons (un ou plusieurs), à la fois de la première pile et de la deuxième pile.

Bien sûr, les piles ne peuvent pas devenir négatives, mais elles peuvent atteindre 0. Quel que soit le joueur qui enlève le dernier compteur, il gagne la partie.

Pour les plus géométriques, voici une formulation équivalente du jeu que vous pouvez jouer sur cette applet . Une seule reine commence sur un carré d'un échiquier quart infini dont le coin est en bas à gauche. Les joueurs alternent en déplaçant la reine, qui se déplace comme une reine d'échecs mais limitée à trois directions:

1. Vers le bas
2. La gauche
3. En diagonale vers le bas et à gauche

Celui qui déplace la reine dans le coin gagne.

Associer les coordonnées de la reine (avec coin (0,0) ) aux tailles des piles respectives, il est facile de voir que les deux jeux sont identiques.

Jeu parfait

(Vous pouvez ignorer cela si vous êtes familier avec les notions de jeu parfait et de coups gagnants.)

Puisque le Nim de Wythoff est un jeu fini et déterministe, il a une notion de jeu parfait . Un joueur parfait est une stratégie qui gagnera toujours d'une position théoriquement gagnée, c'est-à-dire une position dans laquelle il existe une stratégie qui garantit une victoire.

Pour être une stratégie gagnante, il suffit de se déplacer pour toujours passer à une position gagnante théorique pour le joueur qui vient de bouger, et donc le joueur qui ne passe pas ensuite. Les premières de ces positions gagnantes (également appelées positions froides ) sont (0,0), (1,2), (2,1), (3,5), (5,3). Voir l'article Wikipedia pour une explication d'un algorithme pour trouver une stratégie gagnante pour le Nim de Wythoff, ainsi qu'une formule pour générer des positions gagnantes.

Exigences du programme

Écrire un programme ou une fonction prend une position en entrée et sort un coup gagnant sous la forme de la position après ce coup. Le moins d'octets gagne.

S'il n'y a pas de coup gagnant, c'est-à-dire que la position est une perte théorique, votre programme devrait l'indiquer et être annulé.

Votre programme doit s'exécuter dans un délai raisonnable. Ainsi, une recherche exponentielle récursive d'arbre de jeu ne suffira pas. Si vous souhaitez précalculer et coder en dur une stratégie, c'est très bien.

Contribution

Une paire (i,j)de nombres non négatifs représentant au maximum la taille des tas 99. Cela peut être deux nombres, un tuple, une liste ou tout autre conteneur que vous préférez.

Production

Imprimez ou affichez la position après votre déménagement, à nouveau sous la forme de deux chiffres ou d'un conteneur de celle-ci. Cela doit être un mouvement légal vers une position gagnante. S'il y a plusieurs de ces mouvements, tout le monde va bien, mais un seul.

S'il n'y a pas de coup gagnant, vous devez l'indiquer dans la sortie. Toute sortie comme False, None, 0, ou (-1,-1)fera, aussi longtemps que ce n'est pas une situation juridique, et est la même pour chaque entrée perdante.

Exemple d'exécutions

f(5,0)   = (0,0)
f(2,2)   = (1,2)   # Or (2,1) or (0,0) 
f(1,2)   = False
f(13,9)  = (13,8)  # Or (10,6)
f(10,6)  = False
f(5,10)  = (5,3)
f(25,30) = (8,13)    

Haskell, 167 165 caractères

c p=o p:c(o p:p)
o p=[(a,b)|a<-[0..],b<-[0..a],(a,b)?p==[]]!!0
(a,b)?p=[y|y@(c,d)<-p,c==a||c==b||d==b||a+d==b+c]
f x@(a,b)|a<b=f(b,a)|x?c[]!!0==x=(0,-1)|1>0=x?c[]!!0

L'algorithme est inefficace, mais il s'exécute toujours dans une seconde (mais pas dans la console interactive) pour les entrées <100.

Explication:

c p=o p:c(o p:p)

La liste des positions froides pour un ensemble de positions froides précédentes est une position froide suivie de la liste des positions froides pour cette position et les précédentes (Inefficacité: cette position est générée deux fois)

o p=[(a,b)|a<-[0..],b<-[0..a],(a,b)?p==[]]!!0

Une position froide est la première paire de sorte qu'aucune position froide ne peut être atteinte à partir de cette paire (inefficacité: nous devrions plutôt rechercher à partir de la paire précédente)

(a,b)?p=[y|y@(c,d)<-p,c==a||c==b||d==b||a+d==b+c]

Les positions accessibles à partir d'une paire sont celles telles que leurs premiers éléments correspondent, leurs seconds éléments correspondent, leurs différences correspondent ou le plus petit tas avant la suppression est le plus grand tas après la suppression.

f x@(a,b)|a<b=f(b,a)
         |x?c[]!!0==x=(0,-1)
         |1>0=x?c[]!!0

(méthode principale) Si les tas sont dans le mauvais ordre, échangez-les. Sinon, si la première position froide accessible depuis une position est la position elle-même, indiquer l'échec (idéalement, on reviendrait à la Maybe (Int,Int)place). Sinon, retournez cette position froide (Inefficacité: ladite paire est recherchée deux fois. Pire, la liste des positions froides est générée deux fois)

GolfScript ( 63 57 octets)

{\]zip{~-}%0|$(!*,1=}+1,4*{..,,^[(.@,2/+.2$]+}38*2/?0]0=`

Attend l'entrée de stdin dans le formulaire [a b]et laisse la sortie sur stdout dans ce formulaire ou 0s'il s'agit d'une position perdante. Démo en ligne

Aperçu

,4*{..,,^[(.@,2/+.2$]+}38*2/

calcule une liste de positions froides (y compris la version inversée [b a]pour chaque position froide [a b]) à l'aide de la propriété de séquence Beatty .

?Recherche ensuite la première position froide satisfaisant le bloc créé par

{\]zip{~-}%0|$(!*,1=}+

qui fondamentalement vérifie que la position est accessible à partir de la position d'entrée en calculant la différence de vecteur et ensuite vérifier qu'il est soit [0 x], [x 0]ou [x x]pour certains x > 0. IMO ce test est le bit de plus habiles: 0|$forces toute matrice dans l' un de ces formats sous la forme [0 x]tandis que la cartographie [0 0]à [0], [a b]où ni , ani best 0un réseau à trois éléments, et [-x 0]ou [-x -x]à [-x 0]. (!*,1=Vérifie ensuite que nous avons [0 x].

Enfin, 0]0=`le cas de secours et le formatage pour la sortie.

Pyth 57 58 61 62

K1.618Jm,s*dKs*d*KKU39M<smf|}TJ}_TJm,-Ghb-Hebt^,0hk2U99 1

Essayez-le en ligne.

Assez similaire aux autres réponses, mais cette page wikipedia ne donnait pas grand-chose d'autre à faire;) Le nombre magique 39est le nombre de positions froides avec des valeurs < 99.

Définit une fonction gque vous pouvez appeler comme g 30 25. Retourne []pour échec, [(13,8)]en cas de succès.

Explication

K1.618                            : K=phi (close enough for first 39 values)
      Jm,s*dKs*d*KKU39            : J=cold positions with the form (small,big)
M<s                              1: Define g(G,H) to return this slice: [:1] of the list below 
   mf|}TJ}_TJ                     : map(filter: T or reversed(T) in J, where T is each member of..
             m,-Ghb-Hebt^,0hk2    : [(G H) - (0 x+1),(x+1 0) and (x+1 x+1)]
                              U99 : for each x from 0 - 98

Javascript ES6 - 280 octets

Minifié

r=x=>~~(x*1.618);g=(y,x)=>y(x)?g(y,x+1):x;s=A=>A?[A[1],A[0]]:A;f=(a,b)=>j([a,b])||j([a,b],1);j=(A,F)=>l(A,F)||s(l(s(A),F));l=(A,F)=>([a,b]=A,c=(F&&a+b>=r(b)&&(e=g(x=>a+b-2*x-r(b-x),0))?[a-e,b-e]:(e=g(x=>r(a+x)-2*a-x,0))+a<b?[a,a+e]:(e=r(b)-b)<a?[e,b]:0),c&&r(c[1]-c[0])==c[0]?c:0)

Étendu

r = x => ~~(x*1.618);
g = (y,x) => y(x) ? g(y,x+1) : x;
s = A =>A ? [A[1],A[0]] : A;
f = (a,b) => j([a,b]) || j([a,b],1);
j = (A,F) => l(A,F) || s(l(s(A),F));
l = (A,F) => (
    [a,b] = A,
    c = (
        F && a+b >= r(b) && (e = g( x => a+b - 2*x - r(b - x), 0 )) ? [a-e,b-e] :
        (e = g( x => r(a+x) - 2*a - x, 0)) + a < b ? [a,a+e] :
        (e = r(b) - b) < a ? [e,b] : 0
    ),
    c && r(c[1] - c[0]) == c[0] ? c : 0
);

Algorithme agréable et rapide. S'exécute en O (n), mais s'exécuterait en temps constant si ce n'était pour une boucle d'économie d'octets. La boucle est implémentée comme un incrémenteur récursif, donc le script échouera finalement avec une erreur de récursivité pour n dans les centaines ou les milliers. Utilise la même propriété de séquence Beatty que M. Taylor mentionne, mais plutôt que de calculer la séquence, elle passe simplement au (x) terme (s) correct (s).

Fonctionne correctement sur toutes les entrées de test et plusieurs dizaines en plus de celles que j'ai testées.

La fonction à invoquer est f. Il renvoie un tableau en cas de succès et un 0abandon.

Perl 5-109 (avec 2 drapeaux)

#!perl -pl
for$a(@v=0..99){for$b(@v){$c=$a;$d=$b;${$:="$a $b"}||
map{$$_||=$:for++$c.$".++$d,"$a $d","$c $b"}@v}}$_=$$_

Usage:

$ perl wyt.pl <<<'3 5'

$ perl wyt.pl <<<'4 5'
1 2

Calcule simplement la solution pour chaque entrée possible, puis ne fait qu'une seule recherche.