Polyomino Solver

polyomino.py

# -*- coding: utf-8 -*-
#!/usr/bin/env python
"""Finds n-order Polyominos
https://en.wikipedia.org/wiki/Polyomino

Hamish Campbell <[email protected]>
http://polemic.net.nz
License: CC-BY 2012, use it for good, not for evil. 
"""

import sys
import itertools
import timeit

USAGE = """
%s
Usage: %s n [display|timeit [reps]]
""" % (__doc__, sys.argv[0])

class Polyomino(object):

    ADJACENT_SEARCH_XYS = ((-1, 0), (1, 0), (0, -1), (0, 1))

    def __init__(self, squares):
        self.__squares = tuple(sorted(squares))

    def key(self):
        """
        Returns the hash of this paritucular Polyomino configuration
        """
        return hash(self.__squares)

    def rotate(self):
        """
        Returns a new Polyomino rotated 90 degrees
        """
        m = max(max(self.__squares, key=max))
        return Polyomino([(c[1], m - c[0] - 1) for c in self.__squares])

    def translate(self):
        """
        Returns a Polyomino translated to origin (or self, if it is already at the origin)
        """
        xs, ys = zip(*self.__squares)
        minx, miny = min(xs), min(ys)
        return Polyomino(zip((x - minx for x in xs), (y - miny for y in ys))) if (minx or miny) else self

    def adjacents(self):
        """
        Returns set of all empty adjacent squares
        """
        return set((c[0]+x, c[1]+y) for c, (x, y) in itertools.product(self.__squares, self.ADJACENT_SEARCH_XYS)).difference(self.__squares)

    def raise_order(self):
        """
        Returns a list superset of next order Polyominos based on this one
        """
        return [Polyomino(self.__squares + ((adj,))) for adj in self.adjacents()]

    def __hash__(self):
        """
        Generates a unique hash for this Polyomino (minimum key of all rotated, translated siblings)
        """
        if not hasattr(self, "__hash_cache"):
            p = self.translate()
            k = p.key() 
            for i in range(3):
                p = p.rotate().translate()
                k = min(k, p.key())
            setattr(self, "__hash_cache", k)
        return getattr(self, "__hash_cache")

    def __eq__(self, other):
        return hash(self) == hash(other)

    def __unicode__(self):
        """
        Returns a 'map' of the Polyomino, translated to the origin.
        """
        return self.translate()._as_map()

    def _as_map(self):
        """
        Returns a string map representation of the Polyomino (in order bounds only!)
        """
        order = len(self.__squares)
        header = u"┌%s┐" % (u"─" * order)
        body = ''.join([u"\n│%s│" % (''.join([u"█" if (x, y) in self.__squares else u" " for x in range(order)])) for y in range(order)])
        footer = u"\n└%s┘" % (u"─" * order)
        return unicode("%s%s%s" % (header, body, footer))

def polyominos(n):
    """Get a set of all polynominos for order `n`"""
    if n == 1:
        return [Polyomino(((0, 0), ))]
    results = set()
    for p in polyominos(n - 1):
        for candidates in p.raise_order():
            results.add(candidates)
    return results

# ---

if __name__ == "__main__":
    args = sys.argv
    if len(args) < 2:
        print USAGE
    elif len(args) == 2:
        n = int(args[1])
        l = len(polyominos(n))
        print "There %s %s %s%s-order polyominos." % ("is" if l == 1 else "are", l, n, "st" if n == 1 else ("nd" if n % 10 == 2  else "th"))
    elif len(args) > 2:
        n = int(args[1])
        if args[2] == 'display':
            ps = polyominos(n)
            l = len(ps)
            print "There %s %s %s%s-order polyominos." % ("is" if l == 1 else "are", l, n, "st" if n == 1 else ("nd" if n % 10 == 2  else "th"))
            for p in ps:
                print unicode(p)
        elif args[2] == 'timeit':
            reps = 100
            if len(args) > 3:
                reps = int(args[3])
            print "Timing polynominos count (order %s), %s repitions" % (n, reps)
            print timeit.Timer("len(polyominos(%d))" % n, "from __main__ import polyominos").timeit(number=reps)