Breadth-First Search in Ruby

It’s Advent of Code season.

My favourite archetype of programming puzzle is probably Breadth-first Search. I wanted to share how I like to write BFS in Ruby, using only built-in features. I usually end up writing something like this from scratch each time it’s needed (nothing wrong with copy-paste, but I find it easy enough and it allows adding any special requirements of the problem).

To avoid spoilers I’ll use a made up problem.

Let’s say we’re given a maze, and we want to find how many steps it takes to get from the entrance to the exit. Let’s assume we’re given coordinates for both.

Breadth first search starts at one position, and explores all adjacent positions before moving on. Then it will explore the positions adjacent to those adjacent positions, et cetera. It explores all positions at a given distance, before exploring the positions at that distance + 1.

Here’s how I might write this, which added comments:

require "set" # In Ruby 3.2+ we don't need to `require "set"` anymore 🎉

# 4 cardinal directions, for convenience
DIRS = [[0, 1], [0,-1], [1, 0], [-1, 0]]

def bfs(map, start, target)
  width, height = map[0].size, map.size

  # We use a visited list so that we check each location only once
  # Without this we'd revisit the same locations multiple times and our
  # queue would be very large.
  visited = Set.new

  # The "trick" to my approach that I wanted to share is that my queue is two
  # arrays, "queue" and "next_queue", which allow us to track our steps without
  # extra work.
  # We will be reading each item from "queue" to get our "current" location,
  # and pushing the next steps onto "next_queue".
  # We start with our queue only including the initial position.
  queue = [start]
  next_queue = []

  steps = 0

  while !queue.empty?
    # Loop over each item in queue
    queue.each do |pos|
      x, y = pos

      # Have we already visited this position? If so, skip it
      next if visited.include?(pos)
      visited.add(pos)

      # Is this a "wall" in the maze? If so, skip it
      next if map[y][x] == "#"

      # Have we reached our target? If so, return how many steps we've taken
      return steps if target == pos

      # Try to take another step in each cardinal direction
      DIRS.each do |(dx, dy)|
        nx, ny = x + dx, y + dy

        # Check that our next step is in bounds
        next if nx < 0 || ny < 0
        next if nx >= width || ny >= height

        # Add our next step to next_queue. There may be duplicates, but we'll
        # sort that out with the visited list when we see it.
        # Keep in mind we'll process everything in "queue" before we start
        # looking at "next_queue".
        next_queue << [nx, ny]
      end
    end

    # Here's where we swap the queues, we start processing what was next_queue,
    # and replace next_queue with a new empty queue.
    queue, next_queue = next_queue, queue.clear

    # Because we process all of queue before next_queue, and this is a BFS, we
    # are looking at our steps in order. As we swap the queues, we increment
    # the steps.
    steps += 1
  end

  # If we get here... the maze is unsolvable :(
end

p bfs(<<~MAP.lines(chomp: true), [0,0], [4,4])
.#...
.#.#.
.#...
.#.#.
...#.
MAP

One thing I like about BFS/DFS (Depth-First Search) is that they’re pretty intuitive: if you sat down with no knowledge of them, and attempted to write a program to solve a maze, you’d probably either writing BFS (if using a queue), or DFS (if using recursion or a stack).

This pattern is most obvious for mazes or grid-search type problems, but the nodes this visits can be any type of state. More difficult problems tend to be a bit more abstract in the relation between the problem statement and a searchable graph.

Happy hacking!