#include <string.h>
#include <stdlib.h>
#include <stdio.h>

/*
  Sol LeWitt's "Open Cubes" sequence: 1, 3, 123, ...
  
  Counts the number of ways to remove 0 or more edges of an n-cube such that remaining edges are connected and span all n dimensions.

  An alternate sequence considers reflections equivalent: 1, 3, 78, ...

  This program generates the 123 (and 78) solutions for n=3
  
  Bit Encoding...

  BIT  0 1 2 3 4 5 6 7 8 9 10 11 
  -------------------------------
  V0   0 0 0 1 1 2 2 3 4 4  5  6 
  V1   1 2 4 3 5 3 6 7 5 6  7  7 

       x - - - - x - - x -  -  x    X_mask =  0x921
       - y - y - - - - - y  y  -    Y_mask =  0x60a
       - - z - z - z z - -  -  -    Z_mask =  0x0d4

  Written by Andrew Weimholt - Feb 12, 2013
*/
#define MAXV 8
#define MAXE 12
//
static int X  = 0x921;
static int Y  = 0x60a;
static int Z  = 0x0d4;
//
static int v0[MAXE] = {0,0,0,1,1,2,2,3,4,4,5,6};
static int v1[MAXE] = {1,2,4,3,5,3,6,7,5,6,7,7};
//
static int e[MAXV][MAXV];
void init_e(){int i=0;for(int b=0;b<MAXE;b++)e[v0[b]][v1[b]]=e[v1[b]][v0[b]]=++i;}
//
static int vmask[MAXV];
void init_vm(){for(int e=0;e<MAXE;e++){vmask[v0[e]]|=(1<<e);vmask[v1[e]]|=(1<<e);}}
//
static int perm3[6][3] = {{0,1,2},{0,2,1},{1,0,2},{1,2,0},{2,0,1},{2,1,0}};
//                         even    odd     odd     even    even    odd
//
//  odd permutations have index congruent to 1 or 2 mod 4
// even permutations have index congruent to 0 or 3 mod 4
//
static int axis_permutation_parity[MAXV] = {0,1,1,0,0,1};
static int axis_reflection_parity [MAXV] = {0,1,1,0,1,0,0,1};
//
static int chiral_sensitive_solns  [0x1000]; // configurations which differ by even permutations of the cube (rotations only) are considered equivalent. 
static int chiral_insensitive_solns[0x1000]; // configurations which differ by even/odd permutations (rotations or reflections) are considered equivalent.
static int num_chiral_sensitive_solns   = 0;
static int num_chiral_insensitive_solns = 0;
//
//////////////////////////////////////////////////////////////////////////////////////////

int permute(int x, int perm)
{
  int  B[3] = {!!(x&4), !!(x&2), !!(x&1)};
  int NB[3] = {B[perm3[perm][0]], B[perm3[perm][1]], B[perm3[perm][2]]};
  return (NB[0]?4:0)|(NB[1]?2:0)|(NB[2]?1:0);
}

int transform_e(int edge, int perm, int mask)
{
  int a = permute(v0[edge],perm) ^ mask;
  int b = permute(v1[edge],perm) ^ mask;
  int newE = e[a][b]-1;
  if (newE == -1)
  {
    printf("fatal error: A=%d, B=%d, a=%d, b=%d\n", v0[edge], v1[edge], a, b);
    exit(0);
  }
  return newE;
}

int transform_cub(int cub, int perm, int mask)
{
  int newcube = 0;
  for (int i=0;i<MAXE;i++)
    if (cub & (1<<i))
      newcube |= (1<<transform_e(i,perm,mask));
  return newcube;
}

int connected(int n, int *masks)
{
  if (n<2)
    return 1;

  int k=0;
  int array[MAXV];

  for (int i=0;i<n;i++)
  {
    int j=0;
    int flag=0;
    for(;j<k;j++)
      if (masks[i]&array[j])
        flag=(array[j] |= masks[i]);
    if (flag==0)
      array[k++] = masks[i];
  }
 
  return (k<n) ? connected(k,array) : 0;
}

int intact(int C)
{
  int v[MAXV];
  int n=0;
  for (int i=0;i<MAXV;i++)
    if (C & vmask[i])
      v[n++] = (C & vmask[i]);  
  return connected(n,v);
}

void eval(int C)
{
  // full-3d check
  if (!((C&X)&&(C&Y)&&(C&Z)))
    return;

  // connected check
  if (!intact(C))
    return;

  // canonical check
  int canon_odd = 1;

  for (int perm=0;perm<6;perm++) for (int mask=0;mask<8;mask++)
  {
    int odd = axis_permutation_parity[perm] ^ axis_reflection_parity[mask]; 
     
    int newC = transform_cub(C,perm,mask);
    if ((unsigned int)newC < (unsigned int)C)
    {
      if (odd)         // an odd permutation with a lower numerical representation does not rule out that possibility
        canon_odd = 0; // that this is the canonical representation among even permutations. 
      else 
        return;        // but, once an even permutation is found which has a lower numerical representation, we are done
    }
  }

  // if we get here, then C is the canonical representation among even permutations, and if we get here with canon_odd
  // still non-zero, then C is the canonocal representation among even AND odd permutations.

  chiral_sensitive_solns[num_chiral_sensitive_solns++] = C;
  if (canon_odd)
    chiral_insensitive_solns[num_chiral_insensitive_solns++] = C;
}

int main(int argc, char *argv[])
{
  init_e();
  init_vm();
  for (int c=1;c<0x1000;c++)
    eval(c);

  /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  // Output results
  //
  // Output contains the 123 chiral-sensitive solutions followed immediately by the 78 chiral-insensitive solutions.
  //
  // When running under linux/unix... 
  //    to show only the first 123 lines:    OpenCubes3d |head -123
  //    to show only the last   78 lines:    OpenCubes3d |tail -78
  // 
  /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////  

  int max[2]      = { num_chiral_sensitive_solns, num_chiral_insensitive_solns };
  int *soln[2]    = {     chiral_sensitive_solns,     chiral_insensitive_solns };
  char fmt[2][32] = { "%03d: 0x%03x\n",           "%02d: 0x%03x\n"             };

  for (int n=0;n<2;n++) 
    for (int i=0;i<max[n];i++)
      printf(fmt[n], i+1, soln[n][i]);
 
  return 0;
}