polyonimoes.py

#!/usr/bin/env python
"""
  Calculate and displays all possible N-ominoes for a given N.
  
  (c) 2010 Craig de Stigter
  
  [email protected]
  http://flavors.me/craigds
"""

import sys
from operator import itemgetter

USAGE = """
Calculates and displays all possible N-ominoes for a given N.
Usage: %s N
""" % sys.argv[0]

class Ominoe(tuple):
    def __new__(cls, iterable):
        # ensure always sorted
        return tuple.__new__(cls, sorted(iterable, key=itemgetter(1,0)))
    
    def __init__(self, iterable):
        super(Ominoe, self).__init__(iterable)
        
        if not self:
            raise ValueError, "Can't have an empty ominoe"
        
        self.minx = min([o[0] for o in self])
        self.maxx = max([o[0] for o in self])
        self.miny = self[0][1]
        self.maxy = self[-1][1]
    
    def translate(self, dx, dy):
        return Ominoe([(z[0] + dx, z[1] + dy) for z in self])
    
    def rotate_cw(self):
        """
        Returns a new ominoe, rotated 90 degrees clockwise and then translated to (0, 0)
        """
        coords = []
        for (x, y) in self:
            coords.append((-y, x))
        o = Ominoe(coords)
        
        # translate, otherwise rotation will have just put us in the wrong quadrant
        if o.minx != 0 or o.miny != 0:
            o = o.translate(-o.minx, -o.miny)
        return o
    
    def normalise(self):
        """
        Translates the ominoe such that minx and miny are both 0,
        and normalises rotation.
        """
        
        # now rotate. Doesn't matter which way, as long as it's reproducible.
        # (i.e. any of the four possible inputs should produce the same output)
        o = self.rotate_cw()
        min_hash = hash(o)
        last = o
        for i in range(3):
            r = last.rotate_cw()
            h = hash(r)
            if h < min_hash:
                o = r
                min_hash = h
            last = r
        return o
    
    def is_adjacent(self, (x, y)):
        if (x, y) in self:
            return False
        
        for coord in (
                (x, y-1),
                (x, y+1),
                (x-1, y),
                (x+1, y),
        ):
            if coord in self:
                return True
        return False
    
    def mutate(self, coord):
        assert coord not in self, "Bad mutation, %s is already in this ominoe" % coord
        return Ominoe(list(self)+[coord])
    
    def get_mutations(self):
        mutations = set()
        
        for x in range(self.minx-1, self.maxx+2):
            for y in range(self.miny-1, self.maxy+2):
                if self.is_adjacent((x, y)):
                    zz = self.mutate((x, y))
                    zz = zz.normalise()
                    mutations.add(zz)
        return mutations
        
    def render(self):
        rows = []
        for y in range(self.miny, self.maxy + 1):
            rows.append([' '] * (self.maxx - self.minx + 1))
        
        for x, y in self:
            rows[y][x] = 'X'
        
        return '\n'.join([''.join(row) for row in rows]) + '\n'




def get_ominoes(src_ominoes):
    """
    Given an iterable of (N-1)-ominoes, returns a list of all possible N-ominoes.
    """
    dest_ominoes = set()
    
    for src in src_ominoes:
        dest_ominoes.update(src.get_mutations())
    return dest_ominoes


def usage():
    print USAGE
    sys.exit(2)

def main():
    if len(sys.argv) != 2:
        usage()
    
    try:
        N = int(sys.argv[1])
    except ValueError:
        usage()
    
    i = 1
    i_ominoes = set([Ominoe([(0, 0)])])
    while i < N:
        i += 1
        i_ominoes = get_ominoes(i_ominoes)
        
        print "\n\n%d-ominoes:" % i
        for ominoe in i_ominoes:
            print ominoe.render()
        
        print "(%d total %d-ominoes)" % (len(i_ominoes), i)

if __name__ == '__main__':
    main()