I’ve recently been attending rogue.rb meetups. At the last few meetups, we’ve been playing with writing a maze solver, an exercise taken from the Ruby Programming Challenge For Newbies series.

I missed the first meetup where the group started on the challenge, but made it to the second. At that point, there was code for parsing the maze and some helper classes for various parts, but no work yet on solving the maze.

As I thought about the problem, I realized that solving mazes is really just a graph traversal problem. At first, I thought of using a recursive depth-first search algorithm, but then realized that a breadth-first search algorithm would be better, because it would find the shortest solution automatically.

No one there that night had heard of these algorithms, so I explained them and we decided to spike an implementation. It worked well, but we ran out of time that night to do a proper solution.

The problem intrigued me, and I couldn’t leave it alone, so I created a branch, deleted the existing code, and started over from scratch. I could have forked, but I wanted to leave the code under roguerb for others to see and play with.

In my experiment, I had a few goals:

  1. Continue learning RSpec.
  2. Solve the problem completely without introducing a bunch of classes. I normally have a pretty low threshold for introducing a new class, and I wanted to hold off a bit.
  3. Try to test-drive the algorithm.

At the next meetup, we walked through my branch and discussed some of the decisions I’d made and the tradeoffs. I found it a really interesting and helpful discussion. In the end, the group decided to merge my branch into the trunk and we added a command-line script to solve a maze in a file or piped in on standard input.

Since then, I did a bit more work to clean up some of the specs I wasn’t happy with and to add the ability to overlay the solution onto the maze as part of the output from the command-line runner.

The code is on GitHub. You can work through the commit history, starting from here to see what I did with it.

Overall, I’m pretty happy with how everything turned out. I’m particularly pleased with how the core of the solving algorithm looks:

Maze Solving Algorithm
class Solver

  # ...

 
  def solve(maze)

    enqueue(Path.new(maze.starting_cell))

 
    while !done? do

      path = next_path

      return path if path.complete?

 
      path.successors.each { |new_path| enqueue(new_path) }

    end

 
    Path.new

  end

 
  #...

end

How did I do on my goals?

I definitely know RSpec better than I did, but I’m not sure I’m using it as well as I could be.

By the time I introduced the Cell and Path classes, the code was crying out for them, in my opinion, so I think I did pretty well on that goal.

I’m somewhat happy with how I test-drove the algorithm. I started out by solving mazes that could be solved with only a single step. That let me flesh out the concept of neighbors and the stopping condition. The easiest transformation from there seemed to be the recursive depth-first solution, so I went there next. That forced me to deal with already-visited cells and the repetition of navigating from cell to cell. I then wrote a test that caused the recursive algorithm to find a longer-than-optimal path. At that point, I had two choices:

  1. Modify the algorithm to collect all possible solutions and then choose the shortest.

  2. Switch to the breadth-first algorithm.

I chose the latter, as I thought it was a better solution. I don’t feel like the specs drove me to evolve the algorithm, but that’s probably because I already had a well-known algorithm in mind when I started.

I’d really appreciate comments from others about what I could do better. Could I be using RSpec more idiomatically? Did I take the solution in a good direction? Any improvements that could be made? Was it worth the cost of making cells know about their maze?