nac-trinket/nac.py

   1 import itertools
   2 import functools
   3 import collections
   4 import random
   5
   6 def xo_count(board):
   7     xs = 0
   8     os = 0
   9     for c in board:
  10         if c == 'x':
  11             xs += 1
  12         elif c == 'o':
  13             os += 1
  14     return xs, os
  15
  16 def valid_board(board):
  17     xs, os = xo_count(board)
  18     return (xs - os) == 0 or (xs - os) == 1
  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 def show_boards(bs):
  55     rows = [[], [], []]
  56     for b in bs:
  57         s = ''.join(b)
  58         for i in range(3):
  59             rows[i] += [s[i*3:i*3+3]]
  60     return '\n'.join('  '.join(r) for r in rows)
  61
  62
  63 # 0 1 2    6 3 0
  64 # 3 4 5 -> 7 4 1
  65 # 6 7 8    8 5 2
  66 rotation = {0: 6, 1: 3, 2: 0, 3: 7, 4: 4, 5: 1, 6: 8, 7: 5, 8: 2}
  67 inverse_rotation = {t: f for f, t in rotation.items()}
  68
  69 # 0 1 2    2 1 0
  70 # 3 4 5 -> 5 4 3
  71 # 6 7 8    8 7 6
  72 reflection = {0: 2, 1: 1, 2: 0, 3: 5, 4: 4, 5: 3, 6: 8, 7: 7, 8: 6}
  73
  74 def rotate(board, n=1):
  75     b = board
  76     for _ in range(n):
  77         b = tuple(b[rotation[i]] for i in range(len(board)))
  78     return b
  79
  80
  81 def reflect(board, r=True):
  82     if r:
  83         return tuple(board[reflection[i]] for i in range(len(board)))
  84     else:
  85         return board
  86
  87 def transform(board, n, r):
  88     b = rotate(board, n)
  89     return reflect(b, r)
  90
  91 def untransform(board, n, r):
  92     b = reflect(board, r)
  93     return rotate(b, abs(4-n))
  94
  95 def all_transforms(board):
  96     return [(transform(board, rot, ref), rot, ref)
  97             for rot in range(4)
  98             for ref in [False, True]]
  99
 100 def score(board):
 101     return ''.join(board)
 102
 103 def canonical(board):
 104     return max(all_transforms(board), key=lambda brf: score(brf[0]))
 105
 106 def non_winning_boards():
 107     return set([canonical(b)[0] for b in all_boards()
 108            if not winner(b)
 109            ])
 110
 111
 112 def successors(board):
 113     xs, os = xo_count(board)
 114     succs = []
 115     if (xs - os) == 0:
 116         # add an x
 117         for i in range(len(board)):
 118             if board[i] == '.':
 119                 succs += [tuple(board[:i] + ('x',) + board[i+1:])]
 120
 121     if (xs - os) == 1:
 122         # add an o
 123         for i in range(len(board)):
 124             if board[i] == '.':
 125                 succs += [tuple(board[:i] + ('o',) + board[i+1:])]
 126     return succs
 127
 128
 129 def vacants(board):
 130     return [i for i, c in enumerate(board) if c == '.']
 131
 132
 133 def apply_move(board, position, piece):
 134     return tuple(board[:position] + (piece,) + board[position+1:])
 135
 136 def token_for_player(is_player_1):
 137     if is_player_1:
 138         return 'x'
 139     else:
 140         return 'o'
 141