Welcome to Software Development on Codidact!
Will you help us build our independent community of developers helping developers? We're small and trying to grow. We welcome questions about all aspects of software development, from design to code to QA and more. Got questions? Got answers? Got code you'd like someone to review? Please join us.
I want to speed up my Two Closed Loops solver
+3
−0
User trichoplax of Codidact posted the following puzzle:
Note: User trichoplax has given me permission to use text and images from their post. This is appreciated.
Goal of trichoplax’s puzzle:
Rearrange and/or rotate the 25 tiles below, including the blank tile, to form a 5x5 square so that the two different styles of line each form a single closed loop.
Here is a solution:
Review request:
I solved this puzzle by hand and later created a JavaScript program to solve this and similar puzzles.
If you wish to run my program go to following website:
My OpenProcessing JavaScript solver
I tested my program with a number of tile sets that were simpler than trichoplax’s puzzle and the program was able to solve all test cases. The solve times ranged from a few seconds to a few minutes.
But when I tried to use my program to solve trichoplax’s puzzle, it would only solve it occasionally in a reasonable amount of time. However I am confident that my program would always solve trichoplax’s puzzle if I allowed it to run for a very long time.
I want to make my program more efficient. I would appreciate any type of review of my program but I am especially interested in ideas to make the program quicker.
Here is my JavaScript code:
// ***** OVERVIEW OF PROGRAM *****
// Program written by Will Gibson
// This program is related to the puzzle posted by user trichoplax of Codidact at:
// https://proposals.codidact.com/posts/295850
// In solving the tiles, the goal in this program is slightly different than trichoplax's puzzle. ...
// ... In trichoplax's puzzle, the goal is to arrange the tile set to form ...
// ... one closed loop for each of the 2 different colored set of lines (curved or straight). ...
// ... However, this program allows for tile sets with either one, two or three colors. ...
// ... Also, this program considers the tile set to be solved, if for each color, ...
// ... the lines form one OR MORE closed loops.
/* ---------- OPTIONS (start) ---------- */
// If <solveTheTileSet> is true, the program attempts to solve the tile set, ...
// ... otherwise it simply displays the tile set.
solveTheTileSet = true;
// <PERMUTE_ROTATE_SIZE> is the number of tiles to be permuted and/or rotated ...
// ... during each attempt to improve the arrangement of the tile set.
PERMUTE_ROTATE_SIZE = 4;
// Every <SCRAMBLE_FREQUENCY> drawing frames, if the program hasn't completely solved the tile set, ...
// ... it randomizes the positions of the tiles. The purpose of this is to avoid getting stuck ...
// ... in the program's hill climbing algorithm.
SCRAMBLE_FREQUENCY = 35;
// For each dashed arc/line, <NUM_DASHED_{arc/line}_SEGMENTS> indicates how many dashes are drawn.
NUM_DASHED_ARC_SEGMENTS = 5;
NUM_DASHED_LINE_SEGMENTS = 7;
/* ========== OPTIONS (end) ========== */
function setup() {
// <tiles> stores the arcs/lines information for the square grid of the tile set. ...
//
// ... The grid can be as small as 2 x 2 and as large as 9 x 9. ...
//
// ... Thin red arcs/lines are represented using the numbers 1 through 6. ...
// ... 1, 2, 3, 4 represents arcs whose center is a tile corner. ...
// ... 1: Top left, 2: Top right, 3: Bottom left, 4: Bottom right. ...
// ... 5: Vertical line, 6: Horizontal line. ...
//
// ... Medium width dashed black arcs/lines are represented using the numbers 11 through 16 ...
// ... with their positions being defined like thin red arcs/lines except 10 larger in value.
//
// ... Thick blue/purple arcs/lines are represented using the numbers -1 through -6, ...
// ... with their positions being defined like thin red arcs/lines except negative in value.
tiles = [ // TEST # 1, All 3 colors (3 loops)
[ [ 1], [-1], [11], [] ],
[ [], [ 1], [-1], [11] ],
[ [11], [], [ 1], [-1] ],
[ [-1], [11], [], [ 1] ]
];
tiles = [ // TEST # 2, Figure 8 and tiny loop
[ [11], [-1], [11], [-1] ],
[ [11], [-1], [11], [11] ],
[ [-2,13], [15,16], [ ], [ ] ],
[ [ ], [ ], [ ], [ ] ]
];
tiles = [ // TEST # 3, Big L & tiny loop
[ [-1], [1], [1], [-1] ],
[ [ 1], [1], [1], [ 1] ],
[ [ 5], [5], [5], [ 5] ],
[ [-1], [5], [5], [-1] ]
];
tiles = [ // TEST # 4, Big outside loop
[ [ ], [ ], [ ], [ ] ],
[ [11], [11], [11], [11] ],
[ [15], [15], [15], [15] ],
[ [15], [15], [15], [15] ]
];
tiles = [ // TEST # 5, 5 loops
[ [-1,4], [-1,4], [-1,14], [-1,14] ],
[ [ 1 ], [11 ], [ 1 ], [11 ] ],
[ [ 1 ], [11 ], [ 1 ], [11 ] ],
[ [ 1 ], [11 ], [ 1 ], [11 ] ]
];
tiles = [ // TEST # 6, 2 intersecting loops
[ [ 5,-6], [ 5,-6], [ 6,-5], [ 6,-5], [ 5 ] ],
[ [ 5 ], [ 1 ], [ 1 ], [ 1 ], [ 1 ] ],
[ [-1 ], [-1 ], [-1 ], [-1 ], [ ] ],
[ [ ], [ ], [ ], [ ], [ ] ],
[ [ ], [ ], [ ], [ ], [ ] ]
];
tiles = [ // trichoplax's 5 x 5 puzzle
[ [], [ 4], [ 4], [ 4], [ 4] ],
[ [ 4], [ 4], [ 4], [-4], [-4] ],
[ [-4], [-4], [-4], [-4], [-4] ],
[ [-1,-4], [-5], [-5], [ 6,-5], [ 6,-5] ],
[ [ 4,-1], [ 5,6], [ 5,6], [ 6,-5], [ 6,-5] ]
];
gridSize = tiles.length;
createCanvas(windowWidth, windowHeight);
// <bestScore> represents how close the current arrangement of tiles is ...
// ... to a collection of closed loops (and no loose ends) where for each closed loop ...
// ... the arcs/lines in that closed loop are colored the same. ...
//
// ... A perfect fully solved arrangement of tiles will have a score of 0. ...
// ... However, for each common edge of two adjacent tiles where the arcs/lines (if present) ...
// ... do not match, the score is reduced by a small amount. ...
// ... If a common edge has no arcs/lines coming to it, there is no reduction. ...
// ... If a common edge has only one arc/line coming to it, there is a small reduction. ...
// ... If a common edge has two arcs/lines coming to it AND ...
// ... if the colors of the arcs/lines are not the same, there is a small reduction.
//
// ... Similarly, for every arc/line extending to the edge of the grid, ...
// ... the score is reduced by a large amount because ...
// ... that arc/line can not be continued to form a closed loop.
//
// ... The more negative the score, the worse the arrangement of tiles is.
bestScore = evaluateTiles(tiles);
} // end setup
function windowResized() {
resizeCanvas(windowWidth, windowHeight);
} // end windowResized
function draw() {
// This functions draws the tile set as it hopefully improves until a solved state.
background('white');
drawGridLines();
drawTiles();
POSSIBLE_TILE_SET_MODIFICATION:
if( solveTheTileSet && (bestScore !== 0) ) {
// Occasionally completely permute the tiles to hopefully not get stuck in hill climbing
if( frameCount !== 0 ) {
if( (frameCount % SCRAMBLE_FREQUENCY) === 0 ) {
randomizeTiles(tiles);
bestScore = evaluateTiles(tiles); // Recompute score
}
}
IMPROVEMENT_REQUIRED_LOOP:
for( attemptCtr=0; attemptCtr<1234567; attemptCtr++ ) {
allowIdenticalScore = false;
success = attemptToInchTowardSolution( allowIdenticalScore );
if(success) {
break POSSIBLE_TILE_SET_MODIFICATION;
}
}
EQUAL_SCORE_OK_LOOP:
for( attemptCtr=0; attemptCtr<1234567; attemptCtr++ ) {
allowIdenticalScore = true;
success = attemptToInchTowardSolution( allowIdenticalScore );
if(success) {
break POSSIBLE_TILE_SET_MODIFICATION;
}
}
}
} // end draw
function drawGridLines() {
squareSize = floor( min(windowWidth, windowHeight) / (gridSize+0.5) );
squareSize = 2 * floor(squareSize/2); // Ensure even square size
topLeftX = floor( (windowWidth -gridSize*squareSize) / 2 );
topLeftY = floor( (windowHeight-gridSize*squareSize) / 2 );
stroke(['magenta','black'][frameCount % 2]);
strokeWeight(6);
point(topLeftX-10, topLeftY-10); // Show program is active
// Draw grid lines
gridLineWidth = floor( 0.06*squareSize );
gridLineColor = '#808080';
strokeWeight(gridLineWidth);
stroke (gridLineColor);
for( row=0; row<=gridSize; row++ ) { // Horizontal lines
startX = topLeftX;
endX = topLeftX + gridSize*squareSize;
startY = topLeftY + row*squareSize;
endY = startY;
line(startX, startY, endX, endY);
}
for( col=0; col<=gridSize; col++ ) { // Vertical lines
startX = topLeftX + col*squareSize;
endX = startX;
startY = topLeftY;
endY = topLeftY + gridSize*squareSize;
line(startX, startY, endX, endY);
}
} // end drawGridLines
function drawTiles() {
// Set size and color information
halfSquareSize = floor(squareSize/2);
thinLineHalfWidth = floor( 0.07*squareSize );
thinLineColor = '#BB3333';
thinArcMinDiameter = squareSize - 2*thinLineHalfWidth;
thinArcMaxDiameter = squareSize + 2*thinLineHalfWidth;
dashedLineHalfWidth = floor( 0.12*squareSize );
dashedLineColor = 'black';
dashedArcMinDiameter = squareSize - 2*dashedLineHalfWidth;
dashedArcMaxDiameter = squareSize + 2*dashedLineHalfWidth;
thickLineInsideHalfWidth = floor( 0.10*squareSize );
thickLineInsideColor = '#BBDDFF';
thickLineBorderWidth = floor( 0.06*squareSize );
thickLineBorderColor = '#9933EE';
thickArcInsideMinDiameter = squareSize - 2*thickLineInsideHalfWidth;
thickArcInsideMaxDiameter = squareSize + 2*thickLineInsideHalfWidth;
thickArcBorder_1_MinDiameter = thickArcInsideMinDiameter - 2*thickLineBorderWidth;
thickArcBorder_1_MaxDiameter = thickArcInsideMinDiameter;
thickArcBorder_2_MinDiameter = thickArcInsideMaxDiameter;
thickArcBorder_2_MaxDiameter = thickArcInsideMaxDiameter + 2*thickLineBorderWidth;
for( row=0; row<gridSize; row++ ) { // Display all tiles
for( col=0; col<gridSize; col++ ) {
squareMinX = topLeftX + col*squareSize;
squareMinY = topLeftY + row*squareSize;
// Each tile has either 0, 1 or 2 arcs/lines
for( lineTypeSub=0; lineTypeSub < tiles[row][col].length; lineTypeSub++ ) {
lineType = tiles[row][col][lineTypeSub];
switch (abs(lineType)) { // Collect information about arcs
case 1:
case 11:
centerX = squareMinX;
centerY = squareMinY;
startAngle = 0;
finalAngle = HALF_PI;
break;
case 2:
case 12:
centerX = squareMinX + squareSize;
centerY = squareMinY;
startAngle = HALF_PI;
finalAngle = PI;
break;
case 3:
case 13:
centerX = squareMinX;
centerY = squareMinY + squareSize;
startAngle = 3*HALF_PI;
finalAngle = TWO_PI;
break;
case 4:
case 14:
centerX = squareMinX + squareSize;
centerY = squareMinY + squareSize;
startAngle = PI;
finalAngle = 3*HALF_PI;
break;
}
SOLID = 1;
DASHED = 2;
switch (lineType) { // Draw arcs and lines
case 1:
case 2:
case 3:
case 4:
drawArc(centerX, centerY, thinArcMinDiameter, thinArcMaxDiameter,
thinLineColor, startAngle, finalAngle, SOLID);
break;
case 11:
case 12:
case 13:
case 14:
drawArc(centerX, centerY, dashedArcMinDiameter, dashedArcMaxDiameter,
dashedLineColor, startAngle, finalAngle, DASHED);
break;
case 5:
x = squareMinX + halfSquareSize - thinLineHalfWidth - 0.5;
y = squareMinY;
rectWidth = 2*thinLineHalfWidth+1;
rectHeight = squareSize+1;
noStroke();
fill(thinLineColor);
rect(x, y, rectWidth, rectHeight);
break;
case 15:
x = squareMinX + halfSquareSize - dashedLineHalfWidth - 0.5;
totalNumSegments = 2*NUM_DASHED_LINE_SEGMENTS;
rectWidth = 2*dashedLineHalfWidth+1;
rectHeight = squareSize/totalNumSegments;
noStroke();
fill(dashedLineColor);
for( segmentCtr=0; segmentCtr<NUM_DASHED_LINE_SEGMENTS; segmentCtr++ ) {
y = squareMinY + ( 0.5 + 2*segmentCtr ) * rectHeight;
rect(x, y, rectWidth, rectHeight);
}
break;
case 6:
x = squareMinX;
y = squareMinY + halfSquareSize - thinLineHalfWidth - 0.5;
rectWidth = squareSize+1;
rectHeight = 2*thinLineHalfWidth+1;
noStroke();
fill(thinLineColor);
rect(x, y, rectWidth, rectHeight);
break;
case 16:
y = squareMinY + halfSquareSize - dashedLineHalfWidth - 0.5;
totalNumSegments = 2*NUM_DASHED_LINE_SEGMENTS;
rectWidth = squareSize/totalNumSegments;
rectHeight = 2*dashedLineHalfWidth+1;
noStroke();
fill(dashedLineColor);
for( segmentCtr=0; segmentCtr<NUM_DASHED_LINE_SEGMENTS; segmentCtr++ ) {
x = squareMinX + ( 0.5 + 2*segmentCtr ) * rectWidth;
rect(x, y, rectWidth, rectHeight);
}
break;
case -1:
case -2:
case -3:
case -4:
drawArc(centerX, centerY, thickArcInsideMinDiameter, thickArcInsideMaxDiameter,
thickLineInsideColor, startAngle, finalAngle, SOLID);
drawArc(centerX, centerY, thickArcBorder_1_MinDiameter, thickArcBorder_1_MaxDiameter,
thickLineBorderColor, startAngle, finalAngle, SOLID);
drawArc(centerX, centerY, thickArcBorder_2_MinDiameter, thickArcBorder_2_MaxDiameter,
thickLineBorderColor, startAngle, finalAngle, SOLID);
break;
case -5:
x = squareMinX + halfSquareSize - thickLineInsideHalfWidth - 0.5;
y = squareMinY;
rectWidth = 2*thickLineInsideHalfWidth+1;
rectHeight = squareSize+1;
noStroke();
fill(thickLineInsideColor);
rect(x, y, rectWidth, rectHeight);
x = squareMinX + halfSquareSize - thickLineInsideHalfWidth - thickLineBorderWidth-0.5;
rectWidth = thickLineBorderWidth+1;
fill(thickLineBorderColor);
rect(x, y, rectWidth, rectHeight);
x = squareMinX + halfSquareSize + thickLineInsideHalfWidth - 0.5;
rect(x, y, rectWidth, rectHeight);
break;
case -6:
x = squareMinX;
y = squareMinY + halfSquareSize - thickLineInsideHalfWidth - 0.5;
rectWidth = squareSize+1;
rectHeight = 2*thickLineInsideHalfWidth+1;
noStroke();
fill(thickLineInsideColor);
rect(x, y, rectWidth, rectHeight);
y = squareMinY + halfSquareSize - thickLineInsideHalfWidth - thickLineBorderWidth-0.5;
rectHeight = thickLineBorderWidth+1;
fill(thickLineBorderColor);
rect(x, y, rectWidth, rectHeight);
y = squareMinY + halfSquareSize + thickLineInsideHalfWidth - 0.5;
rect(x, y, rectWidth, rectHeight);
break;
}
}
}
}
} // end drawTiles
function drawArc(centerX, centerY, minDiameter, maxDiameter,
arcColor, startAngle, finalAngle, SOLID_or_DASHED) {
noFill();
strokeWeight(1);
stroke(arcColor);
for( arcDiameter=minDiameter; arcDiameter<=maxDiameter; arcDiameter++ ) {
if( SOLID_or_DASHED === SOLID ) {
arc(centerX, centerY, arcDiameter, arcDiameter, startAngle, finalAngle);
}
else {
totalNumSegments = 2*NUM_DASHED_ARC_SEGMENTS;
dashedAngleRange = (finalAngle-startAngle) / totalNumSegments;
for( segmentCtr=0; segmentCtr<NUM_DASHED_ARC_SEGMENTS; segmentCtr++ ) {
dashedStartAngle = startAngle + ( 0.5 + 2*segmentCtr ) * dashedAngleRange;
dashedFinalAngle = dashedStartAngle + dashedAngleRange;
arc(centerX, centerY, arcDiameter, arcDiameter, dashedStartAngle, dashedFinalAngle);
}
}
}
} // end drawArc
function attemptToInchTowardSolution( allowIdenticalScore ) {
// This function tries to incrementally improve the tile set by ...
// ... randomly permuting and/or rotating a subset of the tiles.
// Create space for working copy of tile set (up to size 9 x 9). ...
// ... Initially fill with dummy values.
workingTiles = [
[1,2,3,4,5,6,7,8,9],
[2,0,0,0,0,0,0,0,0],
[3,0,0,0,0,0,0,0,0],
[4,0,0,0,0,0,0,0,0],
[5,0,0,0,0,0,0,0,0],
[6,0,0,0,0,0,0,0,0],
[7,0,0,0,0,0,0,0,0],
[8,0,0,0,0,0,0,0,0],
[9,0,0,0,0,0,0,0,0]
];
// Make a working copy of the tile set and later try to improve it
for( row=0; row<gridSize; row++ ) {
for( col=0; col<gridSize; col++ ) {
workingTiles[row][col] = freshCopy(tiles[row][col]);
}
}
// Randomly pick a set of tiles to be permuted and/or rotated. ...
// ... Hopefully this modified tile set is closer to a collection of monochromatic closed loops.
pickRow = new Array(PERMUTE_ROTATE_SIZE);
pickCol = new Array(PERMUTE_ROTATE_SIZE);
do {
for( pickSub=0; pickSub<PERMUTE_ROTATE_SIZE; pickSub++ ) {
pickRow[pickSub] = floor(random(gridSize));
pickCol[pickSub] = floor(random(gridSize));
}
// Check for duplicate tile positions
duplicateTiles = false; // So far, no duplicate tiles
for( checkSub_1=0; checkSub_1<PERMUTE_ROTATE_SIZE-1; checkSub_1++ ) {
for( checkSub_2=checkSub_1+1; checkSub_2<PERMUTE_ROTATE_SIZE; checkSub_2++ ) {
if( pickRow[checkSub_1] === pickRow[checkSub_2] &&
pickCol[checkSub_1] === pickCol[checkSub_2] ) {
duplicateTiles = true; // Drats!
}
}
}
} while (duplicateTiles);
// Make random tile permutation of [0 1 2 ... PERMUTE_ROTATE_SIZE-1]
tilePermute = new Array(PERMUTE_ROTATE_SIZE);
for( fillSub=0; fillSub<PERMUTE_ROTATE_SIZE; fillSub++ ) {
tilePermute[fillSub] = fillSub; // Initially the permutation is [0 1 2 ...]
}
// Now, randomize the permutation
for( randSub_1=0; randSub_1<PERMUTE_ROTATE_SIZE-1; randSub_1++ ) {
randSub_2 = randSub_1 + floor( random( PERMUTE_ROTATE_SIZE - randSub_1 ) );
// Swap permutation entries at positions randSub_1 & randSub_2
savePerm = tilePermute[randSub_1];
tilePermute[randSub_1] = tilePermute[randSub_2];
tilePermute[randSub_2] = savePerm;
}
// Permute the picked tiles
for( pickSub=0; pickSub<PERMUTE_ROTATE_SIZE; pickSub++ ) {
workingTiles [pickRow[pickSub]] [pickCol[pickSub]] =
freshCopy(
tiles [pickRow[tilePermute[pickSub]]] [pickCol[tilePermute[pickSub]]]
);
}
// Randomly rotate the picked tiles in a clockwise direction (0, 90, 180 or 270 degrees)
for( pickSub=0; pickSub<PERMUTE_ROTATE_SIZE; pickSub++ ) {
row = pickRow[pickSub];
col = pickCol[pickSub];
numberOf90DegreeRotations = floor(random(4));
for( rotationCtr=1; rotationCtr<=numberOf90DegreeRotations; rotationCtr++ ) {
// Each tile has either 0, 1 or 2 arcs/lines
for( lineTypeSub=0; lineTypeSub < workingTiles[row][col].length; lineTypeSub++ ) {
lineType = workingTiles[row][col][lineTypeSub];
switch (lineType) {
case 1:
newLineType = 2;
break;
case 2:
newLineType = 4;
break;
case 3:
newLineType = 1;
break;
case 4:
newLineType = 3;
break;
case 5:
newLineType = 6;
break;
case 6:
newLineType = 5;
break;
case 11:
newLineType = 12;
break;
case 12:
newLineType = 14;
break;
case 13:
newLineType = 11;
break;
case 14:
newLineType = 13;
break;
case 15:
newLineType = 16;
break;
case 16:
newLineType = 15;
break;
case -1:
newLineType = -2;
break;
case -2:
newLineType = -4;
break;
case -3:
newLineType = -1;
break;
case -4:
newLineType = -3;
break;
case -5:
newLineType = -6;
break;
case -6:
newLineType = -5;
break;
}
workingTiles[row][col][lineTypeSub] = newLineType;
}
}
}
workingScore = evaluateTiles(workingTiles);
// How does new score compare with previous best score?
if( allowIdenticalScore ) {
if( workingScore < bestScore ) {
return(false); // Exit since working tile set is not at least as good as before
}
}
else {
if( workingScore <= bestScore ) {
return(false); // Exit since working tile set is not better arranged
}
}
bestScore = workingScore; // Ta da! We've found a good arrangement of the tile set.
// Update the tile set from the working copy because the working copy has a good tile arrangement
for( row=0; row<gridSize; row++ ) {
for( col=0; col<gridSize; col++ ) {
tiles[row][col] = freshCopy(workingTiles[row][col]);
}
}
return(true); // Tile set is nicely arranged
} // end attemptToInchTowardSolution
function evaluateTiles(tiles) {
// This function determines how well the tile set is solved.
// Create space for edge information for a tile set (up to size 9 x 9). ...
// ... Initially fill with dummy values.
edges = [
[1,2,3,4,5,6,7,8,9],
[2,0,0,0,0,0,0,0,0],
[3,0,0,0,0,0,0,0,0],
[4,0,0,0,0,0,0,0,0],
[5,0,0,0,0,0,0,0,0],
[6,0,0,0,0,0,0,0,0],
[7,0,0,0,0,0,0,0,0],
[8,0,0,0,0,0,0,0,0],
[9,0,0,0,0,0,0,0,0]
];
for( row=0; row<gridSize; row++ ) {
for( col=0; col<gridSize; col++ ) {
edges[row][col] = [0,0,0,0]; // Each tile has 4 edges: top, bottom, left, right
}
}
// Tile edge subscripts
TOP_EDGE = 0;
BOTTOM_EDGE = 1;
LEFT_EDGE = 2;
RIGHT_EDGE = 3;
// Thin, dashed or thick line
NO_LINE = 0;
THIN_LINE = 1;
DASHED_LINE = 2;
THICK_LINE = 3;
// Collect edge information for all tiles
for( row=0; row<gridSize; row++ ) {
for( col=0; col<gridSize; col++ ) {
// Each tile has either 0, 1 or 2 arcs/lines
for( lineTypeSub=0; lineTypeSub < tiles[row][col].length; lineTypeSub++ ) {
lineType = tiles[row][col][lineTypeSub];
if(lineType >= 1) {
if(lineType <= 6) {
thinDashedOrThick = THIN_LINE;
}
else {
thinDashedOrThick = DASHED_LINE;
}
}
else {
thinDashedOrThick = THICK_LINE;
}
switch (abs(lineType)) {
case 1:
case 11:
edges[row][col][LEFT_EDGE] = thinDashedOrThick;
edges[row][col][ TOP_EDGE] = thinDashedOrThick;
break;
case 2:
case 12:
edges[row][col][ TOP_EDGE] = thinDashedOrThick;
edges[row][col][RIGHT_EDGE] = thinDashedOrThick;
break;
case 3:
case 13:
edges[row][col][ LEFT_EDGE] = thinDashedOrThick;
edges[row][col][BOTTOM_EDGE] = thinDashedOrThick;
break;
case 4:
case 14:
edges[row][col][BOTTOM_EDGE] = thinDashedOrThick;
edges[row][col][ RIGHT_EDGE] = thinDashedOrThick;
break;
case 5:
case 15:
edges[row][col][ TOP_EDGE] = thinDashedOrThick;
edges[row][col][BOTTOM_EDGE] = thinDashedOrThick;
break;
case 6:
case 16:
edges[row][col][ LEFT_EDGE] = thinDashedOrThick;
edges[row][col][RIGHT_EDGE] = thinDashedOrThick;
break;
}
}
}
}
// Now use the information in <edges>:
// Do arcs/lines inside grid mismatch in color? If so, decrease <tileScore> a bit.
// Do arcs/lines extend to the edge of the grid? If so, decrease <tileScore> a lot. (more serious)
SMALL_PENALTY = 1;
LARGE_PENALTY = 20;
tileScore = 0;
// For all columns, check top & bottom edges of tiles
for( col=0; col<gridSize; col++ ) {
if( edges[0][col][TOP_EDGE] !== NO_LINE ) {
tileScore -= LARGE_PENALTY;
}
for( row=0; row<gridSize-1; row++ ) {
if( edges[row][col][BOTTOM_EDGE] !== edges[row+1][col][TOP_EDGE] ) {
tileScore -= SMALL_PENALTY;
}
}
if( edges[gridSize-1][col][BOTTOM_EDGE] !== NO_LINE ) {
tileScore -= LARGE_PENALTY;
}
}
// For all rows, check left & right edges of tiles
for( row=0; row<gridSize; row++ ) {
if( edges[row][0][LEFT_EDGE] !== NO_LINE ) {
tileScore -= LARGE_PENALTY;
}
for( col=0; col<gridSize-1; col++ ) {
if( edges[row][col][RIGHT_EDGE] !== edges[row][col+1][LEFT_EDGE] ) {
tileScore -= SMALL_PENALTY;
}
}
if( edges[row][gridSize-1][RIGHT_EDGE] !== NO_LINE ) {
tileScore -= LARGE_PENALTY;
}
}
return(tileScore);
} // end evaluateTiles
function freshCopy(sourceArray) {
// This function makes and returns a duplicate copy of the array called <sourceArray>
freshSize = sourceArray.length;
freshArray = new Array(freshSize);
for(elementSub=0; elementSub<freshSize; elementSub++) {
freshArray[elementSub] = sourceArray[elementSub];
}
return(freshArray);
} // end freshCopy
function randomizeTiles(tiles) {
// This function randomly shuffles the tiles to try to prevent the program ...
// ... from getting stuck during its hill climbing which is designed to improve the tile set.
for( row=0; row<gridSize; row++ ) {
for( col=0; col<gridSize; col++ ) {
randRow = floor(random(gridSize));
randCol = floor(random(gridSize));
saveTile = freshCopy( tiles[ row][ col] );
tiles[ row][ col] = freshCopy( tiles[randRow][randCol] );
tiles[randRow][randCol] = saveTile;
}
}
} // end randomizeTiles
0 comment threads