#!/usr/bin/env python

# Re: 21838.msg, about distinct shapes made up of contiguously-placed
# unit cubes.  James Waldby -- 1 June 2014

# This program uses a 27-bit value (called an "id#") to represent a
# shape within a 3-cube (ie in a 3x3x3 cube).  Each 1-bit in an id#
# corresponds to an occupied block in the shape the number describes.

# There are 24 different orthogonal orientations of a cube, so
# typically one shape's id# is rotationally equivalent to 23 other
# id#'s.  Also, some shapes can be translated (without rotation)
# within the 3-cube, so in some cases 2*24 or 3*24, etc., id#'s might
# be equivalent.  [For any given id# k, the "for (mask,delt) ..." loop
# makes a list of translated values equivalent to k.]

# In its first main loop, the program counts up thru id#'s.  For each
# id# it tests if the number has been seen before.  If so the loop is
# done with that id#.  If id# not seen before: (1) the program tests
# if the shape is valid, and if so saves the id# in array pv[]; (2) it
# generates all rotates and translates of the id# and marks them as
# seen.

# To test shape validity, the program finds a 1-bit in the shape's
# id#.  It adds populated orthogonal neighbors of that bit to a list,
# then recurses to find neighbors of neighbors, etc, creating a bit
# mask of reachable cells.  After recursion, if the reachable-mask
# matches the id# then id# is valid.
#----------------------------------------------------------
# Letters a-i mentioned in roll(), and j-r mentioned in turn(), refer
# to certain ranks and files of a 3-cube.  Bits belonging to the
# various ranks and files can be extracted from an id# using the
# octal-number masks shown below.  Letters are assigned as follows:
# Cells viewed from front side are labeled (across and down) abc; def;
# and ghi.  Cells viewed from top side are labeled jkl; mno; and pqr.
#     a 0400400400      j 0700000000
#     b 0040040040      k 0070000000
#     c 0004004004      l 0007000000
#     d 0200200200      m 0000700000
#     e 0020020020      n 0000070000
#     f 0002002002      o 0000007000
#     g 0100100100      p 0000000700
#     h 0010010010      q 0000000070
#     i 0001001001      r 0000000007
#----------------------------------------------------------
# The "roll" transform sends
#    a->c, b->f, c->i, d->b, e->e, f->h, g->a, h->d, i->g.
def roll(v):
    return (0400400400 & v)>>6 | (0040040040 & v)>>4 |(0004004004 & v)>>2 | (0200200200 & v)>>2 | (0020020020 & v) | (0002002002 & v)<<2 | (0100100100 & v)<<2 | (0010010010 & v)<<4 | (0001001001 & v)<<6
#----------------------------------------------------------
# The "turn" transform sends
#    j->l, k->o, l->r, m->k, n->n, o->q, p->j, q->m, r->p.
def turn(v): return (0700000000 & v)>>6 | (0070000000 & v)>>12 | (0007000000 & v)>>18 | (0000700000 & v)<<6 | (0000070000 & v) | (0000007000 & v)>>6 | (0000000700 & v)<<18 | (0000000070 & v)<<12 | (0000000007 & v)<<6
#----------------------------------------------------------
# For background on sequence()'s (RTTT)^3 RTR (RTTT)^3 series, see an
# answer at <[url]http://stackoverflow.com/questions/16452383[/url]> "How to get
# all 24 rotations of a 3-dimensional array?"
def sequence (v):      # Generate sequence of 24 transforms of v
    for cycle in range(2):
        if cycle:
            v = roll(turn(roll(v))) # Do RTR between (RTTT)^3 sequences
        for step in range(3):   # Do RTTTRTTTRTTT for 12 transforms
            v = roll(v)
            yield(v)
            for i in range(3):
                v = turn(v)
                yield(v)
#----------------------------------------------------------
# Make lists of neighbors of cells
def makeNbrLists():
    nbrs = []               # Init list of lists of neighbors of cells
    for cell in range(27):
        lcell = []              # Init list of neighbors of cell
        width = 27
        while width > 1:
            step = width/3
            nbr = cell + step  # to create id of an adjacent cell, upwards
            if nbr%width > cell%width:
                lcell.append(nbr)
            nbr = cell - step  # to create id of an adjacent cell, downwards
            if nbr%width < cell%width:
                lcell.append(nbr)
            width = step   # Go to next axis (from x to y to z, in turn)
        nbrs.append(tuple(lcell))
    return tuple(nbrs)
#----------------------------------------------------------
def bitCount(v):
    nb = 0
    while v:
        nb += v&1
        v >>= 1
    return nb
#----------------------------------------------------------
def findNbrs(cel, mcel, visited):
    if mcel and not (visited & mcel):
        visited |= mcel
        for nbr in nbrLists[cel]:
            visited |= findNbrs(nbr, (1<<nbr) & tvshape, visited)
    return visited
#----------------------------------------------------------
def testValidShape(shape):
    global tvshape
    tvshape = shape
    if not tvshape:
        return 0             # Require at least one unit cube in shape
    for i in range(nbits):
        if tvshape & (1<<i):    # Find a 1-bit
            b1 = i;  break
    return shape == findNbrs(b1, 1<<b1, 0)
#----------------------------------------------------------
def printShape(s):
    for y in (0,3,6):
        print 'y{}  '.format(y/3),    
        for z in (0,1,2):
            print '  ',
            for x in (0,9,18):
                b = x+y+z
                print 'x' if s & (1<<b) else 'o',
        if y==0:
            print '   {}b'.format(bitCount(s))
        elif y==3:
            print '   {}'.format(testValidShape(s))
        else:
            print '   {:09o} {:3d}\n'.format(s, s)
#----------------------------------------------------------
# Main starts here
from sys import exit
nbits = 27
hiCount = 1<<nbits
deLimit = hiCount
#deLimit = 3*(1<<18)
#deLimit = 100002
pv = []                    # Clear the principal-values array
uv = [0]*hiCount           # Set up the used-values flag array

#print sorted(['{:09o}'.format(x) for x in sequence(3)])
#print
#print sorted(['{:09o}'.format(x) for x in sequence(3*512)])
#print
nbrLists = makeNbrLists()
#print nbrLists

for i in xrange(1,1<<nbits):
    if i>deLimit: break
#    if i & 077777777 == 1:
#        print 'i = {:8d} = {:09o}'.format(i,i)
    if uv[i]==0:
        if testValidShape(i):
            pv.append(i)
#            print
#            print 'append {}  {:6o}: '.format(i,i)
#        else: print 'not append {}  {:6o}: '.format(i,i)

        # Make list of applicable translates
        translates = [i]
        for (mask,delt) in [(0111111111,-1), (0007007007, -3), (0000000777, -9), (0444444444,1), (0700700700,3), (0777000000, 9)]:
            for far in (1,2):
                tras = translates
                for v in tras:
                    if v&mask == 0:
                        w = v<<delt if delt>0 else v>>-delt
                        if not w in translates: translates.append(w)
        # Process list of translates
        for shape in translates:
            if uv[shape]==0:
#                print '\nSeq. {:6o}: '.format(shape),
                for u in sequence(shape):
                    uv[u] = i   # Flag shape u as in use (as a transform of i)
#                    print '{:o} '.format(u),
#                print

# Make histogram of bit-counts, ie # of shapes with given # of bits
bc = [0]*(nbits+1)
for i in pv:
    bc[bitCount(i)] += 1

for i in range(nbits+1):
    print '{:3}: {:9}'.format(i, bc[i])

# Print the shapes that are made of 4 cubes
print '         z=0      z=1      z=2'
for i in pv:
    if bitCount(i)==4:
        printShape(i)
print
# Print the shapes that are made of 26 cubes
print '         z=0      z=1      z=2'
for i in pv:
    if bitCount(i)==26:
        printShape(i)

#print pv
#print [i for i in pv if i<deLimit]

exit(0)

#print '        z=0    z=1    z=2'
for i in pv:
    if i>deLimit: break
    if testValidShape(i):
        printShape(i)