phil wade dot org
I'm Phil Wade, a developer who works on the web and on android. This is a blog about me and my life.

Interflix is my first android app. It's a netflix que manager currently in development.

If you'd like to get in touch with me, fire an email to phil (at) philwade (dot) org

I also occasionally post on twitter if you're into that sort of thing. I'm @phil_wade

My girlfriend and I write about the things we cook: Us Versus Dinner

Subscribe to RSS

Knight's Traversal 2
by phil | Jan 26, 2012 - 04 p.m.


Hey.

So remember a week ago, when I wrote a bit about some code I had written to solve the Knight's Keypad Traversal problem over at Programming Praxis? Sure you do. It's the last post I wrote. Go read it if you haven't.

Anyway, my solution used recursion, and was not the best solution because the complexity of getting the answer grew exponentially. I did not understand fully the better solution, so this week, I made it my business to understand it. I also decided it would be a good time to try and write some code in Ruby, for reasons which are clear to no one. (Notes on Ruby: Arrays seem far too difficult to create.)

The correct solution is the Dynamic Programming solution, which basically means we collapse the problem into smaller subproblems that are faster to solve. Bear with me here, as I've just finished grappling with this solution myself. I personally got a lot out of this stackoverflow answer. Like the recursive solution, we find the base case, which for this problem is the length of a single step path, and we solve it for every position on the key pad. By adding those single step path values together, we can determine the length of a two step path. When you start on one and step to either six or eight, you have one step left, and the know the length of a one step path from any number already, so you just add those together.
i.e. [two step path from one] = [one step path from 8] + [one step path from 6].
Here is a chart that illustrates the first two rows:

1 2 3 4 5 6 7 8 9 0
1 1 1 1 1 1 1 1 1 1
2 2 2 2 3 3 2 2 2 2


What makes this faster than the recursive solution is that we build up from the base case and each successive case is just a bit of quick addition with the previous steps answers. Here is some code. 

paths = [
        [4, 6], #0
        [6,8], #1
        [7,9], #2
        [4,8], #3
        [0, 3, 9], #4
        [], #5
        [7, 1, 0], #6
        [6,2], #7
        [3,1], #8
        [4,2] #9
        ]

n = ARGV[0].to_i

counts = Array.new(n + 1) { Array.new(10) { |i| i } }

(0..9).each do |i|
    counts[1][i] = 1
end

(2..n).each do |number|
    (0..9).each do |digit|
        sum = 0
        paths[digit].each do |from|
            sum += counts[number - 1][from]
        end
        counts[number][digit] = sum
    end
end

puts counts[n][1]
(on bitbucket)

I hope that it is fairly straightforward to see. I've found Ruby easier to read than to write so far. For every path length, we just check on step back in our array of previous answers and add together what we find. It is also quite zippy when compared to the recursive version. One is in python, the other ruby, so the comparison is sort of moot, but just for kicks: 
[phil@philsmacbook:random-bits ]$ time python knight_keypad.py 10
1424

real    0m0.346s
user    0m0.017s
sys     0m0.018s
[phil@philsmacbook:random-bits ]$ time ruby knight_keypad.rb 10
1424

real    0m0.047s
user    0m0.003s
sys     0m0.004s


(I tried to run 100, but I think the recursive version is still going.) Pretty cool stuff. Let me know if this post doesn't make a lot of sense... I'm still learning to explain technical things, and since this is something it took me the better part of a day to understand, it might not be perfectly clear. Enjoy. 0 comments
Knight's Traversal
by phil | Jan 20, 2012 - 04 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. 0 comments
The Future
by phil | Jan 13, 2012 - 11 a.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. 0 comments
New Year Projects
by phil | Jan 4, 2012 - 06 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: 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. 0 comments
This week's excercise
by phil | Nov 16, 2011 - 11 a.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. 0 comments