// tangram.cpp - program to solve tangram square puzzle, print solutions

#include "search.hpp"
#include "puzzle.h"

// class Tangram - solve tangram square, print solutions
class Tangram {

private:

// The tangram square is divided into 4 by 4 smaller squares, each of which
// is divided into 4 isosceles, right triangles, so that their hypotenuses
// are the sides of the smaller squares. Subsets of these 64 triangles are
// the only positions that the tangram parts can occupy in a solution.
// The 16 triangles along the top edges of the 16 smaller squares are numbered
// 0x00 to 0x0F, from left to right then top to bottom of the larger square.
// The same triangles with the larger square rotated 90 degrees clockwise, are
// numbered 0x10 to 0x1F. 180 degrees, 0x20 to 0x2F. 270 degrees, 0x30 to 0x3F.

// puzzle - the puzzle, with redundancies suppressed
puzzle::Puzzle puzzle;

// search server with 0x40 (64) locations
search::Server<search::PosFixed<0x40> > searchserver;

// horiz - sets of maps; horiz[i] translates parts horizontally 0 to i locations
Maps horiz[4];

// vert - sets of maps; vert[i] translates parts vertically 0 to i locations
Maps vert[4];

// maketranslate - make horiz and vert translate map sets
void maketranslate()
{
	Map horizmap(0x40), vertmap(0x40);
	int i;

	for (i = 0x00; i < 0x10; i += 0x04) {
		horizmap.rot(0x01, 0x00 + i, 0x04);
		horizmap.rot(0x03, 0x20 + i, 0x04);
		vertmap.rot(0x01, 0x10 + i, 0x04);
		vertmap.rot(0x03, 0x30 + i, 0x04);
	}
	horizmap.rot(0x0C, 0x10, 0x10);
	horizmap.rot(0x04, 0x30, 0x10);
	vertmap.rot(0x04, 0x00, 0x10);
	vertmap.rot(0x0C, 0x20, 0x10);
	for (i = 0; i < 4; i++) horiz[i] = horizmap.nestlist(i);
	for (i = 0; i < 4; i++) vert[i] = vertmap.nestlist(i);
}

// getmaps - return 2 symmetry maps, reflect diagonally and rotate 90 degrees
Maps getmaps(void)
{
	Maps maps(2);
	Map map(0x40);
	int i;

	for (i = 0; i < 0x40; i += 0x04) map.rev(i, 0x04);
	for (i = 0; i < 0x40; i += 0x20) map.rot(0x10, i, 0x20);
	maps[1] = map;
	map.rot(0x10);
	maps[0] = map;
	return (maps);
}

// getshape - return shape with n parts and position of nloc locations given in
// base, which can be translated nvert locations vertically, nhoriz horizontally
Shape getshape(int *base, int nloc, int nvert, int nhoriz, int n)
{
	Poss poss;
	Pos pos(nloc);
	Shape shape;
	int i;

	std::copy(base, base + nloc, pos.begin());
	poss = vert[nvert] * horiz[nhoriz] * Poss(pos);
	shape = Shape(n, poss);
	return (shape);
}

// getshapes - return set of tangram shapes (5 shapes, 7 parts)
Shapes getshapes(void)
{
	int tab0[] = { 0x00, 0x01, 0x02, 0x03, 0x05, 0x06,
			0x14, 0x18, 0x19, 0x1C, 0x2D, 0x2E, 0x37, 0x3A, 0x3B, 0x3F
	};
	int tab1[] = { 0x00, 0x01, 0x04, 0x1C, 0x2F, 0x32, 0x33, 0x37 };
	int tab2[] = { 0x04, 0x05, 0x1C, 0x1D, 0x2E, 0x2F, 0x36, 0x37 };
	int tab3[] = { 0x00, 0x01, 0x18, 0x1C, 0x2D, 0x2E, 0x37, 0x3B };
	int tab4[] = { 0x00, 0x01, 0x1C, 0x37 };
	Shapes shapes(5);

	maketranslate();
	shapes[0] = getshape(tab0, 16, 2, 0, 2);
	shapes[1] = getshape(tab1, 8, 2, 2, 1);
	shapes[2] = getshape(tab2, 8, 2, 2, 1);
	shapes[3] = getshape(tab3, 8, 3, 1, 1);
	shapes[4] = getshape(tab4, 4, 3, 2, 2);
	return (shapes);
}

// printsolution - print nth solution with PartIds, s, which index parts
// output is a two-dimensional diagram of letter-coded triangles
void printsolution(int n, const PartIds &s, const Parts &parts)
{
	std::string codes;
	int i, j, k, l;

	std::cout << std::endl << "Solution " << n << ":" << std::endl;
	codes = parts.select(s).decode("abcdefg", std::string(0x40, '.'));
	for (i = 0; i < 4; i++) for (k = 0; k < 8; k++) {
		for (j = 0; j < 4; j++) for (l = 0; l < 8; l++)
			std::cout << (k == 7 || l == 7 || k == l || k == 6 - l? ' ':
				codes[k < l? k < 6 - l? 0x00 + 4*i + j: 0x1C + i - 4*j:
						k > 6 - l? 0x2F - 4*i - j: 0x33 - i + 4*j]) << ' ';
		std::cout << std::endl;
	}
}

// setsol - print all solutions for PartIdss, s, which index parts
void setsol(const PartIdss &s, const Parts &parts)
{
	PartIdss::const_iterator si;
	int n;

	std::cout << "Number of solutions: " << s.size() << std::endl;
	n = 0;
	for (si = s.begin(); si != s.end(); si++)
		printsolution(++n, *si, parts);
}

public:

// Tangram - initialize tangram puzzle
Tangram(void) : puzzle(0x40)
{
}

// run - run search and print solutions to tangram square puzzle
void run(void)
{
	puzzle.setmaps(getmaps());
	puzzle.setshapes(getshapes());
	puzzle.search(searchserver);
	setsol(puzzle.getsolutions(), puzzle.getparts());
}

}; // end of class Tangram

// main - solve tangram square puzzle, print solutions
int main(void)
{
	Tangram().run();
	return (0);
}