Monthly Archives: December 2015

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 »

Tiny Windows programs that are awesome

I consider myself a Windows power user, having used this OS almost exclusively on all my PCs and laptops since I was a student with Windows 95, and now as a professional software developer on Windows 10. Over the years, I’ve found that I like my Windows experience a certain way, and I’ve installed a ton of different apps and utilities. As I prepare to replace the hard drive in my aging Dell XPS 1340 (2009) with a faster SSD (on which I plan to reinstall Windows 7, and maybe see if it can handle Windows 10 too), I’m reminded of a few programs that I’ve found indispensable and will be installing on the new disk right away. Sure, there are plenty of professional applications that are released by huge corporations and have equally massive, sprawling installations over your disk, but I’m most impressed with the little apps that are well-written and just work. So that’s what this list will focus on — tiny programs that just work. Here are my favourites, in no particular order! Read more »