/* Filter to format solutions for "845 Combinations",
   a puzzle from an unknown author having ROC patent 66009.
   Programmed by r mcnelly Jan 2002.  rmcnelly@cris.com
   Program processes output of dpfp.c by Frans Faase
   and gendpfp.c by Frans Faase.

  References:

  http://home.planet.nl/~faase009/HaDPF.html
      Programs and algorithms for solving Discrete Piece Fitting Puzzles,
   of which 845 Combinations is one
  http://www-cs-faculty.stanford.edu/~knuth/papers/dancing.ps.gz
   References [1] 845 Combinations Puzzles:
  845 Interestingly Combinations (Taiwan: R.O.C. Patent 66009)
  . [There is no indication of the author or manufacturer.
  This puzzle, which is available from www.puzzletts.com,
  actually has only 83 solutions.
  It carries a Chinese title, "Dr. Dragon's Intelligence Profit System."]

  http://www.asahi-net.or.jp/~rh5k-isn/Puzzle/845Combinations/
     The above site lists information and solutions

  http://www.cs.virginia.edu/lounge/games.html
     The above site mentions 845 Combinations in a list of 'lounge games'

*/
#include <stdio.h>
#include <string.h>

int main(int argc, char * argv[])
{
 FILE * fin;
 FILE * fout;
 int soln[120];
 char comma;
 int i;
 int count = 1;
 int bogus = 0;
 int node = 0;
 int s[10] = {0,0,0,0,0,0,0,0,0,0};
 int t = 0;
 int x[30]= {0,0,0,0,0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
 int y = 0;
 char format13t[40]="%d       %d       %d       %d       %d\n";
 char format13b[40]="%d       %d       %d       %d       %d\n";
 char format46t[40]="%d       %d       %d       %d       %d\n";
 char format46b[40]="%d       %d       %d       %d       %d\n";
 char format79t[40]="%d       %d       %d       %d       %d\n";
 char format79b[40]="%d       %d       %d       %d       %d\n";

 fin = stdin;
 fout = stdout;

 while(!feof(fin))
 {
  for(i=0;i<120;i++)
  {
   fscanf(fin, "%d %c", &soln[i],&comma);
  }
  if(feof(fin))
   break;
  /* if pairs of pieces cross at internal node, this is no soln */
  node = 0;
  strcpy(format13t,"%d       %d       %d       %d       %d\n");
  strcpy(format13b,"%d       %d       %d       %d       %d\n");
  strcpy(format46t,"%d       %d       %d       %d       %d\n");
  strcpy(format46b,"%d       %d       %d       %d       %d\n");
  strcpy(format79t,"%d       %d       %d       %d       %d\n");
  strcpy(format79b,"%d       %d       %d       %d       %d\n");
  if((soln[29] == soln[30] && soln[23] == soln[40]
   && soln[30] != soln[40]) )
  {
   node += 1;
   strcpy(format13t,"%d   ####%d####   %d       %d       %d\n");
   strcpy(format13b,"%d   ####%d####   %d       %d       %d\n");
  }
  if((soln[56] == soln[57] && soln[50] == soln[67]
   && soln[57] != soln[67]) )
  {
   node += 2;
   strcpy(format13t,"%d       %d   ####%d####   %d       %d\n");
   strcpy(format13b,"%d       %d   ####%d####   %d       %d\n");
  }
  if((soln[83] == soln[84] && soln[77] == soln[94]
   && soln[84] != soln[94]) )
  {
   node += 3;
   strcpy(format13t,"%d       %d       %d   ####%d####   %d\n");
   strcpy(format13b,"%d       %d       %d   ####%d####   %d\n");
  }
  if((soln[32] == soln[33] && soln[24] == soln[41]
   && soln[33] != soln[41]) )
  {
   node += 4;
   strcpy(format46t,"%d   ####%d####   %d       %d       %d\n");
   strcpy(format46b,"%d   ####%d####   %d       %d       %d\n");
  }
  if((soln[59] == soln[60] && soln[51] == soln[68]
   && soln[60] != soln[68]) )
  {
   node += 5;
   strcpy(format46t,"%d       %d   ####%d####   %d       %d\n");
   strcpy(format46b,"%d       %d   ####%d####   %d       %d\n");
  }
  if((soln[86] == soln[87] && soln[78] == soln[95]
   && soln[87] != soln[95]) )
  {
   node += 6;
   strcpy(format46t,"%d       %d       %d   ####%d####   %d\n");
   strcpy(format46b,"%d       %d       %d   ####%d####   %d\n");
  }
  if((soln[35] == soln[36] && soln[25] == soln[42]
   && soln[36] != soln[42]) )
  {
   node += 7;
   strcpy(format79t,"%d   ####%d####   %d       %d       %d\n");
   strcpy(format79b,"%d   ####%d####   %d       %d       %d\n");
  }
  if((soln[62] == soln[63] && soln[52] == soln[69]
   && soln[63] != soln[69]) )
  {
   node += 8;
   strcpy(format79t,"%d       %d   ####%d####   %d       %d\n");
   strcpy(format79b,"%d       %d   ####%d####   %d       %d\n");
  }
  if((soln[89] == soln[90] && soln[79] == soln[96]
   && soln[90] != soln[96]) )
  {
   node += 9;
   strcpy(format79t,"%d       %d       %d   ####%d####   %d\n");
   strcpy(format79b,"%d       %d       %d   ####%d####   %d\n");
  }
  if((soln[29] == soln[30] && soln[23] == soln[40]
   && soln[30] != soln[40]) ||
  (soln[56] == soln[57] && soln[50] == soln[67]
   && soln[57] != soln[67]) ||
  (soln[83] == soln[84] && soln[77] == soln[94]
   && soln[84] != soln[94]) ||
  (soln[32] == soln[33] && soln[24] == soln[41]
   && soln[33] != soln[41]) ||
  (soln[59] == soln[60] && soln[51] == soln[68]
   && soln[60] != soln[68]) ||
  (soln[86] == soln[87] && soln[78] == soln[95]
   && soln[87] != soln[95]) ||
  (soln[35] == soln[36] && soln[25] == soln[42]
   && soln[36] != soln[42]) ||
  (soln[62] == soln[63] && soln[52] == soln[69]
   && soln[63] != soln[69]) ||
  (soln[89] == soln[90] && soln[79] == soln[96]
   && soln[90] != soln[96]) )
  {
   fprintf(fout,"node %d BOGUS(%d) in ",node,++bogus);
   fprintf(stderr,"Node %d is BOGUS(%d) in solution\n",node,bogus,count);
  }
  else
  {
   if(soln[13] == 4)
   {
    s[4]++;
    t++;
   }
   else if(soln[12] == 7)
   {
    s[7]++;
    t++;
   }
   else
   {
    s[soln[0]]++;
    t++;
   }
   if(soln[0] == 7 && soln[1] == 7)
    x[0]++;
   if(soln[12] == 7 && soln[17] == 7)
    x[1]++;
   if(soln[0] == 9 && soln[13] == 9)
    x[2]++;
   if(soln[0] == 9 && soln[14] == 9)
    x[3]++;
   if(soln[0] == 6 && soln[3] == 6 && soln[12] == 6)
    x[4]++;
   if(soln[0] == 6 && soln[3] == 6 && soln[15] == 6)
    x[5]++;
   if(soln[0] == 6 && soln[12] == 6 && soln[39] == 6)
    x[6]++;
   if(soln[0] == 8 && soln[12] == 8 && soln[27] == 8)
    x[7]++;
   if(soln[0] == 8 && soln[13] == 8 && soln[14] == 8)
    x[8]++;
   if(soln[0] == 8 && soln[12] == 8 && soln[13] == 8)
    x[9]++;
   if(soln[0] == 2 && soln[3] == 2 && soln[30] == 2)
    x[10]++;
   if(soln[0] == 2 && soln[27] == 2 && soln[30] == 2)
    x[11]++;
   if(soln[0] == 2 && soln[3] == 2 && soln[27] == 2)
    x[12]++;
   if(soln[12] == 2 && soln[39] == 2 && soln[40] == 2)
    x[13]++;
   if(soln[12] == 3 && soln[27] == 3 && soln[57] == 3)
    x[14]++;
   if(soln[0] == 3 && soln[30] == 3 && soln[41] == 3)
    x[15]++;
   if(soln[0] == 0 && soln[13] == 0 && soln[27] == 0)
    x[16]++;
   if(soln[12] == 0 && soln[3] == 0 && soln[13] == 0)
    x[17]++;
   if(soln[0] == 0 && soln[12] == 0 && soln[39] == 0)
    x[18]++;
   if(soln[0] == 0 && soln[3] == 0 && soln[14] == 0)
    x[19]++;
   if(soln[0] == 5 && soln[12] == 5 && soln[39] == 5)
    x[20]++;
   if(soln[12] == 5 && soln[14] == 5 && soln[29] == 5)
    x[21]++;
   if(soln[12] == 5 && soln[14] == 5 && soln[0] == 5)
    x[22]++;
   if(soln[0] == 5 && soln[13] == 5 && soln[54] == 5)
    x[23]++;
   if(soln[13] == 4 && soln[27] == 4 && soln[40] == 4)
    x[24]++;
   if(soln[0] == 1 && soln[12] == 1 && soln[40] == 1)
    x[25]++;
   if(soln[0] == 1 && soln[3] == 1 && soln[12] == 1)
    x[26]++;
   if(soln[0] == 1 && soln[12] == 1 && soln[39] == 1)
    x[27]++;
   if(soln[0] == 1 && soln[12] == 1 && soln[30] == 1)
    x[28]++;
   if(soln[0] == 1 && soln[3] == 1 && soln[14] == 1)
    x[29]++;
  }

  fprintf(fout,"Solution %d\n",count++);
  fprintf(fout,"x %d %d %d x %d %d %d x %d %d %d x %d %d %d x\n",
   soln[12],soln[17],soln[22],soln[39],soln[44],soln[49],
   soln[66],soln[71],soln[76],soln[93],soln[98],soln[103]);
  fprintf(fout,"%d       %d       %d       %d       %d\n",
   soln[0],soln[27],soln[54],soln[81],soln[108]);
  fprintf(fout,"%d       %d       %d       %d       %d\n",
   soln[1],soln[28],soln[55],soln[82],soln[109]);
  fprintf(fout,format13t,
   soln[2],soln[29],soln[56],soln[83],soln[110]);
  fprintf(fout,"x %d %d %d x %d %d %d x %d %d %d x %d %d %d x\n",
   soln[13],soln[18],soln[23],soln[40],soln[45],soln[50],
   soln[67],soln[72],soln[77],soln[94],soln[99],soln[104]);
  fprintf(fout,format13b,
   soln[3],soln[30],soln[57],soln[84],soln[111]);
  fprintf(fout,"%d       %d       %d       %d       %d\n",
   soln[4],soln[31],soln[58],soln[85],soln[112]);
  fprintf(fout,format46t,
   soln[5],soln[32],soln[59],soln[86],soln[113]);
  fprintf(fout,"x %d %d %d x %d %d %d x %d %d %d x %d %d %d x\n",
   soln[14],soln[19],soln[24],soln[41],soln[46],soln[51],
   soln[68],soln[73],soln[78],soln[95],soln[100],soln[105]);
  fprintf(fout,format46b,
   soln[6],soln[33],soln[60],soln[87],soln[114]);
  fprintf(fout,"%d       %d       %d       %d       %d\n",
   soln[7],soln[34],soln[61],soln[88],soln[115]);
  fprintf(fout,format79t,
   soln[8],soln[35],soln[62],soln[89],soln[116]);
  fprintf(fout,"x %d %d %d x %d %d %d x %d %d %d x %d %d %d x\n",
   soln[15],soln[20],soln[25],soln[42],soln[47],soln[52],
   soln[69],soln[74],soln[79],soln[96],soln[101],soln[106]);
  fprintf(fout,format79b,
   soln[9],soln[36],soln[63],soln[90],soln[117]);
  fprintf(fout,"%d       %d       %d       %d       %d\n",
   soln[10],soln[37],soln[64],soln[91],soln[118]);
  fprintf(fout,"%d       %d       %d       %d       %d\n",
   soln[11],soln[38],soln[65],soln[92],soln[119]);
  fprintf(fout,"x %d %d %d x %d %d %d x %d %d %d x %d %d %d x\n",
   soln[16],soln[21],soln[26],soln[43],soln[48],soln[53],
   soln[70],soln[75],soln[80],soln[97],soln[102],soln[107]);
  fprintf(fout,"\n");
  if(feof(stdin))
   break;
 }
 fprintf(fout,"TOTAL BOGUS=%d\n",bogus);
 fprintf(fout,"TOTAL SOLUTIONS=%d\n",count-bogus-1);
 fprintf(stderr,"TOTAL BOGUS=%d\n",bogus);
 fprintf(stderr,"TOTAL SOLUTIONS=%d\n",count-bogus-1);
 for(i=0;i<10;i++)
 {
  fprintf(fout,"piece[%d]=%d\n",i,s[i]);
  fprintf(stderr,"piece[%d]=%d\n",i,s[i]);
 }
 fprintf(fout,"tot=%d\n",t);
 fprintf(stderr,"tot=%d\n",t);
 for(i=0;i<30;i++)
 {
  fprintf(fout,"way[%d]=%d ",i,x[i]);
  fprintf(stderr,"way[%d]=%d ",i,x[i]);
  if(i % 3 == 2)
  {
   fprintf(fout,"\n");
   fprintf(stderr,"\n");
  }
 }
 for(i=0;i<30;i++)
  y+=x[i];
 fprintf(fout,"tot ways=%d\n",y);
 fprintf(stderr,"tot ways=%d\n",y);
 return 0;
}