Tag Archives: Algorithms

Solving Mushroom Man 113 with Dynamic Programming

Here’s something that might sound strange. Today, while playing the retro puzzle game “Mushroom Man” — a great throwback to “Chip’s Challenge” — I noticed how similar one of the levels was to solving a programming contest question. In level 113 “Don’t Drink the Water,” there is a large number of water tiles and only a limited amount of oxygen available to cross those tiles. At one point, I found myself on a spot where all paths left me exactly 1 oxygen short. Eventually, I needed to work backwards, counting the tiles to look for a solution. The shape of the level — a 10×10 grid with the goal in the corner — reminded me a lot of a dynamic programming solution where you would fill in a 2D integer array.

Dynamic Programming?

The origin of the term dynamic programming has very little to do with writing code. It was first coined by Richard Bellman in the 1950s, a time when computer programming was an esoteric activity practiced by so few people as to not even merit a name. Back then programming meant “planning,” and “dynamic programming” was conceived to optimally plan multistage processes.

– https://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf

Dynamic programming is about breaking a large problem into sub-problems, and using those sub-solutions to find the large solution. While you could write a DP solution recursively, it’s usually much more efficient to start with the smallest problem, and iteratively build up to the large one. A lot of the classic examples, such as the longest subsequence problem, can be solved by building a 2-dimensional table. For that reason, I like to think of DP algorithms as table-building. Read more »

Solving Continuity Levels with Dijkstra’s Shortest Path

Continuity (game screen)

(This article was originally posted here.)

Continuity is a new Flash game that I was playing recently. It combines platforming and puzzle in a novel way – your character must jump from platform to platform collecting keys to open a door, but must do so inside mini-levels (squares). The macro-game is essentially an 8-puzzle (8 pieces in a 3×3 square grid), where you shift the puzzle pieces using the one empty space, such that your character can succeed in the mini-levels.

This game is perfectly solvable through logic and working backwards, though for some of the harder levels you need to keep a long memory of steps. In short, I became bored and impatient of solving the puzzles in my head, and decided after ~30 levels, it’d be more interesting to automate it by writing a solver.

I also took this opportunity to get familiar with Python, a language well known for its fast prototyping and easy learning curve. I have only worked in Python once, during a 4-month internship 4 years ago, but otherwise, my main skills are in C and Java. However the syntax required to write good algorithms and data structures in these “classic” languages can get quite long and annoying. So I coded up a Python script to solve the final two levels.

The rest of this post details how to develop the solution. The solution is relatively simple because we can just treat each exit in a square as a point in a directed graph, where each edge in the graph A->B specifies that point B is reachable from point A, and then apply a search algorithm through the graph. I chose Dijkstra’s shortest path algorithm, which runs fast and finds the best (shortest) solution. However, my program did require a lot of manual data entering to specify the paths/exits in each puzzle piece, so it wasn’t fully automatic. Perhaps Python has some magic that could automate this :). Lastly, I skipped solving the 8-puzzle, since it’s not necessary.

Read more »