Cube Counter

#/usr/bin/python
# -*- coding: utf8 -*-

def build_rotations():
  # base table provides rotations that map each axis onto the X axis in both
  # orientations
  base_rotations = [
    [0, 1, 2,  1,  1,  1],
    [0, 1, 2, -1, -1,  1], # 180° rotation about Z
    [1, 0, 2,  1, -1,  1], # +90° rotation about Z
    [1, 0, 2, -1,  1,  1], # -90° rotation about Z
    [2, 1, 0,  1,  1, -1], # +90° rotation about Y
    [2, 1, 0, -1,  1,  1]] # -90° rotation about Y

  all_rotations = []
  # now that we've established the X axis, spin about the X axis to explore the
  # mappings onto the Y and Z axes.
  for r in base_rotations:
    all_rotations += [[r[0], r[1], r[2], r[3],  r[4],  r[5]]]   # no rotation
    all_rotations += [[r[0], r[2], r[1], r[3],  r[4], -r[5]]]  # +90° rotation about X
    all_rotations += [[r[0], r[1], r[2], r[3], -r[4], -r[5]]] # 180° rotation about X
    all_rotations += [[r[0], r[2], r[1], r[3], -r[4],  r[5]]]  # -90° rotation about X

  return all_rotations

rotation_table = build_rotations()

face_size = 8
offset_join_size = 6

def canonicalize_placement(placement):
  minima = [min([p[i] for p in placement]) for i in range(3)]
  maxima = [max([p[i] for p in placement]) for i in range(3)]
  size = [maxima[i] - minima[i] for i in range(3)]
  center = [(maxima[i] + minima[i])//2 for i in range(3)]

  placement = [[p[i] - center[i] for i in range(3)] for p in placement]

  best_str = None
  best = None
  best_count = 1

  for rotation in rotation_table:
    map = rotation[0:3]
    scale = rotation[3:6]

    rotated = sorted([tuple([p[map[i]] * scale[i] for i in range(3)]) for p in placement])

    rotated_str = str(rotated)

    if best is None or rotated_str < best_str:
      best = rotated
      best_str = rotated_str
      best_count = 1
    elif rotated_str == best_str:
      best_count += 1

  return (best, best_count)

def collides(placement, new_location):
  for p in placement:
    dist = [abs(p[i] - new_location[i]) for i in range(3)]
    if max(dist) < face_size:
      return True
  return False

def neighbor_locations(base_location):
  for face_axis in range(3):
    axis2 = (face_axis+1)%3
    axis3 = (face_axis+2)%3
    for face_axis_dir in [-1,1]:
      delta = [0,0,0]
      delta[face_axis] = face_axis_dir * face_size
      yield tuple([base_location[i] + delta[i] for i in range(3)])
      delta[axis2] = +offset_join_size
      yield tuple([base_location[i] + delta[i] for i in range(3)])
      delta[axis2] = -offset_join_size
      yield tuple([base_location[i] + delta[i] for i in range(3)])
      delta[axis2] = 0
      delta[axis3] = +offset_join_size
      yield tuple([base_location[i] + delta[i] for i in range(3)])
      delta[axis3] = -offset_join_size
      yield tuple([base_location[i] + delta[i] for i in range(3)])

def count_placements(count):
  prev_placements = {}
  for n in range(1,count+1):
    placements = {}
    if n == 1:
      (placement, count) = canonicalize_placement([(0,0,0)])
      placements[str(placement)] = (placement, count)
    else:
      for base,unused in prev_placements.values():
        for neighbor_base in base:
          for new_loc in neighbor_locations(neighbor_base):
            if not collides(base, new_loc):
              (placement, count) = canonicalize_placement(base + [new_loc])
              placement_str = str(placement)
              if not placement_str in placements:
                placements[placement_str] = (placement, count)
              #  print '%s: %d'%(placement_str, count)
      print '%d: %s'%(n, len(placements))
    prev_placements = placements