A Simple LightsOut Grid in Python.

logrid.py

from cStringIO import StringIO

class LoGrid(object):

    def __init__(self, dim, init_state=[]):
        """Set up a square matrix of `dim` by `dim` size.

        Optionally, provide an initial state in the form of a linear boolean
        array (list) of length `dim` squared.

        """
        self._dim = dim
        if init_state:
            if dim * dim != len(init_state):
                raise ValueError('Dimension does not agree!')
            self._grid_array = [bool(x) for x in init_state]
        else:
            self._grid_array = [False for x in range(dim * dim)]

    @property
    def dim(self):
        return self._dim

    def __verify_coordinate(self, x, y):
        if (not (0 <= x < self._dim)) or \
           (not (0 <= y < self._dim)):
            raise IndexError((x, y))

    def __index(self, x, y):
        # convert a two-dimensional (x, y) coordinate to a flat array index
        self.__verify_coordinate(x, y)
        return x * self._dim + y

    def is_off(self, x, y):
        return not self.is_on(x, y)

    def is_on(self, x, y):
        return self._grid_array[self.__index(x, y)]

    def toggle(self, x, y):
        index = self.__index(x, y)
        self._grid_array[index] = not self._grid_array[index]
        if x > 0:               # toggle left neighbor
            lindex = self.__index(x-1, y)
            self._grid_array[lindex] = not self._grid_array[lindex]
        if x < self._dim - 1:   # toggle right neighbor
            rindex = self.__index(x+1, y)
            self._grid_array[rindex] = not self._grid_array[rindex]
        if y > 0:               # toggle top neighbor
            tindex = self.__index(x, y-1)
            self._grid_array[tindex] = not self._grid_array[tindex]
        if y < self._dim - 1:   # toggle bottom neighbor
            bindex = self.__index(x, y+1)
            self._grid_array[bindex] = not self._grid_array[bindex]

    def all_on(self):
        return all(self._grid_array)

    def all_off(self):
        return all([not x for x in self._grid_array])


def print_logrid(logrid):
    """Return a string representation of the grid,
    where each row is separated by a newline.

    """
    buf = StringIO()
    dim = logrid.dim
    for i in range(dim * 2):
        if i % 2 == 0:  # print separator
            buf.write(dim * '+---')
            buf.write('+\n')
        else:           # print cells
            row = (i - 1) / 2
            for col in range(dim):
                buf.write('| %s ' % ('x' if logrid.is_on(row, col) else '.'))
                if col == dim - 1:
                    buf.write('|\n')
    buf.write(dim * '+---')
    buf.write('+\n')
    return buf.getvalue()


def apply_toggles(logrid, coords, on_toggle=None):
    """Apply a series of toggles (expressed in a list of (x,y) coordinate tuples)
    to a LoGrid.

    Optionally, caller can provide a callback that will be called after
    each toggle event, given the arguments: < g, (x,y) >
    where `g` is the LoGrid graph and (x,y) is the coordinate tuple toggled.

    """
    for x, y in coords:
        logrid.toggle(x, y)
        if on_toggle:
            on_toggle(logrid, (x, y))


def solve_logrid(logrid):
    """Given a LoGrid in some state, this function outputs a valid
    solution in the form of a list of (x,y) coordinate tuples.

    """
    if logrid.all_off():
        return []
    # TODO
    raise NotImplementedError


# for debugging purposes...
if __name__ == '__main__':
    import time
    g = LoGrid(5)
    print
    print 'Empty grid...'
    print print_logrid(g)

    def on_toggle(g, coord):
        print 
        print 'Toggling %s...' % repr(coord)
        time.sleep(1)
        print print_logrid(g)

    apply_toggles(g, [(1,1), (1,2), (4,4)], on_toggle)

logrid_test.py

import unittest
import logrid


class LoGridTest(unittest.TestCase):

    def test_dim_ctor(self):
        g = logrid.LoGrid(5)
        self.assertEquals(5, g.dim)
        self.assertTrue(g.all_off())
        self.assertFalse(g.all_on())

    def test_dim_ctor_error(self):
        with self.assertRaises(ValueError):
            g = logrid.LoGrid(5, [True for x in range(5)])

    def test_dim_ctor_init_state(self):
        g = logrid.LoGrid(5, [True for x in range(25)])
        self.assertTrue(g.all_on())
        g = logrid.LoGrid(5, [1 for x in range(25)])
        self.assertTrue(g.all_on())

    def test_toggle_1(self):
        g = logrid.LoGrid(5)
        g.toggle(1,1)
        self.assertTrue(g.is_off(0,0))
        self.assertFalse(g.is_on(0,0))
        self.assertTrue(g.is_on(1,1))
        self.assertTrue(g.is_on(0,1))
        self.assertTrue(g.is_on(2,1))
        self.assertTrue(g.is_on(1,0))
        self.assertTrue(g.is_on(1,2))
        self.assertFalse(g.all_off())
        self.assertFalse(g.all_on())

    def test_toggle_2(self):
        g = logrid.LoGrid(5)
        g.toggle(4,4)
        self.assertTrue(g.is_on(4,4))
        self.assertTrue(g.is_on(3,4))
        self.assertTrue(g.is_on(4,3))
        self.assertFalse(g.all_off())
        self.assertFalse(g.all_on())

    def test_apply_toggles_0(self):
        g = logrid.LoGrid(5)
        logrid.apply_toggles(g, [])
        self.assertTrue(g.all_off())

    def test_apply_toggles_1(self):
        g = logrid.LoGrid(5)
        toggles = [(1,1), (1,2), (4,4)]

        capture = {'idx':0} # cute hack to simulate a captured variable in a lambda
        def on_toggle(lo_g, coord, capture=capture):
            x, y = coord
            self.assertIs(lo_g, g)
            self.assertEquals(toggles[capture['idx']], coord)
            capture['idx'] += 1

        logrid.apply_toggles(g, toggles, on_toggle)

    def test_apply_toggles_2(self):
        g = logrid.LoGrid(5)
        toggles = [(1,1), (1,2), (4,4)]
        logrid.apply_toggles(g, toggles)
        # verify the output of the above series of toggles
        self.assertTrue(g.is_on(0,1))
        self.assertTrue(g.is_on(0,2))
        self.assertTrue(g.is_on(1,0))
        self.assertTrue(g.is_off(1,1))
        self.assertTrue(g.is_off(1,2))
        self.assertTrue(g.is_on(1,3))
        self.assertTrue(g.is_on(2,1))
        self.assertTrue(g.is_on(2,2))
        self.assertTrue(g.is_on(3,4))
        self.assertTrue(g.is_on(4,3))
        self.assertTrue(g.is_on(4,4))

    def test_coord_out_of_range(self):
        g = logrid.LoGrid(5)
        with self.assertRaises(IndexError):
            g.is_off(5,5)
        with self.assertRaises(IndexError):
            g.is_on(0,-1)
        with self.assertRaises(IndexError):
            g.toggle(5,5)

    def test_solve_logrid_1(self):
        g = logrid.LoGrid(5)
        toggles = logrid.solve_logrid(g)
        logrid.apply_toggles(g, toggles)
        self.assertTrue(g.all_off())

    # TODO: more tests for solve_logrid() correctness verification


if __name__ == '__main__':
    unittest.main()