This is an online exercise that I am trying to understand the solution to.
The question is:
Given the image below (a multidimensional array) the 0 values act as a pipe and the 1 values act as cement. I need to write code to determine if the "pipe" extends from the top of the first array(you can say this is an "opening" of a pipe) to the bottom of the last array.
const arr = [ [0, 0, 0, 0, 1], [0, 0, 1, 0, 0], [0, 0, 0, 1, 0], [1, 1, 1, 1, 0], [1, 0, 1, 1, 0], ]The code you write for the above array would output "true" because the 0 values form the following pattern (replace with the asterisk):
const arr = [ [0, 0, 0, *, 1], [0, 0, 1, *, *], [0, 0, 0, 1, *], [1, 1, 1, 1, *], [1, 0, 1, 1, *], ]
In my head I visualize this problem as one where I would create a pointer to move through the arrays. If the rules only required the coder to work with a single 0 per array the problem would be easy to solve. Being that there are multiple dead ends is where my mind turns to mush. I assume there is an easier way to look at this problem that thinking in loops. I know that this can be mathemetized but I am not exactly a math person.
My remedial though process is to simply create a collection of functions such as:
checkSurroundingValues()
goForward()
goBackward()
goLeft()
goDOwn()
goUp()
etc , but doing it this way evolves into an over complicated mess. I figure there are a few tricks to visualize how to complete this problem. I want to understand "the trick" and thought process clearly.
I feel like the way to go is to write code that follows each "zero" and effectively spawns off a new "crawler" to follow each trail but I have no idea how to write that. :)
doing it this way evolves into an over complicated mess
It's more repetitive than you need, but not by that much.
First make a Set or array of indicies visited so far, eg 1_2 corresponds to having visited arr[1][2]. Make a recursive function that:
Checks to see if the position being iterated over has been visited yet. If so, return
Checks to see if the position being iterated over has a 1 or 0. If 1, return.
Checks to see if the position being iterated over has the maximum x index (in which case you're at the bottom); return true
Call the function recursively with all four surrounding squares: (0, 1), (1, 0), (0, -1), (-1, 0). If any of the recursive calls return true, return true. Should be as simple as
return [
recuse(x + 1, y),
recuse(x - 1, y),
recuse(x, y + 1),
recuse(x, y - 1),
].some(Boolean);
To start out the recursion, call the function for all top elements at index 0 in the input array.
There are a number of things you have to do to put it together, but it's a pretty simple algorithm.