Chomp est un jeu à deux joueurs avec une configuration d'un rectangle de pièces. Chaque joueur retire à tour de rôle n'importe quelle pièce, ainsi que toutes les pièces au-dessus et à sa droite. Celui qui prend la pièce en bas à gauche perd. Il peut être prouvé assez facilement que le premier joueur a toujours un coup gagnant (sauf avec un rectangle 1 par 1); trouve le.

1. L'entrée correspond aux dimensions du rectangle (deux chiffres)
2. La sortie est l'emplacement du coup gagnant (deux chiffres)
3. S'il y a plus d'un coup gagnant, vous pouvez en sortir n'importe lequel.

C'est le golf de code; le code le plus court (n'importe quelle langue) gagne.

Exemples

Remarque: Les sorties ne sont que les deux nombres; l'art ASCII ci-dessous est juste pour démontrer ce que signifient les chiffres.

Entrée: 5 3 (index basés sur 1 à partir du coin inférieur gauche)

Sortie: 4 3

XXX--
XXXXX
XXXXX

Entrée: 4 4

Sortie: 2 2

X---
X---
X---
XXXX

Prime

Soustrayez 15 caractères de votre score si vous produisez tous les coups gagnants. Chaque paire de numéros doit être séparée par une nouvelle ligne.

GolfScript, 82 ( 108 97 caractères - 15 bonus)

~),1/{{:F$0=),{F\+}/}%}@(*(0*\{1${1$\{\(@<},=},{1$\{\(@>},+(-!},:Y!{.,/+0}*;}/;Y{.-1=.@?)' '@)n}/

Comme je ne connaissais aucune heuristique, cette solution effectue une recherche exhaustive sur l'espace de la solution. Vous pouvez essayer le code en ligne . Bien que l'implémentation soit très efficace, l'espace de recherche croît très rapidement avec l'augmentation des entrées.

Exemples:

> 5 3
4 3

> 5 4
3 3

> 6 6
2 2

Comme mentionné ci-dessus, l'implémentation ne repose pas sur la récursivité mais visite chaque nœud de l'espace de recherche une seule fois. Vous trouverez ci-dessous une version annotée du code qui décrit les blocs de construction plus en détail.

La représentation d'une seule planche de taille w * h est donnée par une liste de w nombres compris entre 0 et h . Chaque numéro donne le nombre de pièces dans la colonne correspondante. Ainsi, une configuration valide est une liste où les nombres n'augmentent pas du début à la fin (à chaque déplacement, vous vous assurez que toutes les colonnes à droite sont au plus aussi hautes que celles choisies).

~                   # Evaluate the input (stack is now w h)

# BUILDING THE COMPLETE STATE SPACE
# Iteratively builds the states starting with 1xh board, then 2xh board, ...

),1/                # Generate the array [[0] [1] ... [h]] which is the space for 1xh
{                   # This loop is now ran w-1 times and each run adds all states for the 
                    # board with one additional column
  {                 # The {}/] block simply runs for each of the existing states
    :F$0=           #   Take the smallest entry (which has to be the last one)
    ),              #   For the last column all values 0..x are possible
    {F\+}/          #     Append each of these values to the smaller state
  }%
}@(*

# The order ensures that the less occupied boards are first in the list.
# Thus each game runs from the end of the list (where [h h ... h] is) to 
# the start (where [0 0 ... 0] is located).

# RUN THROUGH THE SEARCH SPACE
# The search algorithm therefore starts with the empty board and works through all
# possible states by simply looping over this list. It builds a list of those states
# which are known as non-winning states, i.e. those states where a player should 
# aim to end after the move

(                   # Skips the empty board (which is a winning configuration)
0*\                 # and makes an empty list out of it (which will be the list of
                    # known non-winning states (initially empty))
{                   # Loop over all possible states
  1$                #   Copy of the list of non-winning states
  {                 #   Filter those which are not reachable from the current state,
                    #   because at least one column has more pieces that the current
                    #   board has
    1$\{\(@<},=
  },
  {                 #   Filter those which are not reachable from the current state,
                    #   because no valid move exists
    1$\{\(@>},+     #     Filter those columns which are different between start and
                    #     end state
    (-!             #     If those columns are all of same height it is possible to move
  },
  :Y                #   Assign the result (list of all non-winning states which are
                    #   reachable from the current configuration within one move)
                    #   to variable Y

  !{                #   If Y is non-empty this one is a winning move, otherwise 
                    #   add it to the list
    .,/+
    0               #     Push dummy value
  }*;
}/
;                   # Discard the list (interesting data was saved to variable Y)

# OUTPUT LOOP
# Since the states were ordered the last one was the starting state. The list of 
# non-winning states were saved to variable Y each time, thus the winning moves 
# from the initial configuration is contained in this variable.

Y{                  # For each item in Y
  .-1=.@?)          #   Get the index (1-based) of the first non-h value
  ' '               #   Append a space
  @)                #   Get the non-h value itself (plus one)
  n                 #   Append a newline
}/

Python 2 3, 141-15 = 126

def win(x,y):w([y]*x)
w=lambda b,f=print:not[f(r+1,c+1)for r,p in enumerate(b)for c in range(p)if(r+c)*w(b[:r]+[min(i,c)for i in b[r:]],max)]

Recherche minimax par force brute. Pour chaque coup possible, nous voyons récursivement si l'adversaire peut gagner après avoir fait ce coup. Assez faiblement golfé; quelqu'un d'autre devrait pouvoir faire beaucoup mieux. Cela ressemble à un travail pour APL.

• winest l'interface publique. Il prend les dimensions du tableau, le convertit en une représentation du tableau et le transmet àw .
• west l'algorithme minimax. Il prend un état de plateau, essaie tous les coups, construit une liste dont les éléments correspondent aux coups gagnants et retourne True si la liste est vide. Avec la valeur par défaut f=print, la création de la liste a pour effet secondaire d'imprimer les coups gagnants. Le nom de la fonction avait plus de sens lorsqu'il renvoyait une liste de coups gagnants, mais j'ai ensuite déplacé l' notavant de la liste pour économiser de l'espace.
• for r,p in enumerate(b)for c in xrange(p) if(r+c): Itérer sur tous les mouvements possibles. 1 1est traité comme un pas légal, simplifiant un peu le cas de base.
• b[:r]+[min(i,c)for i in b[r:]]: Construire l'état du plateau après le mouvement représenté par des coordonnées retc .
• w(b[:r]+[min(i,c)for i in b[r:]],max): Recurse pour voir si le nouvel état est un état perdant. maxest la fonction la plus courte que j'ai pu trouver qui prendrait deux arguments entiers et ne se plaindrait pas.
• f(r+1,c+1): Si fest imprimer, imprime le mouvement. Peu importef soit, il produit une valeur pour remplir la longueur de la liste.
• not [...]: notrenvoie Truepour les listes vides et Falsepour les non vides.

Code Python 2 original, complètement non golfé, y compris la mémorisation pour gérer des entrées beaucoup plus importantes:

def win(x, y):
    for row, column in _win(Board([y]*x)):
        print row+1, column+1

class MemoDict(dict):
    def __init__(self, func):
        self.memofunc = func
    def __missing__(self, key):
        self[key] = retval = self.memofunc(key)
        return retval

def memoize(func):
    return MemoDict(func).__getitem__

def _normalize(state):
    state = tuple(state)
    if 0 in state:
        state = state[:state.index(0)]
    return state

class Board(object):
    def __init__(self, state):
        self.state = _normalize(state)
    def __eq__(self, other):
        if not isinstance(other, Board):
            return NotImplemented
        return self.state == other.state
    def __hash__(self):
        return hash(self.state)
    def after(self, move):
        row, column = move
        newstate = list(self.state)
        for i in xrange(row, len(newstate)):
            newstate[i] = min(newstate[i], column)
        return Board(newstate)
    def moves(self):
        for row, pieces in enumerate(self.state):
            for column in xrange(pieces):
                if (row, column) != (0, 0):
                    yield row, column
    def lost(self):
        return self.state == (1,)

@memoize
def _win(board):
    return [move for move in board.moves() if not _win(board.after(move))]

Démo:

>>> for i in xrange(7, 11):
...     for j in xrange(7, 11):
...         print 'Dimensions: {} by {}'.format(i, j)
...         win(i, j)
...
Dimensions: 7 by 7
2 2
Dimensions: 7 by 8
3 3
Dimensions: 7 by 9
3 4
Dimensions: 7 by 10
2 3
Dimensions: 8 by 7
3 3
Dimensions: 8 by 8
2 2
Dimensions: 8 by 9
6 7
Dimensions: 8 by 10
4 9
5 6
Dimensions: 9 by 7
4 3
Dimensions: 9 by 8
7 6
Dimensions: 9 by 9
2 2
Dimensions: 9 by 10
7 8
9 5
Dimensions: 10 by 7
3 2
Dimensions: 10 by 8
6 5
9 4
Dimensions: 10 by 9
5 9
8 7
Dimensions: 10 by 10
2 2

Perl 6: 113 108 caractères - 15 = 93 points

Celui-ci était difficile! Voici la version non mise en cache, qui est techniquement correcte mais prendra beaucoup de temps pour les entrées non triviales.

sub win(*@b){map ->\i,\j{$(i+1,j+1) if @b[i][j]&&!win @b[^i],@b[i..*].map({[.[^j]]})},(^@b X ^@b[0])[1..*]}

Cela fonctionne exactement comme l'implémentation Python de @ user2357112 (votez pour lui / elle, je n'aurais pas pu comprendre cela sans son travail!) Sauf que win () prend une planche (tableau) Chomp au lieu d'une largeur et d'une longueur. Il peut être utilisé comme:

loop {
    my ($y, $x) = get.words;
    .say for @(win [1 xx $x] xx $y)
}

Une version avec mémorisation, qui peut réellement gérer des entrées décentes (pas optimisées pour la lisibilité, cependant):

my %cache;
sub win (*@b) {
    %cache{
        join 2, map {($^e[$_]??1!!0 for ^@b[0]).join}, @b
    } //= map ->\i,\j{
        $(i+1,j+1) if @b[i][j] and not win
            @b[^i], @b[i..*].map({[.[^(* min j)]]}).grep: +*;
    },(^@b X ^@b[0])[1..*]
}