head	1.10;
access;
symbols;
locks
	poly:1.10; strict;
comment	@ * @;


1.10
date	2006.04.16.20.11.26;	author poly;	state Exp;
branches;
next	1.9;

1.9
date	2006.04.13.05.22.57;	author poly;	state Exp;
branches;
next	1.8;

1.8
date	2006.04.11.03.19.24;	author poly;	state Exp;
branches;
next	1.7;

1.7
date	2006.04.08.17.28.31;	author poly;	state Exp;
branches;
next	1.6;

1.6
date	2006.04.06.03.48.37;	author poly;	state Exp;
branches;
next	1.5;

1.5
date	2006.04.05.03.55.11;	author poly;	state Exp;
branches;
next	1.4;

1.4
date	2006.04.03.03.11.52;	author poly;	state Exp;
branches;
next	1.3;

1.3
date	2006.04.01.08.39.24;	author poly;	state Exp;
branches;
next	1.2;

1.2
date	2006.03.31.07.19.18;	author poly;	state Exp;
branches;
next	1.1;

1.1
date	2006.03.30.07.23.29;	author poly;	state Exp;
branches;
next	;


desc
@in
@


1.10
log
@in
@
text
@/*
 *  units.c
 *  omino_fitting_2006
 *
 *  Created by david van brink on 3/29/06.
 *  Copyright 2006 __MyCompanyName__. All rights reserved.
 *
 */

#include <stdio.h>
#include "units.h"
#include "Fittings.h"
#include "Memory.h"
#include "Printing.h"

static void reportSequenceSearch(char *title,OFSequenceSearch *search,int forceShow);



static void complain(char *m)
{
	printf("ERROR: %s\n",m);
}

static int gAssertOKCount = 0;

#define assert(_m,_n) if(!(_n)) printf("ERROR %d [%s:%d] %s\n",++gErrorCount,__FILE__,__LINE__,_m); else gAssertOKCount++;

#define assertNotZero(_m,_n) assert(_m,(_n)!=0)
#define assertZero(_m,_n) assertEquals(_m,(_n),0)
#define assertEquals(_m,_n1,_n2) if((_n1) != (_n2)) printf("ERROR %d [%s:%d] %d!=%d %s\n",++gErrorCount,__FILE__,__LINE__,_n1,_n2,_m); \
		else gAssertOKCount++;
#define assertNotEquals(_m,_n1,_n2) if((_n1) == (_n2)) printf("ERROR %d [%s:%d] %d==%d %s\n",++gErrorCount,__FILE__,__LINE__,_n1,_n2,_m); \
		else gAssertOKCount++;

#define assertEqualsX(_m,_n1,_n2) if((_n1) != (_n2)) printf("ERROR %d [%s:%d] x%x!=x%x %s\n",++gErrorCount,__FILE__,__LINE__,_n1,_n2,_m); \
		else gAssertOKCount++;

static int gErrorCount;

static void checkMemory(void)
{
	char *n = Malloc(20);
	assertNotZero("Malloc",(int)n);
	
	n[19] = 99;
	n[200]=100;
	FreeAt((void **)&n);
	assertZero("FreeAt",(int)n);
}


static void checkRotations(void)
{
	OFOmino *o = newOFOmino("112",10,0);
// first cell
	assertEquals("cr0",o->orientations[0]->cellOffsets[0],0);
	assertEquals("cr0",o->orientations[1]->cellOffsets[0],0);
	assertEquals("cr0",o->orientations[2]->cellOffsets[0],12);
	assertEquals("cr0",o->orientations[3]->cellOffsets[0],20);
	assertEquals("cr0",o->orientations[4]->cellOffsets[0],2);
	assertEquals("cr0",o->orientations[5]->cellOffsets[0],0);
	assertEquals("cr0",o->orientations[6]->cellOffsets[0],8);
	assertEquals("cr0",o->orientations[7]->cellOffsets[0],21);
// last cell
	assertEquals("cr3",o->orientations[0]->cellOffsets[3],12);
	assertEquals("cr3",o->orientations[1]->cellOffsets[3],19);
	assertEquals("cr3",o->orientations[2]->cellOffsets[3],0);
	assertEquals("cr3",o->orientations[3]->cellOffsets[3],1);
	assertEquals("cr3",o->orientations[4]->cellOffsets[3],10);
	assertEquals("cr3",o->orientations[5]->cellOffsets[3],21);
	assertEquals("cr3",o->orientations[6]->cellOffsets[3],0);
	assertEquals("cr3",o->orientations[7]->cellOffsets[3],0);


	o = newOFOmino("112",10,2);
	assertEquals("cr0",o->orientations[0]->cellOffsets[0],-12);
	assertEquals("cr0",o->orientations[1]->cellOffsets[0],-20);
	assertEquals("cr0",o->orientations[2]->cellOffsets[0],0);
	assertEquals("cr0",o->orientations[3]->cellOffsets[0],0);
	assertEquals("cr0",o->orientations[4]->cellOffsets[0],-8);
	assertEquals("cr0",o->orientations[5]->cellOffsets[0],-21);
	assertEquals("cr0",o->orientations[6]->cellOffsets[0],-2);
	assertEquals("cr0",o->orientations[7]->cellOffsets[0],0);
}

static void checkRotatePoints()
{
	OFPoints *p = pointsFromDescription("0002");
	
	assertEquals("p",p->cells[1].x,3);
	assertEquals("p",p->cells[1].y,1);
	
	rotatePoints(p,1);
	assertEquals("p",p->cells[1].x,-1);
	assertEquals("p",p->cells[1].y,3);

	rotatePoints(p,-1);
	assertEquals("p",p->cells[1].x,3);
	assertEquals("p",p->cells[1].y,1);
	
	int i;
	for(i = 0; i < 8; i++)
	{
	rotatePoints(p,-i);
	rotatePoints(p,i);
	assertEquals("p",p->cells[1].x,3);
	assertEquals("p",p->cells[1].y,1);
	}
}

static void checkFillOrderConsistency(void)
{
	/*
	When we describe a polyomino, say ..: "112", then
	the 8 rotations should be the same for all 8 "fill orders". The
	offsets will be different, but the apparent-aspect of
	all should be the same.
	*/
	OFOmino *o = newOFOmino("112",10,0);
	
	int offsetDeltas[8][3]; // 4 cells, 3 deltas
	// populate from fill-order 0, all 8 rotations
	int i,j;
	for(i = 0; i < 8; i++)
		for(j = 0; j < 3; j++)
			offsetDeltas[i][j] = o->orientations[i]->cellOffsets[j + 1]
					- o->orientations[i]->cellOffsets[j];
	
	// and compare against the other seven
	int fillOrder;
	for(fillOrder = 0; fillOrder < 8; fillOrder++)
	{
		OFOmino *o2 = newOFOmino("112",10,fillOrder);

		for(i = 0; i < 8; i++)
			for(j = 0; j < 3; j++)
			{
				int d0 = offsetDeltas[i][j];
				int dX = o2->orientations[i]->cellOffsets[j + 1]
						- o2->orientations[i]->cellOffsets[j];
				assertEquals("fill order consistency",d0,dX);
			}
	}
}




static void checkPerimeter(void)
{
	OFPoints *ooc = pointsFromDescription("123");
	positionFirstPoint(ooc);
	getPerimeterPoints(ooc);
	
	rotatePoints90(ooc);
	positionFirstPoint(ooc);
	getPerimeterPoints(ooc);

	rotatePoints90(ooc);
	positionFirstPoint(ooc);
	getPerimeterPoints(ooc);

	rotatePoints90(ooc);
	positionFirstPoint(ooc);
	getPerimeterPoints(ooc);
	
	ooc = pointsFromDescription("1");
	OFPoints *peri = getPerimeterPoints(ooc);
	OFOffsets *periO = offsetsFromPoints(peri,10);
	assertEquals("perimeter length",periO->cellCount,8);
	assertEquals("perimeter[1]",periO->cellOffsets[0],9);
	assertEquals("perimeter[2]",periO->cellOffsets[1],10);
	assertEquals("perimeter[3]",periO->cellOffsets[2],11);
	assertEquals("perimeter[4]",periO->cellOffsets[3],1);
	assertEquals("perimeter[5]",periO->cellOffsets[4],-9);
	assertEquals("perimeter[6]",periO->cellOffsets[5],-10);
	assertEquals("perimeter[7]",periO->cellOffsets[6],-11);
	assertEquals("perimeter[0]",periO->cellOffsets[7],-1);
}

// Visually assure that the perimeter is ok
static void displayPerimeterish(void)
{
	printf("---------------------------------------\n");
	printf("-- Perimeters\n");
	OFOmino *ofo = newOFOmino("11221",14,0);
	
	int i;
	for(i = 0; i < 8; i++)
	{
		OFField *off = newOFField(12,12);
		int base = 5 * off->rowCells + 6;
		int k;
		for(k = 0; k < ofo->orientations[i]->cellCount; k++)
			off->cells[base + ofo->orientations[i]->cellOffsets[k]] = 'O';
		for(k = 0; k < ofo->perimeters[i]->cellCount; k++)
			off->cells[base + ofo->perimeters[i]->cellOffsets[k]] = 'A' + k; //k ? 'X' : '.';
//		printField
		(off);
	}
	printf("---------------------------------------\n");
}
	

static void newOFO(void)
{
	OFOmino *ofo = newOFOmino("123",3,0);//3,0);
	assertNotZero("newOFOmino",ofo);
	assertEquals("fill order",ofo->fillOrder,0);
	assertEquals("field row",ofo->fieldRow,3);
	assertEquals("orientation count",ofo->orientationCount,8);
	
	assertEquals("omino size",ofo->orientations[0]->cellCount,6);
	assertEquals("omino size",ofo->orientations[1]->cellCount,6);
	assertEquals("omino size",ofo->orientations[2]->cellCount,6);
	
	assertNotZero("orientation 0",ofo->orientations[0]);
	
	// "123" on row 3 should make 0,3,4,6,7,8
	assertEquals("123",ofo->orientations[0]->cellOffsets[0],0);
	assertEquals("123",ofo->orientations[0]->cellOffsets[1],3);
	assertEquals("123",ofo->orientations[0]->cellOffsets[2],4);
	assertEquals("123",ofo->orientations[0]->cellOffsets[3],6);
	assertEquals("123",ofo->orientations[0]->cellOffsets[4],7);
	assertEquals("123",ofo->orientations[0]->cellOffsets[5],8);

	// first ccw rotation
	assertEquals("123",ofo->orientations[1]->cellOffsets[0],2);
	assertEquals("123",ofo->orientations[1]->cellOffsets[1],1);
	assertEquals("123",ofo->orientations[1]->cellOffsets[2],4);
	assertEquals("123",ofo->orientations[1]->cellOffsets[3],0);
	assertEquals("123",ofo->orientations[1]->cellOffsets[4],3);
	assertEquals("123",ofo->orientations[1]->cellOffsets[5],6);

	// first ccw rotation
	assertEquals("123",ofo->orientations[3]->cellOffsets[0],4);
	assertEquals("123",ofo->orientations[3]->cellOffsets[1],5);
	assertEquals("123",ofo->orientations[3]->cellOffsets[2],2);
	assertEquals("123",ofo->orientations[3]->cellOffsets[3],6);
	assertEquals("123",ofo->orientations[3]->cellOffsets[4],3);
	assertEquals("123",ofo->orientations[3]->cellOffsets[5],0);

	// reflected
	assertEquals("-123",ofo->orientations[4]->cellOffsets[0],0);
	assertEquals("-123",ofo->orientations[4]->cellOffsets[1],3);
	assertEquals("-123",ofo->orientations[4]->cellOffsets[2],2);
	assertEquals("-123",ofo->orientations[4]->cellOffsets[3],6);
	assertEquals("-123",ofo->orientations[4]->cellOffsets[4],5);
	assertEquals("-123",ofo->orientations[4]->cellOffsets[5],4);
}

static void checkPerimeter2()
{
	OFPoints *p = pointsFromDescription("2");
	assertEquals("pointcount",p->cellCount,2);
	OFPoints *peri = getPerimeterPoints(p);
	
	assertEquals("perimeter pointcount",peri->cellCount,10);
	peri = copyPoints(peri);
	assertEquals("perimeter pointcount",peri->cellCount,10);
}

// make sure unique values are being poked in for each cell
// these are used to generate hashes on rows and columns, and also
// of course for the detailed checks themselves.
static void checkCellID(void)
{
	// give a simple known tiling problem, filling
	// a square with 4 rotations of 11322
//	printField2(search->field);
/*
  +--+--------------+
  |  |              |
  |  |        +-----+
  |  |        |     |
  |  +-----+  |     |
  |        |  |     |
  |     +--+--+     |
  |     |  |        |
  |     |  +-----+  |
  |     |        |  |
  +-----+        |  |
  |              |  |
  +--------------+--+
*/
	OFSequenceSearch *search = newSequenceSearch("11322",6,6);
	solveWithSequence(search);

	int v = getFieldCell(search->field,5,5) & kCellID;
	assertEqualsX("5,5",0x00400000,v);

	v = getFieldCell(search->field,4,5) & kCellID;
	assertEqualsX("5,5",0x00410000,v);
	v = getFieldCell(search->field,3,2) & kCellID;
	assertEqualsX("3,2",0x00240000,v);
}

void checkChecksums()
{
/*

using these two patterns
  +-----+
  |     | --> 0x00640000
  +--+  |
  |  |  | --> 0x00e10000
  |  |  |
  |  |  | --> 0x00e20000
  |  +--+
  |     | --> 0x00a70000
  +-----+
  |     | --> 0x00640000
  +--+  |
  |  |  | --> 0x00e10000
  |  |  |
  |  |  | --> 0x00e20000
  |  +--+
  |     | --> 0x00a70000
  +-----+
  |     | --> 0x00640000
  +--+  |
  |  |  | --> 0x00e10000
  |  |  |
  |  |  | --> 0x00e20000
  |  +--+
  |     | --> 0x00a70000
  +-----+
                                       
  +--------+--+--------+--+--------+--+
  |        |  |        |  |        |  |
  |  +-----+  |  +-----+  |  +-----+  |
  |  |        |  |        |  |        |
  +--+--------+--+--------+--+--------+

*/
	OFSequenceSearch *search1 = newSequenceSearch("112",2,12);
	solveWithSequence(search1);
	// manually insert checksums
	int y;
	for(y = 0; y < search1->field->height; y++)
		computeRowChecksum(search1->field,y);
	//printField2(search->field);
	for(y = 0; y < 4; y++)
	{
		assertEqualsX("checksum row 4",search1->field->rowChecksums[y],search1->field->rowChecksums[y+4]);
		assertEqualsX("checksum row 8",search1->field->rowChecksums[y],search1->field->rowChecksums[y+8]);
		assertNotEquals("checkum !row  1",search1->field->rowChecksums[y],search1->field->rowChecksums[y+1]);
		assertNotEquals("checkum !row  2",search1->field->rowChecksums[y],search1->field->rowChecksums[y+2]);
		assertNotEquals("checkum !row  3",search1->field->rowChecksums[y],search1->field->rowChecksums[y+3]);
	}
	
	// same thing for column checksums now
	OFSequenceSearch *search2 = newSequenceSearch("112",12,2);
	solveWithSequence(search2);
	// manually insert checksums
	int x;
	for(x = 0; x < search2->field->width; x++)
		computeColumnChecksum(search2->field,x);
	//printField2(search2->field);
	for(x = 0; x < 4; x++)
	{
		assertEqualsX("checksum column 4",search2->field->columnChecksums[x],search2->field->columnChecksums[x+4]);
		assertEqualsX("checksum column 8",search2->field->columnChecksums[x],search2->field->columnChecksums[x+8]);

		assertNotEquals("checkum !col  1",search2->field->columnChecksums[x],search2->field->columnChecksums[x+1]);
		assertNotEquals("checkum !col  2",search2->field->columnChecksums[x],search2->field->columnChecksums[x+2]);
		assertNotEquals("checkum !col  3",search2->field->columnChecksums[x],search2->field->columnChecksums[x+3]);
	}
	
	// lastly -- make sure our automatic row & checksummer works as designed
	OFSequenceSearch *search1a = newSequenceSearch("112",2,12);
	makeStdHalfstripSequence(search1a); 
	search1a->halfstripHalting = 0; // but dont *actually* stop on a halfstrip. we want them this time.
	int didSolve = solveWithSequence(search1a);
	assertNotZero("solved with halfstrips",didSolve);
	for(y = 0; y < search1a->field->height - 3; y++)  // last three checksums NOT computed, because: rectangle finished!
	for(y = 0; y < search1a->field->height; y++)
		assertEqualsX("checkSum inside sequence",search1a->field->rowChecksums[y],search1->field->rowChecksums[y]);
}


// imperativeInsertion -- takes a plain old sequence and
// adds halfstrip-halting to it
void checkImperativeInsertion()
{
	OFSequenceSearch *search = newSequenceSearch("1",4,4);
	makeEllSequence(search);
	insertChecksumImperatives(search);

	// we expect sequence items 4, 9, 14 to be rows from bottom,
	// and then 16, 18, 20 to be columns from left
	// and then 22 to be row, 23 column
	assertEqualsX("row  4",search->offsetSequence[4],  0x80000000);
	assertEqualsX("row  9",search->offsetSequence[9],  0x80010000);
	assertEqualsX("col 12",search->offsetSequence[12], 0xC0030003);
	assertEqualsX("col 15",search->offsetSequence[15], 0xC0020003);
	assertEqualsX("col 18",search->offsetSequence[18], 0xC0010003);
	assertEqualsX("row 20",search->offsetSequence[20], 0x80020000);
	assertEqualsX("row 22",search->offsetSequence[22], 0x80030000);
	assertEqualsX("col 23",search->offsetSequence[23], 0xC0000000);


	// a nonsquare
	OFSequenceSearch *search2 = newSequenceSearch("1",2,4);
	makeEllSequence(search2);
	insertChecksumImperatives(search2);
	assertEqualsX("row  2",search2->offsetSequence[2],  0x80000000);
	assertEqualsX("row  5",search2->offsetSequence[5],  0x80010000);
	assertEqualsX("col  8",search2->offsetSequence[8],  0xC0010001);
	assertEqualsX("row 10",search2->offsetSequence[10], 0x80020000);
	assertEqualsX("row 12",search2->offsetSequence[12], 0x80030000);
	assertEqualsX("col 13",search2->offsetSequence[13], 0xc0000000);


}



void checkFailingTiling(void)
{
	OFSequenceSearch *search1 = newSequenceSearch("1211",5,5);
	int didSolve = solveWithSequence(search1);
	assertZero("fail, we want!",didSolve);
	int most = search1->deepestCount;
	assertNotZero("fit a bunch though",most == 4);
}


void checkHalfStripHalting()
{
	/* Do a seahorse search with and without, compare results */
	OFSequenceSearch *search1 = newSequenceSearch("1212321",9,44);
	solveWithSequence(search1);
	OFSequenceSearch *search2 = newSequenceSearch("1212321",9,44);
	insertChecksumImperatives(search2);
	solveWithSequence(search2);
	
	int fewerPiecesFit = search2->deepestCount < search1->deepestCount;
	int fewerPiecesPlaced = search2->placementsPlaced < search1->placementsPlaced;
	assertNotZero("halfStrip fewer?",fewerPiecesFit);
	assertNotZero("halfStrip fewer?",fewerPiecesPlaced);

//	reportSequenceSearch("without halfstrip halting",search1,1);
//	reportSequenceSearch("with halfstrip halting",search2,1);
}

void checkHalfStripHaltingColumns()
{
	/* Do a seahorse search with and without, compare results */
	OFSequenceSearch *search1 = newSequenceSearch("1212321",44,9);
	makeUpSequence(search1);
	solveWithSequence(search1);
	OFSequenceSearch *search2 = newSequenceSearch("1212321",44,9);
	makeUpSequence(search2);
	insertChecksumImperatives(search2);
	solveWithSequence(search2);
	
	int fewerPiecesFit = search2->deepestCount < search1->deepestCount;
	int fewerPiecesPlaced = search2->placementsPlaced < search1->placementsPlaced;
	assertNotZero("halfStrip fewer?",fewerPiecesFit);
	assertNotZero("halfStrip fewer?",fewerPiecesPlaced);

//	reportSequenceSearch("without halfstrip halting",search1,1);
//	reportSequenceSearch("with halfstrip halting",search2,1);
}




void check3332Basic()
{
	OFField *field = newOFField(25,22);
	OFOmino *omino = newOFOmino("3332",field->rowCells,0);
	OFSearch *search = newSearch(field,omino);
	search->perimeterCheck = 8;
	solve(search);
	assertEquals("solved 3332 basic",search->curCount,50);
	assertEquals("expected placed-count",20127,search->placementsPlaced);
	assertEquals("expected tried-count",160866,search->placementsTried);
}

void check3332Sequence()
{
	
	int i;
	for(i = 0; i < 3; i++)
	{
		OFSequenceSearch *search = newSequenceSearch("3332",25,22);
		
		char *name;
		switch(i) {
			case 0:	makeCombSequence(search); name="3332 comb"; break;
			case 1:	makeEllSequence(search); name="3332 L"; break;
			case 2:	makeYouSequence(search); name="3332 U"; break;
		}

		search->perimeterCheck = 0;
		search->fillCount = 50;
		solveWithSequence(search);
		assertEquals(name,search->curCount, 50);
		freeSequenceSearchAt(&search);
	}
}

void check3332HalfStripped()
{
		OFSequenceSearch *search = newSequenceSearch("3332",25,22);
		
		makeStdHalfstripSequence(search); 

		search->perimeterCheck = 0;
		search->fillCount = 50;
		int solved = solveWithSequence(search);
		assertEquals("std halfstripped",search->curCount, 50);
		assertNotZero("std halfstripped",solved);
		freeSequenceSearchAt(&search);
}


static void checkNewOFField()
{
	OFField *f = newOFField(10,5);
	assertEquals("field size",84,f->cellCount);
	assertEquals("row cells",12,f->rowCells);
	//printField(f);
	FreeAt((void **)&f);
	FreeAt((void **)&f);
}

static void checkNewOFSearch()
{
	OFField *field = newOFField(5,10);
	OFOmino *omino = newOFOmino("1211",field->rowCells,0);
	assertEquals("omino size",omino->orientations[0]->cellCount,5);
	assertEquals("omino size",omino->orientations[1]->cellCount,5);
	assertEquals("omino size",omino->orientations[2]->cellCount,5);
	assertEquals("omino size",omino->orientations[3]->cellCount,5);
	assertEquals("omino size",omino->orientations[4]->cellCount,5);
	assertEquals("omino size",omino->orientations[5]->cellCount,5);
	assertEquals("omino size",omino->orientations[6]->cellCount,5);
	assertEquals("omino size",omino->orientations[7]->cellCount,5);
	OFSearch *search = newSearch(field,omino);
	assertNotZero("search",search);
	if(!search)
		return;
	assertEquals("fillCount",search->fillCount,10);
	
	placePiece(search);
//	printField(search->field);
}

void trySolve()
{
	OFField *field = newOFField(5,10);
	OFOmino *omino = newOFOmino("1211",field->rowCells,0);
	OFSearch *search = newSearch(field,omino);
//	if(solve(search))
//		printField(search->field);
	printf("search->curCount = %d\n",search->curCount);
}

static void reportSearch(OFSearch *search)
{
	int curCount = search->curCount;
	if(curCount < 0)
		curCount = 0;
	OFOmino *omino = search->omino;
	printf("---------\n%s\n",omino->name);
	printf("took %lld mSec to place %d %d-ominoes\n",search->dur/1000,curCount,omino->orientations[0]->cellCount);
	printf("placementsTried: %lld  (%lld/second)\n",search->placementsTried,search->placementsTried * 1000000LL / search->dur);
	printf("placementsPlaced: %lld  (%lld/second)\n",search->placementsPlaced,search->placementsPlaced * 1000000LL / search->dur);
	if(search->curCount > 3)
		printField2(search->field);
	printf("search->curCount = %d\n",search->curCount);
	printf("--------------\n\n");
}

// doShow +1=show, -1=DONT show, 0 maybe show
static void reportSequenceSearch(char *title,OFSequenceSearch *search,int doShow)
{
	OFOmino *omino = search->omino[0];

	int curCount = search->curCount;
	if(curCount < 0)
		curCount = 0;
	
	int fullCount = search->field->width * search->field->height / omino->orientations[0]->cellCount;

	// did generate checksums?
	int didChecksums = 0;
	OFSequenceElement *w = search->offsetSequence;
	while(*w != SEQUENCE_IMPERATIVE_SUCCESS)
	{
		if(*w & SEQUENCE_IMPERATIVE_COLUMNCOMPLETE)
			didChecksums = 1;
		w++;
	}

	printf("---------\n%s\n%s\n",title,omino->name);
	printf("[%d x %d] ",search->field->width,search->field->height);
	printf("took %lld mSec to place max %d final %d (of %d) %d-ominoes\n",search->dur/1000,search->deepestCount,curCount,fullCount,omino->orientations[0]->cellCount);

	printf("generateChecksums: %s,  halfstripHalting: %s",didChecksums ? "Yes" : "no",search->halfstripHalting ? "Yes" : "no");
	if(search->halfstripRejections)
		printf(", halfstripRejections: %lld",search->halfstripRejections);
	printf("\n");

	printf("placementsTried: %lld  (%lld/second)\n",search->placementsTried,search->placementsTried * 1000000LL / search->dur);
	printf("placementsPlaced: %lld  (%lld/second)\n",search->placementsPlaced,search->placementsPlaced * 1000000LL / search->dur);
	if(search->curCount >= search->fillCount || doShow && (doShow >= 0))
		printField2(search->field);
	printf("search->curCount = %d\n",search->curCount);
	printf("--------------\n\n");
}

void trySequenceSolve3332(int pieceCount)
{
	printf("---------\nSequence [ %d] \n",pieceCount);

	OFSequenceSearch *search = newSequenceSearch("3332",25,22);
	
	makeCombSequence(search);
	makeEllSequence(search);
	makeYouSequence(search);
	
	search->perimeterCheck = 0;
	search->fillCount = pieceCount;
	solveWithSequence(search);
	reportSequenceSearch("Sequence",search,0);
}


void trySeahorse(char *shape,int x,int y)
{
	printf("\n\n\n-------------------------------------------\n\n\n");
	OFSequenceSearch *s = newSequenceSearch(shape,x,y);

	makeYouSequence(s);
	insertChecksumImperatives(s);
	s->perimeterCheck = 10;
	
	printf("starting %s (%dx%d) at %s %s...\n",shape,x,y,__DATE__,__TIME__);

	solveWithSequence(s);
	printf(" %13lld || %13lld || %6lld || %3d || %12.4f \n|-\n",
		   s->placementsTried,
		   s->placementsPlaced,
		   s->halfstripRejections,
		   s->deepestCount,
		   s->dur / 1000000.000 );
	
	printField2(s->field);
	printf("\n\n\n-------------------------------------------\n\n\n");
}

void compareSeahorseHalfstripHalting(void)
{
	int x = 33;
	int y = 48;
	
	int doHalfstrip;
	int whichSequence;
	int doPerimeter;
	for(whichSequence = 0; whichSequence < 3; whichSequence++)
		for(doHalfstrip = 0; doHalfstrip < 2; doHalfstrip++)
			for(doPerimeter = 0; doPerimeter < 2; doPerimeter++)
			{
				char *shape;
				shape = "1212321";
				OFSequenceSearch *s = newSequenceSearch(shape,x,y);
				
				if(whichSequence == 1) makeYouSequence(s);
				else if(whichSequence == 2) makeEllSequence(s);
				
				if(doHalfstrip) insertChecksumImperatives(s);
				else s->halfstripHalting = 0;
				
				if(doPerimeter) s->perimeterCheck = 10;
				
				printf("|| %s || %dx%d || %3s || %3s || %3s || ",
					shape,
					x,y,
					whichSequence==1 ? "U" : whichSequence==2 ? "L" : "Std",
					doHalfstrip ? "yes" : "no",
					doPerimeter ? "yes" : "no",
					0
					);
				solveWithSequence(s);
				printf(" %13lld || %13lld || %6lld || %3d || %12.4f \n|-\n",
					s->placementsTried,
					s->placementsPlaced,
					s->halfstripRejections,
					s->deepestCount,
					s->dur / 1000000.000 );
			}


return;

	OFSequenceSearch *s4 = newSequenceSearch("1212321",x,y);
	makeYouSequence(s4);
	insertChecksumImperatives(s4);
	s4->perimeterCheck = 10;
	solveWithSequence(s4);
	reportSequenceSearch("seahorse, U-sequence, with halfstrip",s4,1);

	OFSequenceSearch *s3 = newSequenceSearch("1212321",x,y);
	makeYouSequence(s3);
	s3->perimeterCheck = 0;
	solveWithSequence(s3);
	reportSequenceSearch("seahorse, U-sequence, no halfstrip",s3,1);
	

	OFSequenceSearch *s5 = newSequenceSearch("1212321",x,y);
	makeYouSequence(s5);
	s5->perimeterCheck = 0;
	solveWithSequence(s5);
	reportSequenceSearch("seahorse, L-sequence, no halfstrip",s5,1);

	OFSequenceSearch *s6 = newSequenceSearch("1212321",x,y);
	makeYouSequence(s6);
	insertChecksumImperatives(s6);
	solveWithSequence(s6);
	reportSequenceSearch("seahorse, L-sequence, with halfstrip",s6,1);
	

	OFSequenceSearch *s1 = newSequenceSearch("1212321",x,y);
	s1->perimeterCheck = 0;
	solveWithSequence(s1);
	reportSequenceSearch("seahorse, no halfstrip",s1,1);

	OFSequenceSearch *s2 = newSequenceSearch("1212321",x,y);
	insertChecksumImperatives(s2);
	solveWithSequence(s2);
	reportSequenceSearch("seahorse, with halfstrip",s2,1);
	
}


void compareSequences12211(int pieceCount)
{
	printf("\n\n\n\n\n");
	int ZZ;
	for(ZZ = 0; ZZ < 6; ZZ++)
	{
		OFSequenceSearch *search = newSequenceSearch("12211",19,28);

		int zzseq = ZZ % 3;
		int doHalfstrip = ZZ / 3;
		if(zzseq == 1)
		{
			makeEllSequence(search);
			printf("---------\nL-Sequence [ %d] \n",pieceCount);
		}
		else if(zzseq == 2)
		{
			makeYouSequence(search);
			printf("---------\nU-Sequence [ %d] \n",pieceCount);
		}
		else
		{
			printf("---------\nSTD Sequence [ %d] \n",pieceCount);
		}
		
		search->halfstripHalting = doHalfstrip;
		if(doHalfstrip)
			insertChecksumImperatives(search);

		
		search->perimeterCheck = 0;
		search->fillCount = pieceCount;
		solveWithSequence(search);
		reportSequenceSearch("Sequence",search,0);
	}
}

void visitSeahorseEll(int width, int height,int percent)
{
	OFSequenceSearch *search = newSequenceSearch("1232121",width,height);
	search->fillCount = search->fillCount * percent / 100;
	makeEllSequence(search);
	solveWithSequence(search);
	reportSequenceSearch("Seahorse Ell",search,0);
}

void scanSeahorseElls()
{
	int x;
	int y;
	
//	for(x = 20; x < 50; x++)
//		for(y = x; y < 50; y++)
	for(x = 46; x <= 72; x++)
		for(y = x; y <= 72; y++)
		{
			if(x * y % 12 == 0)
			{
				OFSequenceSearch *search = newSequenceSearch("1232121",x,y);
//				search->fillCount = search->fillCount * 80 / 100;
				makeEllSequence(search);
				solveWithSequence(search);
				search->perimeterCheck = 9;
				reportSequenceSearch("Seahorse Ell",search,0);
			}
		}
}




void basic3332()
{
	OFField *field = newOFField(25,22);
	OFOmino *omino = newOFOmino("3332",field->rowCells,0);
	OFSearch *search = newSearch(field,omino);
	search->perimeterCheck = 8;
	solve(search);
	reportSearch(search);
	assertEquals("expected placed-count",20127,search->placementsPlaced);
	assertEquals("expected tried-count",160866,search->placementsTried);
}

void visitSeahorse()
{
	OFField *field = newOFField(40,90);
	OFOmino *omino = newOFOmino("1232121",field->rowCells,0);
	
	OFSearch *search = newSearch(field,omino);
	
	assertEquals("perimeter",search->omino->perimeters[0]->cellCount,8);
	
	search->fillCount = 82;
	search->perimeterCheck = 20;
	solve(search);
	reportSearch(search);
}

void visit11()
{
	OFField *field = newOFField(40,40);
	OFOmino *omino = newOFOmino("551",field->rowCells,0);
	
	OFSearch *search = newSearch(field,omino);
	
	assertEquals("perimeter",search->omino->perimeters[0]->cellCount,26);
	
	search->fillCount = 20;
	search->perimeterCheck = 20;
	solve(search);
	reportSearch(search);
}



void tryDifferentHoleChecks()
{
	int hole;
	for(hole = 1; hole < 18; hole++)
	{
		OFField *field = newOFField(19,28);
		OFOmino *omino = newOFOmino("12211",field->rowCells,0);
		OFSearch *search = newSearch(field,omino);
		search->perimeterCheck = hole;
		solve(search);
//		printf("perimeter:%2d %6lldmSec %12lld tried %12lld placed (%8d tried/sec, %8d placed/sec)\n",
//				hole,
//				search->dur / 1000,
//				search->placementsTried,
//				search->placementsPlaced,
//				(int)(1000000 * search->placementsTried / search->dur),
//				(int)(1000000 * search->placementsPlaced / search->dur));
		
		printf("|| '''%d''' || '''%.1fs''' || '''%d million''' || %lld || %d/sec || '''%d million''' || %lld || %d/sec\n|-\n",
				hole, search->dur / 1000000.0,
				 (int)((search->placementsTried + 500000) / 1000000),search->placementsTried,(int)(1000000 * search->placementsTried / search->dur),
				 (int)((search->placementsPlaced + 500000) / 1000000),search->placementsPlaced,(int)(1000000 * search->placementsPlaced / search->dur) );

	}
}

void trySolve3()
{
	OFField *field = newOFField(19,28);
	OFOmino *omino = newOFOmino("12211",field->rowCells,0);
	OFSearch *search = newSearch(field,omino);
	if(solve(search))
		printField2(search->field);
	printf("search->curCount = %d\n",search->curCount);
}

void trySolve4()
{
	OFField *field = newOFField(30,32);
	OFOmino *omino = newOFOmino("2422",field->rowCells,0);
	OFSearch *search = newSearch(field,omino);
	if(solve(search))
		printField(search->field);
	printf("search->curCount = %d\n",search->curCount);
}

void trySolve5()
{
	OFField *field = newOFField(23,24);
	OFOmino *omino = newOFOmino("12111",field->rowCells,0);
	OFSearch *search = newSearch(field,omino);
	if(solve(search))
		printField2(search->field);
	printf("search->curCount = %d\n",search->curCount);
}

int runUnitTests(void)
{
	setbuf(stdout,0);
	printf("\n\n\n-------------------------------------------------\n unit tests %s %s\n\n",__DATE__,__TIME__);
	gErrorCount = 0;

	check3332Sequence();

	checkFailingTiling();
	checkChecksums();
	check3332HalfStripped();
	checkCellID();
	checkImperativeInsertion();
	checkRotatePoints();
	checkRotations();
	checkPerimeter();
	checkPerimeter2();
	checkMemory();
	check3332Basic();
	check3332Sequence();
	checkNewOFField();
	checkNewOFSearch();
	checkFillOrderConsistency();
	checkHalfStripHalting();
	checkHalfStripHaltingColumns();

	trySeahorse("1212321",72,72);
	
	

	//compareSeahorseHalfstripHalting();

//	basic3332();


	//compareSequences12211(76);
	
	//scanSeahorseElls();

//
//	displayPerimeterish();
//	newOFO();
//	trySolve();
////	tryDifferentHoleChecks();
//	visitSeahorse();
//	//visit11();
////	trySolve3();
//	//trySolve4();
//	//trySolve5();

	printf("%d Assertions OK\n%d ERRORS\n",gAssertOKCount,gErrorCount);
	return gErrorCount;
}

@


1.9
log
@in .
@
text
@d579 1
a579 1

d611 1
a611 1
	if(search->curCount >= search->fillCount || doShow)
d634 22
d659 39
a697 2
	int x = 48;
	int y = 72;
d699 1
d914 1
d938 1
d942 1
a942 1
	compareSeahorseHalfstripHalting();
@


1.8
log
@in
@
text
@d16 4
a148 25
static void checkSpiral(void)
{
	OFField *f1 = newOFField(8,8);
	OFField *f2 = makeSpiralField(f1);
	assertNotZero("spiral field",f2);
	assertEquals("spiral offset",f2->cells[11],0);
	assertEquals("spiral offset",f2->cells[18],1);
	assertEquals("spiral offset",f2->cells[88],2);
	assertEquals("spiral offset",f2->cells[86],2);
	assertEquals("spiral offset",f2->cells[82],2);
	assertEquals("spiral offset",f2->cells[81],3);
	
//	printField3(f2);
//	printField2(f2);
}

static void checkLeftRight(void)
{
	OFField *f1 = newOFField(8,8);
	OFField *f2 = makeRightLeftField(f1);
	f2 = makeRightLeftField(f2);
	
//	printField3(f2);
//	printField2(f2);
}
d337 2
a338 2
	OFSequenceSearch *search = newSequenceSearch("112",2,12);
	solveWithSequence(search);
d341 2
a342 2
	for(y = 0; y < search->field->height; y++)
		computeRowChecksum(search->field,y);
d346 5
a350 5
		assertEqualsX("checksum row 4",search->field->rowChecksums[y],search->field->rowChecksums[y+4]);
		assertEqualsX("checksum row 8",search->field->rowChecksums[y],search->field->rowChecksums[y+8]);
		assertNotEquals("checkum !row  1",search->field->rowChecksums[y],search->field->rowChecksums[y+1]);
		assertNotEquals("checkum !row  2",search->field->rowChecksums[y],search->field->rowChecksums[y+2]);
		assertNotEquals("checkum !row  3",search->field->rowChecksums[y],search->field->rowChecksums[y+3]);
d354 2
a355 2
	search = newSequenceSearch("112",12,2);
	solveWithSequence(search);
d358 3
a360 3
	for(x = 0; x < search->field->width; x++)
		computeColumnChecksum(search->field,x);
	//printField2(search->field);
d363 2
a364 2
		assertEqualsX("checksum column 4",search->field->columnChecksums[x],search->field->columnChecksums[x+4]);
		assertEqualsX("checksum column 8",search->field->columnChecksums[x],search->field->columnChecksums[x+8]);
d366 3
a368 3
		assertNotEquals("checkum !col  1",search->field->columnChecksums[x],search->field->columnChecksums[x+1]);
		assertNotEquals("checkum !col  2",search->field->columnChecksums[x],search->field->columnChecksums[x+2]);
		assertNotEquals("checkum !col  3",search->field->columnChecksums[x],search->field->columnChecksums[x+3]);
d370 49
d420 46
d468 3
d514 1
a514 1
		solveWithSequence(search);
d516 1
d565 3
d570 1
a570 1
	printf("took %lld mSec to place %d %d-ominoes\n",search->dur/1000,search->curCount,omino->orientations[0]->cellCount);
d579 2
a580 1
static void reportSpiralSearch(char *title,OFSpiralSearch *search)
a582 9
	printf("---------\n%s\n%s\n",title,omino->name);
	printf("took %lld mSec to place %d %d-ominoes\n",search->dur/1000,search->curCount,omino->orientations[0]->cellCount);
	printf("placementsTried: %lld  (%lld/second)\n",search->placementsTried,search->placementsTried * 1000000LL / search->dur);
	printf("placementsPlaced: %lld  (%lld/second)\n",search->placementsPlaced,search->placementsPlaced * 1000000LL / search->dur);
	if(search->curCount >= search->fillCount)
		printField2(search->field);
	printf("search->curCount = %d\n",search->curCount);
	printf("--------------\n\n");
}
d584 16
a599 3
static void reportSequenceSearch(char *title,OFSequenceSearch *search)
{
	OFOmino *omino = search->omino[0];
d602 7
a608 1
	printf("took %lld mSec to place %d %d-ominoes\n",search->dur/1000,search->curCount,omino->orientations[0]->cellCount);
d611 1
a611 1
	if(search->curCount >= search->fillCount)
a616 23

void trySpiralSolve3332(int pieceCount)
{
	OFSpiralSearch *search = newSpiralSearch("3332",25,22);
	search->perimeterCheck = 0;
	search->fillCount = pieceCount;
	solveWithSpiral(search);
	reportSpiralSearch("SPIRAL",search);
}

void tryRLSolve3332(int pieceCount)
{
	printf("---------\nRightLeft [ %d] \n",pieceCount);

	OFSpiralSearch *search = newSpiralSearch("3332",25,22);
	search->spiralField = makeRightLeftField(search->field);
	//search->spiralField = makeRightField(search->field);
	search->perimeterCheck = 0;
	search->fillCount = pieceCount;
	solveWithSpiral(search);
	reportSpiralSearch("RIGHTLEFT",search);
}

d630 48
a677 1
	reportSequenceSearch("Sequence",search);
d685 1
a685 1
	for(ZZ = 0; ZZ < 3; ZZ++)
d689 3
a691 1
		if(ZZ == 1)
d696 1
a696 1
		else if(ZZ == 2)
d705 4
d714 1
a714 1
		reportSequenceSearch("Sequence",search);
d724 1
a724 1
	reportSequenceSearch("Seahorse Ell",search);
d744 1
a744 1
				reportSequenceSearch("Seahorse Ell",search);
d854 1
d857 1
d859 2
a861 2

	// silent fast tests, keep running!
d863 1
a863 1
	checkChecksums();
a868 2
	checkSpiral();
	checkLeftRight();
d874 7
a881 1
//	trySequenceSolve3332(50);
d885 1
a885 1
//	compareSequences12211(76);
a888 3
//	trySpiralSolve3332(24);  // THIS TAKES FORVER
//	
//
@


1.7
log
@in
@
text
@d21 3
a23 1
#define assert(_m,_n) if(!(_n)) printf("ERROR %d [%s:%d] %s\n",++gErrorCount,__FILE__,__LINE__,_m);
d27 7
a33 1
#define assertEquals(_m,_n1,_n2) if((_n1) != (_n2)) printf("ERROR %d [%s:%d] %d!=%d %s\n",++gErrorCount,__FILE__,__LINE__,_n1,_n2,_m);
d37 1
a37 1
static void memory(void)
d73 33
a105 8
	assertEquals("cr0",o->orientations[0]->cellOffsets[0],0);
	assertEquals("cr0",o->orientations[1]->cellOffsets[0],0);
	assertEquals("cr0",o->orientations[2]->cellOffsets[0],-12);
	assertEquals("cr0",o->orientations[3]->cellOffsets[0],-20);
	assertEquals("cr0",o->orientations[4]->cellOffsets[0],-2);
	assertEquals("cr0",o->orientations[5]->cellOffsets[0],0);
	assertEquals("cr0",o->orientations[6]->cellOffsets[0],-8);
	assertEquals("cr0",o->orientations[7]->cellOffsets[0],-21);
d108 34
d147 1
a147 1
	OFField *f1 = newField(8,8);
d157 2
a158 2
	printField3(f2);
	printField2(f2);
d163 1
a163 1
	OFField *f1 = newField(8,8);
d165 1
d167 2
a168 2
	printField3(f2);
	printField2(f2);
d213 1
a213 1
		OFField *off = newField(12,12);
d285 120
d406 1
a406 1
static void newOFField()
d408 38
a445 1
	OFField *f = newField(10,5);
d453 1
a453 1
static void newOFSearch()
d455 1
a455 1
	OFField *field = newField(5,10);
d477 1
a477 1
	OFField *field = newField(5,10);
d556 1
d569 1
a569 1
	for(ZZ = 0; ZZ < 2; ZZ++)
d576 6
a581 1
			printf("---------\nELL Sequence [ %d] \n",pieceCount);
d630 1
a630 1
void trySolve2()
d632 1
a632 1
	OFField *field = newField(25,22);
d638 2
d644 1
a644 1
	OFField *field = newField(40,90);
d659 1
a659 1
	OFField *field = newField(40,40);
d679 1
a679 1
		OFField *field = newField(19,28);
d702 1
a702 1
	OFField *field = newField(19,28);
d712 1
a712 1
	OFField *field = newField(30,32);
d722 1
a722 1
	OFField *field = newField(23,24);
d735 6
d742 10
d753 2
a754 2
//	checkSpiral();
//	checkLeftRight();
a755 3
//	int i;
//	for(i = 1; i < 20; i++)
		//tryRLSolve3332(50);
a756 1
//	trySequenceSolve3332(50);
d759 1
a759 1
	scanSeahorseElls();
a764 2
//	checkPerimeter();
//	checkPerimeter2();
a765 1
//	memory();
a766 2
//	newOFField();
//	newOFSearch();
a768 1
	trySolve2();
d774 2
a775 1
	
@


1.6
log
@in
@
text
@d273 1
a273 1
static void reportSpiralSearch(OFSpiralSearch *search)
d276 1
a276 1
	printf("---------\nSPIRAL\n%s\n",omino->name);
d286 13
d300 2
a301 1
void trySpiralSolve3332()
d305 1
a305 1
	search->fillCount = 50;
d307 1
a307 1
	reportSpiralSearch(search);
d310 1
a310 1
void tryRLSolve3332()
d312 2
d316 1
a316 1
	search->spiralField = makeRightField(search->field);
d318 1
a318 1
	search->fillCount = 50;
d320 1
a320 1
	reportSpiralSearch(search);
d323 74
d501 1
d504 2
a505 2
	checkSpiral();
	checkLeftRight();
d507 8
a514 1
	tryRLSolve3332();
d516 1
a516 1
//	trySpiralSolve3332();  // THIS TAKES FORVER
@


1.5
log
@in
@
text
@d40 63
d273 36
d328 1
a328 1
	search->fillCount = 89;
d341 1
a341 1
	assertEquals("perimeter",search->omino->perimeters[0]->cellCount,8);
d411 20
a430 9
	checkPerimeter();
	checkPerimeter2();
	displayPerimeterish();
	memory();
	newOFO();
	newOFField();
	newOFSearch();
	trySolve();
//	tryDifferentHoleChecks();
d432 5
a436 5
	visitSeahorse();
	//visit11();
//	trySolve3();
	//trySolve4();
	//trySolve5();
@


1.4
log
@in
@
text
@d42 19
a60 19
	OFOminoCells *ooc = cellsFromDescription("123");
	positionFirstCell(ooc,0);
	discoverPerimeter(ooc);
	
	rotateCells90(ooc);
	positionFirstCell(ooc,0);
	discoverPerimeter(ooc);

	rotateCells90(ooc);
	positionFirstCell(ooc,0);
	discoverPerimeter(ooc);

	rotateCells90(ooc);
	positionFirstCell(ooc,0);
	discoverPerimeter(ooc);
	
	ooc = cellsFromDescription("1");
	OFOminoCells *peri = discoverPerimeter(ooc);
	OFOrientedOmino *periO = cellsToOffsets(peri,10);
d64 1
a64 1
	assertEquals("perimeter[3]",periO->cellOffsets[2],113);
d89 1
a89 1
		printField
d143 12
d184 1
a184 1
	//printField(search->field);
d215 1
d220 32
d313 1
d320 1
a320 1
	tryDifferentHoleChecks();
d322 3
a324 1
	trySolve3();
@


1.3
log
@in
@
text
@d40 56
d148 1
a148 1
	printField(f);
d172 1
a172 1
	printField(search->field);
d180 14
a193 2
	solve(search);
	printField(search->field);
d195 1
d204 27
a230 2
	printField(search->field);
	printf("search->curCount = %d\n",search->curCount);
d238 2
a239 2
	solve(search);
	printField(search->field);
d248 2
a249 2
	solve(search);
	printField(search->field);
d258 2
a259 2
	solve(search);
	printField(search->field);
d266 3
d274 1
d277 2
a278 2
	trySolve4();
	trySolve5();
@


1.2
log
@in
@
text
@d119 50
d176 5
@


1.1
log
@Initial revision
@
text
@d12 1
a12 1
#include "fittings.h"
d14 1
d42 1
a42 1
	OFOmino *ofo = newOFOmino("123",3,0);
d48 4
d62 15
a76 7
	// "123" on row 3 should make 0,3,4,6,7,8
	assertEquals("123",ofo->orientations[1]->cellOffsets[0],0);
	assertEquals("123",ofo->orientations[1]->cellOffsets[1],-1);
	assertEquals("123",ofo->orientations[1]->cellOffsets[2],2);
	assertEquals("123",ofo->orientations[1]->cellOffsets[3],-2);
	assertEquals("123",ofo->orientations[1]->cellOffsets[4],1);
	assertEquals("123",ofo->orientations[1]->cellOffsets[5],4);
d78 1
a78 1
	// "123" on row 3 should make 0,3,4,6,7,8
d85 29
d115 2
a118 1

d124 2
@