The code in the Stack Snippet is meant to work as follows:
propagateChanges, has reached will be logged to the console at intervals. It should never exceed 4, as this is the greatest number of steps the algorithm should have to perform in order for the map to reach a stable configuration. (This means that all tiles will have either reached a value of 4 or else be within 4 steps of a 'center' (number value = 0) tile.)Instead, when I click the top rightmost cell in the table, the algorithm seems to produce the correct result. The map (which is represented by the HTML table) appears visually correct, meaning all tile numbers resolve to the final values which they are expected and intended to have.
But, recursive calls keep on being generated from within the for loop at the bottom of propagateChanges, even after the map appears to have reached the final, stable configuration.
I have a conditional statement around the recursive step, which ensures that each tile being evaluated:
The second condition, I believe, should keep the algorithm from creating "cycles" where neighboring tiles generate recursive calls back and forth between each other.
So, what is going wrong here? Obviously, I must be missing a base case somehow, since infinite recursion is happening, but after looking over the code multiple times I still don't see what it is.
const rows = document.getElementsByTagName('tr');
var tiles = [];
for (var r = 0; r < rows.length; r++) {
tiles[r] = [];
for (var c = 0; c < rows[r].cells.length; c++) {
// Store table cell's row and column indices, along with the cell itself, to simplify later accesses
tiles[r][c] = {
r: r,
c: c,
tile: rows[r].cells[c]
};
}
}
// Helper function: avoid out-of-bounds errors when accessing array elements by returning a table cell only if its indices exist in the 'tiles' array
function getTile(r, c) {
if (r > -1 && r < 4 && c > -1 && c < 5) {
return tiles[r][c];
}
}
// If the current tile is NOT within 4 steps of any centers (i.e. tiles numbered 0), increase its number by 1 until it reaches the maximum value of 4. Then do the same for each neighboring tile, after a 1-second delay.
// Eventually, after a *maximum* of 4 iterations, the grid should stabilize, meaning all numbers should have reached their final values.
// All tiles will either have value 4, or else be within 4 steps of a center tile (numbered 0), in which case their values will NOT increase.
function propagateChanges(currentTile, R, C, depth) {
var rDist = Math.abs(currentTile.r - R);
var cDist = Math.abs(currentTile.c - C);
if (depth > maxDepth) {
maxDepth = depth;
}
if (depth > 4) {
overflowed = true;
return;
} else if (rDist < 3 && cDist < 3 && (rDist + cDist < 3)) {
var val = Number(currentTile.tile.textContent);
// Somehow, this function got called on a tile with value <= 0 or >= 4. This shouldn't happen: exit without performing any recursive steps.
if (val >= 4 || val <= 0) {
return;
} else {
var centerCoords = isCenterWithin4Tiles(currentTile.r, currentTile.c);
const adjacents = [getTile(currentTile.r - 1, currentTile.c), getTile(currentTile.r + 1, currentTile.c), getTile(currentTile.r, currentTile.c - 1), getTile(currentTile.r, currentTile.c + 1)];
// Don't increase the tile's number value if there's a center nearby (i.e. within 4 steps)
if (!centerCoords) {
currentTile.tile.textContent = val + 1;
// Perform recursive call on original block after 1 second delay
setTimeout(function() {
propagateChanges(currentTile, R, C, depth + 1);
}, 1000);
}
// Recursive calls on the 4 adjacent tiles
// Only proceed in a given direction if either no nearby centers were found, or else the adjacent tile in that direction will be further from any/all centers than currentTile is (in either the row [r] or column [c] direction).
// Not being able to move back in the direction of a center is intended to prevent an infinite cycle of recursive calls from being generated.
for (let i = 0; i < adjacents.length; i++) {
if (adjacents[i] !== undefined) {
let adjVal = Number(adjacents[i].tile.textContent);
if (adjVal < 4 && adjVal > 0 && (!centerCoords || isFurtherFromAll(adjacents[i], currentTile, centerCoords))) {
/* THIS IS WHERE THE PROBLEM OCCURS */
setTimeout(function() {
propagateChanges(adjacents[i], R, C, depth + 1);
}, 1000);
}
}
}
}
}
}
// Find the lowest numbered tile within 4 steps of the origin (i.e. the tile the user clicked), and invoke the propagateChanges function on it IF it is not a true center (which are numbered 0)
function locateCenter(currentTile, R, C, depth) {
if (depth > maxDepth) {
maxDepth = depth;
}
if (depth > 4) {
overflowed = true;
return;
} else {
const val = Number(currentTile.tile.textContent);
var rDist = Math.abs(currentTile.r - R);
var cDist = Math.abs(currentTile.c - C);
// If a center is encountered, do not continue. Don't check any tiles that are more than 4 steps away from the origin coordinates.
if (val > 0 && (rDist < 4 && cDist < 4 && (rDist + cDist < 4))) {
const adjacents = [getTile(currentTile.r - 1, currentTile.c), getTile(currentTile.r + 1, currentTile.c), getTile(currentTile.r, currentTile.c - 1), getTile(currentTile.r, currentTile.c + 1)];
var hasLowerNumberedNeighbor = false;
var adjVal;
for (let i = 0; i < adjacents.length; i++) {
if (adjacents[i] !== undefined) {
adjVal = Number(adjacents[i].tile.textContent);
// Encountered a center within 4 steps of the origin: do not continue.
if (adjVal == 0) {
return;
}
// Encountered neighboring tile with value less than that of the current tile, and < 4: perform *instant* recursive step horizontally and update boolean.
// USE <, NOT <=, or else it will be an infinite cycle!
else if (adjVal < 4 && adjVal < val) {
hasLowerNumberedNeighbor = true;
locateCenter(adjacents[i], R, C, depth + 1);
}
}
}
// If no adjacent tile has a lower number, then currentTile must be cut off from all centers.
if (!hasLowerNumberedNeighbor) {
// The current tile should begin counting up to 4, and propagate changes outward to its neighbors
propagateChanges(currentTile, currentTile.r, currentTile.c, 0);
}
}
}
}
/* Return type of this function will vary. If any centers (tile value == 0) are located within the specified distance, it will return an array of objects containing their x and z coordinates.
(This evaluates to *true* in conditional statements.) Otherwise, it will return false. */
function isCenterWithin4Tiles(r, c) {
var coords = [];
for (var rAway = -3; rAway < 4; rAway++) {
for (var cAway = -3; cAway < 4; cAway++) {
if ((Math.abs(rAway) + Math.abs(cAway) < 4) && ((r + rAway) > -1 && (c + cAway) > -1 && (r + rAway) < 4 && (c + cAway) < 5)) {
const val = tiles[r + rAway][c + cAway].tile.textContent;
if (val == 0) {
coords.push({
r: r + rAway,
c: c + cAway
});
}
}
}
}
return (coords.length) ? coords : false;
}
// Returns true if the coordinates for 'next' are further from ALL centers (i.e., coordinate pairs in the 'comparisons' array) than are the coordinates for 'current', and false otherwise.
function isFurtherFromAll(next, current, comparisons) {
var compared = {};
for (var i = 0; i < comparisons.length; i++) {
// 'next' is further than 'current' from the center in a given direction: Value for that direction will be *positive*.
// 'next' and 'current' are an equal distance from the center: Value will be *0*.
// 'next' is closer to center than current: Value will be *negative*.
compared.r = Math.abs(next.r - comparisons[i].r) - Math.abs(current.r - comparisons[i].r);
compared.c = Math.abs(next.c - comparisons[i].c) - Math.abs(current.c - comparisons[i].c);
// If 'next' is closer than 'current' to the source *in either direction*, OR 'next' is *not* further than 'current' in *at least one* direction, return false
if ((compared.r < 0) || (compared.c < 0) || (compared.r + compared.c === 0)) {
return false;
}
}
return true;
}
// Limit max recursion depth to 4, as the function reaching a greater depth than this indicates the algorithm will never terminate
var maxDepth = 0;
var overflowed = false; // If this becomes true, the function will exit without generating further recursive calls.
function progressReport() {
console.log("Maximum depth reached in recursive function: " + maxDepth);
if (overflowed) {
console.warn("OVERFLOW");
} else {
setTimeout(progressReport, 3000); // Every 3 seconds
}
}
progressReport();
// When the tile in the top right corner is clicked, set its number to the max value (4) and invoke the incrementation algorithm on it
var clicked = false;
document.getElementById("clickHere").addEventListener('click', function() {
if (!clicked) {
clicked = true;
tiles[0][4].tile.textContent = 4;
locateCenter(tiles[0][4], 0, 4, 0);
}
});table {
font-size: 18px;
}
table {
td {
width: 20px;
height: 20px;
}
}<body>
<table>
<tr>
<td>2</td>
<td>2</td>
<td>2</td>
<td>1</td>
<td id="clickHere">0</td>
</tr>
<tr>
<td>1</td>
<td>1</td>
<td>2</td>
<td>2</td>
<td>1</td>
</tr>
<tr>
<td>0</td>
<td>0</td>
<td>1</td>
<td>2</td>
<td>2</td>
</tr>
<tr>
<td>0</td>
<td>0</td>
<td>1</td>
<td>2</td>
<td>3</td>
</tr>
</table>
</body>The problem with the code in your question has to do with how you're defining "within 4 steps of a 'center' tile".
It seems like once you arrive at a tile, you only want to perform recursive calls on each neighboring tile if neither the current nor the neighboring tile are within 4 steps of any 'center' (value = 0) tiles.
This must be the intent, because you have specified you don't want tiles' numbers to decrease if they are within 4 blocks of a 'center', and, once it has been determined that no further changes will be made to a given tile's number value, there is no reason to invoke the recursive function on that tile.
As it currently stands, your conditional statement:
if (adjVal < 4 && adjVal > 0 && (!centerCoords || isFurtherFromAll(adjacents[i], currentTile, centerCoords))) {
is only checking for center tiles being within 4 steps of the current tile, and no check is being performed for proximity of a 'center' to the adjacent tile.
This means that a tile at the very edge of the region surrounding a 'center' will be 3 steps away from the center, while the next adjacent tile will be 4 steps away (causing isFurtherFromAll(adjacents[i], currentTile, centerCoords) to evaluate to true, since 4 > 3). So, there is a mismatch between the value of your conditional statement and whether you intend for the recursive call on adjacents[i] to actually be performed. The recursion should not actually happen, because the adjacent tile is 4 steps from any/all centers, but this is never actually checked!
Adding an additional check for the adjacent tile being within 4 steps of any centers fixes the problem.
So, the conditional statement around the recursive call within the loop should actually be:
if (adjVal < 4 && adjVal > 0 && ((!centerCoords || isFurtherFromAll(adjacents[i], currentTile, centerCoords)) && (!adjCenterCoords || isFurtherFromAll(adjacents[i], currentTile, adjCenterCoords)))) {
Complete (working) code:
const rows = document.getElementsByTagName('tr');
var tiles = [];
for (var r = 0; r < rows.length; r++) {
tiles[r] = [];
for (var c = 0; c < rows[r].cells.length; c++) {
// Store table cell's row and column indices, along with the cell itself, to simplify later accesses
tiles[r][c] = {
r: r,
c: c,
tile: rows[r].cells[c]
};
}
}
// Helper function: avoid out-of-bounds errors when accessing array elements by returning a table cell only if its indices exist in the 'tiles' array
function getTile(r, c) {
if (r > -1 && r < 4 && c > -1 && c < 5) {
return tiles[r][c];
}
}
// If the current tile is NOT within 4 steps of any centers (i.e. tiles numbered 0), increase its number by 1 until it reaches the maximum value of 4. Then do the same for each neighboring tile, after a 1-second delay.
// Eventually, after a *maximum* of 4 iterations, the grid should stabilize, meaning all numbers should have reached their final values.
// All tiles will either have value 4, or else be within 4 steps of a center tile (numbered 0), in which case their values will NOT increase.
function propagateChanges(currentTile, R, C, depth) {
var rDist = Math.abs(currentTile.r - R);
var cDist = Math.abs(currentTile.c - C);
if (depth > maxDepth) {
maxDepth = depth;
}
if (depth > 4) {
overflowed = true;
return;
} else if (rDist < 3 && cDist < 3 && (rDist + cDist < 3)) {
var val = Number(currentTile.tile.textContent);
// Somehow, this function got called on a tile with value <= 0 or >= 4. This shouldn't happen: exit without performing any recursive steps.
if (val >= 4 || val <= 0) {
return;
} else {
var centerCoords = isCenterWithin4Tiles(currentTile.r, currentTile.c);
var adjCenterCoords; // Will be used to test whether each tile adjacent to the current one is near a center, inside the loop at the end of this function
const adjacents = [getTile(currentTile.r - 1, currentTile.c), getTile(currentTile.r + 1, currentTile.c), getTile(currentTile.r, currentTile.c - 1), getTile(currentTile.r, currentTile.c + 1)];
// Don't increase the tile's number value if there's a center nearby (i.e. within 4 steps)
if (!centerCoords) {
currentTile.tile.textContent = val + 1;
// Perform recursive call on original block after 1 second delay
setTimeout(function() {
propagateChanges(currentTile, R, C, depth + 1);
}, 1000);
}
// Recursive calls on the 4 adjacent tiles
// Only proceed in a given direction if either no nearby centers were found, or else the adjacent tile in that direction will be further from any/all centers than currentTile is (in either the row [r] or column [c] direction).
// Not being able to move back in the direction of a center is intended to prevent an infinite cycle of recursive calls from being generated.
for (let i = 0; i < adjacents.length; i++) {
if (adjacents[i] !== undefined) {
let adjVal = Number(adjacents[i].tile.textContent);
adjCenterCoords = isCenterWithin4Tiles(adjacents[i].r, adjacents[i].c);
// This time, ensure the adjacent tile is further NOT ONLY from any center tiles near *currentTile*, BUT ALSO from any centers near *itself*!
if (adjVal < 4 && adjVal > 0 && ((!centerCoords || isFurtherFromAll(adjacents[i], currentTile, centerCoords)) && (!adjCenterCoords || isFurtherFromAll(adjacents[i], currentTile, adjCenterCoords)))) {
/* WITH THE EXTRA CONDITION, THIS WILL NO LONGER GENERATE INFINITE BACK-AND-FORTH CYCLES BETWEEN ADJACENT TILES */
setTimeout(function() {
propagateChanges(adjacents[i], R, C, depth + 1);
}, 1000);
}
}
}
}
}
}
// Find the lowest numbered tile within 4 steps of the origin (i.e. the tile the user clicked), and invoke the propagateChanges function on it IF it is not a true center (which are numbered 0)
function locateCenter(currentTile, R, C, depth) {
if (depth > maxDepth) {
maxDepth = depth;
}
if (depth > 4) {
overflowed = true;
return;
} else {
const val = Number(currentTile.tile.textContent);
var rDist = Math.abs(currentTile.r - R);
var cDist = Math.abs(currentTile.c - C);
// If a center is encountered, do not continue. Don't check any tiles that are more than 4 steps away from the origin coordinates.
if (val > 0 && (rDist < 4 && cDist < 4 && (rDist + cDist < 4))) {
const adjacents = [getTile(currentTile.r - 1, currentTile.c), getTile(currentTile.r + 1, currentTile.c), getTile(currentTile.r, currentTile.c - 1), getTile(currentTile.r, currentTile.c + 1)];
var hasLowerNumberedNeighbor = false;
var adjVal;
for (let i = 0; i < adjacents.length; i++) {
if (adjacents[i] !== undefined) {
adjVal = Number(adjacents[i].tile.textContent);
// Encountered a center within 4 steps of the origin: do not continue.
if (adjVal == 0) {
return;
}
// Encountered neighboring tile with value less than that of the current tile, and < 4: perform *instant* recursive step horizontally and update boolean.
// USE <, NOT <=, or else it will be an infinite cycle!
else if (adjVal < 4 && adjVal < val) {
hasLowerNumberedNeighbor = true;
locateCenter(adjacents[i], R, C, depth + 1);
}
}
}
// If no adjacent tile has a lower number, then currentTile must be cut off from all centers.
if (!hasLowerNumberedNeighbor) {
// The current tile should begin counting up to 4, and propagate changes outward to its neighbors
propagateChanges(currentTile, currentTile.r, currentTile.c, 0);
}
}
}
}
/* Return type of this function will vary. If any centers (tile value == 0) are located within the specified distance, it will return an array of objects containing their x and z coordinates.
(This evaluates to *true* in conditional statements.) Otherwise, it will return false. */
function isCenterWithin4Tiles(r, c) {
var coords = [];
for (var rAway = -3; rAway < 4; rAway++) {
for (var cAway = -3; cAway < 4; cAway++) {
if ((Math.abs(rAway) + Math.abs(cAway) < 4) && ((r + rAway) > -1 && (c + cAway) > -1 && (r + rAway) < 4 && (c + cAway) < 5)) {
const val = tiles[r + rAway][c + cAway].tile.textContent;
if (val == 0) {
coords.push({
r: r + rAway,
c: c + cAway
});
}
}
}
}
return (coords.length) ? coords : false;
}
// Returns true if the coordinates for 'next' are further from ALL centers (i.e., coordinate pairs in the 'comparisons' array) than are the coordinates for 'current', and false otherwise.
function isFurtherFromAll(next, current, comparisons) {
var compared = {};
for (var i = 0; i < comparisons.length; i++) {
// 'next' is further than 'current' from the center in a given direction: Value for that direction will be *positive*.
// 'next' and 'current' are an equal distance from the center: Value will be *0*.
// 'next' is closer to center than current: Value will be *negative*.
compared.r = Math.abs(next.r - comparisons[i].r) - Math.abs(current.r - comparisons[i].r);
compared.c = Math.abs(next.c - comparisons[i].c) - Math.abs(current.c - comparisons[i].c);
// If 'next' is closer than 'current' to the source *in either direction*, OR 'next' is *not* further than 'current' in *at least one* direction, return false
if ((compared.r < 0) || (compared.c < 0) || (compared.r + compared.c === 0)) {
return false;
}
}
return true;
}
// Limit max recursion depth to 4, as the function reaching a greater depth than this indicates the algorithm will never terminate
var maxDepth = 0;
var overflowed = false; // If this becomes true, the function will exit without generating further recursive calls.
function progressReport() {
console.log("Maximum depth reached in recursive function: " + maxDepth);
if (overflowed) {
console.warn("OVERFLOW");
} else {
setTimeout(progressReport, 3000); // Every 3 seconds
}
}
progressReport();
// When the tile in the top right corner is clicked, set its number to the max value (4) and invoke the incrementation algorithm on it
var clicked = false;
document.getElementById("clickHere").addEventListener('click', function() {
if (!clicked) {
clicked = true;
tiles[0][4].tile.textContent = 4;
locateCenter(tiles[0][4], 0, 4, 0);
}
});table {
font-size: 18px;
}
table {
td {
width: 20px;
height: 20px;
}
}<body>
<table>
<tr>
<td>2</td>
<td>2</td>
<td>2</td>
<td>1</td>
<td id="clickHere">0</td>
</tr>
<tr>
<td>1</td>
<td>1</td>
<td>2</td>
<td>2</td>
<td>1</td>
</tr>
<tr>
<td>0</td>
<td>0</td>
<td>1</td>
<td>2</td>
<td>2</td>
</tr>
<tr>
<td>0</td>
<td>0</td>
<td>1</td>
<td>2</td>
<td>3</td>
</tr>
</table>
</body>