Chomp ist ein Zwei-Spieler-Spiel mit einem Aufbau aus einem Rechteck von Stücken. Jeder Spieler ist an der Reihe und entfernt ein beliebiges Teil sowie alle darüber und rechts davon befindlichen Teile. Wer das linke untere Stück nimmt, verliert. Es kann ziemlich leicht bewiesen werden, dass der erste Spieler immer einen Gewinnzug hat (außer bei einem 1-zu-1-Rechteck); finde es.

1. Eingabe ist die Abmessung des Rechtecks ​​(zwei Zahlen)
2. Ausgabe ist der Ort des Gewinnzugs (zwei Zahlen)
3. Wenn es mehr als einen Gewinnzug gibt, können Sie jeden davon ausgeben.

Das ist Code Golf; Der kürzeste Code (jede Sprache) gewinnt.

Beispiele

Hinweis: Die Ausgaben sind nur die beiden Zahlen; Die unten stehende ASCII-Grafik soll nur veranschaulichen, was die Zahlen bedeuten.

Eingabe: 5 3 (Indizes 1-basiert ab linker unterer Ecke)

Ausgabe: 4 3

XXX--
XXXXX
XXXXX

Eingabe: 4 4

Ausgang: 2 2

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

Bonus

Subtrahieren Sie 15 Zeichen von Ihrer Punktzahl, wenn Sie alle Gewinnzüge ausgegeben haben. Jedes Zahlenpaar muss durch eine neue Zeile getrennt werden.

GolfScript, 82 ( 108 97 Zeichen - 15 Bonus)

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

Da ich keine Heuristik kannte, führt diese Lösung eine umfassende Suche im Lösungsraum durch. Sie können den Code online ausprobieren . Obwohl die Implementierung sehr effizient ist, wächst der Suchraum mit zunehmender Eingabe sehr schnell.

Beispiele:

> 5 3
4 3

> 5 4
3 3

> 6 6
2 2

Wie oben erwähnt, beruht die Implementierung nicht auf Rekursion, sondern besucht jeden Knoten des Suchraums nur einmal. Im Folgenden finden Sie eine kommentierte Version des Codes, in der die Bausteine ​​ausführlicher beschrieben werden.

Die Darstellung einer einzelnen Tafel der Größe w * h ergibt sich aus einer Liste von w Zahlen im Bereich von 0 bis h . Jede Zahl gibt die Stückzahl in der entsprechenden Spalte an. Eine gültige Konfiguration ist also eine Liste, in der die Zahlen von Anfang bis Ende nicht ansteigen (bei jeder Bewegung stellen Sie sicher, dass alle Spalten rechts höchstens so hoch sind wie die ausgewählte).

~                   # 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)]

Brute-Force-Minimax-Suche. Für jeden möglichen Zug sehen wir rekursiv, ob der Gegner gewinnen kann, nachdem wir diesen Zug gemacht haben. Ziemlich schwach golfen; jemand anderes sollte es besser machen können. Das fühlt sich wie ein Job für APL an.

• winist die öffentliche Schnittstelle. Es nimmt die Abmessungen der Karte an, konvertiert sie in eine Kartendarstellung und übergibt sie an w.
• wist der Minimax-Algorithmus. Es nimmt einen Board-Status an, versucht alle Züge, erstellt eine Liste, deren Elemente Gewinnzügen entsprechen, und gibt True zurück, wenn die Liste leer ist. Standardmäßig f=printhat das Erstellen der Liste den Nebeneffekt, dass die Gewinnzüge gedruckt werden. Der Funktionsname machte mehr Sinn, wenn er eine Liste mit Gewinnzügen zurückgab, aber dann habe ich ihn notvor die Liste verschoben , um Platz zu sparen.
• for r,p in enumerate(b)for c in xrange(p) if(r+c): Alle möglichen Züge durchgehen. 1 1wird als nicht legaler Schritt behandelt, was den Basisfall ein wenig vereinfacht.
• b[:r]+[min(i,c)for i in b[r:]]: Konstruiere den Zustand der Tafel nach dem Zug, dargestellt durch Koordinaten rund c.
• w(b[:r]+[min(i,c)for i in b[r:]],max): Überprüfen Sie, ob der neue Zustand ein Verlustzustand ist. maxist die kürzeste Funktion, die ich finden konnte, die zwei ganzzahlige Argumente annehmen und nicht meckern würde.
• f(r+1,c+1): Wenn fgedruckt wird, wird der Zug gedruckt. Was auch immer fist, es wird ein Wert zum Auffüllen der Listenlänge erzeugt.
• not [...]: notGibt Truefür leere Listen und Falsefür nicht leere zurück.

Ursprünglicher Python 2-Code, komplett ungolfed, einschließlich Memo-Funktion für viel größere Eingaben:

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

Demo:

>>> 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 Zeichen - 15 = 93 Punkte

Dieser war hart! Hier ist die nicht zwischengespeicherte Version, die technisch korrekt ist, aber für nicht triviale Eingaben sehr viel Zeit in Anspruch nimmt .

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..*]}

Es funktioniert genau wie die Python-Implementierung von @ user2357112 (ich hätte es nicht ohne seine Arbeit herausfinden können!), Außer dass win () ein Chomp-Board (Array) anstelle einer Breite und Länge benötigt. Es kann verwendet werden wie:

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

Eine Version mit Memoization, die tatsächlich anständige Eingaben verarbeiten kann (allerdings nicht für Lesbarkeit optimiert):

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..*]
}