Binary Tree Boat Race

Posted by Skrud at Friday, August 25th 2006 at 1:51pm

This idea came up while having a few pints at Les 3 Brasseurs last night, and then it steeped and elaborated and now it’s either absolutely brilliant, ridiculously nerdy, or both.

It’s a merger of a traditional Boat Race and the infamous Binary Tree data structure.

The Boat Race is a drinking game, in which two teams line up with a beer in front of each player, and start chugging. Like in a relay race, a person can’t start drinking until the player before him/her finishes. The first team to finish all their beers wins.

A Binary Tree is a way of organizing data. Each data is contained in a “node” and each node as at most two “children” which are below it in the tree. There is a “root” node, which is where the tree starts. It can have two “child nodes”, and each of those can have two child nodes, and so on. A node with no children is called a “leaf”. So at each level of the tree, you have at most double the number of nodes as the previously. Where n is the level if the tree, and the root is at n = 0, the maximum number of nodes at each level is 2ⁿ. A path through a binary tree is called traversal.

In the Binary Tree Boat Race, the players arrange themselves as a Binary Tree and start drinking in a parallel breadth-first pattern: The root starts drinking, and as soon as he finishes, the two people below him start drinking. As soon as they finish the people below them start drinking and so on. Here’s a diagram:

The winners of the Binary Tree Boat Race are all the members of the path leading from the root to the leaf node that finished drinking first. The root always wins. Following the diagram, if player F finishes drinking first, then the winners are the root, player B and player F.

Try it next Frosh. :)

Tags: beer, fun, geek | 4 comments

Futile Efforts

Posted by Skrud at Sunday, June 4th 2006 at 11:43am

For some reason, Hydro Québec seems to think it’s a great idea to do power-line maintenance on a Sunday when everybody’s home, as oppose to in the middle of a weekday when nobody’s at my house except for maybe a delivery man. As soon as I woke up this morning, and couldn’t hear the comfortable, reassuring electric hum that my electronic devices give off I knew something was wrong. Luckily my laptop has a built-in modem. Dial-up is a lot worse than I remembered it.

Anyway, this is a pretty good opportunity to get caught up on missed blogging.

Noah visited Montreal last week from Vancouver, B.C. He’s one of the SFU people that I met at CUTC 2005, and he’s going on a lengthy tour of Europe for the next month(?). He had an 11-day stopover in Montreal, so I showed him around.

We started off at … McKibbins, and then Brutopia, and Dundee’s, Hurley’s, St-Elizabeth’s Pub, a shisha bar, and the beer festival. There was also a SOEN BBQ that I brought Noah and his friend Janis to, hoping to introduce them to some of Montreal’s top-quality geeks. They were both a lot of fun. You can read all about Noah’s adventures on his blog.

I really need to get some coffee (our coffee machine is electric and I don’t think we’ve ever foreseen the lcak of electricity as a barrier between grogginess and glorious caffeination). The family’ll be going off to brunch soon, though, to meet with family friends visiting from the U.S. I’m supposed to introduce some people to “Montreal nightlife”. Unless they like beer as much as Noah, I doubt I’ll have anything interesting to show them… :\

Tags: beer, cutc, life | no comments