TweetFollow Us on Twitter

Sep 99 Challenge

Volume Number: 15 (1999)
Issue Number: 9
Column Tag: Programmer's Challenge

Programmer's Challenge

by Bob Boonstra, Westford, MA

Playfair Decipher

This month the Challenge ventures into the world of codebreaking. Simple codes, perhaps, but codes with a real-world history. Tom Saxton recently wrote to suggest a Challenge based on a simple substitution cipher. The problem we picked is a little more complicated, being based on letter pairs (digraphs) rather than single character substitutions. Invented by Sir Charles Wheatstone in the mid-1800s, the Playfair cipher (named after his friend, Baron Lyon Playfair) was used to encrypt telegraphic traffic and was also used during the Boer War and the First World War.

The Playfair cipher uses a 5x5 encryption matrix, in which each letter of the alphabet appears once. (The letters "i" and "j" map to the same cell.) While we codebreakers don't know what the keyword is, or what the matrix is for any given cipherText, we are fortunate in that our Intelligence organization has determined that our adversaries create their matrices from a keyword in a known manner.

As an example, let's use the keyword "cryptogram" to generate the encryption matrix. First, we write the unique characters in the keyword across in one line: Notice that the letter "r" appears only once, even though it occurs twice in the keyword.

				CRYPTOGAM

Next, the remaining letters of the alphabet are written below:

				CRYPTOGAM
				BDEFHIKLN
				QSUVWXZ-

To form the 5x5 encryption matrix, the letters are read off by columns:

				C  B  Q  R  D
				S  Y  E  U  P
				F  V  T  H  W
				O IJ  X  G  K
				Z  A  L  M  N

To encode a message, the plainText is split into two-letter groups. If a two-letter group would consist of a double letter, an 'X' is inserted between the double letters. An 'X' is also added at the end if needed to complete the last group. So, if the plainText is "The scheme really works." the two-letter groups formed as follows:

				TH ES CH EM ER EA LX LY WO RK SX

Each letter pair is encoded using the encryption matrix. If the letters are in the same row, the letter to its right in that row (wrapping the row if necessary) replaces each letter. If the letters are in the same column, each letter is replaced by the letter beneath it in that column (again, wrapping the column back to the top if necessary). If the letters are in different rows and columns, each letter is replaced with the letter at the intersection of its row and the other letter's column. So, in our example, the cipherText becomes:

				HW UY RF UL UQ YL QL AE FK DG EO

So, with that explanation, the prototype for the code you should write is:

#if defined(__cplusplus)
extern "C" {
#endif

void InitPlayfair(
	const char *words[],		/* dictionary words */
	long numDictionaryWords		/* number of null-terminated words in dictionary */
);

void DecodePlayfair(
	const char *cipherText,	/* null-terminated text to decode */
	char *plainText					/* null-terminated decoded text */
);

void TermPlayfair(void);

#if defined(__cplusplus)
}
#endif

All of the words used in the plainText messages, as well as the keyword used to construct the encryption matrix, will be included in the numDictionaryWords words provided to your InitPlayfair routine. The words will contain only uppercase alphabetic characters and will be sorted in alphabetical order. Your InitPlayfair routine may analyze the dictionary and allocate memory to store any analysis results. After InitPlayfair is called, DecodePlayfair will be called multiple (an average of 10-100) times with cipherText messages that are to be decoded into plainText. Finally, TermPlayfair will be called so that you can return any memory allocated by InitPlayfair.

The winner will be the solution that decodes all of the cipherText correctly in the least amount of execution time. A large fixed penalty will be added for each message that is decoded incorrectly.

This will be a native PowerPC Challenge, using the latest CodeWarrior environment. Solutions may be coded in C, C++, or Pascal. Following our tradition for September Challenges, solutions may also be coded in assembly language. In response to numerous requests, solutions in Java will also be accepted this month. Java entries must be accompanied by a test driver that uses the interface provided in the problem statement.

Thanks to Tom Saxton for suggesting this Challenge. Tom wins two Programmer's Challenge points for the suggestion, as can you if you send in an idea that inspires a Challenge used in the column.

Three Months Ago Winner

Ernst Munter (Kanata, ON, Canada) makes yet another appearance in the Programmer's Challenge victory lane for submitting the fastest solution to the June Tetraminx Challenge. The Tetraminx Challenge required entrants to solve a puzzle with moveable pieces in the Rubik's Cube tradition, where the puzzle is shaped in the form of a truncated tetrahedron, with 28 triangular facelets arranged in 4 hexagonal and 4 triangular faces. Ernst was one of five entries to this contest, and his solution was more than twice as fast as his nearest competitor.

The Tetraminx problem is small enough that exhaustive computation of the solution for all possible problems is feasible, although barely so. Several contestants noted that all scrambled states are within 11 moves from the "solved" state. Ernst tells me that there are 933120 unique legal puzzle positions, of which 283888 are within 7 moves of the "start" position, 764355 within 8 moves, 930631 within 9 moves, 933088 within 10 moves, and all 933120 within 11 moves. Ernst and Rob Shearer both decided that spending cycles to precompute solutions would save time when solving a large number of test cases. Both Rob and Ernst explored the possibility of precomputing solution tables as part of "off the clock" initialization, but I decided that was contrary to the spirit of this Challenge. Initialization time was counted in the evaluation of all of the entries.

Ernst also included an option to precompute solutions up to a parameterized look-ahead depth, trading off reduced initialization time for increased individual solution time. The optimal setting for that look-ahead depth depends on the estimated number of test cases to be evaluated. For scoring purposes, I set that parameter to the worst case maximum value of 11 moves. Setting the parameter to the value suggested by Ernst for the actual number of test cases made it run even faster: 5.2 seconds instead of 8.3 seconds. At the worst case setting, Ernst's solution table occupies a little over 10MB, with a 22-bit state code stored in a 32-bit word for each legal state. The code for constructing the tree is in the Init method of the SolutionTree object, and the code for searching it is in the Solve method. While not used in the scored solution because the look-ahead parameter was set to its maximum value, the SearchNode object provides the logic to search backward from a puzzle position until a position in the incomplete solution tree is reached.

The table below lists the results for each of the solutions submitted. The test cases consisted of the same 100000 randomly generated puzzle positions. Three of the entries completed all of the test cases in a relatively short period of time. For the other entries, I scaled back the test cases to a number that could be solved within a couple of minutes. The table includes the total execution time and the number of puzzle moves generated to solve the test cases, along with an extrapolated total score that estimates the time needed to solve the full set of test cases. As usual, the table also lists the code size, data size, and programming language for each entry. The number in parentheses after the entrant's name is the total number of Challenge points earned in all Challenges prior to this one..

Name Total Score # Tests Time (secs) # Moves Code Size Data Size Lang
Ernst Munter (467) 8.3 100000 8.3 779347 6184 78356 C++
Willeke Rieken (51) 18.2 100000 18.2 1344553 11032 548 C++
Rob Shearer (7) 21.2 100000 21.2 779347 28764 3733 C++
Derek Ledbetter 3121.2 1000 31.2 7724 27928 3595 C++
Randy Boring (110) 112898.7 100 112.9 778 9536 399 C

Top Contestants

Listed here are the Top Contestants for the Programmer's Challenge, including everyone who has accumulated 10 or more points during the past two years. The numbers below include points awarded over the 24 most recent contests, including points earned by this month's entrants.

Rank Name Points
1. Munter, Ernst 221
2. Saxton, Tom 108
3. Boring, Randy 75
4. Maurer, Sebastian 70
5. Rieken, Willeke 51
6. Heithcock, JG 37
7. Lewis, Peter 31
8. Nicolle, Ludovic 27
9. Brown, Pat 20
10. Hostetter, Mat 20
11. Mallett, Jeff 20
12. Murphy, ACC 14
13. Shearer, Rob 14
14. Jones, Dennis 12
15. Hewett, Kevin 10
16. Selengut, Jared 10
17. Smith, Brad 10
18. Varilly, Patrick 10

There are three ways to earn points: (1) scoring in the top 5 of any Challenge, (2) being the first person to find a bug in a published winning solution or, (3) being the first person to suggest a Challenge that I use. The points you can win are:

1st place 20 points
2nd place 10 points
3rd place 7 points
4th place 4 points
5th place 2 points
finding bug 2 points
suggesting Challenge 2 points

Here is Ernst's winning Tetraminx solution:

Tetraminx.cp
Copyright © 1999 Ernst Munter

/*

  Combined Version:
  	choose one-step solution lookup directly from puzzle state
  	or tree search with selectable degree of look-ahead.
  	
Tetraminx Combinatorics
------------
I think of the puzzle as a number of solid parts, the smaller tetrahedra, and use the term "tet" for the 10 tetrahedra which make up the puzzle.

Tets are moved relative to each other when the puzzle is twisted. The 28 observable colored triangular facelets are attached and fixed to the four corner tets (4 facelets each), and the six edge tets (2 facelets each).  To solve the puzzle, we do not need to track the 28 facelets but only the 10 tets and bring them into their unique home positions.

Each twist (Move) of the puzzle sends 4 tets to neighboring positions.

Each of the corner tets can only be in one of 3 different positions. The edge tets share 12 possible positions (6 places on the edges, times two for the two colors which can be flipped).

The entire puzzle state can be represented in a single 32-bit word.

The number of combinations of all positions of the 4 corner tets is 81.

The possible locations of the 6 unique edge tets are given by their permutations, that is 6! = 720.  In addition, each edge tet can be flipped to be in one of 2 flip position.  Flip positions are not entirely independent of the edge tet locations, and only the "even" parity combinations are found in a legal puzzle, that is 32 flip positions.

These three fields put together require 22 bits. This leaves room to store the move code that leads to or from this state to another state, alongside the state code.

Solution Strategy
---------
The puzzle has exactly 933,120 legal states, and 3,732,480 possible states.

A tree of 81 * 720 * 32 nodes would be sufficient to store all possible state-move combinations, taking into account the even flip parity requirement.

I pre-build the entire inverse solution tree either at program start, under control of the constructor of this static class, or alternatively during the first call to Tetraminx().

The inverse solution tree starts at the solution, and grows with each added move.  Only new nodes representing puzzle states not found earlier, are stored.

Each node contains a 22 bit index of the father node, and a 3-bit move code, the move needed to reach this node.

This tree is stored as an array of actually 81 * 1024 * 32 nodes, in about 10.1 MB.  Each non-0 node of the tree corresponds to a legal puzzle state, from which the shortest solution can be traced back towards the root of the tree.

A ping-pong pair of stacks is used to temporarily hold the states and moves at one level, from which the states and moves of the next level are generated.

One-step Solution Lookup
------------
For solving, the puzzle state, given in the form of 28 colored facelets is first converted to a representation as tets, and then converted to the 22-bit state code which forms the index of a node in the inverse solution tree.

The move sequence that leads to this node from the solution root can now be traced in reverse, while recording the inverse of each move stored in the nodes on the way to the root.

Tree Search with Look-Ahead
--------------
It takes a noticable time, perhaps a few seconds depending on CPU and memory speed, to prebuild the entire 10 MB inverse solution tree.

A second algorithm is presented which makes use of a partial inverse solution tree that can be initialized more quickly.

We solve a puzzle which requires more moves than the prebuilt tree contains, by searching with a forward tree until a node in the inverse tree is encountered.  At that point the remaining moves can be retrieved from the partial inverse tree.

This algorithm offers a trade-off between initialization time and solution time.  The more puzzles need to be solved, the faster the amortization of the investment in initialization time, and the bigger an inverse solution tree can be justified.

Assumptions
------
It is assumed that only valid puzzles are presented.  Invalid puzzles (missing colors for example) and unsolvable puzzles will probably return numMoves = 0, but this has not been tested exhaustively.

The program allocates about 11 MB of memory. I set the minimum heap size for my test program to 16 MB.
*/

#include <stdlib.h>
#include <string.h>
#include "tetra.h"

// set SILENT_INIT = 0
// if you want table initialization deferred until the first puzzle.

// SILENT_INIT set to 0 for compliance with Challenge evaluation criteria
#define SILENT_INIT 0

#if SILENT_INIT

	// Initialization time will not be measured
	// Pre-build complete solution tree and use full look-ahead
	#define M 11

#else

	// Initialization time will count, but total time can be optimized
	// by setting LOOK_AHEAD to an appropriate value, for example:

	//	very few tests	( < 	   10 )  optimal LOOK_AHEAD = 4
	//	very short run	( < 	  100 )  optimal LOOK_AHEAD = 5
	//	     short run	( <     5,000 )  optimal LOOK_AHEAD = 6
	//	   average run	( <   100,000 )  optimal LOOK_AHEAD = 7
	//		  long run	( < 1,000,000 )  optimal LOOK_AHEAD = 8
	//	very  long run	( > 1,000,000 )  optimal LOOK_AHEAD = 11

// Challenge set to max value- unfair to optimize based on knowledge of test data
//	#define LOOK_AHEAD 7
	#define LOOK_AHEAD 11

	#define M (LOOK_AHEAD <  4 ?  4 : LOOK_AHEAD)

#endif

typedef unsigned char U8;
typedef unsigned long U32;
typedef unsigned short U16;

enum {
	L,R,B,K,
	k4colors=(1<<kYellow)|(1<<kBlue)|(1<<kRed)|(1<<kGreen),
	kAllEdges = 0x3F
};

// Moves and puzzle piece enumerations differ from the caller's.
// My moves are represented as +L -L +R -R +B -B +K -K
//		so that the 6 moves to try next (without back tracking
//		or duplicating the last move) can be generated easily.
// Edges and corners are rearranged so that one code can consistently
//		be used to refer to the whole piece.

inline Move Convert2Move(const int m)
	{return Move(1+m/2+4*(m&1));}
// Converts my move representation back to the caller's.

enum {	// re-numbered edge and corner facelet codes
	eLR,eRL,			//	0,1	edges with adjacent facelets
	eLB,eBL,			//	2,3
	eLK,eKL,			//	4,5
	eRB,eBR,			//	6,7
	eRK,eKR,  		//	8,9
	eBK,eKB,			//	10,11
	vRL,vKL,vBL,sL,		//	12..corner codes padded with singles
  	vLR,vBR,vKR,sR,	//	16..mod 4 so we can use 2-bit masks
  	vRB,vLB,vKB,sB,	//	20..
  	vLK,vRK,vBK,sK		//	24..
};

const U8 kMyNumbering[28] = {
	sL,sR,sB,sK,
	eBR,eRK,eKB,
	eLB,eBK,eKL,
  	eKR,eRL,eLK,
  	eLR,eRB,eBL,
  	vRL,vKL,vBL,
  	vLR,vBR,vKR,
  	vRB,vLB,vKB,
  	vLK,vRK,vBK
};

struct MyPieceState
struct MyPieceState {
// Make sure we are not penalized if enums are stored as 4-byte ints
  U8	piece;
  U8 	color;
};

/**************** Puzzle Analysis and Conversion *************/
// The Puzzle as given in the form of facelets and colors is analysed
// and re-constructed as a set of Tets.

static const int homeFace[10]={R,L,R,L, L,L,L,R,R,B};
static U8 faceColor[4];

static const int cornerSequence[4][4] = {
	{R,K,B,0},
	{L,B,K,0},
	{R,L,K,0},
	{L,R,B,0}
};

static const int kEdgeMap[4][4] = {
	{ 0, 4, 5, 6},
	{-4, 0, 7, 8},
	{-5,-7, 0, 9},
	{-6,-8,-9, 0}
};

 struct Tet
struct Tet {
// either a corner (3 faces) or an edge (2 faces)
	int		 		numFaces;
	int				pos;
	MyPieceState	face[3];
	U8				color;

	void AddFace(const MyPieceState & ps){face[numFaces++]=ps;}

	U32 LearnColor()
// For a corner tet, we learn the "nominal" color, i.e. the color
// of the opposing hexagon, by finding the missing 4th color.
	{
		int colorBit =
			k4colors
			& ~(1 << face[0].color)
			& ~(1 << face[1].color)
			& ~(1 << face[2].color);
		int c=0;

		do {
			c++;
			colorBit >>=1;
		}
		while (colorBit);
		return color = c-1;
	}

	bool LearnPosition(const int corner)//,const U8 faceColor[])
// We learn the position of a corner tet by counting the turns needed
// to bring the tet into its home position.
	{
		U32 home,homeColor=faceColor[homeFace[corner]];

		if (homeColor == face[0].color)
		{
			home=0;
			pos=face[0].piece;
		}
		else if (homeColor == face[1].color)
		{
			home=1;
			pos=face[1].piece;
		}
		else if (homeColor == face[2].color)
		{
			home=2;
			pos=face[2].piece;
		}
		else return false;

		return true;
	}

	void SetColor(const U32 c){color=c;}
	void SetPosition(const int p){pos=p;}
};

static int CmpState(const void* a,const void* b)
// for sorting pieces by position
{
	return ((MyPieceState*)a)->piece - ((MyPieceState*)b)->piece;
}

struct Puzzle
static struct Puzzle {
// Intermediate representation of the puzzle, from the set of
// 28 "Pieces" into a set of 10 "tets".
	Tet			 tet[4 + 6];
	MyPieceState myState[28];
	U8	 		 color2face[5];

	bool Init(const PieceState state[28])
// The puzzle is created from the 28 PieceStates through steps of
// learning the hexagon colors, the corner positions and the
// edge positions.
	{

// To simplify things, the PieceStates are converted to
// MyPieceType numbering, and sorted by position
		ConvertPieceNumbering(state);
		qsort(myState,28,sizeof(MyPieceState),CmpState);

		memset(tet,0,sizeof(tet));
		if (!LearnColors()) 	return false;
		if (!LearnCornerPositions()) return false;

		SetEdgeHomeColors();

		return LearnEdgePositions();
	}

	void ConvertPieceNumbering(const PieceState* s)
	{
		MyPieceState* ms=myState;
		for (int i=0;i<28;i++,ms++,s++)
		{
			ms->piece=kMyNumbering[s->piece];
			ms->color=s->color;
		}
	}

	bool LearnColors()
// Analyzes corner pieces to determine the face colors.
// The color of a hexagonal face is the 4th color missing
// among the triangle colors around the opposite corner
	{
		int corner,facelet=vRL,allFaces=0;
		for (corner=L;corner<=K;corner++)
		{
			for (int i=0;i<3;i++)
				tet[corner].AddFace(myState[facelet++]);
			faceColor[corner]=tet[corner].LearnColor();
			color2face[faceColor[corner]]=corner;
			allFaces |= 1 << faceColor[corner];
			facelet++;	// skip single facelets
		}
		return (allFaces == k4colors);// check that 4 colors exist
	}

	bool LearnCornerPositions()
	{
		for (int corner=L;corner<=K;corner++)
			if (!tet[corner].LearnPosition(corner))
				return false;

		return true;
	}

	void SetEdgeHomeColors()
	{
		for (int i=4;i<10;i++)
			tet[i].SetColor(faceColor[homeFace[i]]);
	}

	bool LearnEdgePositions()
	{
		static int pair[6][2]={
			{eLR,eRL},{eLB,eBL},{eLK,eKL},
			{eRB,eBR},{eRK,eKR},{eBK,eKB}
		};
		int posBits=0;

		for (int p=0;p<6;p++)
		{
			int i=Assign(myState[pair[p][0]],myState[pair[p][1]]);
			if (i==0) return false;
			int pos;
			if (i>0) pos = pair[p][0];
			else
			{
				i=-i;
				pos = pair[p][1];

			}
			tet[i].SetPosition(pos);
			tet[i].AddFace(myState[pair[p][0]]);
			tet[i].AddFace(myState[pair[p][1]]);
			posBits |= 1<<(pos>>1);
		}

		return (posBits == kAllEdges); // check that all edges were found
	}

	int Assign(const MyPieceState f1,const MyPieceState f2)
	{
		int hexFace1=color2face[f1.color];
		int hexFace2=color2face[f2.color];
		return kEdgeMap [hexFace1] [hexFace2];
	}

	U32 GetCornerCode()
// returns an enumeration of the 81 possible corner combinations
	{
		U32 cc =
			3 * (3 * (3 * (0x3 & P.tet[0].pos)
						+ (0x3 & P.tet[1].pos) )
				   +      (0x3 & P.tet[2].pos) )
		  +			  (0x3 & P.tet[3].pos);
		return cc;
	}

	U32 GetEdgeCode()
// returns a 15-bit concatenation of the first 5 edge positions
// the 6th position is implied by the permutation of 6 edges.
	{
		U32 ec = ((0x7 & (P.tet[4].pos >> 1)) << 12)
			| 	 ((0x7 & (P.tet[5].pos >> 1)) <<  9)
			|	 ((0x7 & (P.tet[6].pos >> 1)) <<  6)
			|	 ((0x7 & (P.tet[7].pos >> 1)) <<  3)
			|  	  (0x7 & (P.tet[8].pos >> 1));
		return ec;
	}

	U32 GetFlipCode()
// returns a 5-bit concatenation of the first 5 edge flip positions
// the 6th flip position is implied by the even parity of the flips.
	{
		U32 fc = ((1 & P.tet[4].pos) << 4)
			| 	 ((1 & P.tet[5].pos) << 3)
			|	 ((1 & P.tet[6].pos) << 2)
			|	 ((1 & P.tet[7].pos) << 1)
		  	|	  (1 & P.tet[8].pos);
		return fc;
	}
} P;

/************************ Code Converter *********************/
// Based on a 22-bit representation of puzzle state.
// Builds lookup tables to allow next states to be derived from
// the current state and the move number, by simple operations.
//
// Four corners, five edge pieces, and the flip-state of five edges,
// are independently represented in 7, 10, and 5-bit fields of the
// state code, and rotated separately.

typedef U8	CornerCode;	// range 0 to 80
typedef U8	FlipCode;	// range 0 to 31
typedef U16	EdgeCode;	// range 0 to 719 + ((0 - 31) << 10)
// StateCode = (Corners << 15) + (Flips << 10) + Edges;
typedef	U32	StateCode;	// range 0 to 81*32*1024 - 1 = 2,654,207

const U32 kSolution=0;

// Rotation groups for corners, edges, and flip bits
const U8 kRotCorner[4]  = {1,2,0,0};

enum {lr,lb,lk,rb,rk,bk};
const U8 kRotEdge[6][4] = {
	{lr,lr,lk,rb},	//lr
	{lb,bk,lb,lr},	//lb
	{lk,lb,rk,lk},	//lk
	{rk,rb,rb,lb},	//rb
	{bk,rk,lr,rk},	//rk
	{rb,lk,bk,bk}	//bk
};

const U8 kRotFlip[6][4] = {
	{0,0,1,0},	//lr
	{0,0,0,1},	//lb
	{0,1,1,0},	//lk
	{1,0,0,1},	//rb
	{1,0,0,0},	//rk
	{0,1,0,0}	//bk
};
struct CodeConverter
static
struct CodeConverter {
	U16			compressTable[32768];	// 5 * 3-bit pos to range 0-719
	CornerCode 	cornerMoveTable[81][8];	// translates corners by move
	EdgeCode	edgeMoveTable[720][8];	// translates edges + flips by move

	CodeConverter()
// Constructor builds these tables on program launch
	{
		MakeCompressTable();
		MakeCornerTable();
		MakeEdgeTable();
	}

#define BIT(x) (1<<x)
	void MakeCompressTable()
// Sequentially numbers all permutations of the numbers 0 to 5
// and stores their index in a table at the 15-bit index (5*3 bits).
    {
    	U32 used=0,a,b,c,d,e,index=0;
     	for (a=0;a<6;a++)
        {
         	used |= BIT(a);
            for (b=0;b<6;b++)
            {
            	if (used & BIT(b)) continue;
             	used |= BIT(b);
	            for (c=0;c<6;c++)
    	        {
        	    	if (used & BIT(c)) continue;
            	 	used |= BIT(c);
		            for (d=0;d<6;d++)
    		        {
        		    	if (used & BIT(d)) continue;
            		 	used |= BIT(d);
			            for (e=0;e<6;e++)
    			        {
        			    	if (used & BIT(e)) continue;
												U32 addr=8*(8*(8*(8*a+b)+c)+d)+e;
																compressTable[addr]=index;
																		index++;
                        }
                		used &= ~BIT(d);
                    }
                	used &= ~BIT(c);
                }
                used &= ~BIT(b);
            }
            used &= ~BIT(a);
        }
	}

	U32 C3(int a,int b,int c,int d)
// Concatenates 4 corner positions, MOD 3
	{
		return 3*(3*(3*a+b)+c)+d;
	}

	void MakeCornerTable()
// Computes all moves on all 81 edge combinations
	{
		int a,b,c,d,r;
		for (a=0;a<3;a++)
		{
			for (b=0;b<3;b++)
			{
				for (c=0;c<3;c++)
				{
					for (d=0;d<3;d++)
					{

						int addr=C3(a,b,c,d);
						CornerCode*
						cp=&cornerMoveTable[addr][0];
						r=kRotCorner[a]; *cp++=C3(r,b,c,d);
						r=kRotCorner[r]; *cp++=C3(r,b,c,d);
						r=kRotCorner[b]; *cp++=C3(a,r,c,d);
						r=kRotCorner[r]; *cp++=C3(a,r,c,d);
						r=kRotCorner[c]; *cp++=C3(a,b,r,d);
						r=kRotCorner[r]; *cp++=C3(a,b,r,d);
						r=kRotCorner[d]; *cp++=C3(a,b,c,r);
						r=kRotCorner[r]; *cp++=C3(a,b,c,r);
					}
				}
			}
		}
	}

	void MakeEdgeTable()
	{
// First, computes all even numbered moves on the 720 edge permutations
// and the corresponding flip bits
		int a,b,c,d,e,used=0,index=0;
		for (a=0;a<6;a++)
		{
			used |= BIT(a);
			for (b=0;b<6;b++)
			{
				if (used & BIT(b)) continue;
				used |= BIT(b);
				for (c=0;c<6;c++)
				{
					if (used & BIT(c)) continue;
					used |= BIT(c);
					for (d=0;d<6;d++)
					{
						if (used & BIT(d)) continue;
						used |= BIT(d);
						for (e=0;e<6;e++)
						{
							if (used & BIT(e)) continue;
							for (int m=0;m<8;m+=2)
							{
								U32	xa=kRotEdge[a][m/2],
									xb=kRotEdge[b][m/2],
									xc=kRotEdge[c][m/2],
									xd=kRotEdge[d][m/2],
									xe=kRotEdge[e][m/2];

								U32
									data=8*(8*(8*(8*xa+xb)+xc)+xd)+xe;
									data=compressTable[data];

								U32	fa=kRotFlip[a][m/2],
									fb=kRotFlip[b][m/2],
									fc=kRotFlip[c][m/2],
									fd=kRotFlip[d][m/2],
									fe=kRotFlip[e][m/2];

								int	flip=2*(2*(2*(2*fa+fb)+fc)+fd)+fe;
									edgeMoveTable[index][m]=
										(data | (flip<<10));
							}
							index++;
						}
						used &= ~BIT(d);
					}
					used &= ~BIT(c);
				}
				used &= ~BIT(b);
			}
			used &= ~BIT(a);
		}

// Odd numbered moves are then just the even moves, repeated:
		for (int i=0;i<720;i++)
			for (int m=0;m<8;m+=2)
				edgeMoveTable[i][m+1] =
					NextEdges(edgeMoveTable[i][m],m);
	}
	StateCode Init(const Puzzle & P)
// Reduces a 28-piece Puzzle state to a 22 bit state code
	{

		U32 corners	= P.GetCornerCode();
		U32 edges	= compressTable[P.GetEdgeCode()];
		U32 flips	= P.GetFlipCode();

		StateCode s = (corners << 15)
			|		  (flips << 10)
			|		   edges;
		return s;
	}

	StateCode Next(const StateCode code,const int m)
// Moves the puzzle state through move "m".
	{
		U32 corners		= 0x7F & (code >> 15);
		U32 flipEdges	= 0x7FFF & code;

		StateCode next = (cornerMoveTable[corners][m] << 15)
						| NextEdges(flipEdges,m);

		return next;
	}

	U32 NextEdges(U32 flipEdges,int m)
// "flipEdges" consists of 5 flip bits and 10 edge position bits
//	To effect a move of the edges,
//		the existing flip bits must be XORed with the flip bits
//		from the table, and ORed with the new position bits.
	{
		return (flipEdges & (31<<10)) ^
			edgeMoveTable[flipEdges & 1023][m];
	}
} CC;
/*********************** Magic Lookup **********************/
enum {
	kTableSize = 81 * 32    * 1024	// 2,654,208 * 4 = 10,368 KB
};		  //corners * flips * edges

struct SolutionTree
static struct SolutionTree {
// The inverse solution tree
	U32*	tree;			// primary table
	bool	valid;

	SolutionTree()
	{
#if SILENT_INIT
		Init();				// Constructor invokes Init();
#endif
	}

	~SolutionTree(){delete [] tree;}

enum {kStackSize=0x80000};//  about 17K larger than needed

void Init()
// Builds the large lookup tree
	{
		if (valid) return;
// Get the memory and clear it
		tree=new U32[kTableSize];
		memset(tree,0,sizeof(U32)*kTableSize);

// Get a stack for holding sets of states while building the tree

		U32*	stack=new U32[kStackSize];// 500K words

		U32*	stackEnd=stack+kStackSize;
		U32* 	SP1=stack;		//from stack up
		U32* 	SP2=stackEnd;	//from stackEnd down
#define PUSH1(s) 	{*++SP1=s;}
#define PUSH2(s) 	{*-SP2=s;}
#define POP1(s) 	{s=*SP1-;}
#define POP2(s) 	{s=*SP2++;}
#define STACK1		(SP1 > stack)
#define STACK2		(SP2 < stackEnd)

// The root node at 0 (kSolution == 0)
		U32 state=kSolution;
		tree[state]=kSolution;

// Make the first level moves, one node for each of 8 possible moves

		U32 code = 0,n;
		for (n=0;n<8;n++,code += 0x20000000)
		{
			U32 next=CC.Next(state,code >> 29);
			PUSH1(next | code);

//			tree[next]=state | code;
		// 1
#if M >= 11
#define kStop kSolution
#else
#define kStop 720
#endif
			tree[next]=kStop | code;
		// 1
		}

// Make the remaining nodes.
// At each level, we expand the tree from all the nodes of the
// previous level which are held on the stack.
// Only 6 moves need to be considered since the 7th move would
// be reversing the previous move, and the 8th possible move
// would be a repeat of the previous move, but that double move
// is the same as the single inverse move (L+L+ = L-), and that
// single move is already represented at the earlier level.

// For each new state reached, we only add it into the tree if
// it is new and not the solution.

// The longest move sequence needed to solve any puzzle is eleven.
		for (int level=2,n;level<=M;level++)
		{
// The stack is used from both ends;  while the previous level's states
// are popped off one end, the new states are pushed on at the other.
			while (STACK1) {

				POP1(state);
				U32 code=(state + 0x40000000) & 0xC0000000;
				state &= 0x003FFFFF;
				for (n=0;n<6;n++,code += 0x20000000)
				{
					U32 next=CC.Next(state,code >> 29);

					if ((next!=kSolution) && !tree[next])
					{
						PUSH2(next | code);
						tree[next]=state | code;
		// 2,4,6,8,10
					}
				}

			}
			if (++level > M) break;
// Repeat, with stack roles reversed
			while (STACK2) {

				POP2(state);
				U32 code=(state + 0x40000000) & 0xC0000000;
				state &= 0x003FFFFF;
				for (n=0;n<6;n++,code += 0x20000000)
				{
					U32 next=CC.Next(state,code >> 29);
					if ((next!=kSolution) && !tree[next])
					{
						PUSH1(next | code);

						tree[next]=state | code;
		// 3,5,7,9,11
					}
				}
			}
		}

		delete [] stack;	// not needed any more

		valid=true;
	}

	long Solve(U32 state,Move moves[],const int maxMoves)
// Solve the puzzle by tracing states and moves through the tree.
// Each tree lookup[state] yields the next state
// and the move to change the puzzle to it, towards the solution.
	{
		if (state==kSolution)	// already solved, 0 moves
			return 0;

#if SILENT_INIT == 0
		Init();					// setup the tree if necessary
#endif

		long numMoves;			// traverse the tree, collect moves
		state = tree[state];
		for (numMoves=0;numMoves<maxMoves;) {
			int myMove=(state >> 29) ^ 1;// invert: L+ becomes L-
			moves[numMoves++]=Convert2Move(myMove);
			state &= 0x3FFFFF;
			if (state == kStop)
				return numMoves;
			state = tree[state];
		}

		return 0;	// not found, probably illegal, or maxMoves too low
	}

#if M < 11
	int EndRun(U32 state,Move moves[])
// Endrun traversing a partial inverse solution tree.
// If the state is found in the tree, the remaining moves are retrieved
// Returns 0 if solution not in tree.
	{
		int numMoves;			// traverse the tree, collect moves
		state = tree[state];
		if ((state==0) || (state==kStop))
			return 0;
		for (numMoves=0;numMoves<M;) {
			int myMove=(state >> 29) ^ 1;// invert: L+ becomes L-
			moves[numMoves++]=Convert2Move(myMove);
			state &= 0x3FFFFF;
			if (state == kStop)
				return numMoves;
			state = tree[state];
		}

		return 0;
	}
#endif
} magic;

#if M < 11
/************************* SearchNode ***********************/
// The node for the non-recursive exhaustive tree search to solve
// the puzzle in the smallest number of moves.
// Each node has a current state, and an array of next states which
// serve as the stack for back tracking.

// Moving forward in the tree is done by casting the last unused
// compact state on the array into a SearchNode and continue from there.
// Backtracking means, going back to the previous SearchNode and taking
// the next last nextState to go forward with.

struct SearchNode
struct SearchNode {
	U32			theState;
	int 		numNext;
	SearchNode*	prevNode;
	U32			nextState[8];// includes move code at MSB

	void Init(const Puzzle & P)
// The first search node is initialized from the original Puzzle.
	{
		theState=CC.Init(P);
		numNext=0;
		prevNode=0;
	}

	int Make8moves(Move moves[])
// Generates all 8 future states for the first search level.
// If any of these would solve the puzzle, the final moves are
// copied into moves[].

	{
		for (int firstMove=0;firstMove<8;firstMove++)
		{
			U32 next=CC.Next(theState,firstMove);
			int numCopied=magic.EndRun(next,moves+1);
			if (numCopied) {
				moves[0]=Convert2Move(firstMove);
				return 1 + numCopied;

			}
			nextState[firstMove]=next | (firstMove << 29);
		}
		numNext=8;
		return 0;
	}

	int Make6moves(Move moves[])

// Generates 6 future states for the next search level.
// Note:
// the two moves NOT generated are the two redundant moves: the
// same, and its opposite, as the last move at the previous level.

// If any of the moves would solve the puzzle, the final moves are
// copied into moves[].

	{
		int myMove=7 & (2 + ((theState >> 30) << 1));
		for (int i=0;i<6;i++,myMove = (myMove + 1) & 7)
		{
			U32 next=CC.Next(theState,myMove);
			int numCopied=magic.EndRun(next,moves+1);
			if (numCopied) {
				moves[0]=Convert2Move(myMove);
				return 1 + numCopied;
			}
			nextState[i]=next | (myMove << 29);
		}
		numNext=6;
		return 0;
	}

	int LookAhead(Move moves[])
// Looks ahead up to M moves, by consulting the lookup table.
// If the current state is in the search tree we solve the puzzle,
// Otherwise a high number (99) is returned.

	{
		int numMoves=magic.EndRun(0x003FFFFF & theState,moves);
		if (numMoves==0)
			return 99;// not found
		return numMoves;
	}

	SearchNode* NextNode(int & level)
// Move forward in the search tree;  typecasts the last node of
// the nextState array into a SearchNode and returns it.
// Returns 0 if no more moves are left.
// Tracks "level", the position of the forward search in the tree.

	{
		if (numNext)
		{
			SearchNode* Q=(SearchNode*)(&nextState[-numNext]);
			Q->numNext=0;
			Q->prevNode=this;
			level++;
			return Q;
		} else return 0;
	}

	SearchNode* BackTrack(int & level)
// Backtracks one or more steps, to the node which has nextMoves.
// Returns the address of the node reached, or 0.
// Tracks "level", the position of the forward search in the tree.

	{
		SearchNode* S=this;
		do
		{
			level-;
			S=S->prevNode;
		} while (S && (0 == S->numNext));
		return S;
	}
};

struct TreeSolver

/********************** Solver Tree Search *******************/

// Non-recursive exhaustive search.
enum{kMaxMoves=11};
struct TreeSolver {
	SearchNode searchNode[kMaxMoves];// stack of nodes

	TreeSolver(const Puzzle & P){searchNode[0].Init(P);}

	int Solve(Move moves[],int maxMoves)

// Returns the number of moves to solve,
// and populates the moves[] array.

	{
		if (maxMoves==0)
			return 0;		// no moves allowed

		if (searchNode[0].theState == kSolution)
			return 0;		// solved puzzle, no moves
		if (maxMoves>11) maxMoves=11;

#if SILENT_INIT == 0
		magic.Init();		// setup the tree if necessary
#endif

		SearchNode* Q=&searchNode[0];

// Perhaps it's really simple, and only <= M moves are needed

		int movesCopied = Q->LookAhead(moves);
		if (movesCopied <= maxMoves)
			return movesCopied;		// found quick solution

// Quit if no more than M moves are allowed

		if (maxMoves <= M)
			return 0;

// Setup all 8 possible first moves.
// If this solves it (with M+1 moves), return success

		movesCopied = Q->Make8moves(moves);
		if (movesCopied)
			return movesCopied;

		int predict=M+1,best=99;

#define level (predict-(M+1))	// if we solve at level x, numMoves = predict

// All solutions from here on will have M+2 moves or more

		if (predict < maxMoves) 		// else quit now

		for (;;) {						// search-tree traversal loop

			Q = Q->NextNode(predict);	// next search level
			if (Q)
			{
				movesCopied = Q->Make6moves(moves+level);
				if (movesCopied) 		// found a solution
				{
					SearchNode* temp=Q;
					Q=Q->prevNode;
					for (int i=level-1;i>=0;i-)
					{

						moves[i]=Convert2Move(temp->theState >> 29);
						temp=temp->prevNode;
					}

					best = predict-;

					maxMoves = predict;	// limit search to 1 less than best

					if (0 == (Q = Q->BackTrack(predict))) break;
				}
				else if (predict >= maxMoves)
					if (0 == (Q = Q->BackTrack(predict))) break;
			}
			else if (0 == (Q = Q->BackTrack(predict))) break;
		}

		if (best >= 99)
			return 0;	// no solution found; best was not set.

		return best;
	}
};

#endif

Tetraminx
/******************* Published Entry Point *******************/

long /* numberOfMoves */ Tetraminx (
  PieceState state[28],		/* initial state of the 28 pieces */
  Move moves[],						/* moves you generate */
  long maxMoves						/* maximum storage in move array */
) {

// convert to internal Puzzle (tet) format and check validity

	if (P.Init(state))
	{

#if M >= 11

// (Use complete static solution tree)
// Convert to compressed format

		StateCode sc = CC.Init(P);
// and solve.
		return magic.Solve(sc,moves,maxMoves);

#else

// (Use combination static and dynamic tree)
// Initialize tree solver class

		TreeSolver ts(P);
// and solve.
		return ts.Solve(moves,maxMoves);

#endif
	}
	return 0;
}
 
AAPL
$117.60
Apple Inc.
-1.03
MSFT
$47.47
Microsoft Corpora
-0.12
GOOG
$541.08
Google Inc.
+1.81

MacTech Search:
Community Search:

Software Updates via MacUpdate

RapidWeaver 6.0.3 - Create template-base...
RapidWeaver is a next-generation Web design application to help you easily create professional-looking Web sites in minutes. No knowledge of complex code is required, RapidWeaver will take care of... Read more
iPhoto Library Manager 4.1.10 - Manage m...
iPhoto Library Manager lets you organize your photos into multiple iPhoto libraries. Separate your high school and college photos from your latest summer vacation pictures. Or keep some photo... Read more
iExplorer 3.5.1.9 - View and transfer al...
iExplorer is an iPhone browser for Mac lets you view the files on your iOS device. By using a drag and drop interface, you can quickly copy files and folders between your Mac and your iPhone or... Read more
MacUpdate Desktop 6.0.3 - Discover and i...
MacUpdate Desktop 6 brings seamless 1-click installs and version updates to your Mac. With a free MacUpdate account and MacUpdate Desktop 6, Mac users can now install almost any Mac app on macupdate.... Read more
SteerMouse 4.2.2 - Powerful third-party...
SteerMouse is an advanced driver for USB and Bluetooth mice. It also supports Apple Mighty Mouse very well. SteerMouse can assign various functions to buttons that Apple's software does not allow,... Read more
iMazing 1.1 - Complete iOS device manage...
iMazing (was DiskAid) is the ultimate iOS device manager with capabilities far beyond what iTunes offers. With iMazing and your iOS device (iPhone, iPad, or iPod), you can: Copy music to and from... Read more
PopChar X 7.0 - Floating window shows av...
PopChar X helps you get the most out of your font collection. With its crystal-clear interface, PopChar X provides a frustration-free way to access any font's special characters. Expanded... Read more
Carbon Copy Cloner 4.0.3 - Easy-to-use b...
Carbon Copy Cloner backups are better than ordinary backups. Suppose the unthinkable happens while you're under deadline to finish a project: your Mac is unresponsive and all you hear is an ominous,... Read more
ForeverSave 2.1.3 - Universal auto-save...
ForeverSave auto-saves all documents you're working on while simultaneously doing backup versioning in the background. Lost data can be quickly restored at any time. Losing data, caused by... Read more
Voila 3.8.1 - Capture, annotate, organiz...
Voila is a screen-capture, recording, and annotation tool that is a full-featured replacement for Mac's screen-capture and screen-recording capabilities. It has a large and robust set of editing,... Read more

Latest Forum Discussions

See All

Screeny (Utilities)
Screeny 1.0 Device: iOS iPhone Category: Utilities Price: $.99, Version: 1.0 (iTunes) Description: Screeny is an utility app that helps you save space consumed by screenshots. It screens your camera roll and helps you to filter and... | Read more »
Tilt to Live Bundle Set to Arrive This T...
Tilt to Live Bundle Set to Arrive This Thanksgiving Posted by Ellis Spice on November 25th, 2014 [ permalink ] One Man Left has unveiled an upcoming Tilt to Live bundle, allowing players to get the series for a di | Read more »
BattleLore: Command (Entertainment)
BattleLore: Command 1.0 Device: iOS Universal Category: Entertainment Price: $9.99, Version: 1.0 (iTunes) Description: ***NOTE: Compatible with iPad 2/iPad mini, iPod touch 5 and up and iPhone 4S and up – WILL NOT RUN ON EARLIER... | Read more »
Weather Or Not Review
Weather Or Not Review By Jennifer Allen on November 25th, 2014 Our Rating: :: STYLISH WEATHER REPORTINGiPhone App - Designed for the iPhone, compatible with the iPad Check the weather quickly and conveniently with Weather or Not... | Read more »
The All-New Football Manager Handheld 20...
The All-New Football Manager Handheld 2015 is Available Now Posted by Jessica Fisher on November 25th, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Six iOS Games to Get You Ready for Thank...
Image Source: Friends Wiki At this point in the month, you or at least a few people you know are probably getting ready to scramble around (or are already scrambling around) for Thanksgiving Dinner. It’s a hectic day of precise oven utilization, but... | Read more »
Call of Duty: Heroes: Tips, Tricks, and...
Hello Heroes: What’d we think of Call of Duty‘s take on Clash of Clans? Check out our Call of Duty: Heroes review to find out! Just downloaded Call of Duty: Heroes and need some handy tips and tricks on how to get ahead of the rest? As we often do,... | Read more »
Call of Duty: Heroes Review
Call of Duty: Heroes Review By Jennifer Allen on November 25th, 2014 Our Rating: :: CLASH OF FRANCHISESUniversal App - Designed for iPhone and iPad Mix Clash of Clans with Call of Duty, and this is what you get.   | Read more »
Slider Review
Slider Review By Jordan Minor on November 25th, 2014 Our Rating: :: SLIDE TO PLAYUniversal App - Designed for iPhone and iPad Slider has all the excitement of unlocking your phone screen.   | Read more »
oh my giraffe (Games)
oh my giraffe 1.0.0 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0.0 (iTunes) Description: Eat fruits while being chased by lions. Cut the vines to send fruit plummeting onto the lions. Don't worry, your flexible... | Read more »

Price Scanner via MacPrices.net

Early Black Friday sale price: 15-inch 2.2GHz...
 B&H Photo has the 2014 15″ 2.2GHz Retina MacBook Pro on sale today for $1699.99. Shipping is free, and B&H charges NY sales tax only. Their price is $300 off MSRP, equalling Best Buy’s price... Read more
13-inch 2.5GHz MacBook Pro (refurbished) avai...
The Apple Store has Apple Certified Refurbished 13″ 2.5GHz MacBook Pros available for $170 off the cost of new models. Apple’s one-year warranty is standard, and shipping is free: - 13″ 2.5GHz... Read more
Early Black Friday MacBook Pro sale: 15-inch...
 Best Buy has posted early Black Friday prices on 15″ Retina MacBook Pros, with models on sale for $300 off MSRP on their online store for a limited time. Choose free local store pickup (if available... Read more
A9 Chips Already?
It’s barely more than a couple of months since Apple got the first A8 systems-on-chip into consumer hands, but rumor and news focus is already turning to the next-generation A9 SoC. Apple Daily... Read more
NewerTech Announces NuGuard KXs Impact X-Orbi...
NewerTech has announced updates to its family of Impact X-Orbing Screen Armor bringing military grade, triple layer protection to Apple’s new iPhone 6 and 6 Plus. Like all models in the NuGuard KXs... Read more
13-inch 1.4GHz MacBook Air on sale for $889,...
 B&H Photo has the 13″ 1.4GHz/128GB MacBook Air on sale for $889 including free shipping plus NY tax only. Their price is $110 off MSRP. B&H will also include free copies of Parallels Desktop... Read more
Save up to $300 on Macs and iPads with your A...
Purchase a new Mac or iPad at The Apple Store for Education and take up to $300 off MSRP. All teachers, students, and staff of any educational institution qualify for the discount. Shipping is free,... Read more
Apple refurbished Mac Pros available for up t...
The Apple Store is offering Apple Certified Refurbished Mac Pros for up to $600 off the cost of new models. An Apple one-year warranty is included with each Mac Pro, and shipping is free. The... Read more
Jumptuit Launches One-Tap Windows 8.1 iTunes...
Jumptuit has launched Windows 8.1 support for One-Tap iTunes Sync. with which Windows 8.1 users can now easily sync their iTunes libraries with Microsoft OneDrive. Jumptuit provides easy access from... Read more
Apple restocks refurbished 13-inch 2014 Retin...
The Apple Store has restocked Apple Certified Refurbished 2014 13″ 2.6GHz Retina MacBook Pros for up to $230 off the cost of new models. An Apple one-year warranty is included with each model, and... Read more

Jobs Board

*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
Senior Event Manager, *Apple* Retail Market...
…This senior level position is responsible for leading and imagining the Apple Retail Team's global event strategy. Delivering an overarching brand story; in-store, Read more
*Apple* Retail - Multiple Positions (US) - A...
Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.