Miles V. Aronnax

I'm sure many people recall the Google Labs Aptitude Test question (#10) about an infinite, square lattice of one Ohm resisters. Other people may recall it from this xkcd comic. But in short, the problem is to find the equivalent resistance between two points separated on the grid by a knight's move (as in chess).

The Friday before last I convinced myself that if I could find a pattern to counting the number of simple paths connecting the two points, I could then solve for the effective resistance. After several hours of coding to find the number of paths with seven steps (or edges), I realized I was wrong. However, I still found the problem interesting and hence decided to post the code here.

[NOTE: You may notice that I use the term "grid" instead of "lattice" for most of this entry and in the code. That was a failing on my part to understand the difference. This is only a terminology issue and can be ignored.]

Below you can find my code which will count the number of paths of a specified length on an infinite, square grid between any two points you specify. All the files needed to rebuild or modify the source are included in the jar file. If you want to play without downloading it, there is an button below:

As far as downloads go, the two files below are identical except for which interface they run by default. The CountPathsCLI runs the command line interface. The CountPathsGUI launches a "graphical" interface. On most computers, you can download the GUI version and double-click on the file to run the program. Otherwise, you need to invoke "java -jar CountPathsCLI.jar" or similar. (Append "--help" to the CLI command to get the options list.)

As for my problem, I've run the code for over 80 hours now and found the number of simple paths for a pair of knight's move vertices separated by up to 33 edges (461,245,663,954 paths of a few trillion). Below is a graph showing that this isn't a simple exponential dependence.

As for what to do now, I don't know. I haven't had any luck finding a formula that generates the number of paths from the path length. Maybe I should go work with my infection modeling code (zombies, of course) and then come back later. Yes, that sounds good.

By the way, originally I had written this in a stupid way where I added all the vertices that need to be explored to the end of a queue. This meant that I needed a lot of memory to run the code. In fact, I was using ~9 GB at one point. Normally one doesn't like to admit, let alone publish their mistakes, but I really like this screenshot of htop where I was using most of the 8 core machine with 12 GB of RAM. It just makes me happy.