nac-trinket/nac.py

   1 import itertools
   2
   3
   4 def xo_count(board):
   5     xs = 0
   6     os = 0
   7     for c in board:
   8         if c == 'x':
   9             xs += 1
  10         elif c == 'o':
  11             os += 1
  12     return xs, os
  13
  14
  15 def valid_board(board):
  16     xs, os = xo_count(board)
  17     return (xs - os) == 0 or (xs - os) == 1
  18
  19
  20 def empty_board():
  21     return tuple('.' * 9)
  22
  23
  24 def all_boards():
  25     return [b for b in itertools.product('.xo', repeat=9)
  26             if valid_board(b)]
  27
  28
  29 def winner(board):
  30     winning_player = None
  31     if board[0] == board[1] == board[2] and board[0] != '.':
  32         winning_player = board[0]
  33     if board[3] == board[4] == board[5] and board[3] != '.':
  34         winning_player = board[3]
  35     if board[6] == board[7] == board[8] and board[6] != '.':
  36         winning_player = board[6]
  37     if board[0] == board[3] == board[6] and board[0] != '.':
  38         winning_player = board[0]
  39     if board[1] == board[4] == board[7] and board[1] != '.':
  40         winning_player = board[1]
  41     if board[2] == board[5] == board[8] and board[2] != '.':
  42         winning_player = board[2]
  43     if board[0] == board[4] == board[8] and board[0] != '.':
  44         winning_player = board[0]
  45     if board[2] == board[4] == board[6] and board[2] != '.':
  46         winning_player = board[2]
  47     return winning_player
  48
  49
  50 def show_board(b):
  51     s = ''.join(b)
  52     return s[0:3] + '\n' + s[3:6] + '\n' + s[6:9]
  53
  54
  55 def show_boards(bs):
  56     rows = [[], [], []]
  57     for b in bs:
  58         s = ''.join(b)
  59         for i in range(3):
  60             rows[i] += [s[i*3:i*3+3]]
  61     return '\n'.join('  '.join(r) for r in rows)
  62
  63
  64 # 0 1 2    6 3 0
  65 # 3 4 5 -> 7 4 1
  66 # 6 7 8    8 5 2
  67 rotation = {0: 6, 1: 3, 2: 0, 3: 7, 4: 4, 5: 1, 6: 8, 7: 5, 8: 2}
  68 inverse_rotation = {t: f for f, t in rotation.items()}
  69
  70 # 0 1 2    2 1 0
  71 # 3 4 5 -> 5 4 3
  72 # 6 7 8    8 7 6
  73 reflection = {0: 2, 1: 1, 2: 0, 3: 5, 4: 4, 5: 3, 6: 8, 7: 7, 8: 6}
  74
  75
  76 def rotate(board, n=1):
  77     b = board
  78     for _ in range(n):
  79         b = tuple(b[rotation[i]] for i in range(len(board)))
  80     return b
  81
  82
  83 def reflect(board, r=True):
  84     if r:
  85         return tuple(board[reflection[i]] for i in range(len(board)))
  86     else:
  87         return board
  88
  89
  90 def transform(board, n, r):
  91     b = rotate(board, n)
  92     return reflect(b, r)
  93
  94
  95 def untransform(board, n, r):
  96     b = reflect(board, r)
  97     return rotate(b, abs(4-n))
  98
  99
 100 def all_transforms(board):
 101     return [(transform(board, rot, ref), rot, ref)
 102             for rot in range(4)
 103             for ref in [False, True]]
 104
 105
 106 def score(board):
 107     return ''.join(board)
 108
 109
 110 def canonical(board):
 111     return max(all_transforms(board), key=lambda brf: score(brf[0]))
 112
 113
 114 def non_winning_boards():
 115     return set([canonical(b)[0] for b in all_boards()
 116                 if not winner(b)])
 117
 118
 119 def successors(board):
 120     xs, os = xo_count(board)
 121     succs = []
 122     if (xs - os) == 0:
 123         # add an x
 124         for i in range(len(board)):
 125             if board[i] == '.':
 126                 succs += [tuple(board[:i] + ('x',) + board[i+1:])]
 127
 128     if (xs - os) == 1:
 129         # add an o
 130         for i in range(len(board)):
 131             if board[i] == '.':
 132                 succs += [tuple(board[:i] + ('o',) + board[i+1:])]
 133     return succs
 134
 135
 136 def vacants(board):
 137     return [i for i, c in enumerate(board) if c == '.']
 138
 139
 140 def apply_move(board, position, piece):
 141     return tuple(board[:position] + (piece,) + board[position+1:])
 142
 143
 144 def token_for_player(is_player_1):
 145     if is_player_1:
 146         return 'x'
 147     else:
 148         return 'o'