Grant Muller

Algorithms Can Really Beat You Up

“Here’s a simple one” remarked the young man as he drew a diagram on the board. “You should have this figured out in about five minutes.”

I stared at the pyramid of numbers scribbled hastily in blue dry erase. The only thing clear to me in that moment was that I wouldn’t have this figured out in five minutes. Or even ten.

“Any number in the pyramid, or in this case tree array, is the sum of the two numbers above it,” the young man continued, “write a function that gets the value of any x, y coordinate in this structure.”

Hearing it out loud didn’t improve my confidence much. I stood in front of the white board with the dry erase marker hanging slack in my hand. It occured to me that five minutes had probably already passed. I began to draw lines on the board connecting various nodes. I drew the coordinates of array values at various locations, hoping an answer would pop out at me. I stood back and chewed on the marker a little before realizing what I was doing. I was dumbfounded. I was stumped.

I gave up.

I walked away from the board that day, defeated. It was the first blow my ego had experienced in a long time, and over such a simple problem, one that I apparently should have solved “in about five minutes”. I began to question my ability as a software engineer. I began to question whether all the software I’d written over the past half-decade was worthless junk. Maybe I’m just not l33t? Maybe if I can’t even solve a problem so seemingly simple in “about five minutes”, I should just hang up my hat?

The problem hung over my head for the next week. One night, as I laid in an uncomfortable Chicago bed, I thought long and hard about what happened that day. I couldn’t believe that I gave up. I never give up. I walked away without getting to a solution. Over the past week I hadn’t even tried to solve the problem. I slumped around feeling sorry for myself and my apparent lack of skill as an engineer. That night, somewhere between waking and dreaming, I stopped the pity party and started figuring the damn thing out.

The mental image of that numerical pyramid that had haunted my thoughts over the past week was top of mind as I woke in the morning. I started to trace through it as I showered, creating further iterations. Adding values at the end in an effort to find a pattern somewhere. I grabbed my iPad and stylus and drew it out again, adding array notation values as I had drawn on the board.

I stopped thinking about how long it was taking me to solve the problem, and focused on this pyramid of numbers. I still couldn’t find a pattern in the values, nothing that said to me that for any x, y coordinate I could simply subtract or add a number here or there and have a solution.

Not too long afterwards Cary awoke and we walked to a local coffee shop (Intelligentsia on Randolph St, highly recommended).

“Whatcha working on” Cary asked.

I described the problem to her.

“It sounds like something that has no practical application in the real world.”

True or not, It dominated my mental world, and I had to solve it before I went crazy. I started to use Cary as a sounding board.

“I should just start writing down the rules that I know.” I suggested out loud.

“Yeah, treat it like a logic puzzle”

So I did. Here were the rules I came up with:

 1. 0, 0 = 1
 2. 1, 0 = 1
 3. 1, 1 = 1
 4. if x is equal to y, then the value is 1
 5. if y is equal to 0, then the value is 1

That looked about right. I focused on these rules instead of a pyramid. I realized that rule 4 is really the same as rule 1 and 3. 0 is equal to 0, and 1 is equal to 1. I also realized that rule 2 is the same as rule 5. In the end, I really only had 2 rules:

 1. if x is equal to y, then the value is 1
 2. if y is equal to 0, then the value is 1

I distilled further.

 1. if x is equal to y, then the value is 1
 2. if x or y is less than 0, or y is less than x than the value is 0.

“I’m an idiot” I groaned, “It’s a simple recursive function.”

All of the values could be derived from two simple rules, their parent nodes derived from their parent’s node and so on. If I wanted to know the value of any number in the array, it was simply a matter of performing the check again, using the same function, on the left and right hand side of the expression, all the way back to 0, 0.

Let’s look at it more closely:

The value of any x, y coordinate in the system is the sum of two other values in the coordinate system, x-1, y-1 and x-1, y. For example, to get the value of the integer at location 4, 2:

getValue(4, 2) = getValue(3, 1) + getValue(3, 2)
    getValue(3, 1) = getValue(2, 0) + getValue(2, 1)
    getValue(3, 2) = getValue(2, 1) + getValue(2, 2)
         getValue(2, 0) = getValue(1, -1) + getValue(1, 0)
         getValue(2, 1) = getValue(1, 0) + getValue(1, 1)
         getValue(2, 1) = getValue(1, 0) + getValue(1, 1)
         getValue(2, 2) = getValue(1, 1) + getValue(1, 2)
              etc

Given that these two values are themselves the sum of their “parent” nodes, this same function can be called with their coordinates plugged in for x and y, and those values summed, all the way back to the value of 0, 0. If I pick an x or y coordinate that is less than 0, or if I pick a value pair like 5 and 6, then I’m going to get a 0 back. Everything else should return a 1 or the sum of the parent nodes.

Here was the simple 3 line ruby function I wrote to accommodate this:

It was that simple.

This was an important reminder that sometimes you just have to walk away from a problem, shake your hands out, talk to your wife over coffee, and relax before approaching the problem again. It restored my confidence to go back and solve this little problem. My ego had taken a real blow, and the thought of giving up on it was driving me bat shit crazy. Its a lot like riding a bike or doing backflips. If you screw up and land on your face, you have to immediately get up and do ten more to avoid the psychological after effects of that perceived failure.

To get back on the bike, I plan on doing several more of these over the next few months. Depending on how interesting they are, I’ll report them here.

Update: Victor Nicollet has educated me in the way of Pascal’s Triangle, the diagram featured above. His solution to the problem and accompanying blog post are well worth the time to read and understand. Thanks Victor.

Tags

4 comments

  1. Your solution makes an exponential number of calls to compute the result 🙂 there’s a faster way to do the same:

    function T(x,y) { var num = 1, denom = 1, start = y-x; for (i = 1; i <= x; ++i) { num = num * (start + i); denom = denom * i; } return num / denom; }

    1. Loved your article on Pascal’s triangle and I appreciate the explanation. Your solution enlightened the hell out of me. I’m going to post an update.

Leave a Reply

Your email address will not be published. Required fields are marked *