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

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

Chess board of ebony inlaid with ivory from the Mughal Empire, 16th century (Photo credit: Metropolitan Museum of Art)

What a human would do

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

Finding adjacent squares

[ [ "00", "01", "02", "03" ],
[ "10", "31", "12", "13" ],
[ "20", "21", "22", "23" ],
[ "30", "33", "32", "33" ] ]
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
[ 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]]
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

Finding all possible paths between two squares with recursion

A matryoshka doll is an example of aesthetic recursion: Each doll contains smaller versions of itself (Photo credit: Wikimedia Foundation)
  1. Recursion solves a big problem (the recursive case) by repeatedly solving an identical but smaller problem (the base case). The base case looks the same as the recursive case — just on a smaller scale.
  2. When using recursion, one must always specify a base case and make sure your program reaches it. Without reaching a base case, a recursive method will repeat indefinitely, and Ruby will quickly give up and die, gurgling out a SystemStackError in defeat.
  • 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.
  • 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
  1. First, we define current_square_value by getting the value in the current_coordinates of our board;
  2. 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;
  3. 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;
  4. 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 .pushed onto it, and then recur by calling possible_paths again — this time with our next_possible_path.

Conclusion: The limitations of recursion

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

--

--

--

Oh geez, Josh Frank decided to go to Flatiron? He must be insane…

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

If You Are Python Programmer Then This Should Worry You!.

Finding and Deleting in Binary Trees

Open to Change

My first six months with Plutus

List of File Formats !!! Explained

Is investing in automation testing worth it for organizations?

How to create Subdomain and Addon domain on hosting using cPanel

Mortgage Fraud Attorney

mortgage fraud attorney

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Josh Frank

Josh Frank

Oh geez, Josh Frank decided to go to Flatiron? He must be insane…

More from Medium

Programming Threads as your friends.

“No problem can withstand the assault of sustained thinking.” — Voltaire

Phase-3 At FlatIron School!