Water pipe coding exercise. How do I visualize solving this problem

user_1152980 0
Viewed 80

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. :)

path-finding arrays javascript
1 Answers

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.

user_95152070
Related