From 282da8de86748e42e0891daaa7ce81aa423fed44 Mon Sep 17 00:00:00 2001 From: Eevee Date: Tue, 9 Dec 2008 21:50:02 -0500 Subject: [PATCH] Improved creating a grid from data. Grid.from_lists is now a constructor that optionally takes explicit height and width; without them, it attempts to guess the likely dimensions of the grid and boxes. Added a Grid.from_string that is similar but reads from a string. --- pseudoku.py | 123 ++++++++++++++++++++++++++++++++++++++++++++++++++++-------- 1 file changed, 108 insertions(+), 15 deletions(-) diff --git a/pseudoku.py b/pseudoku.py index e6db889..d48c656 100644 --- a/pseudoku.py +++ b/pseudoku.py @@ -1,8 +1,15 @@ +from __future__ import division + +from math import sqrt +import re from weakref import proxy symbols = [str(x + 1) for x in range(9)] + [chr(x + 97) for x in xrange(26)] +class GridSizeError(Exception): + pass + class CellGroup(object): """Represents any group of cells in a grid.""" @@ -215,6 +222,40 @@ class Grid(object): """Hashes a row and column into a flat array index.""" return row * self._size + col + @classmethod + def _infer_box_size(cls, dimension): + """Attempts to infer the size of a box, given some dimension of the + entire grid, i.e. the number of cells per box/row/column. + + Returns a tuple of height, width.""" + + # Most obvious: probably n * n. + root = int(sqrt(dimension)) + if root ** 2 == dimension: + return root, root + + # Otherwise, probably n * (n - 1) or n * (n - 2). + # These puzzles generally have the wide side (n) as the width. + # This is of course entirely unreliable, but better than nothing.. + # n^2 - (1|2)n - dimension = 0 + # Determinant is (1|2)^2 + 4 * dimension and has to be square + for difference in 1, 2: + determinant = difference ** 2 + 4 * dimension + root = int(sqrt(determinant)) + if root ** 2 != determinant: + continue + + n = (-difference + root) / 2 + if n != int(n): + continue + + # Success! + return n - difference, n + + # Okay, I don't have a clue. + raise GridSizeError("Can't infer box height and width for grid size " + "%d; please specify them manually" % dimension) + ### Accessors def _get_box_height(self): @@ -233,7 +274,7 @@ class Grid(object): return self._rows + self._columns + self._boxes cell_groups = property(_get_cell_groups) - ### Methods + ### Constructors def __init__(self, box_height=3, box_width=None): if not box_width: @@ -253,7 +294,17 @@ class Grid(object): self._cells[self._cellidx(row, col)] \ = Cell(self, row, col) - def from_lists(self, *rows): + @classmethod + def from_matrix(cls, rows, box_height=None, box_width=None): + """Creates and returns a grid read from a list of lists.""" + + if not box_height: + box_height, box_width = cls._infer_box_size(len(rows)) + elif not box_width: + box_width = box_height + + self = cls(box_width=box_width, box_height=box_height) + for row in xrange(self._size): for col in xrange(self._size): value = rows[row][col] @@ -261,6 +312,49 @@ class Grid(object): continue self.cell(row, col).set_naively(value - 1) + return self + + @classmethod + def from_string(cls, grid, box_height=None, box_width=None): + # XXX sanity check dimensions + """Creates and returns a grid from a string of symbols. + + Symbols are the digits 1 to 9 followed by the letters of the alphabet. + Zeroes and periods are assumed to be empty cells. All other characters + are ignored. + + Since whitespace is ignored, the string could be all in one line or + laid out visually in a square, one row per line.""" + + # Collapse the string down to just characters we want + grid = grid.lower() + grid = re.sub('\\.', '0', grid) + grid = re.sub('[^0-9a-z]', '', grid) + + # Figure out the length of one side/box + size = int(sqrt(len(grid))) + if size ** 2 != len(grid): + # XXX + raise GridSizeError("Provided string does not form a square") + + # Set height/width.. + if not box_height: + box_height, box_width = cls._infer_box_size(size) + elif not box_width: + box_width = box_height + + self = cls(box_width=box_width, box_height=box_height) + + for row in xrange(self._size): + for col in xrange(self._size): + ch = grid[ self._cellidx(row, col) ] + if ch == '0': + continue + self.cell(row, col).set_naively(symbols.index(ch)) + + return self + + ### Methods def cell(self, row, column): return self._cells[self._cellidx(row, column)] @@ -321,19 +415,18 @@ class Grid(object): return res - -grid = Grid(3, 3) -grid.from_lists( - [ 0, 0, 0, 6, 9, 0, 0, 0, 0 ], - [ 9, 0, 5, 0, 0, 8, 7, 6, 0 ], - [ 0, 0, 4, 0, 0, 1, 0, 2, 0 ], - [ 6, 0, 0, 0, 5, 0, 0, 0, 3 ], - [ 3, 8, 0, 0, 0, 0, 0, 4, 9 ], - [ 7, 0, 0, 0, 3, 0, 0, 0, 2 ], - [ 0, 7, 0, 9, 0, 0, 3, 0, 0 ], - [ 0, 2, 3, 1, 0, 0, 4, 0, 8 ], - [ 0, 0, 0, 0, 8, 3, 0, 0, 0 ], -) +grid = Grid.from_string("..... ..... ..... ..... ....") +grid = Grid.from_string(""" + ...69.... + 9.5..876. + ..4..1.2. + 6...5...3 + 38.....49 + 7...3...2 + .7.9..3.. + .231..4.8 + ....83... +""") print grid -- 2.7.4