Solving Mushroom Man 113 with Dynamic Programming

Here’s something that might sound strange. Today, while playing the puzzle game “Mushroom Man” — a great throwback to old PC games like “Chip’s Challenge” — I noticed how similar one of the levels was to a 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.

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.

Reaching the exit from this point is impossible.

This level is a great candidate for table-building because it has practically no obstacles and the few that exist can be ignored (the pink jellybeans can be pushed aside, and the purple teleporters only serve to force you along a certain path at the very start). It also doesn’t feature a lot of different items or dependencies, so it doesn’t require any backtracking (e.g. to find the best order to acquire items). Overall, it’s one of the easier levels.

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!

Replacing a dead battery on a Mazda key fob? Don’t buy a cheap one (updated)

Six months ago, the battery in my 2010 Mazda 3’s key fob (aka “flip-key”) totally died and I needed to replace it. The battery in these things is a CR1620, which I couldn’t find anywhere in stores, so I ordered the cheapest ones I could find off eBay — a pack of 3 generic brand Eunicell (made in China) for \$2.18 CAD shipped. Unfortunately, I didn’t have a good first experience with them. There’s an orange LED that should light up whenever you press a button on the key fob. On a working key fob that still contained the original Panasonic battery from the manufacturer, the LED was bright and solid, but on the one I had just replaced, it was flickering and dim. I actually couldn’t get the first battery to work, so I had to take a 2nd one from the 3-pack, and that eventually did work, but never 100% reliably. I also had to reprogram the key fob to be recognized by my car. I concluded that these batteries were just “weak” or underpowered, or that the eBay seller was giving me old/used stock (I now realize that this wasn’t true. EDIT: it turns out my original suspicions were probably correct; see update below!). Anyway, a week ago, I sought out a brand name and ordered a 5-pack of Sony batteries (made in Japan) from Amazon, which cost me \$13 all in (including Ontario taxes).

Top-right: Original Panasonic battery (made in Indonesia).

How I fixed my Logitech G500 mouse click problem

Several months ago, my favourite gaming mouse, a Logitech G500, developed an annoying problem that I will call “ghost clicks”. This is how I explained it to Logitech support:

If I hold the left mouse button for a long time, such as if I want to select a long section of text, it will randomly “let go” and my selection will be broken, even though my finger did *not* let go. Another case is if I click and hold a scroll bar to slowly scroll a webpage, it will randomly “let go”, as if the button released and re-clicked by itself.

Fortunately, Logitech has an excellent 3-year warranty and my mouse was only 2 years old, so they sent me a brand new G500s (the G500 model is now discontinued). Being the holiday season, I decided to gift the new one to my brother, use a spare mouse at work (3.5-year old MX518, still going strong!), and make do with my semi-broken G500 with the ghost-clicks at home.

Long story short, I had a mouse that still felt and looked great, but with a left mouse click that only worked about 70% of the time. This is just tantalizing enough to convince you that everything is OK, and then BAM! – a ghost click when you least expect it. After a few months I was determined to fix it.

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.

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

—> Instructions to install the script here <—

Banjo-Kazooie Maps

I found these maps originally here, but there were two level locations missing (Clanker’s Cavern and Freezeezy Peak), so I decided to edit them. I added level labels, as well as colour-coded the cauldron portals — cauldrons with the same colour dot teleport to each other.

Here are the improved maps for Banjo-Kazooie, one of my favourite games on the N64:

Reversola – Reverse Engineering Sola Rola

Introduction

I was browsing the Kongregate forums one day, when a post caught my eye. It was a list of broken games on the site that still had achievements to earn, and the clever ways that people had found to progress in those games far enough to earn the achievements. Sola Rola: The Gravity Maze was one of the few that hadn’t been solved. This game was interesting because not only was it broken on Kongregate, it was also broken on every single other Flash game portal out there, including the game’s own sponsor Gimme5Games and the website of its creator, EvilFree Productions.

This was a simple physics-based game where you rotate the environment, similar to Loco Roco, but with its own cheeky characters having to navigate a maze. Around September 24, 2010, something changed that broke the game. No matter which website or computer you accessed it from, the game would show the sponsor logo and then a blank white screen. For two years, seemingly no one could figure it out, so in September of 2012, I set out to investigate it myself. Two weeks later, with the help of the Kongregate community, we were able to recreate the original levels to get a working version of the game for people to play and — if they are into this sort of thing — earn the achievements.

Why it Doesn’t Work

A few people already found out why the game doesn’t load. When the game starts, it tries to load two XML files: translate.xml, containing language strings, and levelList.xml, containing the level list. The problem is these files were ONLY located on the Gimme5Games server and the files are now nowhere to be found. This explains why the game was broken no matter which portal hosted the game (SWF file). After an hour of fruitless searching through internet archives, and several efforts to contact the developer, it was clear the original files would not be found. Another approach had to be taken.

In April of 2012, askon, a Kongregate user, posted the source code decompiled from the game’s SWF file, and a way to fool the game into starting with an empty XML file. All that was missing were the contents of that file — the level data! Fortunately, someone had recorded every single level of the game on Youtube, so we had hope to reconstruct the levels, if we only we knew the structure of the XML files. That is where I would come in. More on that later.

Getting the Game to Start

The hosts file entry bypasses the DNS lookup and redirects requests to our server.

When the game starts, it requests the XML files using ordinary HTTP requests to “http://www.gimme5games.com/solarola/translate.xml” and “http://www.gimme5games.com/solarola/levels/levelList.xml”. Since those are gone forever, we need the game to look for those files on a different server — one that we control. One obvious way would be to modify the compiled SWF file itself, however that wouldn’t allow us to earn achievements on the Kongregate site. Instead, we will redirect the request at the DNS lookup step. The easiest way to do this is to modify the “hosts” file of the local machine. Now, instead of asking a remote DNS server for the IP address of gimme5games.com, our PC will simply use the entry in our hosts file.

Spoiler-free VODs for Eurocup 2012 on TSN

TSN.ca offers free video-on-demand (VOD) replays of full Eurocup matches this year. However, on the same page, they also have links to highlight clips, whose titles are unfortunately shown along with the final scores. So if you were planning to watch a full match, the result has already been spoiled once you visit the page. My brother brought this up, and I came up with the following solution – a user script to hide/remove the scores from the VOD page.

There are two scripts. The first simply removes any numbers from the Highlights row. The second removes the entire Highlights row, including the thumbnails (which could be a spoiler as well). Use whichever you like. The 2nd script is best for maximum protection from spoilers.

How to use these: AFTER the VOD page has already loaded, copy one of the scripts into your web browser’s address bar and hit <Enter>. (You will have to avert your eyes at the beginning to avoid seeing the scores before the script runs. An easy way is to resize the browser to a small size before going to the TSN site.)

Note for Google Chrome users: Chrome has a security measure that won’t let you copy/paste a URL with javascript in it. When you paste, “javascript:” is automatically removed from the beginning and it won’t work. The solution is to manually type “javascript:” in front of the URL. To minimize your typing, I suggest copying the script starting from the second letter, i.e. “avascript: …”, manually typing a “j”, then pasting the rest.

This was tested to work on Google Chrome (v19) and Mozilla Firefox (3.6).

/*
* Scripts to remove spoilers (scores/results) from TSN video on demand
* http://www.tsn.ca/window/euro2012/?episode=117716#episode117716
* Author: zAlbee, 2012-06-13
* http://zalbee.intricus.net/2012/06/spoiler-free-vods-for-eurocup-2012-on-tsn/
*/

Script 1. Replaces all numbers with X:

javascript:var list=document.querySelectorAll(".playlistitem");
for(var i in list){
var childs=list[i].childNodes;
for(var j=0;j<childs.length;j++){
var ch=childs[j];
if(ch.nodeName=="H3")ch.innerHTML=ch.innerHTML.replace(/[0-9]+/g,'X');
}
}

Same as above, but on one line:

javascript:var list=document.querySelectorAll(".playlistitem");for(var i in list){var childs=list[i].childNodes;for(var j=0;j<childs.length;j++){var ch=childs[j];if(ch.nodeName=="H3")ch.innerHTML=ch.innerHTML.replace(/[0-9]+/g,'X');}}

Result:

Script 2. Removes entire highlights row:

javascript:document.getElementById("mainplaylist").style.display="none";void(0);

That’s it.

Why I sold my Apple iPad and bought an ASUS Transformer tablet

When Apple first announced their first ever tablet, the iPad, I wasn’t too interested. Like many people, I laughed it off as a giant iPod Touch with a silly name. A large, expensive touchscreen with no physical keyboard or buttons, running only toy apps designed for an iPod/iPhone, minus the phone capability — sounds pretty useless, right? (Well, we all know how that turned out.) Imagine my surprise when my fiancée’s father had already bought one — with 64GB and 3G, no less — and moreover, he didn’t have a use for it, so they were going to give it to me! I wasn’t sure whether to be excited or tell him he’d wasted his money. After all, I didn’t have any real use for it either, but it would be my first iOS (actually my first Apple) device, and I wanted to see what all the hype was about.

Fast forward 10 months later, and I was starting to find a use for the tablet… in bed. No joke. I kept it on a nightstand unused for weeks at a time (a testament to the great battery life), and only picked it up after an especially tiring day, when I just wanted to lie back and relax. (Why? If I’m awake, I’d be using my real laptop connected to a 23″ monitor at my desk.) I loved the large touch-screen, the light weight, and the long battery life, but it was also frustrating. So much potential, but there was so much that I just couldn’t do.

Kongregate Stats and Graphs

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: