# Find the optimal starting move of Chomp

Chomp is a two-player game with a setup of a rectangle of pieces. Each player takes a turn removing any piece, along with all pieces above it and to its right. Whoever takes the bottom-left piece loses. It can be proven fairly easily that the first player always has a winning move (except with a 1-by-1 rectangle); find it.

1. Input is the dimensions of the rectangle (two numbers)
2. Output is the location of the winning move (two numbers)
3. If there is more than one winning move, then you can output any of them.

This is code golf; shortest code (any language) wins.

# Examples

Note: The outputs are just the two numbers; the ASCII art below is just to demonstrate what the numbers mean.

Input: 5 3 (indices 1-based starting from lower-left corner)

Output: 4 3

XXX--
XXXXX
XXXXX

Input: 4 4

Output: 2 2

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

# Bonus

Subtract 15 characters from your score if you output all of the winning moves. Each pair of numbers must be separated by a newline.

• In your first example, I think that you have one too many dashes – kitcar2000 Mar 18 '14 at 22:13
• @Kitcar You're right; fixed. – Ypnypn Mar 18 '14 at 22:25
• I can't understand the output format. How do those numbers correspond to those positions? – undergroundmonorail Mar 19 '14 at 13:55
• @undergroundmonorail 1-based index from the bottom left. first index is horizontal axis and second index is vertical index. – Martin Ender Mar 19 '14 at 14:18
• In response to your bounty: In Chess, you have less than 119 possible moves at any given time (usually much less), and no supercomputer to this day has come close to solving Chess using even the best known algorithms. On a 10 by 10 Chomp grid, there are 100 possible first moves, and each of those has 1-99 potential second moves. What makes you think that would be easy to brute force? I recommend limiting your grid size if you want brute force answers. EDIT: But don't do that. Changing requirements mid contest is bad. – Rainbolt Mar 21 '14 at 14:39

### GolfScript, 82 (108 97 characters - 15 bonus)

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

Since I didn't know for any heuristics this solution performs an exhaustive search over the solution space. You may try the code online. Although the implementation is very efficient the search space grows very fast with increasing input.

Examples:

> 5 3
4 3

> 5 4
3 3

> 6 6
2 2

As mentioned above the implementation does not rely on recursion but visits each node of the search space only once. Below you can find an annotated version of the code which describes the building blocks in more detail.

The representation of a single board of size w * h is given by a list of w numbers in the range 0 to h. Each number gives the amount of pieces in the corresponding column. Thus, a valid configuration is a list where the numbers are non-increasing from start to end (with any move you ensure that all columns to the right are at most as high as the chosen one).

~                   # 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
}/
• +1 For the solution itself and for the very nicely commented code – Xuntar Mar 24 '14 at 10:16
• Bottom-up dynamic programming, rather than top-down. Nice. I considered doing that, but generating states in a valid order for bottom-up traversal was more work and more confusing than recursive search. I'm surprised the code ended up so long; I expected a terse language like Golfscript could have produced a much shorter solution. – user2357112 supports Monica Mar 24 '14 at 10:17
• Very nice and well thought out – Mouq Mar 24 '14 at 22:23

## 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 search. For every possible move, we recursively see if the opponent can win after we make that move. Pretty weakly golfed; someone else should be able to do much better. This feels like a job for APL.

• win is the public interface. It takes the dimensions of the board, converts it to a board representation, and passes that to w.
• w is the minimax algorithm. It takes a board state, tries all moves, builds a list whose elements correspond to winning moves, and returns True if the list is empty. With the default f=print, building the list has a side effect of printing the winning moves. The function name used to make more sense when it returned a list of winning moves, but then I moved the not in front of the list to save a space.
• for r,p in enumerate(b)for c in xrange(p) if(r+c): Iterate over all possible moves. 1 1 is treated as not a legal move, simplifying the base case a bit.
• b[:r]+[min(i,c)for i in b[r:]]: Construct the state of the board after the move represented by coordinates r and c.
• w(b[:r]+[min(i,c)for i in b[r:]],max): Recurse to see whether the new state is a losing state. max is the shortest function I could find that would take two integer arguments and not complain.
• f(r+1,c+1): If f is print, prints the move. Whatever f is, it produces a value to pad the list length.
• not [...]: not returns True for empty lists and False for nonempty.

Original Python 2 code, completely ungolfed, including memoization to handle much larger inputs:

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
• For the 13x13 take 2x2 and you'd win. – davidsbro Mar 21 '14 at 22:23
• @davidsbro: Yes, that's the winning move for any square board bigger than 1x1, but my code hadn't computed it yet. – user2357112 supports Monica Mar 21 '14 at 23:08

# Perl 6: 113 108 characters - 15 = 93 points

This one was tough! Here's the uncached version, which is technically correct but will take a very long time for non-trivial inputs.

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..*]} It works just like @user2357112's Python implementation (upvote him/her, I couldn't have figured this out without his/her work!) except that win() takes a Chomp board (array) instead of a width and length. It can be used like: loop { my ($y, $x) = get.words; .say for @(win [1 xx$x] xx $y) } A version with memoization, which can actually handle decent inputs (not optimized for readability, though): 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..*]
}