# December 28: Finding paths on a grid in Ruby with recursion

Neither COVID nor a weeklong winter break will stop me from coding, no-sir-ee! This week’s blog post even includes code you can fork and clone for yourself! I’m covering today’s subject, **grid path problems,** because I’ve seen a few solutions on search engines but never one in Ruby. Let’s dive in!

# Background: What’s a grid path problem? Why should we care?

Grid path problems are widely studied in applied mathematics, and software engineers are commonly asked to solve them in job interviews. That’s because they require breaking a complicated problem down into smaller parts, demonstrating a programmer’s computational thinking skills.

There are dozens of variations of the grid path problem (also called the *grid traversal *or *matrix path problem*), all more or less the same in their essence and core. Imagine a little grid, like a miniature version of an ordinary chess board, with the King in the top-left corner. *How do we find the chess King’s shortest path to the bottom right corner?*

Solutions to the grid path problem have numerous profound real-world applications. The most obvious are games played on grids, like chess, checkers, Conquest, Quoridor, or non-western games like Go, Shogi or Chaturanga. But, the grid path problem is also a good proxy for many other non-game domains that can be modeled as matrices with nodes. Navigation apps like Waze, Mapquest and Google Maps model addresses, intersections and freeway exits as nodes on a massive matrix of streets and highways. *(Navigation software does *not* employ the pure naïve recursion I make use of here. Those apps replace a great deal of the recursion that would otherwise be necessary with very sophisticated heuristics, cooked up by very well-paid nerds, for performance reasons that will become clear below. But, the core principle they operate on is essentially the same.)*

# What a human would do

If I were to ask you, dear reader, to find the path a chess King could take between two given squares, you would probably follow a checklist similar to the one below:

- Look at all the current square’s adjacent squares;
- Find all the squares adjacent to each of the current square’s adjacent squares;
- Repeat (i.e., keep finding adjacent squares), excluding squares already in the path, until you’ve arrived at the target destination square.

This is exactly the strategy our code will use to solve the grid path problem. Let’s write it!

# Finding adjacent squares

In the context of this Ruby method, a grid will be represented as an array of row arrays (a* two-dimensional* or *nested* array) like so:

`[ [ "00", "01", "02", "03" ],`

[ "10", "31", "12", "13" ],

[ "20", "21", "22", "23" ],

[ "30", "33", "32", "33" ] ]

Each square can be identified by an array of size 2 in the format `[ row, column ]`

, so for the above array `[ 2, 3 ]`

would represent square `"23"`

.

Now examine the following method, which takes as arguments a `board`

and the `coordinates`

of a square, and returns an array of coordinates of `adjacent_squares`

:

`def adjacent_squares( board, coordinates )`

rows = [ coordinates[ 0 ] - 1, coordinates[ 0 ], coordinates[ 0 ] + 1 ]

columns = [ coordinates[ 1 ] - 1, coordinates[ 1 ], coordinates[ 1 ] + 1 ]

all_adjacent_squares = rows.product( columns )

all_adjacent_squares.select{ | square | square[ 0 ].between?( 0, board.size - 1) && square[ 1 ].between?( 0, board.first.size - 1 ) && square != coordinates }

end

First, we define two arrays (`rows`

and `columns`

), containing the rows above and below and the columns to the left and right, respectively, as well as the current row/column, of the `coordinates`

argument. Then, we use Ruby’s `Array.product( Array )`

method, to produce every possible combination of coordinates from `rows`

and `columns`

:

`[ 0, 1, 2 ].product( [ 1, 2, 3 ] )`

# => [[0, 1], [0, 2], [0, 3], [1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 3]]

Finally, we need to remove the current square’s `coordinates`

from our list of `all_adjacent_squares`

— we don’t want to be running around in circles! We also need to account for squares which are on the edge of the grid; if we don’t, we’ll get `nil`

values and/or some very wacky incorrect coordinates (since `Array[ -1 ]`

in Ruby means the last element of an array). We can remove the current square while handling our edge cases with one long `.select`

enumerable — it isn’t pretty, but it gets the job done!

Note that in our `.select`

enumerable, we access the height and width of our `board`

with `board.size`

and `board.first.size`

respectively. This way, our method will still work on grids of any dimension, even non-square grids or grids with only one row/column.

Note as well that this method produces orthogonally- *and* diagonally-adjacent squares. If we want *only* orthogonally-adjacent (up/down/left/right) squares, without diagonals, we’ll have to make some slight adjustments to our method, like below:

`def orthogonally_adjacent_squares( board, coordinates )`

row = coordinates[ 0 ]

column = coordinates[ 1 ]

all_adjacent_squares = [ [ row - 1, column ], [ row, column + 1 ], [ row + 1, column ], [ row, column - 1 ] ]

all_adjacent_squares.select{ | square | square[ 0 ].between?( 0, board.size - 1) && square[ 1 ].between?( 0, board.first.size - 1 ) }

end

Here in `orthogonally_adjacent_squares`

, we won’t have to remove the current square’s `coordinates`

in the last line because it’s easiest to just hard-code our array of `all_adjacent_squares`

without it.

# Finding all possible paths between two squares with recursion

Now that we have a working method to give us `adjacent_squares`

on a`board`

given a square’s `coordinates`

, we can build a method to produce `all_possible_paths`

. To do this, we’ll write a *recursive* method — a method that calls itself!

** Recursion is absolutely central to computer science and software engineering** because it has so many potential applications. It’s so powerful, in fact, that programming languages exist which

*only*use recursion and have no loops or other flow controls!

The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions.

—Niklaus Wirth

A deep dive into recursion is far, *far *beyond the scope of this blog — to be honest, it’s far beyond the scope of most careers. All I ask, in the context of traversing grids, is that you remember two things…

**Recursion solves a big problem (the**The base case looks the same as the recursive case — just on a smaller scale.*recursive case*) by repeatedly solving an identical but smaller problem (the*base case*).- When using recursion,
**one must**Without reaching a base case, a recursive method will repeat indefinitely, and Ruby will quickly give up and die, gurgling out a*always*specify a base case and make sure your program reaches it.`SystemStackError`

in defeat.

So, with all this in mind, think back to our checklist for humans above: find squares adjacent to the current square, then keep finding adjacent squares not already in the current path until we reach our destination. Sounds familiar, doesn’t it? It’s logical to conclude that:

- Our
**recursive case**is*finding the next set of adjacent squares,*and; - Our
**base case**is either*reaching our destination*or*reaching a duplicate square.*

Now consider the method below, which recursively adds `possible_paths`

to a `path_list`

. It accepts the following arguments:

- a
`board`

- a set of
`current_coordinates`

- the coordinates of a
`destination`

- an array to keep track of the
`path_so_far`

- an array of finished paths called
`path_list`

`def possible_paths( board, current_coordinates, destination, path_so_far, path_list )`

current_square_value = board[ current_coordinates[ 0 ] ][ current_coordinates[ 1 ] ]

if current_coordinates == destination

path_so_far.push( current_square_value )

path_list << path_so_far

else

adjacent_squares( board, current_coordinates ).each do | adjacent_coordinate |

if !path_so_far.include?( current_square_value )

next_possible_path = path_so_far.clone.push( current_square_value )

possible_paths( board, adjacent_coordinate, destination, next_possible_path, path_list )

end

end

end

end

What’s going on here? Let’s examine this method step by step:

- First, we define
`current_square_value`

by getting the value in the`current_coordinates`

of our`board`

; - Next we start an
`if`

statement by checking so see if we’ve arrived at our first base case — i.e., when our`current_coordinates`

are the same as our`destination`

‘s coordinates. If we’ve arrived at our`destination`

, hooray! We dance a jig,`.push`

the`current_square_value`

onto the`path_so_far`

, add the`path_so_far`

to our`path_list`

, and stop recurring; - If we haven’t arrived at our
`destination`

yet, we start enumerating over`.each`

`adjacent_coordinate`

in`adjacent_squares`

. We can stop recurring if a particular`adjacent_coordinate`

leads to a square we’ve already visited (our second base case), so we check for that in`.each`

`adjacent_coordinate`

by asking`if !path_so_far.include?( current_square_value )`

. That way, if our`adjacent_coordinate`

has already been counted in`path_so_far`

, we stop recurring by skipping the recursion block and thus avoid giving Ruby an aneurysm; - Finally, if we haven’t arrived at either base case yet, we need to keep recurring! So, inside our
`.each`

enumerable checking each of our`adjacent_squares`

, we create a new variable called`next_possible_path`

, assign to`next_possible_path`

a`.clone`

of the current path with the`current_square_value`

`.push`

ed onto it, and then recur by calling`possible_paths`

again — this time with our`next_possible_path`

.

Whew! That may seem like pretty heavy lifting, but think of how much work recursion is doing for us. When starting at a corner (`[ 0, 0 ]`

) and ending at the opposite corner (`[ board.size, board.first.size ]`

), this method generates **96,371 unique paths on a four-by-four matrix **and **494,596 paths on a three-by-six matrix**—all** **in just a dozen lines of code. That’s the power of recursion!

# Conclusion: The limitations of recursion

Now that we have a method to generate unique `possible_paths`

, finding the shortest is a piece of cake. All we have to do is create a `path_list`

array, populate it with paths using the `possible_paths`

method we just wrote, sort it by `.size`

, and return the `.first`

(the shortest):

`def shortest_path( board, start_coordinates, end_coordinates )`

path_list = []

possible_paths( board, start_coordinates, end_coordinates, [], path_list)

path_list.sort_by( &:size ).first

end

It’s also very easy to re-factor the above methods to solve other grid path problems. We can, for example, change our base case in `possible_paths`

so that we only find paths of a certain `.length`

. Or imagine that some of the squares on our chess board are hot lava and thus impassable — we can change our `adjacent_squares`

method to make certain squares off-limits.

We’ve seen that recursion is incredibly powerful, but that power creates one *huge *drawback: **recursion can create very big instances.** *Exponentially *big, as a matter of fact. See for yourself: recursion in Ruby is manageably quick when traversing matrices with about 20 nodes or so, but for larger grids, grab a snack and get comfortable because you’ll be waiting a good long while. Ruby is especially vulnerable to this because of how it manages its stack, and because its function calls are relatively slow. The difference is less noticeable in languages like Lisp or C, but even then your computer will slow to a crawl and get sizzling hot because it’ll be sucking up more battery power than a Sega Nomad.

In conclusion: recursion is incredibly useful, but **consider your base case and the size of the data you’re iterating over.** Balance your needs and the scale of the problem you’re solving with the limitations of your language and your hardware. When unleashing the power of recursion, remember the wise words of Ruby Spiderman: `great_power.eq?( great_responsibility )`

!