Coverage for xoxo/xoxo.py: 98.28%

1#! /usr/bin/env python

2"""Solve me xoxo."""

3import pathlib

4import sys

5from typing import List, Union

7ENCODING = 'utf-8'

8X = 'x'

9O = 'o' # noqa

10E = ' '

11SYMBOLS = (X, O)

12TOKENS = (E, *SYMBOLS)

13Matrix = List[List[str]]

14Vector = List[str]

17def sanitize_input(strings: Vector) -> Matrix:

18 """Consider only the minimal span and ignore empty lines."""

19 matrix = [row[:-1] for row in strings if row[:-1]]

20 min_span = min([len(row) for row in matrix])

21 return [[cell.lower() if cell.lower() in TOKENS else E for cell in cells[0:min_span]] for cells in matrix]

24def load(grid: pathlib.Path) -> Matrix:

25 """Load the grid from a text file.

27 The symbols have to be exactly present as upper case x and o.

28 To ease entering the data the empty cell can be any other character.

29 """

30 with open(grid, 'rt', encoding=ENCODING) as handle:

31 strings = handle.readlines()

32 return sanitize_input(strings)

35def render_row(cells: Vector, row_number: int) -> str:

36 """The row internal printing format of rows."""

37 inner = ' | '.join(cell.upper() for cell in cells)

38 return f'| {inner} | {row_number :2d}'

41def render_horizontal_border(dim: int, top: bool = False) -> str:

42 """Render the border (default bottom)."""

43 corner = ',' if top else '*'

44 return f'\n{corner}{"---+" * (dim -1)}---{corner}\n'

47def render_ruler(dim: int) -> str:

48 """Render the ruler lines between data rows."""

49 return f'\n|{"---+" * (dim -1)}---|\n'

52def render_col_numbers(dim: int) -> str:

53 """Render the index row labeling the columns with numbers."""

54 return f'{"".join(f" {c :2d} " for c in range(1, dim+1))}\n'

57def matrix_to_text(grid: Matrix) -> str:

58 """Do the ASCIInation dance ..."""

59 dim = len(grid[0])

60 ruler = render_ruler(dim)

61 return ''.join(

62 (

63 render_horizontal_border(dim, top=True),

64 ruler.join(render_row(cells, row_number) for row_number, cells in enumerate(grid, start=1)),

65 render_horizontal_border(dim),

66 render_col_numbers(dim),

67 )

68 )

71def transpose_column(n: int, grid: Matrix) -> Vector:

72 """Transpose a column to a row."""

73 return [r[n] for r in grid]

76def transpose(grid: Matrix) -> Matrix:

77 """Transpose the grid so we can verify column rules on the transposed row."""

78 dim = len(grid)

79 return [transpose_column(n, grid) for n in range(0, dim)]

82def row_twin_max_holds(symbol: str, row: Vector) -> bool:

83 """Three in a row would fail,, so we test for that."""

84 dim = len(row)

85 twin = 2

86 for i in range(0, dim - twin):

87 if all(row[ndx] == symbol for ndx in range(i, i + twin + 1)):

88 return False

89 return True

92def matrix_twin_max_holds(grid: Matrix) -> bool:

93 """Do we have more than twin siblings across the matrix?"""

94 for row in grid:

95 for symbol in SYMBOLS:

96 if not row_twin_max_holds(symbol, row):

97 return False

98 return True

100

101def row_equity_holds(row: Vector) -> bool:

102 """Row equity verification."""

103 dim = len(row)

104 symbol_count = {symbol: 0 for symbol in SYMBOLS}

105 for c in row:

106 if c in symbol_count:

107 symbol_count[c] += 1

108

109 return not any(2 * cnt > dim for cnt in symbol_count.values())

110

111

112def matrix_equity_holds(grid: Matrix) -> bool:

113 """Did we overspend some symbol across the matrix?"""

114 for r in grid:

115 if not row_equity_holds(r):

116 return False

117 return True

118

119

120def rows_equal(wun: Vector, other: Vector) -> bool:

121 """Are the two rows equal (with set symbols)?"""

122 dim = len(wun)

123 for i in range(0, dim):

124 if E in (wun[i], other[i]):

125 return False

126 elif wun[i] != other[i]:

127 return False

128 return True

129

130

131def any_row_equal(grid: Matrix) -> bool:

132 for i in range(0, len(grid) - 1):

133 for j in range(i + 1, len(grid)):

134 if rows_equal(grid[i], grid[j]):

135 return True

136 return False

137

138

139def solve(i: int, j: int, grid: Matrix, transposed: Matrix, dim: int) -> Union[bool, Matrix]:

140 """Recursive solver."""

141 for matrix in (grid, transposed):

142 if any_row_equal(matrix) or not matrix_equity_holds(matrix) or not matrix_twin_max_holds(matrix):

143 return False

144

145 if j >= dim: # Sweep is complete

146 return grid

147

148 jj = j

149 ii = i + 1

150 if ii >= dim:

151 jj = j + 1

152 ii = 0

153

154 c = grid[i][j]

155 if c != E:

156 return solve(ii, jj, grid, transposed, dim)

157

158 grid[i][j] = X

159 transposed[j][i] = X

160 res_for_x = solve(ii, jj, grid, transposed, dim)

161 if res_for_x:

162 return res_for_x

163

164 grid[i][j] = O

165 transposed[j][i] = O

166 res_post = solve(ii, jj, grid, transposed, dim)

167 if not res_post:

168 grid[i][j] = E

169 transposed[j][i] = E

170 return False

171

172 return res_post

173

174

175def solution(grid: Matrix) -> Union[bool, Matrix]:

176 """Seek a solution of the problem grid."""

177 return solve(0, 0, grid, transpose(grid), len(grid))

178

179

180def assess(grid: Matrix) -> str:

181 """Analyze the grid for common hindrance to convergence."""

182 no_option = all([E not in row for row in grid])

183 note = '\n- Note: Received a completely filled (invalid) grid - what is the expectation?' if no_option else ''

184 outer_dim = len(grid)

185 if outer_dim < 2:

186 return f'You need at least 2 times 2 cells for a valid solution.{note}'

187 if outer_dim % 2: # odd i.e. 3, 5, 7, ...

188 return f'You need even squares to balance the symbols per row and column.{note}'

189 inner_dim = len(grid[0])

190 if inner_dim != outer_dim:

191 problem = f'found a {outer_dim} times {inner_dim} rectangle instead.'

192 return f'You need (even) squares to balance the symbols per row and column - {problem}{note}'

193 transposed = transpose(grid)

194 for matrix in (grid, transposed):

195 if any_row_equal(matrix):

196 return f'Neighbor rows or columns are identical.{note}'

197 if not matrix_equity_holds(matrix):

198 return f'Some symbol has been overused.{note}'

199 if not matrix_twin_max_holds(matrix):

200 return f'More than two symbols of a kind together in a row or column.{note}'

201

202 return ''

203

204

205def main(argv: Union[List[str], None] = None) -> int:

206 """Drive the solution of a grid input from file."""

207 argv = sys.argv[1:] if argv is None else argv

208 if not argv:

209 print('usage: xoxo path-to-grid-file')

210 return 0

211

212 grid_path = pathlib.Path(argv[0])

213 if not grid_path.is_file() or not grid_path.stat().st_size:

214 print(f'ERROR: grid file ({grid_path}) does not exist or is empty.')

215 return 1

216

217 partial = load(grid_path)

218 print('Problem:')

219 print(matrix_to_text(partial))

220 findings = assess(partial)

221 if findings:

222 print('Analysis:', assess(partial))

223 print()

224 return 1

225

226 complete = solution(partial)

227 if complete: 227 ↛ 233line 227 didn't jump to line 233, because the condition on line 227 was never false