phil wade dot org
I'm Phil Wade, I write code, homebrew beer and live with two cats, a dog, a wife and a daughter in Buffalo, NY.

Email phil (at) philwade (dot) org



My wife and I write about dinner: Us Versus Dinner

Twitter Github


Subscribe to RSS

Tweets by @phil_wade
A jQuery plugin
by phil | Feb 7, 2012 - 08 p.m.


The other day, in line with my goals for the year, I was working on my family gift distribution project White Elephant. One of my goals for the project has been to push myself toward better page and user interaction design. I've always been a back end sort of guy, telling myself that because I had the know how to code things that I had no reason to care about how those things looked or felt to a user. I've come to realize that assumption is pretty stupid. Taking time to not only make things look pretty, but also make them easy to use is what sets apart outstanding projects from the crummy ones. At this point, I'm a ways from creating the cool things that I want, so actively making myself practice is a step in the right direction.

So back to the main point. I was putting a very stripped down form into a confined space, and instead of having a label next to each input, I thought it would be neat to have some greyed out text that told the user what went in the box. When they clicked the input, the text would disappear and the text they typed would look normal, not greyed out. If you clicked away without typing anything, the original hint text would come back. It looks like this:



I thought it was a clever solution, and that perhaps others would like to use it, so I wrote it as a jQuery plugin. This was a process that took me through the weird world of javascript objects and closures. Things I've touched before, but they always seem a little weird. I found the tutorial on writing jQuery plugins very helpful, and quite instructive about javascript objects as well. You can get the plugin from my bitbucket.

Rotating String
by phil | Feb 2, 2012 - 11 a.m.


Ugh.

I was planning on doing an implementation of a B-Tree this week, but instead I've managed to contract a terrible cold and don't really feel like doing much. Instead of a B Tree, here is another quick puzzle from Programming Praxis. Given two strings, the code must determine if the second is a rotation of the first. For example "ttes" and "stte" are rotations of "test". Here is a bit of code:

def rotate_eq(string1, string2):
    if len(string1) != len(string2):
        return False
    start = string1[0]
    length = len(string1)
    match = False
    
    for i in range(0, length):
        if string2[i] == start:
            match = True
            for j in range(i, length + i):
                #print "does ", string2[j % length], " equal ", string1[j - i]
                if string2[j % length] != string1[j - i]:
                    match = False
                    break


First, the strings must be the same length. After that, I search for first letter of the original string in the second. It then cycles through the rest of the string using offsets and modulus to properly rotate through the strings and compare every character.

After solving it the hard way, I looked at the given solution. It turns out if you double up the original string, any rotation of that string is contained in the new double version. Quite clever, and rather simple to code up:

def rotate_eq2(string1, string2):
    if len(string1) == len(string2):
        temp = string1 + string1
        if string2 in temp:
            return True
    return False


It makes my original version look like overkill. You live, you learn. You can get the source on Bitbucket.
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.
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.
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.