head 1.14; access; symbols; locks poly:1.14; strict; comment @ * @; 1.14 date 2006.04.16.20.11.26; author poly; state Exp; branches; next 1.13; 1.13 date 2006.04.13.05.22.57; author poly; state Exp; branches; next 1.12; 1.12 date 2006.04.11.03.19.24; author poly; state Exp; branches; next 1.11; 1.11 date 2006.04.09.21.06.27; author poly; state Exp; branches; next 1.10; 1.10 date 2006.04.08.17.28.22; author poly; state Exp; branches; next 1.9; 1.9 date 2006.04.06.04.43.51; author poly; state Exp; branches; next 1.8; 1.8 date 2006.04.06.03.48.37; author poly; state Exp; branches; next 1.7; 1.7 date 2006.04.05.03.55.11; author poly; state Exp; branches; next 1.6; 1.6 date 2006.04.03.03.11.27; author poly; state Exp; branches; next 1.5; 1.5 date 2006.04.01.23.14.10; author poly; state Exp; branches; next 1.4; 1.4 date 2006.04.01.08.38.39; author poly; state Exp; branches; next 1.3; 1.3 date 2006.03.31.07.19.08; author poly; state Exp; branches; next 1.2; 1.2 date 2006.03.31.05.05.55; 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.14 log @in @ text @/* * fittings.c * omino_fitting_2006 * * Created by david van brink on 3/29/06. * Copyright 2006 __MyCompanyName__. All rights reserved. * */ #include #include #include "Fittings.h" #include "Printing.h" #include "Memory.h" // Local Protos void rotatePoints90(OFPoints *cells); void reflectPointsY(OFPoints *cells); OFPoints *getPerimeterPoints(OFPoints *cells); OFCellPoint dirSteps[] = { {1,0}, // 0: right {0,1}, // 1: up {-1,0}, // 2: left {0,-1} // 3: down }; OFOffsets *offsetsFromPoints(OFPoints *cells,int fieldRow) { int i; int cellCount = cells->cellCount; OFOffsets *ofoo = Malloc(sizeof(OFOffsets) + cellCount * sizeof(int)); ofoo->cellCount = cellCount; for(i = 0; i < cellCount; i++) ofoo->cellOffsets[i] = cells->cells[i].y * fieldRow + cells->cells[i].x; return ofoo; } // +--------------------------------- // | newOFOmino // | char *ominoDescription: string like "1212321" for seahorse // | int fieldRow: cells across, for computing offsets // | // | Creates the 8 rotations for the described omino. // | OFOmino *newOFOmino(char *ominoDescription, int fieldRow, int fillOrder) { OFOmino *ofo = Malloc(sizeof(OFOmino)); ofo->name = ominoDescription; ofo->fillOrder = fillOrder; // 0 is right,down ofo->fieldRow = fieldRow; ofo->orientationCount = 8; // Get the list of xy-cells OFPoints *ominoPoints = pointsFromDescription(ominoDescription); // unspool the 8 orientations int i; for(i = 0; i < 8; i++) { OFPoints *rotatedPoints = copyPoints(ominoPoints); rotatePoints(rotatedPoints,i); // for fill order, we rotate opposite, assign first (lower-left) point, // and rotate back rotatePoints(rotatedPoints,-fillOrder); positionFirstPoint(rotatedPoints); rotatePoints(rotatedPoints,fillOrder); // rotate after finding first-point OFPoints *perimeterPoints = getPerimeterPoints(rotatedPoints); ofo->orientations[i] = offsetsFromPoints(rotatedPoints,fieldRow); ofo->perimeters[i] = offsetsFromPoints(perimeterPoints,fieldRow); FreeAt((void **)&rotatedPoints); } return ofo; } /* ROTATIONS: orientations -- there are 8 possible orientations. Using standard coordinates -- x right, y up: (also) (value) (turn) 0 0 -- Original -3 1 -- +90 (CCW) -2 2 -- +180 (CCW) -1 3 -- +270 (CCW) -4 4 -- Y-reflected -5 5 -- +90 (CCW) and then Y-reflected -6 6 -- +180 (CCW) and then Y-reflected -7 7 -- +270 (CCW) and then Y-reflected */ void rotatePoints(OFPoints *points,int direction) { // figure equivalent positive direction if negative if(direction < 0) { // strange way to map 0to0,-3to1,-2to2,-1to3, &c direction = -direction; if(direction & 1 && direction < 4) direction ^= 2; } int i; for(i = 0; i < (direction & 3); i++) rotatePoints90(points); if(direction >= 4) reflectPointsY(points); } void freeOFOminoAt(OFOmino **n) { OFOmino *o = *n; int i; for(i = 0; i < o->orientationCount; i++) FreeAt((void**)&(o->orientations[i])); for(i = 0; i < o->orientationCount; i++) FreeAt((void**)&(o->perimeters[i])); FreeAt((void **)n); } void freeSequenceSearchAt(OFSequenceSearch **search) { FreeAt((void **)&(**search).offsetSequence); FreeAt((void **)&(**search).field); int i; for(i = 0; i < 8; i++) freeOFOminoAt(&(**search).omino[i]); } // transform string like "1212321" into list of XY coordinates OFPoints *pointsFromDescription(char *ominoDescription) { int len = strlen(ominoDescription); // first, count them up int cellCount = 0; int i,j; for(i = 0; i < len; i++) cellCount += ominoDescription[i] & 0x0f; // "0".."9" is like that // malloc an OFPoints OFPoints *cells = Malloc(sizeof(OFPoints) + cellCount * sizeof(OFCellPoint)); cells->cellCount = cellCount; // and fill in the cells int t = 0; for(i = 0; i < len; i++) { int height = ominoDescription[i] & 0x0f; for(j = 0; j < height; j++) { cells->cells[t].x = i; cells->cells[t].y = j; t++; } } return cells; } OFPoints *copyPoints(OFPoints *original) { OFPoints *copy = Malloc(sizeof(OFPoints) + original->cellCount * sizeof(OFCellPoint)); copy->cellCount = original->cellCount; int i; for(i = 0; i < copy->cellCount; i++) copy->cells[i] = original->cells[i]; return copy; } // +----------- // | In-place rotation of these cells, counterclockwise, // | where of course Y is "Up" // | void rotatePoints90(OFPoints *cells) { int i; for(i = 0; i < cells->cellCount; i++) { int x = cells->cells[i].x; int y = cells->cells[i].y; cells->cells[i].x = -y; cells->cells[i].y = x; } } // +----------- // | In-place horizontal-flip of these cells // | void reflectPointsY(OFPoints *cells) { int i; for(i = 0; i < cells->cellCount; i++) cells->cells[i].x = -cells->cells[i].x; } // +-------------------- // | Position first cell -- for particular fill order, position // | the first-placed cell at (0,0) // | void positionFirstPoint(OFPoints *cells) { OFCellPoint best = cells->cells[0]; int i; for(i = 1; i < cells->cellCount; i++) { OFCellPoint c = cells->cells[i]; if(c.y < best.y) best = c; else if((c.y == best.y) && (c.x < best.x)) best = c; } // we know the x/y of the "best" cell, offset everyone // so the "best" is at 0,0 for(i = 0; i < cells->cellCount; i++) { cells->cells[i].x -= best.x; cells->cells[i].y -= best.y; } } // sloppy slow hit-testing for an OminoCells static int checkCell(OFPoints *cells,OFCellPoint *p) { int i; for(i = 0; i < cells->cellCount; i++) { OFCellPoint *cell = &cells->cells[i]; if(cell->x == p->x && cell->y == p->y) return 1; } return 0; } static int checkCellBumped(OFPoints *cells,OFCellPoint *p,OFCellPoint *bump) { OFCellPoint bumped = *p; bumped.x += bump->x; bumped.y += bump->y; return checkCell(cells,&bumped); } // +------------------------- // | getPerimeterPoints // | Given an omino-cells list, whose leftmost bottom is at 0,0, // | Describe the peripheral starting on the left, used // | for holefinding. OFPoints *getPerimeterPoints(OFPoints *cells) { OFCellPoint perimeter[1000]; // arbitrary, hopefully big enough int pCount = 0; // start the perimeter to the left of where // we would place it; holes are mostly formed // on the left. OFCellPoint first; first.x = -1; first.y = 1; while(checkCell(cells,&first)) first.x --; int dir = 1; OFCellPoint curCellPoint = first; nextP: perimeter[pCount++] = curCellPoint; // Find the next cell, by veering-right as we walk around the omino int nextDir; for(nextDir = dir + 3; nextDir <= dir + 6; nextDir++) { OFCellPoint nextCellPoint = curCellPoint; nextCellPoint.x += dirSteps[nextDir & 3].x; nextCellPoint.y += dirSteps[nextDir & 3].y; if(!checkCell(cells,&nextCellPoint)) { curCellPoint = nextCellPoint; dir = nextDir & 3; break; // found it } } if(curCellPoint.x == first.x && curCellPoint.y == first.y) { OFPoints *result = Malloc(sizeof(OFPoints) + pCount * sizeof(OFCellPoint)); result->cellCount = pCount; int i; for(i = 0; i < pCount; i++) result->cells[i] = perimeter[i]; return result; } goto nextP; } // +------------------------- // | Create field with frame &c // | OFField *newOFField(int width,int height) { int border = 1; int allTheCells = (width + 2 * border) * (height + 2 * border); OFField *field = Malloc(sizeof(OFField) + allTheCells * sizeof(OFCell)); field->rowChecksums = Malloc(sizeof(int) * height); field->columnChecksums = Malloc(sizeof(int) * width); field->width = width; field->height = height; field->rowCells = width + 2 * border; field->cell00 = border * field->rowCells + border; field->cellCount = allTheCells; // Fill the whole thing int i; for(i = 0; i < allTheCells; i++) field->cells[i] = kCellWall; // and hollow out the center int x,y; for(y = 0; y < height; y++) for(x = 0; x < width; x++) field->cells[field->cell00 + y * field->rowCells + x] = 0; return field; } void freeOFFieldAt(OFField **field) { if(field && *field) { FreeAt((void **)&((**field).rowChecksums)); FreeAt((void **)&((**field).columnChecksums)); } FreeAt((void **)field); } int getFieldCellOffset(OFField *f,int x, int y) { return f->cell00 + x + y * f->rowCells; } OFCell getFieldCell(OFField *f,int x, int y) { return f->cells[f->cell00 + x + y * f->rowCells]; } OFSearch *newSearch(OFField *field,OFOmino *omino) { // compute how many digits in the solution // fail if it doesnt work out right int ominoSize = omino->orientations[0]->cellCount; int fieldSize = field->width * field->height; if(fieldSize % ominoSize) { printf("%d wont fit %d-ominoes!\n",fieldSize,ominoSize); // return 0; } int digitCount = fieldSize / ominoSize; // great, we have a plausible winnah OFSearch *search = Malloc(sizeof(OFSearch) + digitCount * sizeof(OFDigit)); search->field = field; search->omino = omino; search->fillCount = digitCount; return search; } int placePiece(OFSearch *search,int originIndex) { int orientation; originIndex = search->field->cell00; OFCell *origin = search->field->cells + originIndex; for(orientation = 3; orientation < 8; orientation++) { OFCell value = 17 + orientation; OFOffsets *ofoo = search->omino->orientations[orientation]; int i; int offset; for(i = 0; i < ofoo->cellCount; i++) { offset = ofoo->cellOffsets[i]; if(origin[offset]) goto erase; origin[offset] = value; } OFDigit *d = &search->digit[search->curCount++]; d->orientation = orientation; d->fieldCell = originIndex; return 1; // success erase: while(--i >= 0) { offset = ofoo->cellOffsets[i]; origin[offset] = 0; } } return 0; // fail } int solve(OFSearch *search) { OFField *field = search->field; OFOmino *omino = search->omino; OFOffsets *ofo = 0; int i; int result; long long startTime = getUSecTime(); long long placementsTried = 0; long long placementsPlaced = 0; // ------------------------------------ // Initial Conditions int fieldCell = field->cell00; OFDigit *d = search->digit; // ------------------------------------ // Place A Piece TryPlacement: //printf("curCount: %d %d, orientation: %d @@ %d\n",search->curCount,d - search->digit,d->orientation,fieldCell); placementsTried++; ofo = omino->orientations[d->orientation]; // scan the omino, see if field is free for(i = 0; i < ofo->cellCount; i++) if(field->cells[fieldCell + ofo->cellOffsets[i]]) goto TickOver; // scan the perimeter, for hole-trouble if(search->perimeterCheck > 1) { OFOffsets *perimeterOffsets = omino->perimeters[d->orientation]; int lastPerimeterFilled = (1==1); int p; int transitionCount = 0; for(p = 0; p < search->perimeterCheck; p++) { int thisPerimeterFilled = (field->cells[fieldCell + perimeterOffsets->cellOffsets[p]] & kCellOmino) != 0; transitionCount += (thisPerimeterFilled ^ lastPerimeterFilled); lastPerimeterFilled = thisPerimeterFilled; } if(transitionCount > 2) goto TickOver; } // ------------------------------------ // A Viable Placement: Draw the piece OFCell value = (search->curCount % 26) + 'A'; d->fieldCell = fieldCell; for(i = 0; i < ofo->cellCount; i++) field->cells[fieldCell + ofo->cellOffsets[i]] = value; // field->cells[fieldCell + ofo->cellOffsets[i]] = value | (ofo->cellOffsets[i]<<8); placementsPlaced++; // ------------------------------------ // Advance To Next Digit, maybe finished? search->curCount++; d++; if(search->curCount == search->fillCount) goto Success; // ------------------------------------ // Advance to next open cell while(field->cells[fieldCell]) fieldCell++; // ------------------------------------ // And try to place next piece goto TryPlacement; // ------------------------------------ // Cannot Place, tick digit and retry TickOver: d->orientation++; if(d->orientation < 8) goto TryPlacement; // ------------------------------------ // Tried all 8, reset this digit and back up one. d->orientation = 0; d--; search->curCount--; // ------------------------------------ // Backtracked before we began? fail... if(search->curCount < 0) goto Failure; // ------------------------------------ // Erase the previous attempt ofo = omino->orientations[d->orientation]; fieldCell = d->fieldCell; for(i = 0; i < ofo->cellCount; i++) field->cells[fieldCell + ofo->cellOffsets[i]] = 0; // ------------------------------------ // And tick-over to the next digit goto TickOver; Failure: result = 0; goto done; Success: result = 1; done:{} long long endTime = getUSecTime(); search->placementsTried = placementsTried; search->placementsPlaced = placementsPlaced; search->dur = endTime - startTime; return 1; } OFSequenceSearch *newSequenceSearch(char *ominoDescription,int width,int height) { OFField *field = newOFField(width,height); int fieldRow = field->rowCells; int i; OFOmino *ominos[8]; for(i = 0; i < 8; i++) ominos[i] = newOFOmino(ominoDescription, fieldRow,i); int ominoSize = ominos[0]->orientations[0]->cellCount; int fieldSize = field->width * field->height; if(fieldSize % ominoSize) printf("%d wont exactly fit %d-ominoes!\n",fieldSize,ominoSize); int fillCount = fieldSize / ominoSize; OFSequenceSearch *sequenceSearch = Malloc(sizeof(OFSequenceSearch) + fillCount * sizeof(OFDigit)); sequenceSearch->field = field; sequenceSearch->cellCount = width * height; sequenceSearch->halfstripHalting = 1; for(i = 0; i < 8; i++) sequenceSearch->omino[i] = ominos[i]; sequenceSearch->fillCount = fillCount; // default sequence: normal sequenceSearch->offsetSequence = Malloc(sequenceSearch->cellCount * sizeof(OFSequenceElement) + 1); //sequenceSearch->directionSequence = Malloc(sequenceSearch->cellCount * sizeof(int)); for(i = 0; i < sequenceSearch->cellCount; i++) { int x = i % width; int y = i / width; int offset = sequenceSearch->field->cell00 + y * sequenceSearch->field->rowCells + x; sequenceSearch->offsetSequence[i] = offset; } sequenceSearch->offsetSequence[sequenceSearch->cellCount] = SEQUENCE_IMPERATIVE_SUCCESS; return sequenceSearch; } void makeCombSequence(OFSequenceSearch *search) { OFField *field = search->field; // fill up the left half, going right, // then the right half, going left. int w = field->width; int h = field->height; int k = 0; int x,y; for(y = 0; y < h; y++) { for(x = 0; x < w/2; x++) { int dir = 0; int offset = field->cell00 + y * field->rowCells + x; search->offsetSequence[k] = PACK_SEQUENCE_OFFSET_DIR(offset,dir); k++; } } for(y = 0; y < h; y++) { for(x = w-1; x >=w/2; x--) { int dir = 4; int offset = field->cell00 + y * field->rowCells + x; search->offsetSequence[k] = PACK_SEQUENCE_OFFSET_DIR(offset,dir); k++; } } } /* The L sequence fill normally up to the halfwater mark, and then fills vertically, right to left for the other half. ||||||||| ||||||||| ========= ========= This forces three corners to be finished pretty early. */ void makeEllSequence(OFSequenceSearch *search) { OFField *field = search->field; // fill up the left half, going right, // then the right half, going left. int w = field->width; int h = field->height; int k = 0; int x,y; for(y = 0; y < h/2; y++) { for(x = 0; x < w; x++) { int dir = 0; int offset = field->cell00 + y * field->rowCells + x; search->offsetSequence[k] = PACK_SEQUENCE_OFFSET_DIR(offset,dir); k++; } } for(x = w-1; x >= 0; x--) { for(y = h/2; y < h; y++) { int dir = 1; int offset = field->cell00 + y * field->rowCells + x; search->offsetSequence[k] = PACK_SEQUENCE_OFFSET_DIR(offset,dir); k++; } } } /* <<<<<^^^^^ <<<<<^^^^^ <<<<<^^^^^ >>>>>>>>>> >>>>>>>>>> >>>>>>>>>> */ void makeYouSequence(OFSequenceSearch *search) { OFField *field = search->field; // fill up the left half, going right, // then the right half, going left. int w = field->width; int h = field->height; int w2_3 = w/2; //2*w/3; int h1_3 = h/2; // h/3; int k = 0; int x,y; // bottom third for(y = 0; y < h1_3; y++) { for(x = 0; x < w; x++) { int dir = 0; int offset = field->cell00 + y * field->rowCells + x; search->offsetSequence[k] = PACK_SEQUENCE_OFFSET_DIR(offset,dir); k++; } } // right third for(x = w-1; x >= w2_3; x--) { for(y = h1_3; y < h; y++) { int dir = 1; int offset = field->cell00 + y * field->rowCells + x; search->offsetSequence[k] = PACK_SEQUENCE_OFFSET_DIR(offset,dir); k++; } } // remaining upper-left two-thirds for(y = h-1; y >= h1_3; y--) { for(x = w2_3-1; x >= 0; x--) { int dir = 2; int offset = field->cell00 + y * field->rowCells + x; search->offsetSequence[k] = PACK_SEQUENCE_OFFSET_DIR(offset,dir); k++; } } } void makeUpSequence(OFSequenceSearch *search) { OFField *field = search->field; // normal search order, with halfstrip markers inserted int *sequence = Malloc(sizeof(OFSequenceElement) * (field->width * field->height + 1)); int k = 0; int x,y; for(x = 0; x < field->width; x++) { for(y = 0; y < field->height; y++) { int dir = 5; int offset = field->cell00 + y * field->rowCells + x; sequence[k] = PACK_SEQUENCE_OFFSET_DIR(offset,dir); k++; } } sequence[k++] = SEQUENCE_IMPERATIVE_SUCCESS; FreeAt((void **)&search->offsetSequence); search->offsetSequence = sequence; } void makeStdHalfstripSequence(OFSequenceSearch *search) { OFField *field = search->field; // normal search order, with halfstrip markers inserted int *sequence = Malloc(sizeof(OFSequenceElement) * (field->width * field->height + field->height + 1)); // extra element for each row & succeess int k = 0; int x,y; for(y = 0; y < field->height; y++) { for(x = 0; x < field->width; x++) { int dir = 0; int offset = field->cell00 + y * field->rowCells + x; sequence[k] = PACK_SEQUENCE_OFFSET_DIR(offset,dir); k++; } // row-end: sequence[k++] = 0x80000000 + (y << 16); } sequence[k++] = SEQUENCE_IMPERATIVE_SUCCESS; FreeAt((void **)&search->offsetSequence); search->offsetSequence = sequence; } /* +--------------------------------------------- | Given a search and a sequence WITHOUT checksum | imperatives, recreate the sequence with the | imperatives inferred. | | We absolutely assume the correctness of the original | sequence, and that it has no checksum imperatives yet. */ void insertChecksumImperatives(OFSequenceSearch *search) { OFField *field = search->field; int oldSequenceSize = field->width * field->height; int newSequenceSize = oldSequenceSize + field->width + field->height + 1; int *newSequence = Malloc(sizeof(OFSequenceElement) * newSequenceSize); int *cellsDonePerRow = Malloc(sizeof(int) * field->height); int *cellsDonePerColumn = Malloc(sizeof(int) * field->width); int i; int k = 0; for(i = 0; i < oldSequenceSize; i++) { int seqval = search->offsetSequence[i]; newSequence[k++] = seqval; int offset = UNPACK_SEQUENCE_OFFSET(seqval) - field->cell00; int y = offset / field->rowCells; int x = offset % field->rowCells; int possibleRowCompleteImperative = possibleRowCompletionImperative(cellsDonePerRow,y,field->width,field->height,SEQUENCE_IMPERATIVE_ROWCOMPLETE); if(possibleRowCompleteImperative) newSequence[k++] = possibleRowCompleteImperative; int possibleColumnCompleteImperative = possibleRowCompletionImperative( cellsDonePerColumn,x,field->height,field->width,SEQUENCE_IMPERATIVE_COLUMNCOMPLETE); if(possibleColumnCompleteImperative) newSequence[k++] = possibleColumnCompleteImperative; } // final condition newSequence[k++] = SEQUENCE_IMPERATIVE_SUCCESS; // All done, free up the cruft FreeAt((void **)&cellsDonePerRow); FreeAt((void **)&cellsDonePerColumn); FreeAt((void **)&search->offsetSequence); search->offsetSequence = newSequence; // no size needed, other terminal conditions work. } int possibleRowCompletionImperative(int *cellsDonePer, int rowNumber, int cellsPerRow,int rowCount,int rowOrColImperative) { int result = 0; cellsDonePer[rowNumber]++; if(cellsDonePer[rowNumber] == cellsPerRow) // finished a row! { // find out what span to compare against... assume int completeFromBottom = 1; int completeFromTop = 1; int y1; for(y1 = 0; y1 < rowCount; y1++) if(cellsDonePer[y1] != cellsPerRow) // row not done... if(y1 < rowNumber) completeFromBottom = 0; else completeFromTop = 0; if(completeFromBottom || completeFromTop) // only insert if we are contiguous... { if(completeFromBottom) y1 = 0; else y1 = rowCount - 1; result = PACK_SEQUENCE_IMPERATIVE(rowOrColImperative,rowNumber,y1); } } return result; } int solveWithSequence(OFSequenceSearch *search) { OFField *field = search->field; OFField *deepestField = newOFField(field->width,field->height); // we'll save the biggest solution... OFOffsets *ofo = 0; int offsetDirs[4]; offsetDirs[0] = 1; offsetDirs[1] = field->rowCells; offsetDirs[2] = -1; offsetDirs[3] = -field->rowCells; offsetDirs[4] = -1; offsetDirs[5] = field->rowCells; offsetDirs[6] = 1; offsetDirs[7] = -field->rowCells; int i; int result; long long startTime = getUSecTime(); long long placementsTried = 0; long long placementsPlaced = 0; // ------------------------------------ // Initial Conditions OFDigit *d = search->digit; int cellNumber = 0; int fieldCell = UNPACK_SEQUENCE_OFFSET(search->offsetSequence[cellNumber]); // ------------------------------------ // Place A Piece TryPlacement: //printf("curCount: %d %d, orientation: %d @@ %d\n",search->curCount,d - search->digit,d->orientation,fieldCell); placementsTried++; // choose the right omino orientation for the fill direction here int dir = UNPACK_SEQUENCE_DIR(search->offsetSequence[cellNumber]); OFOmino *omino = search->omino[dir]; ofo = omino->orientations[d->orientation]; // scan the omino, see if field is free for(i = 0; i < ofo->cellCount; i++) if(field->cells[fieldCell + ofo->cellOffsets[i]]) goto TickOver; // scan the perimeter, for hole-trouble if(search->perimeterCheck > 1) { OFOffsets *perimeterOffsets = omino->perimeters[d->orientation]; int lastPerimeterFilled = (1==1); int p; int transitionCount = 0; for(p = 0; p < search->perimeterCheck; p++) { int thisPerimeterFilled = (field->cells[fieldCell + perimeterOffsets->cellOffsets[p]] & kCellOmino) != 0; transitionCount += (thisPerimeterFilled ^ lastPerimeterFilled); lastPerimeterFilled = thisPerimeterFilled; } if(transitionCount > 2) goto TickOver; } // ------------------------------------ // A Viable Placement: Draw the piece // OFCell value = (search->curCount % 254) + 1; // d->fieldCell = fieldCell; // d->cellNumber = cellNumber; // d->dir = dir; // for(i = 0; i < ofo->cellCount; i++) // field->cells[fieldCell + ofo->cellOffsets[i]] = value; // OK to draw this piece! do so: placementsPlaced++; d->fieldCell = fieldCell; d->cellNumber = cellNumber; d->dir = dir; OFCell value = (search->curCount % 254) + 1 + (d->orientation << 21); // top3 bits of id for(i = 0; i < ofo->cellCount; i++) field->cells[fieldCell + ofo->cellOffsets[i]] = value + (i << 16); //lower 5 bits of id, good up to 32-omino //yyy //// ------------------------------------ //// Advance To Next Digit, maybe finished? // // search->curCount++; // d++; // if(search->curCount == search->fillCount) // goto Success; // ------------------------------------ // Advance to next open cell int sequenceImperative; Advance: cellNumber++; sequenceImperative = search->offsetSequence[cellNumber]; if(sequenceImperative & 0xf0000000) goto HalfStripHaltCheck; else { fieldCell = UNPACK_SEQUENCE_OFFSET(sequenceImperative); if(field->cells[fieldCell]) // something already drawn here goto Advance; } // ------------------------------------ // Advance To Next Digit, maybe finished? search->curCount++; if(search->curCount > search->deepestCount) { // remember the furthest we got, for posterity. search->deepestCount = search->curCount; int z; for(z = 0; z < deepestField->cellCount; z++) deepestField->cells[z] = field->cells[z]; } d++; if(search->curCount == search->fillCount) goto Success; // ------------------------------------ // And try to place next piece goto TryPlacement; // ------------------------------------ HalfStripHaltCheck: // compute halfstrip for this row or column... if(UNPACK_SEQUENCE_IMPERATIVE(sequenceImperative) == SEQUENCE_IMPERATIVE_ROWCOMPLETE) { int row = UNPACK_SEQUENCE_IMPERATIVE_VALUE(sequenceImperative); computeRowChecksum(search->field,row); int rowCheckFrom = UNPACK_SEQUENCE_IMPERATIVE_FROM(sequenceImperative); int didRepeatRow = checkRepeatedRows(field,rowCheckFrom,row); if(didRepeatRow && search->halfstripHalting) { search->halfstripRejections++; goto EraseAndTick; } } else if(UNPACK_SEQUENCE_IMPERATIVE(sequenceImperative) == SEQUENCE_IMPERATIVE_COLUMNCOMPLETE) { int column = UNPACK_SEQUENCE_IMPERATIVE_VALUE(sequenceImperative); computeColumnChecksum(search->field,column); int colCheckFrom = UNPACK_SEQUENCE_IMPERATIVE_FROM(sequenceImperative); int didRepeatCol = checkRepeatedColumns(field,colCheckFrom,column); if(didRepeatCol && search->halfstripHalting) { search->halfstripRejections++; goto EraseAndTick; } } else if(sequenceImperative == SEQUENCE_IMPERATIVE_SUCCESS) goto Success; goto Advance; // skip halfstrip nonsense // ------------------------------------ // Cannot Place, tick digit and retry TickOver: d->orientation++; if(d->orientation < 8) goto TryPlacement; // ------------------------------------ // Tried all 8, reset this digit and back up one. d->orientation = 0; d--; search->curCount--; // ------------------------------------ // Backtracked before we began? fail... if(search->curCount < 0) goto Failure; // ------------------------------------ // Erase the previous attempt EraseAndTick: cellNumber = d->cellNumber; fieldCell = d->fieldCell; dir = UNPACK_SEQUENCE_DIR(search->offsetSequence[cellNumber]); omino = search->omino[dir]; ofo = omino->orientations[d->orientation]; for(i = 0; i < ofo->cellCount; i++) field->cells[fieldCell + ofo->cellOffsets[i]] = 0; // ------------------------------------ // And tick-over to the next digit goto TickOver; Failure: result = 0; freeOFFieldAt(&search->field); search->field = deepestField; goto done; Success: result = 1; done:{} search->curCount++; // always either -1 or 1-less-than-finish. long long endTime = getUSecTime(); search->placementsTried = placementsTried; search->placementsPlaced = placementsPlaced; search->dur = endTime - startTime; return result; } void computeRowChecksum(OFField *field,int row) { int x; unsigned int checksum = 0; int offset = getFieldCellOffset(field,0,row); for(x = 0; x < field->width; x++) { int cellValue = field->cells[offset++] & kCellID; checksum = (checksum << 1) ^ (checksum >> 31) ^ cellValue; } field->rowChecksums[row] = checksum; } void computeColumnChecksum(OFField *field,int column) { int y; unsigned int checksum = 0; int offset = getFieldCellOffset(field,column,0); for(y = 0; y < field->height; y++) { int cellValue = field->cells[offset] & kCellID; checksum = (checksum << 1) ^ (checksum >> 31) ^ cellValue; offset += field->rowCells; } field->columnChecksums[column] = checksum; } int checkRepeatedRows(OFField *field,int rowCheckFrom,int row) { int bump; if(rowCheckFrom < row) bump = 1; else if(rowCheckFrom > row) bump = -1; else return 0; // just 1 row, cant check yet unsigned int rowChecksum = field->rowChecksums[row]; while(rowCheckFrom != row) { unsigned int aChecksum = field->rowChecksums[rowCheckFrom]; if(aChecksum == rowChecksum) { // checksum matched! oh no. We will check each cell between them now. int x; for(x = 0; x < field->width; x++) { int cellID1 = getFieldCell(field,x,row) & kCellID; int cellID2 = getFieldCell(field,x,rowCheckFrom) & kCellID; if(cellID1 != cellID2) goto Foo; } // they matched. return Yes, we halfstripped. return 1; } Foo: rowCheckFrom += bump; } return 0; // no halfstrip repeat found } int checkRepeatedColumns(OFField *field,int colCheckFrom,int col) { int bump; if(colCheckFrom < col) bump = 1; else if(colCheckFrom > col) bump = -1; else return 0; // just 1 col, cant check yet unsigned int colChecksum = field->columnChecksums[col]; while(colCheckFrom != col) { unsigned int aChecksum = field->columnChecksums[colCheckFrom]; if(aChecksum == colChecksum) { // checksum matched! oh no. We will check each cell between them now. int y; for(y = 0; y < field->height; y++) { int cellID1 = getFieldCell(field,col,y) & kCellID; int cellID2 = getFieldCell(field,colCheckFrom,y) & kCellID; if(cellID1 != cellID2) goto Foo; } // they matched. return Yes, we halfstripped. return 1; } Foo: colCheckFrom += bump; } return 0; // no halfstrip repeat found } @ 1.13 log @in . @ text @d1118 1 @ 1.12 log @in @ text @d350 1 a350 1 void freeOFField(OFField **field) a369 86 // +----------------------------------- // | From a field, generate the spiral // | orientations needed to walk it // | and populate it in a frame-first search OFField *makeSpiralField(OFField *field) { OFField *spiralField = newOFField(field->width,field->height); OFField *markerField = newOFField(field->width,field->height); int fieldCell = spiralField->cell00; int offsetDirs[8]; offsetDirs[0] = 1; offsetDirs[1] = field->rowCells; offsetDirs[2] = -1; offsetDirs[3] = -field->rowCells; offsetDirs[4] = -1; offsetDirs[5] = field->rowCells; offsetDirs[6] = 1; offsetDirs[7] = -field->rowCells; int d = 0; doCell: if(markerField->cells[fieldCell + offsetDirs[d]]) d = (d + 1) & 3; // turn left! if(markerField->cells[fieldCell + offsetDirs[d]]) goto goHome; spiralField->cells[fieldCell] = d; markerField->cells[fieldCell] = 13; fieldCell += offsetDirs[d]; goto doCell; goHome: FreeAt((void **)&markerField); return spiralField; } // +----------------------------------- // | From a field, generate the spiral // | orientations needed to walk it // | and populate it in a frame-first search OFField *makeRightLeftField(OFField *field) { OFField *spiralField = newOFField(field->width,field->height); int fieldCell = spiralField->cell00; int x; int y; for(y = 0; y < spiralField->height; y++) for(x = 0; x < spiralField->width; x++) { fieldCell = (y + 1) * spiralField->rowCells + (x + 1); int d = 0; if(y % 2) { d = 4; if(x == 0) d = 1; } else { d = 0; if(x == (spiralField->width - 1)) d = 1; } spiralField->cells[fieldCell] = d; } return spiralField; } OFField *makeRightField(OFField *field) { OFField *rightField = newOFField(field->width,field->height); int i; for(i = 0; i < rightField->cellCount; i++) rightField->cells[i] = 0; return rightField; } a396 39 OFSpiralSearch *newSpiralSearch(char *ominoDescription,int width, int height) { OFField *field = newOFField(width,height); OFField *spiralField = makeSpiralField(field); int fieldRow = field->rowCells; int i; OFOmino *ominos[8]; for(i = 0; i < 8; i++) ominos[i] = newOFOmino(ominoDescription, fieldRow,i); int ominoSize = ominos[0]->orientations[0]->cellCount; int fieldSize = field->width * field->height; if(fieldSize % ominoSize) printf("%d wont exactly fit %d-ominoes!\n",fieldSize,ominoSize); int fillCount = fieldSize / ominoSize; OFSpiralSearch *spiralSearch = Malloc(sizeof(OFSpiralSearch) + fillCount * sizeof(OFDigit)); spiralSearch->field = field; spiralSearch->spiralField = spiralField; for(i = 0; i < 8; i++) spiralSearch->omino[i] = ominos[i]; spiralSearch->fillCount = fillCount; return spiralSearch; } a441 153 int solveWithSpiral(OFSpiralSearch *search) { OFField *field = search->field; OFOffsets *ofo = 0; int offsetDirs[4]; offsetDirs[0] = 1; offsetDirs[1] = field->rowCells; offsetDirs[2] = -1; offsetDirs[3] = -field->rowCells; offsetDirs[4] = -1; offsetDirs[5] = field->rowCells; offsetDirs[6] = 1; offsetDirs[7] = -field->rowCells; int i; int result; long long startTime = getUSecTime(); long long placementsTried = 0; long long placementsPlaced = 0; // ------------------------------------ // Initial Conditions int fieldCell = field->cell00; OFDigit *d = search->digit; // ------------------------------------ // Place A Piece TryPlacement: //printf("curCount: %d %d, orientation: %d @@ %d\n",search->curCount,d - search->digit,d->orientation,fieldCell); placementsTried++; // choose the right omino orientation for the fill direction here OFOmino *omino = search->omino[search->spiralField->cells[fieldCell]]; ofo = omino->orientations[d->orientation]; // scan the omino, see if field is free for(i = 0; i < ofo->cellCount; i++) if(field->cells[fieldCell + ofo->cellOffsets[i]]) goto TickOver; // scan the perimeter, for hole-trouble if(search->perimeterCheck > 1) { OFOffsets *perimeterOffsets = omino->perimeters[d->orientation]; int lastPerimeterFilled = (1==1); int p; int transitionCount = 0; for(p = 0; p < search->perimeterCheck; p++) { int thisPerimeterFilled = (field->cells[fieldCell + perimeterOffsets->cellOffsets[p]] & kCellOmino) != 0; transitionCount += (thisPerimeterFilled ^ lastPerimeterFilled); lastPerimeterFilled = thisPerimeterFilled; } if(transitionCount > 2) goto TickOver; } // ------------------------------------ // A Viable Placement: Draw the piece OFCell value = (search->curCount % 26) + 'A'; d->fieldCell = fieldCell; for(i = 0; i < ofo->cellCount; i++) field->cells[fieldCell + ofo->cellOffsets[i]] = value; // field->cells[fieldCell + ofo->cellOffsets[i]] = value | (0x00007f00 & ((0x7f & ofo->cellOffsets[i])<<8)); placementsPlaced++; // ------------------------------------ // Advance To Next Digit, maybe finished? search->curCount++; d++; if(search->curCount == search->fillCount) goto Success; // ------------------------------------ // Advance to next open cell while(field->cells[fieldCell]) { int bump = offsetDirs[search->spiralField->cells[fieldCell]]; fieldCell += bump; if(bump < 0) { // printf("XXXX fieldCell = %d\n",fieldCell); //search->curCount = search->fillCount; // fake // return 1; // !!! } } // ------------------------------------ // And try to place next piece goto TryPlacement; // ------------------------------------ // Cannot Place, tick digit and retry TickOver: d->orientation++; if(d->orientation < 8) goto TryPlacement; // ------------------------------------ // Tried all 8, reset this digit and back up one. d->orientation = 0; d--; search->curCount--; // ------------------------------------ // Backtracked before we began? fail... if(search->curCount < 0) goto Failure; // ------------------------------------ // Erase the previous attempt fieldCell = d->fieldCell; omino = search->omino[search->spiralField->cells[fieldCell]]; ofo = omino->orientations[d->orientation]; for(i = 0; i < ofo->cellCount; i++) field->cells[fieldCell + ofo->cellOffsets[i]] = 0; // ------------------------------------ // And tick-over to the next digit goto TickOver; Failure: result = 0; goto done; Success: result = 1; done:{} long long endTime = getUSecTime(); search->placementsTried = placementsTried; search->placementsPlaced = placementsPlaced; search->dur = endTime - startTime; return 1; } d599 1 d607 1 a607 1 sequenceSearch->offsetSequence = Malloc(sequenceSearch->cellCount * sizeof(OFSequenceElement)); d616 1 d767 23 d795 1 a795 1 int *sequence = Malloc(sizeof(int) * (field->width * field->height + field->height)); // extra element for each row d811 2 d818 77 d906 2 d991 8 a998 7 // ------------------------------------ // Advance To Next Digit, maybe finished? search->curCount++; d++; if(search->curCount == search->fillCount) goto Success; d1017 16 d1040 28 a1068 1 printf("nooo\n"); return(0); d1094 1 d1111 2 d1122 1 a1122 1 return 1; d1154 70 @ 1.11 log @in @ text @a18 1 OFPoints *pointsFromDescription(char *ominoDescription); a20 1 static void rotatePoints(OFPoints *points,int direction); d51 2 d72 5 a77 1 d91 22 a112 1 static void rotatePoints(OFPoints *points,int direction) d114 9 d142 9 d323 1 a323 1 OFField *newField(int width,int height) d328 2 d350 20 d377 2 a378 2 OFField *spiralField = newField(field->width,field->height); OFField *markerField = newField(field->width,field->height); d417 1 a417 1 OFField *spiralField = newField(field->width,field->height); d447 1 a447 1 OFField *rightField = newField(field->width,field->height); d485 1 a485 1 OFField *field = newField(width,height); a556 94 int solvex(OFSearch *search) { //search->perimeterCheck = 10; // !!! long long startTime = getUSecTime(); long long placementsTried = 0; long long placementsPlaced = 0; OFField *field = search->field; OFOmino *omino = search->omino; OFOffsets *ofo = 0; int i; int fieldCell = field->cell00; // begin piece at curCount:digit:orientaton // advance to next free cell tryOrientation: while(field->cells[fieldCell]) fieldCell++; OFDigit *d = search->digit + search->curCount; d->fieldCell = fieldCell; // where we are drawing in ofo = omino->orientations[d->orientation]; //tryOrientation: //printf("tryOrientation: %d.%d @@ %d\n",search->curCount,d->orientation,fieldCell); placementsTried++; ofo = omino->orientations[d->orientation]; // scan the omino, see if field is free for(i = 0; i < ofo->cellCount; i++) if(field->cells[fieldCell + ofo->cellOffsets[i]]) { // this digit no good: advance to next advanceDigit: d->orientation++; if(d->orientation < 8) goto tryOrientation; // backtrack a digit search->curCount--; if(search->curCount < 0) { // backtracked to -1, fail goto fail; } d--; // point to previous digit // erase the drawn digit ofo = omino->orientations[d->orientation]; fieldCell = d->fieldCell; for(i = 0; i < ofo->cellCount; i++) field->cells[fieldCell + ofo->cellOffsets[i]] = 0; // and advance THIS one goto advanceDigit; } // got to here -- the piece can be place. another check -- // the perimeter if(search->perimeterCheck > 1) { OFOffsets *perimeterOffsets = omino->perimeters[d->orientation]; int lastPerimeterFilled = (1==1); int p; int transitionCount = 0; for(p = 0; p < search->perimeterCheck; p++) { int thisPerimeterFilled = (field->cells[fieldCell + perimeterOffsets->cellOffsets[p]] & kCellOmino) != 0; transitionCount += (thisPerimeterFilled ^ lastPerimeterFilled); lastPerimeterFilled = thisPerimeterFilled; } if(transitionCount > 2) goto advanceDigit; // { // printf("transitionCount=%d\n",transitionCount); // for(i = 0; i < ofo->cellCount; i++) // field->cells[fieldCell + ofo->cellOffsets[i]] = 99; //return 1;} } // OK to draw this piece! do so: placementsPlaced++; OFCell value = (search->curCount % 26) + 'A'; for(i = 0; i < ofo->cellCount; i++) field->cells[fieldCell + ofo->cellOffsets[i]] = value; // advance curcount & try next search->curCount++; if(search->curCount == search->fillCount) goto succeed; d++; d->orientation = 0; goto tryOrientation; a557 14 int result; fail: result = 0; goto done; succeed: result = 1; done:{} long long endTime = getUSecTime(); search->placementsTried = placementsTried; search->placementsPlaced = placementsPlaced; search->dur = endTime - startTime; return 1; } d856 1 a856 1 OFField *field = newField(width,height); d884 2 a885 2 sequenceSearch->offsetSequence = Malloc(sequenceSearch->cellCount * sizeof(int)); sequenceSearch->directionSequence = Malloc(sequenceSearch->cellCount * sizeof(int)); d919 1 a919 2 search->directionSequence[k] = dir; search->offsetSequence[k] = offset; d930 1 a930 2 search->directionSequence[k] = dir; search->offsetSequence[k] = offset; d964 1 a964 2 search->directionSequence[k] = dir; search->offsetSequence[k] = offset; d975 1 a975 2 search->directionSequence[k] = dir; search->offsetSequence[k] = offset; d1013 1 a1013 2 search->directionSequence[k] = dir; search->offsetSequence[k] = offset; d1025 1 a1025 2 search->directionSequence[k] = dir; search->offsetSequence[k] = offset; d1037 21 a1057 2 search->directionSequence[k] = dir; search->offsetSequence[k] = offset; d1060 2 d1063 3 d1074 3 d1107 1 a1107 1 int fieldCell = search->offsetSequence[cellNumber]; d1117 1 a1117 1 int dir = search->directionSequence[cellNumber]; d1147 9 a1155 1 OFCell value = (search->curCount % 26) + 'A'; d1159 1 d1161 1 a1161 3 field->cells[fieldCell + ofo->cellOffsets[i]] = value; // field->cells[fieldCell + ofo->cellOffsets[i]] = value | (0x00007f00 & ((0x7f & ofo->cellOffsets[i])<<8)); placementsPlaced++; d1174 11 a1184 4 while(field->cells[fieldCell]) { cellNumber++; fieldCell = search->offsetSequence[cellNumber]; d1191 6 d1224 1 a1224 1 dir = search->directionSequence[cellNumber]; d1250 13 d1264 14 a1277 10 @ 1.10 log @in @ text @d1029 65 @ 1.9 log @in @ text @d609 1 d897 206 d1104 8 d1113 2 d1116 4 d1121 2 d1124 5 d1130 25 d1156 2 d1159 7 d1167 2 d1170 1 d1173 3 d1177 9 @ 1.8 log @in @ text @d317 1 a317 1 int offsetDirs[4]; d322 4 d340 1 a340 1 FreeAt((void **)markerField); d365 1 a365 1 d = 2; d620 4 d681 1 d821 1 @ 1.7 log @in @ text @a22 1 OFPoints *copyPoints(OFPoints *original); d25 8 d73 3 d126 2 a127 2 int rowCount = ominoDescription[i] & 0x0f; for(j = 0; j < rowCount; j++) d129 2 a130 2 cells->cells[t].y = i; cells->cells[t].x = j; a224 7 OFCellPoint dirSteps[] = { {1,0}, // 0: right {0,1}, // 1: up {-1,0}, // 2: left {0,-1} // 3: down }; d305 83 d414 39 d605 149 d895 18 @ 1.6 log @in @ text @d19 6 a24 3 OFOminoCells *cellsFromDescription(char *ominoDescription); void rotateCells90(OFOminoCells *cells); void reflectCellsY(OFOminoCells *cells); d26 2 a27 1 OFOrientedOmino *cellsToOffsets(OFOminoCells *cells,int fieldRow) d31 1 a31 1 OFOrientedOmino *ofoo = Malloc(sizeof(OFOrientedOmino) + cellCount * sizeof(int)); d55 1 a55 1 d57 1 a57 1 OFOminoCells *ominoCells = cellsFromDescription(ominoDescription); d60 2 a61 3 int rot; for(rot = 0; rot < 4; rot++) d63 9 a71 22 int flip; for(flip = 0; flip < 8; flip += 4) { positionFirstCell(ominoCells,fillOrder); OFOminoCells *perimeterCells = discoverPerimeter(ominoCells); // int i; // OFOrientedOmino *ofoo = Malloc(sizeof(OFOrientedOmino) + cellCount * sizeof(int)); // // // ofoo->cellCount = cellCount; // for(i = 0; i < cellCount; i++) // { // ofoo->cellOffsets[i] = ominoCells->cells[i].y * fieldRow + ominoCells->cells[i].x; ////grrprintf("++|%4d - %4d - %4d\n",flip+rot,i,ofoo->cellOffsets[i]); // } // ofo->orientations[flip + rot] = ofoo; ofo->orientations[flip + rot] = cellsToOffsets(ominoCells,fieldRow); ofo->perimeters[flip + rot] = cellsToOffsets(perimeterCells,fieldRow); reflectCellsY(ominoCells); } rotateCells90(ominoCells); d77 9 d90 5 a94 6 if(o->orientations) { int i; for(i = 0; i < o->orientationCount; i++) FreeAt((void**)&(o->orientations[i])); } d99 1 a99 1 OFOminoCells *cellsFromDescription(char *ominoDescription) d108 2 a109 2 // malloc an OFOminoCells OFOminoCells *cells = Malloc(sizeof(OFOminoCells) + cellCount * sizeof(OFCellPoint)); d128 11 d144 1 a144 1 void rotateCells90(OFOminoCells *cells) d160 1 a160 1 void reflectCellsY(OFOminoCells *cells) d172 1 a172 1 void positionFirstCell(OFOminoCells *cells, int ignoredFillOrder) d195 1 a195 1 static int checkCell(OFOminoCells *cells,OFCellPoint *p) d207 1 a207 1 static int checkCellBumped(OFOminoCells *cells,OFCellPoint *p,OFCellPoint *bump) d223 1 a223 1 // | discoverPerimeter d227 1 a227 1 OFOminoCells *discoverPerimeter(OFOminoCells *cells) d247 1 a247 1 for(nextDir = dir + 3; nextDir <= dir + 5; nextDir++) d261 1 a261 1 OFOminoCells *result = Malloc(sizeof(OFOminoCells) + pCount * sizeof(OFCellPoint)); d314 1 a314 1 return 0; d338 1 a338 1 OFOrientedOmino *ofoo = search->omino->orientations[orientation]; d363 1 a363 2 // just like placePiece for now... int solve(OFSearch *search) d373 1 a373 1 OFOrientedOmino *ofo = 0; d425 1 a425 1 OFOrientedOmino *perimeterOffsets = omino->perimeters[d->orientation]; d469 1 a469 1 long long dur = search->dur = endTime - startTime; d477 144 @ 1.5 log @in @ text @a16 13 // Local Structures typedef struct { int x,y; } OFCellPoint; typedef struct { int cellCount; OFCellPoint cells[0]; } OFOminoCells; a21 1 void positionFirstCell(OFOminoCells *cells,int fillOrder); d23 13 d46 2 a53 1 int cellCount = ominoCells->cellCount; a62 3 int i; OFOrientedOmino *ofoo = Malloc(sizeof(OFOrientedOmino) + cellCount * sizeof(int)); d64 1 d66 13 a78 7 ofoo->cellCount = cellCount; for(i = 0; i < cellCount; i++) { ofoo->cellOffsets[i] = ominoCells->cells[i].y * fieldRow + ominoCells->cells[i].x; //grrprintf("++|%4d - %4d - %4d\n",flip+rot,i,ofoo->cellOffsets[i]); } ofo->orientations[flip + rot] = ofoo; d185 79 d282 1 a282 1 field->cells[i] = ~0; d357 3 a359 1 search->startTime = getUSecTime(); d413 23 d450 1 d452 2 a453 5 search->endTime = getUSecTime(); printf("fail\n"); printf("placementsTried: %lld\n",placementsTried); printf("placementsPlaced: %lld\n",placementsPlaced); return 0; d456 6 a461 5 search->endTime = getUSecTime(); long long dur = search->endTime - search->startTime; printf("took %lld mSec to place %d %d-ominoes\n",dur/1000,search->curCount,omino->orientations[0]->cellCount); printf("placementsTried: %lld (%lld/second)\n",placementsTried,placementsTried * 1000000LL / dur); printf("placementsPlaced: %lld (%lld/second)\n",placementsPlaced,placementsPlaced * 1000000LL / dur); @ 1.4 log @in @ text @d352 1 a352 1 printf("took %lldd mSec to place %d %d-ominoes\n",dur/1000,search->curCount,omino->orientations[0]->cellCount); @ 1.3 log @in @ text @d13 1 d195 1 a195 1 d236 1 a236 1 void placePiece(OFSearch *search) d240 2 a241 2 OFCell *origin = search->field->cells + search->field->cell00; OFCell value = 18; d243 1 a243 1 for(orientation = 0; orientation < 8; orientation++) d245 1 d256 5 a260 2 return; // success d265 1 a265 1 origin[i] = 0; d268 88 @ 1.2 log @checkpoint @ text @d11 1 d71 1 d162 1 a162 1 for(i = 1; i <= cells->cellCount; i++) d173 1 a173 1 for(i = 0; i <= cells->cellCount; i++) d212 53 @ 1.1 log @Initial revision @ text @d11 1 a11 1 #include "fittings.h" d33 1 d52 3 a54 5 // unspool the first one // TODO rotate and flip the cells, round and round, and also find "upper left" // or whatever for the preferred fill order. d63 2 d76 1 a76 1 d150 64 @