Tag Archives: Kongregate

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 »

Kongregate Night-mode script

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 doesn’t work at all only partially works in Firefox. The reason is this script relies on the $ and $$ functions that are defined in Kongregate’s javascripts. Apparently, Firefox doesn’t allow bookmarklets to access those. EDIT: This did not work in the “javascript:” URL version, but works in the bookmarklet version. However, still only half of it works in Firefox, because Firefox rejects my modifications to the CSS rules, throwing “Error: SecurityError: The operation is insecure.” This rule modification is required for dynamically inserted elements, like chat messages, to use the dark style. Firefox-compatible version to come later.

Kongregate Nightmode Screenshot

EDIT (Dec. 11, 2012): I updated the script to version 2, which colourizes more elements.

—> Instructions to install the script here <—

Read more »

Kongregate Stats and Graphs

Some interesting graphs I conjured up a while back for achievements earned on Kongregate, the popular Flash gaming portal.

Graph 1: Users with X number of badges

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:

Graph 2: Earned Points over Time (zAlbee) Read more »

2010 WTF Game of the Year

I have named the 2010 WTF game of the year. It includes cars and zombies.