Knight's Traversal
Jan 20, 2012 - 09 p.m.

This week marked the internet's main protests against both SOPA and PIPA (look em up!), with many websites going black on Wednesday. I did my part and attended the protest in Manhattan, along with some co-workers. I must say, I've never seen so many iPads, laptops and smartphones at a protest. Then again, it's been a while since I've been to one.

Anyway, today I thought I'd share my solution to a programming problem I saw over a Programming Praxis. The blog itself gives you little programming problems, similar to what you might encounter during a job interview. I read most of them, but only do the occasional one.

This particular problem is a knight's traversal of a phone keypad. That is a chess Knight, given a keypad like so:
1 2 3
4 5 6
7 8 9
   0
We are supposed to find the number of ways the knight can traverse the keypad in n steps, starting on the digit 1. For example, in two steps (counting the initial one as a step), the knight can go to six and to eight, giving two different paths. Here is the code:
import sys
route = {
    '1' : [6, 8],
    '2' : [7, 9],
    '3' : [4, 8],
    '4' : [0, 3, 9],
    #'5' : None, #we don't ever get to five
    '6' : [7, 1, 0],
    '7' : [6, 2],
    '8' : [3, 1],
    '9' : [4, 2],
    '0' : [4, 6],
}

def knight(start, n):
    sum = 0
    if n == 1:
        return 1
    else:
        for i in route[str(start)]:
            sum += knight(i, n - 1)
        return sum


if __name__ == "__main__":
    print knight(1, int(sys.argv[1]))
(you can also grab this code from my bitbucket if you'd like)

The solution I've got is the simplest recursive solution. I hard coded the places the knight can go from each number, mostly because the number of destinations is short enough to type out, but also because trying to find where the knight can move on the irregular board is a bit of a programming puzzle in and of itself.

We want to find the number of end points, which is the same as the number of paths, so the base case for our recursion is when n reaches one, at which point we return the value one. The recursive case simply sums up all of the base cases.

If you look at the solutions on Programming Praxis, this one is considered the lesser solution because things grow exponentially. Here's some timing:

[phil@philsmacbook:random-bits ]$ time python knight_keypad.py 10
1424

real    0m0.046s
user    0m0.014s
sys     0m0.009s
[phil@philsmacbook:random-bits ]$ time python knight_keypad.py 20
5604352

real    0m6.426s
user    0m6.404s
sys     0m0.011s


The alternative given is using a matrix to calculate the values. I haven't attempted this yet, mostly because reading the Lisp it is written in is giving me trouble. It probably would be a good exercise though. Maybe for next week.
The Future
Jan 13, 2012 - 04 p.m.

Sometimes I'm struck by how impressive the technology I use everyday is. The other day, I was riding to work on the subway and listening to a podcast on my phone. I wasn't enjoying it very much, so on when the train crossed the bridge from Brooklyn to Manhattan, I downloaded a new one to listen to. Roughly ten years ago, I wasn't sure that I would ever be able to afford a cell phone, and five years before that, the file I downloaded would have taken a hour on a wired connection in the comfort of my own home. Neat stuff.

I like to think that because most of this sort of convenience enabling technology has appeared during my lifetime that I would be able to manage without it. If I really needed to research something, I could do it in a library. Hell, I worked in a library in high school. I kind of know the Dewey decimal system.

However, yesterday I made my first adult doctor's appointment. Before I could make the appointment, I needed to find a doctor. I asked a co-worker who she used. I called that doctor and found out they were not taking new patients until February. Yikes (a side lesson here is that doctors in NYC are very busy). What followed was a journey through my insurance provider's online list of doctors, yelp lookups, google map locating, reading reviews on other sites and calls. Eventually I found someone that had decent online reviews that would give me an appointment within a reasonable amount of time. They are going to email me the new patient forms so I can fill them out before I come in. At the end of the process, I realized that with the exception of the calls (made from the futuristic cell phone I mentioned in the first paragraph...), none of the tools I used existed fifteen years ago. And I have no idea what I would have done. I suppose I would have used the yellow pages and made a lot more calls, but that seems so inefficient.
New Year Projects
Jan 4, 2012 - 11 p.m.

A while back, my plan to write at least one post a week got away from me. It would be easy to say that this was because I got engaged to my longtime girlfriend (she and I write usversusdinner.com together), and because of the holidays, so I'll just stick with that. It certainly had nothing to do with my tendency to procrastinate about almost everything. Not a chance. I occasionally worry that procrastinating is holding me back from my full potential. I imagine myself being much more successful than I currently am, if only I could get myself together. As a matter of fact, it seems to run in the family. My sister, who writes the excellent blog Mind, Body & Scroll has written few posts about it. This actually is a bit of a relief for me. I'd say my sister is a rather successful person, even if she loves to procrastinate as much as I do. This gives me hope.

However, just hoping won't help me accomplish anything, so in the spirit of the New Year, and even though I despise New Year's resolutions, I'm getting back on the horse and making this the first week back posting every week. We'll just say the lapse until now was a sabbatical.

Because I haven't accomplished much recently (aside from confirming that I'm quite addicted to Super Meat Boy), I'm going to list projects that I have half finished, as well as projects I'd like work on, along with a bit of a description. I'm sort of hoping that publicly listing them will help shame me into finishing them. Here goes:
  • Interflicks: My first android app, for managing your Ques in Netflix. At one point it was almost done, but because of some changes in the way Netflix's API works, parts of it now don't function. I haven't been able to fix it properly because I no longer have a full Netflix account, and they don't seem to be in any rush to fix the issues with their developer support. I've gotten the muster up to work on this a few times, but have come away frustrated. It makes me upset to have an incomplete product floating around in public.
  • Unnamed Epic Fantasy Novel: I was quite excited about this for a while, but epic fantasy requires a lot of looking ahead prep work. I have tons of notes and a half written first chapter. The latest stumbling block is an incomplete magic system. I wanted something that had an internally consistent logic, like everything Brandon Sanderson comes up with, but every one of my attempts either didn't work, or was missing something I wanted. I'll keep attempting, and I'm hoping once the world is a bit more nailed down, I'll feel more confident about the actual writing.
  • White Elephant: Every year, my extended family participates in a Secret Santa style gift exchange. The drawing of names usually involves a hat. This year, someone suggested that a more technical solution would be helpful to everyone. Since I'm the only software engineer in the family, I decided to take it on. I've used it as an oppurtunity to learn Flask, a Python micro web framework. Since the problem is pretty simple, I've also taken it as a challenge to better refine my user interaction and visual design skills, both important things for a web developer. I'd say it is halfway done. The current code is available on my bitbucket.
  • J884501: A short science fiction story about a space ship with a human brain. Or perhaps a human with a spaceship for a body? A neat idea that came to me in the night. It might be a fifth of the way done.
  • tgrep.c: A while ago, Reddit issued a programming challenge called tgrep. I took it on and solved it in Python. Afterward, I decided to try and re-implement it in C, since it was an interesting non-trivial problem and I wanted to learn C. I got some progress, but it is far from finished (C is tough if you've never touched it before 24). The python version as well as my progress with C, is again on Bitbucket
  • Senior Project Remake: My senior project in college was a Google Maps mashup that catalouged the migration of the New York City music scene from Manhattan to Brooklyn. It used data that was hand picked from old copies of the Village Voice on microfilm. Thinking about the code quality makes me shutter. I'd like to try it again using my (hopefully) better skills and modern resources. I'd also like to re-learn the Maps API. This one is just a pipe dream at the moment, no code to speak of.
  • Farm Share Startup: Another idea with no code. I haven't even really nailed the mental model for this one. A site for CSA's to manage their members - payments, schedules, blog posts, etc. I think this one has some legs as a serious business, but I have trouble getting excited about it.
  • CartJumper: An android game, inspired by my favorite Donkey Kong Country level, Minecart Madness. Also the first serious game I've tried to write. Game programming, like C programming, is an area where I have much to learn. I have a very rough prototype on my phone right now, but that's about all the progress currently.
Phew, ok, so there are a couple of things I'd like to work on. I didn't realize quite how many there were on the list until I finished writing it. Now I really should never be without something to do, and if I manage to keep myself busy, something to write about. Let's see what I can accomplish.
This week's excercise
Nov 16, 2011 - 04 p.m.

Yesterday, I realized that I hadn't started thinking about what my writing exercise would be this week. I usually have some ideas by Tuesday, but this week was coming up dry. I spent some time considering various short fiction options, although I'm not sure that that's what I want this blog to be about, or if this is even a good medium for that. So really, nothing.

Then, this morning, I realized that I was doing my weekly writing out of the blue. I was writing a letter to my congressperson, and it was, as a bonus, good practice. Congress is currently considering a bill called SOPA (Stop Online Piracy Act), which has potential to undermine the way we use the internet. While the legality and morality of piracy is debatable, this bill would put in place measures that are a threat to online free speech and innovation, two things we can ill afford to lose. You should read about it and decide how you feel.

If you decide that this bill will be a bad thing, you'll be in the company of Google, Yahoo, and a number of other prominent internet companies, and I would urge you to also write your congressperson. I'm of the opinion that if you like the internet as it is now, you should be opposed to this legislation.

Sorry to be a bit preachy, but as someone who makes their living working online, this sort of thing threatens me personally as well as having terrible ramifications for status as a free society.
Regarding books and ciphers
Nov 8, 2011 - 01 a.m.

I've been trying to write about something (anything really) at least once a week. Last week I failed at this for a variety of reasons, and the week before I wrote a draft of a recipe post for my (and my girlfriend's) other blog, Usversusdinner.com, which is about our cooking adventures. I'll post that once I get it edited and put some pictures into it. This week, I'm getting right back on the horse with this post.

I'm a big fan of Penny Arcade, and about a month ago, the news post was written by a game developer who also happened to be an expert in cryptography. In the post, she included two blocks of numbers: "28-1 10-2 10-3 6-4 18-4 43-1 36-3 9-2 43-4 32-9 41-2 1-1 2-1 45-1 42-3 33-2 3-4" and "42-4 14-2 26-1 32-10 35-3 54-3 56-1 3-3".

I was curious about these, so I did a bit of poking around and discovered that they were the cipher text produced by a type of Book Cipher. You, much like myself before this exercise, may not be familiar with a book cipher. Simply put, a book cipher relies on an existing piece of text, usually a book (go figure), as a key for decoding a message. The coding of the message often isn't complex - usually numbers refer to words in the key text. The obscurity of the cipher comes more from knowing what the key text is, less from the complexity of the code.

Every news post on Penny Arcade accompanies a given comic, so it isn't terribly difficult to guess what the key text for this particular cipher text is (it is this comic).

In this instance, the way the message is coded is "word number-word letter". I was curious what the message was, so I started to counting through the words and then counting through the letters. As it turns out, this is an incredibly dull, slow, and completely unrewarding process. In the past, this was no doubt was a "security feature" of this type of cipher.

Fortunately for me, we live in a world filled with computers, and computers are great at this type of thing. I whipped up a little program in python that de-crypted the text in almost no time. The longest part of the coding session may have been transcribing the text of the comic.

base_cipher = "28-1 10-2 10-3 6-4 18-4 43-1 36-3 9-2 43-4 32-9 41-2 1-1 2-1 45-1 42-3 33-2 3-4 42-4 14-2 26-1 32-10 35-3 54-3 56-1 3-3"
key_text = "Sir I need you to turn off your my what you want me to turn off my book oh you'd like that I bet you'd love to turn off all books wouldn'tcha yeah just \
like hitler uh oh too far you're gonna shock my genitals huh the genital region I think we might start there yeah"

code = base_cipher.split(' ')
key = key_text.split(' ')

for i in code:
   parts = i.split('-')
   index = int(parts[0]) - 1
   print key[index][int(parts[1]) - 1]


It's quite simple thanks to the way that python keys strings just like arrays. I've considered trying to re-write it as a one liner, but it didn't seem like a good use of time.

I split both the cipher text and the key up by spaces, and then cycle through each word-letter pair of the cipher. I split those by the dash, and then use the word part of the pair to grab the right word, and the letter part of the pair to grab the write letter from that word. There is also the subtract by one to compensate for the cipher using an index that starts with one and python using an index that starts with zero. Easy stuff.

You can grab the code if you like from my bitbucket account. I won't say what the message is, but it actually isn't very interesting. No worry though, as I had a great time finding it. I've found that with most worthwhile pursuits, the fun isn't in the destination as much as it is in the journey. Enjoy!