Chomp adalah gim dua pemain dengan pengaturan empat persegi panjang. Setiap pemain secara bergiliran mengeluarkan bagian apa pun, beserta semua bagian di atasnya dan ke kanan. Siapa pun yang mengambil bagian kiri bawah akan kalah. Dapat dibuktikan dengan cukup mudah bahwa pemain pertama selalu memiliki langkah kemenangan (kecuali dengan persegi panjang 1-oleh-1); Temukan.

1. Input adalah dimensi persegi panjang (dua angka)
2. Output adalah lokasi gerakan pemenang (dua angka)
3. Jika ada lebih dari satu gerakan yang menang, maka Anda dapat menampilkannya.

Ini adalah kode golf; kode terpendek (bahasa apa saja) menang.

Contohnya

Catatan: Outputnya hanya dua angka; seni ASCII di bawah ini hanya untuk menunjukkan apa arti angka-angka itu.

Input: 5 3 (indeks berbasis 1 dimulai dari sudut kiri bawah)

Output: 4 3

XXX--
XXXXX
XXXXX

Input: 4 4

Output: 2 2

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

Bonus

Kurangi 15 karakter dari skor Anda jika Anda menghasilkan semua gerakan yang menang. Setiap pasangan angka harus dipisahkan oleh baris baru.

GolfScript, 82 ( 108 97 karakter - 15 bonus)

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

Karena saya tidak tahu heuristik apa pun, solusi ini melakukan pencarian lengkap untuk ruang solusi. Anda dapat mencoba kode online . Meskipun implementasinya sangat efisien, ruang pencarian tumbuh sangat cepat dengan input yang meningkat.

Contoh:

> 5 3
4 3

> 5 4
3 3

> 6 6
2 2

Seperti disebutkan di atas, implementasi tidak bergantung pada rekursi tetapi mengunjungi setiap node ruang pencarian hanya sekali. Di bawah ini Anda dapat menemukan versi kode beranotasi yang menjelaskan blok bangunan secara lebih rinci.

Representasi satu papan ukuran w * h diberikan oleh daftar nomor w dalam kisaran 0 hingga h . Setiap angka memberikan jumlah potongan di kolom yang sesuai. Dengan demikian, konfigurasi yang valid adalah daftar di mana angkanya tidak meningkat dari awal hingga akhir (dengan gerakan apa pun Anda memastikan bahwa semua kolom di sebelah kanan paling tinggi setinggi yang dipilih).

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

Pencarian minimax dengan paksa. Untuk setiap gerakan yang mungkin, kami secara rekursif melihat apakah lawan bisa menang setelah kami melakukan gerakan itu. Golfnya cukup lemah; orang lain harus bisa berbuat lebih baik. Ini terasa seperti pekerjaan untuk APL.

• winadalah antarmuka publik. Dibutuhkan dimensi papan, mengubahnya menjadi representasi papan, dan meneruskannya kew .
• wadalah algoritma minimax. Dibutuhkan status papan, mencoba semua gerakan, membuat daftar yang unsur-unsurnya terkait dengan gerakan menang, dan mengembalikan True jika daftar kosong. Dengan default f=print, membangun daftar memiliki efek samping untuk mencetak gerakan yang menang. Nama fungsi yang digunakan lebih masuk akal ketika mengembalikan daftar langkah yang menang, tapi kemudian saya memindahkannot di depan daftar untuk menghemat tempat.
• for r,p in enumerate(b)for c in xrange(p) if(r+c): Ulangi semua kemungkinan gerakan. 1 1diperlakukan sebagai bukan langkah hukum, menyederhanakan kasus dasar sedikit.
• b[:r]+[min(i,c)for i in b[r:]]: Bangun status dewan setelah langkah diwakili oleh koordinat r dan c.
• w(b[:r]+[min(i,c)for i in b[r:]],max): Kambuh untuk melihat apakah negara baru adalah negara yang kalah. maxadalah fungsi terpendek yang bisa saya temukan yang akan mengambil dua argumen integer dan tidak mengeluh.
• f(r+1,c+1): Jika f dicetak, cetak langkahnya. Apa pun fitu, ia menghasilkan nilai untuk mengisi daftar panjang.
• not [...]: notpengembalian Trueuntuk daftar kosong dan Falseuntuk kosong.

Kode Python 2 asli, sepenuhnya ungolfed, termasuk memoisasi untuk menangani input yang jauh lebih besar:

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 karakter - 15 = 93 poin

Yang ini tangguh! Inilah versi yang tidak di-cache, yang secara teknis benar tetapi akan memakan waktu yang sangat lama untuk input yang tidak sepele.

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

Ini berfungsi seperti implementasi Python @ user2357112 (upvote dia, saya tidak bisa menemukan ini tanpa / karyanya!) Kecuali bahwa win () mengambil papan Chomp (array) bukannya lebar dan panjang. Dapat digunakan seperti:

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

Versi dengan memoisasi, yang sebenarnya dapat menangani input yang layak (meskipun tidak dioptimalkan untuk dibaca):

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