#!/usr/bin/env python

import sys

print >> sys.stderr, "Tic tac toe - enumerate all possible endings"

wins = (
	(1 << 0) | (1 << 1) | (1 << 2),
	(1 << 3) | (1 << 4) | (1 << 5),
	(1 << 6) | (1 << 7) | (1 << 8),
	(1 << 0) | (1 << 3) | (1 << 6),
	(1 << 1) | (1 << 4) | (1 << 7),
	(1 << 2) | (1 << 5) | (1 << 8),
	(1 << 0) | (1 << 4) | (1 << 8),
	(1 << 2) | (1 << 4) | (1 << 6),
)

moves = (
	(1 << 0), (1 << 1), (1 << 2),
	(1 << 3), (1 << 4), (1 << 5),
	(1 << 6), (1 << 7), (1 << 8)
)

def winner(board):
	winner = -1
	global wins
	for player in (0, 1):
		for winning_board in wins:
			if (board[player] & winning_board) == winning_board:
				winner = player
				break
	return winner

# board - an array of 2 ints.
# board[0] - player 0's marks
# board[1] - player 1's marks
# if board[0] & board[1] has any bits set, the
# board doesn't constitute a legal position.

def print_board(bd):
	print "%02x, %02x" % (bd[0], bd[1]),

def next_move(board, player, ply):
	global moves
	filled = board[0] | board[1]
	if filled == 511:  # 9 1-bits
		print_board(board); print 'cat', ply
		return
	for move in moves:
		nextboard = [board[0], board[1]]
		if (filled & move) == 0:
			nextboard[player] = nextboard[player] | move
			if nextboard[0] & nextboard[1] != 0:
				print "Ply", ply, "Invalid board: ", ; print_board(nextboard); print player
				sys.exit(1)
			w = winner(nextboard)
			if w == -1:
				next_move(nextboard, player^1, ply + 1)
			else:
				print_board(nextboard); print w, ply

next_move([0,0], 0, 1)
	
sys.exit(0)