Hi there everyone,
I’ve just done the Find Your Hat project (which I very much enjoyed) and am now trying to create a path solver to check if the randomly generated grid is solveable. Did a bit of research and decided to try to do a breadth-first search.

I got it to work beautifully if the path could be solved, but if it couldn’t, it would go into a crazy loop and make my computer sound like it was about to explode. I realised this was because it wasn’t correctly logging locations as having been ‘visited’. So, I’m trying to fix this and now running into a problem I just don’t understand. HALP

For some reason that I really can’t understand, when my function to find the neighbors of the space I’m investigating checks that the neighbors are a) within the grid and b) aren’t obstacles (‘x’ in the code I’m trying), it works 4 times perfectly (as I intended) and then for some reason continues and changes the input. I don’t understand why it does this, as there isn’t anything in the code to assign values to anything other than the array that isn’t being checked. I have got as far as my skill takes me with this one; I’ve tried logging everything to the console and checking it and just go “Yep, I know exactly where the problem is but I have no idea why it’s doing that”.

Here’s the code:

``````const area = [
['s', 'x', 'o'],
['o', 'o', 'e'],
['x', 'x', 'o']
];

area.forEach(row => console.log(row.join("  ")));

let start = [];
let end = [];

for (let i = 0; i < area.length; i++){
if (area[i].includes('s')){
start = [i, area[i].indexOf('s')];
};
if (area[i].includes('e')){
end = [i, area[i].indexOf('e')];
};
}

console.log("The start coordinates are " + start);
console.log("The end coordinates are " + end);

// BREADTH-FIRST SEARCH FUNCTION; TAKE A GRID, A START AND AN END POINT (AS A COORDINATE ARRAY [Y, X]) AS ARGUMENTS

// DETERMINE SIZE OF GRID

let width = grid.length;
let height = grid[0].length;

// SET NODE (LOCATION) TO BE THE START NODE TEMPORARILY

let location = [start[0], start[1]];

// CREATE QUEUE FOR UNVISITED NODES

let queue = [];
let visited = [];
let neighbors = [];

// ASSIGN LOCATION (AT FIRST, START NODE) TO THE QUEUE
queue.push(location);

// FIND VIABLE NEIGHBORS (NOT OUT OF AREA OR 'X')
function safeArea(c, r){
console.log("c: " + c);
console.log("r: " + r);
if (c < 0 || c > grid.length ){
console.log("failed test 1");
return false;
};
if ( r < 0 || r > grid[0].length ){
console.log("failed test 2");
return false;
};
if ( grid[c][r] === 'x' ){
console.log("failed test 3");
return false;
};
return true;
};

function findNeighbors(node){
console.log("1");
if (safeArea(node[0]-1, node[1])){
neighbors.push([node[0]-1, node[1]]);
};
console.log("2");
if (safeArea(node[0], node[1]-1)){
neighbors.push([node[0], node[1]-1]);
};
console.log("3");
if (safeArea(node[0]+1, node[1])){
neighbors.push([node[0]+1, node[1]]);
};
console.log("4");
if (safeArea(node[0], node[1]+1)){
neighbors.push([node[0], node[1]+1]);
};
};

while (queue.length){

// TAKE NODE FROM QUEUE; MARK IT AS 'VISITED' AND CHECK IF IT'S THE END POINT (IF SO, RETURN 'TRUE')
let currentLocation = queue.shift();

visited.push(currentLocation);

if (currentLocation[0] === end[0] && currentLocation[1] === end[1]){
return currentLocation;
};

findNeighbors(currentLocation);

for (neighbor in neighbors){
if (!visited.includes(neighbor)){
queue.push(neighbor);
};
};

// IF VIABLE NEIGHBORS ARE NOT VISITED, ADD THEM TO THE QUEUE AND REPEAT FOR EACH

};

// IF THE QUEUE IS EMPTY AND THE END HAS NOT BEEN REACHED, RETURN 'FALSE'
return false;

};

``````

And here’s the output I get from that:

s x o
o o e
x x o
The start coordinates are 0,0
The end coordinates are 1,2
1
c: -1
r: 0
failed test 1
2
c: 0
r: -1
failed test 2
3
c: 1
r: 0
4
c: 0
r: 1
failed test 3
1
c: -1
r: undefined
failed test 1
2
c: 0
r: NaN
3
c: 01
r: undefined
/Users/jon/Documents/coding/training/bfs-test/main.js:58
if ( grid[c][r] === ‘x’ ){
^

TypeError: Cannot read property ‘undefined’ of undefined
at safeArea (/Users/jon/Documents/coding/training/bfs-test/main.js:58:21)
at findNeighbors (/Users/jon/Documents/coding/training/bfs-test/main.js:75:13)
at Object. (/Users/jon/Documents/coding/training/bfs-test/main.js:117:13)
at Function.executeUserEntryPoint [as runMain] (internal/modules/run_main.js:72:12)
at internal/main/run_main_module.js:17:47

It took me some time but I finally managed to find where the problem is. It is actually in the next for loop

``````for (neighbor in neighbors){
if (!visited.includes(neighbor)){
queue.push(neighbor);
};
};
``````

You are trying to loop through every element of the `neighbors` array with a ‘for…in’ loop. This type of `for` syntax doesn’t work for arrays, it is actually a syntax used for objects, as it iterates for every property of an object. For iterating each element of an array, use a ‘for…of’ loop. You only need to change it to the following code for it to work

``````for (neighbor of neighbors){
if (!visited.includes(neighbor)){
queue.push(neighbor);
};
};
``````

Here you can find more information of why using ‘for…in’ loops with arrays shouldn’t be done.

If you found this post helpful and solved your problem or question, don’t forget to assign the post as the solution. This way you could help others who have the same question to find it faster.

1 Like

Hi Diego,

Thanks very much for your help! It ended up being a much bigger problem
than that (I had no idea you couldn’t compare arrays directly (i.e., a =
[1,2] =/= b = [1,2]) and so it all didn’t work even after that bit got
fixed, and I spent probably a couple of hours making this face => °_<),
but now I seem to have got it working! Hooray.