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