From 282da8de86748e42e0891daaa7ce81aa423fed44 Mon Sep 17 00:00:00 2001
From: Eevee <eevee@nyarumaa.(none)>
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