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
Some thoughts on Facebook
by phil | Feb 17, 2012 - 12 p.m.


I've never been the biggest fan of Facebook. I have an account, and I check in on it occasionally, but it has never really rubbed me the right way. Why that was the case wasn't clear to me until recently.

Facebook reminds me of AOL. When internet penetration was really ramping up, but before broadband was widely available, AOL was the way that almost everyone got online. AOL wasn't (isn't?) just internet access, it was an entire monolithic internet user experience. For most people, AOL email, AOL chatrooms, AOL instant messaging and AOL content was the internet, and the AOL internet was not very compatible with the rest of the internet. This is what Facebook reminds me of.

Facebook seems to be aiming for the same all encompassing online experience. Facebook can feasibly replace your email, twitter, instant messager, blog, photo sharing service and any online games you might play. There have also been changes recently to try and make facebook your source for news. I suppose all of this is convenient for the user, but I don't like having my entire online presence tied up with one company. Not only does it give them a lot of power, but it nudges you into using whatever implementation of a given technology they are pushing, with no mind to quality. I don't mind facebook keeping track of my friends comings and goings, but when it comes to disseminating information, I prefer twitter. I'd rather maintain my own blog and use a third party instant messaging client because while those service are on facebook, other services do them better.

When I look at the online presences of prominent technology people, they also seem to be spread across different services, picking and choosing the ones that they like, and unlike facebook, I can still check them out without strapping into the service they use. While part of the reason people are so locked into facebook is the lower technological bar for entry, I think as people become more savvy and other services become easier, facebook will start to lose some traction.

Now, AOL is still around, but in an extremely hobbled form. Will the same thing happen to facebook? It doesn't seem super likely, but at the peak of AOL, it didn't seem very likely they were going very far either. AOL had the misfortune of being struck down by broadband, and maybe facebook will have it's own broadband come and strike it down. Perhaps everyone will just leave. Tough to say.
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.