Weekly Programming Challenge #3

Finding Solutions to Mazes

I know, I know. You were probably wondering how long until I brought mazes into this. I can’t help it! Mazes are my go-to for exploration and recreational programming. We’ll get to this week’s challenge in a moment. First, let’s recap last week:

Recap: Challenge #2

Maybe it was just grammars that were intimidating? Or maybe last week was especially busy? I don’t know. But only two people submitted solutions:

1. Alejandro Perea, whose normal mode submission was almost a hard mode submission. All he lacked was a second grammar file! Check out his solution (in Ruby) here: https://github.com/aeperea/programming-challenges/tree/master/02-grammar
2. Lasse Ebert, who submitted a normal mode solution in Elixir! Check it out here: https://github.com/lasseebert/jamis_challenge/tree/master/002_grammar

I was originally going to do a normal mode solution myself, but couldn’t stop thinking about an EBNF grammar parser… so I wound up implementing a hard mode solution, here.

Good work, everyone!

Programming Challenge #3

This challenge isn’t about generating mazes. It’s about solving them. You may already know a few ways to solve mazes — that’s great! You’re ahead of the game. If you’re at a loss, though, Wikipedia has an entire article on it. I won’t go into any detail on them here, since part of the fun of this challenge will be digging into and learning about some of the different techniques involved.

All I’ll give you is a bunch of files, each of which represents a maze. A hash sign “#” represents a wall, and a space represents a passage. An “O” character tells you where the starting point is, and an “X” marks the exit.

Your program must accept any such file as input, and emit the corresponding solution. The details, of course, determine the difference between normal, hard, and “surprise me”…

Normal Mode

For normal mode, your program is only required to be able to solve “perfect” or “simply-connected” mazes — those whose passages do not self-intersect, or form loops. Your program may assume that any file it receives will describe such a maze.

Your output must consist of a series of steps that describe the path to the exit. Each line of output must be either “north”, “south”, “east”, or “west”, indicating which direction must be moved at that point in the solution. At the end, it must tell how many steps were required to solve the maze.

North always points toward the first line of the file, south toward the last. West points toward the first column, east toward the last.

The solution must be the shortest possible solution — that is to say, it must not include any backtracking.

For example, suppose your program received the following simple maze as input:

#######
O   # #
### # #
#   # #
# ### #
#     X
#######

Your output, describing the path from “O” to “X”, would be:

east
east
east
south
south
west
west
south
south
east
east
east
east
east
14 steps

You may produce additional output if you desire, but the solution as described above must be included.

A zip file containing ten mazes of different sizes may be downloaded here (maze-normal.zip, 2.6kB).

Hard Mode

If you want an additional challenge, consider hard mode! Your program must do all that normal mode does, but it also must support multiply-connected, or “braided” mazes. That is, you must support mazes with multiple solutions, and be able to return a shortest solution.

The output should be the same, but again, you may include additional output (of any sort) that you want.

The files from normal mode may be used to test your program, as well as this file (maze-hard.zip, 2.9kB) containing ten braided mazes for use specifically with hard mode.

Surprise Me!

If none of that seems sufficiently challenging, add your own constraints! Sprinkle it all with a bit of creativity and see what you come up with. To meet this level of difficulty, the code itself doesn’t need to be viciously complicated, but the implementation or its output should do something unexpected and surprising.

This challenge will run until Saturday, August 20th, at 12:00 MDT (18:00 UTC).

Submissions are closed for this challenge, but feel free to give it a try anyway! The comments will remain open, so if you’ve got something you’d like to share, please post a link below. If nothing else, check out the next weekly programming challenge!