Chomp to gra dla dwóch graczy z układem prostokąta elementów. Każdy gracz wykonuje turę usuwając dowolny element, wraz ze wszystkimi elementami nad nim i po jego prawej stronie. Kto bierze lewy dolny kawałek, przegrywa. Dość łatwo można udowodnić, że pierwszy gracz zawsze ma ruch wygrywający (z wyjątkiem prostokąta 1 na 1); Znajdź to.

1. Dane wejściowe to wymiary prostokąta (dwie liczby)
2. Dane wyjściowe to lokalizacja zwycięskiego ruchu (dwie liczby)
3. Jeśli jest więcej niż jeden wygrywający ruch, możesz wyprowadzić dowolny z nich.

To jest kod golfowy; najkrótszy kod (dowolny język) wygrywa.

Przykłady

Uwaga: Dane wyjściowe to tylko dwie liczby; Poniższa grafika ASCII ma jedynie na celu pokazanie, co oznaczają liczby.

Dane wejściowe: 5 3 (oparte na indeksach 1, zaczynając od lewego dolnego rogu)

Wyjście: 4 3

XXX--
XXXXX
XXXXX

Wejście: 4 4

Wyjście: 2 2

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

Premia

Odejmij 15 znaków od swojego wyniku, jeśli wypiszesz wszystkie zwycięskie ruchy. Każda para liczb musi być oddzielona nową linią.

GolfScript, 82 ( 108 97 znaków - 15 bonusów)

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

Ponieważ nie znałem żadnej heurystyki, to rozwiązanie wykonuje wyczerpujące wyszukiwanie przestrzeni rozwiązania. Możesz wypróbować kod online . Chociaż implementacja jest bardzo wydajna, przestrzeń wyszukiwania rośnie bardzo szybko wraz ze wzrostem ilości danych wejściowych.

Przykłady:

> 5 3
4 3

> 5 4
3 3

> 6 6
2 2

Jak wspomniano powyżej, implementacja nie opiera się na rekurencji, ale odwiedza każdy węzeł przestrzeni wyszukiwania tylko raz. Poniżej znajduje się adnotowana wersja kodu, która bardziej szczegółowo opisuje bloki konstrukcyjne.

Reprezentacji pojedynczej płytce wielkości wag * h podaje się na liście w ilościach w zakresie od 0 do godz . Każda liczba podaje liczbę sztuk w odpowiedniej kolumnie. Tak więc poprawna konfiguracja to lista, na której liczby nie rosną od początku do końca (przy każdym ruchu upewniasz się, że wszystkie kolumny po prawej stronie są co najwyżej tak wysokie, jak wybrana).

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

Wyszukiwanie minimalne metodą brute-force. Dla każdego możliwego ruchu rekursywnie sprawdzamy, czy przeciwnik może wygrać po tym ruchu. Dość słabo golfa; ktoś inny powinien być w stanie zrobić znacznie lepiej. To wydaje się być pracą dla APL.

• winjest interfejsem publicznym. Pobiera wymiary tablicy, konwertuje ją na reprezentację tablicy i przekazuje do w.
• wjest algorytmem minimax. Przyjmuje stan planszy, wypróbowuje wszystkie ruchy, buduje listę, której elementy odpowiadają zwycięskim ruchom, i zwraca True, jeśli lista jest pusta. Przy ustawieniu domyślnym f=printbudowanie listy powoduje efekt uboczny drukowania zwycięskich ruchów. Nazwa funkcji była bardziej sensowna, gdy zwróciła listę zwycięskich ruchów, ale potem przesunąłem jej notprzód, aby zaoszczędzić miejsce.
• for r,p in enumerate(b)for c in xrange(p) if(r+c): Powtarzaj wszystkie możliwe ruchy. 1 1jest traktowany jako nielegalny ruch, co nieco upraszcza podstawową sprawę.
• b[:r]+[min(i,c)for i in b[r:]]: Zbuduj stan planszy po ruchu reprezentowanym przez współrzędne ri c.
• w(b[:r]+[min(i,c)for i in b[r:]],max): Ponownie sprawdź, czy nowy stan traci stan. maxto najkrótsza funkcja, jaką mogłem znaleźć, która wymagałaby dwóch liczb całkowitych i nie narzekałaby.
• f(r+1,c+1): Jeśli fjest drukowane, drukuje ruch. Cokolwiek fto jest, generuje wartość wypełniającą długość listy.
• not [...]: notzwraca Truepuste listy i Falseniepuste.

Oryginalny kod Pythona 2, całkowicie pozbawiony golfa, w tym zapamiętywanie do obsługi znacznie większych danych wejściowych:

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

Próbny:

>>> 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 znaków - 15 = 93 punkty

Ten był trudny! Oto wersja niebuforowanych który jest technicznie poprawne, ale zajmie bardzo dużo czasu wejść nietrywialnych.

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

Działa tak jak implementacja Pythona @ user2357112 (głosuj na niego / go, nie mógłbym tego rozgryźć bez jego / jej pracy!), Z wyjątkiem tego, że win () bierze tablicę Chomp (tablicę) zamiast szerokości i długości. Może być używany jak:

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

Wersja z zapamiętywaniem, która może obsługiwać przyzwoite dane wejściowe (choć nie zoptymalizowane pod kątem czytelności):

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