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.
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.
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 »
This is a bookmarklet that sets a dark background colour on Kongregate game pages. The goal of this script is to dim nearly all the elements on the page, so as not to distract the player with bright lights, while keeping the chat box and achievement tabs legible.
The script works on Chrome 23 and IE 9, but
EDIT (Dec. 11, 2012): I updated the script to version 2, which colourizes more elements.
—> Instructions to install the script here <—
Read more »
Some interesting graphs I conjured up a while back for achievements earned on Kongregate, the popular Flash gaming portal.
The first one is based on user data collected by MrRubix in late August 2011. It shows how many users have collected a certain number of badges. The data is very bottom-heavy, so it’s using a log scale (for amusement, the graph using a standard scale is mostly useless). 744670 users have only 1 badge, while only 23 users have all 1593 badges (the max number at the time). Interestingly, the graph is mostly descending until the end, where there’s a sharp increase.
The next set is generated by my own script:
Read more »
I have named the 2010 WTF game of the year. It includes cars and zombies.