09.12.09

Morning Headlands Ride

Posted in personal, san francisco at 10:07 am by danvk

On my way in to work Friday morning, I took a detour via the Marin Headlands:

It was a total whiteout on the Golden Gate Bridge, but as soon as I got to the north bay, it cleared right up. I went back into the fog for the ~800 foot climb up Hawk Hill before breaking through and getting some amazing views from the top:

I saw a fighter plane zoom into the city, which made me briefly think that it was Fleet Week. Not so! (It’s in October.)

The ride down the back side was misty, beautiful and frighteningly slick. All in all, I left at 7:40 and got into work with a change of clothes right around 10.

One more view from the top:

Permalink Comments off

09.07.09

Character Palette Bookmarklet

Posted in web at 3:20 pm by danvk

The other day, I noticed that one of my friends had Wikipedia’s article on the em dash bookmarked in her toolbar. While that article is a gem of punctuation literature, it turned out that she would go to it, select an em dash, and copy/paste it into emails.

A better way to do this is with a bookmarklet. Drag this to your browser’s bookmark toolbar:

character palette

Click the bookmarklet on any page. You’ll see a character palette like this:

Select the character you like and either copy/paste it or drag it where you like. Then click “Close” to make the palette go away until you need it again. Enjoy!

Note: I’ve tested this in Firefox, Safari and Chrome. This probably doesn’t work in IE.

Permalink 3 Comments

08.16.09

Cabbie Karma

Posted in personal at 10:44 am by danvk

I rode a cab to Joe and Amy’s wedding yesterday. It cost $5.05. In a rare moment of innumeracy, I handed the driver a $20 bill and asked for $16 in change. (I’d meant to ask for $14.)

In the confusion that ensued, I wound up paying $5 for my ride to an unhappy cab driver and got out before realizing what had happened. I felt terrible — my cabbie karma was at zero.

On the ride home, I resolved to do better. It was $6.15, so I gave the driver a $10 and asked for $2 back. He handed me a single bill. I was about to complain when I noticed that it was a $2 bill. A sure sign that my cabbie karma had been restored!

Permalink Comments off

08.11.09

A Few More Boggle Examples

Posted in boggle at 9:01 pm by danvk

Hopefully the last boggle post for a while! I figured I should throw up a few more examples while I still have time left on my OmniGraffle trial.

There are two main shortcomings to the max/no mark upper bound:

1. It can’t keep track of which words it’s already found.
2. It can’t keep track of which choices it’s made on each cell.

These can both be fixed, but only by incurring great computational complexity. Remember the tradeoff between the “tightness” of a bound and the difficulty of computing it?

Our first example:

Let’s look at the search tree starting with the “t” cell. There are three possible words: “tar”, “tie” and “tier”. Here’s the search tree that max/no mark generates:

(I’m drawing the trees slightly differently than I did in the last post, to make the branching more explicit. Branches inside dotted lines come from multiple possibilities on a cell. Other branches result from the ordinary process of looking in different directions from a cell.)

In this example, max/no mark chooses the “a” when it gets to the “{a,e}” cell directly from the “t”. This makes sense, since it results in one point to the e’s zero. However, when it gets to the “{a,e}” cell through the “ti”, it chooses the “e”. This also makes sense, since it gets two points from the “e” (“tie” and “tier”) vs. zero from the “tia” prefix. By the time it makes this choice, it has no memory of choosing the “a” the last time it encountered this cell. If it did, since the “tie” prefix results in two points to the “ta” prefix’s one, it would make sense to go back and change that choice. But remembering this would require lots of expensive bookkeeping. It’s faster (but yields a looser bound) if we just accept the possibility that we’ll make different choices.

Example number 2 of max/no mark’s failings:

The problem in this case is that max/no mark doesn’t remember which words it’s already found. At first glance, it seems like this problem would be easy to remedy. And it certainly would on this board, in which each cell only has a single possible letter. But if you think about a board with lots of choices, you’ll start to see why it’s best to just give up and accept a looser bound.

Permalink Comments off

Some max/no mark examples

Posted in boggle at 1:41 pm by danvk

After the last post, several people mentioned that they were confused about how the “max/no mark” upper bound on the highest score in a class of Boggle boards worked. With some help from OmniGraffle, I’ve created some instructive examples.

Here’s a class of boards:

The dots mean “no letters here”. The class contains two different boards:

It contains two boards. The one with an “a” has two points worth of words on it, while the one with a “u” only has one. (We’re only looking at words starting with ‘f’ here.)

The diagrams show that the solver starts with the ‘f’ on each board and explores adjacent cells. When it finds a word, it scores it and passes the total score back up the depth-first search tree.

Here’s how the max/no mark bound sees that board class:

When it gets to the “{a,u}” cell, it tries both possible letters. The “a” tree brings back 2 points, whereas the “u” tree brings back 1 point. So it chooses “a” and counts two points. As it so happens, this is the score of the highest-scoring board. The sum/union bound would have added the 1 and the 2, resulting in an upper bound of 3. The max/no mark bound takes advantage of the fact that this cell can only be one of two possibilities, not both.

Now what if we throw a few more letters on:

With the new letters, there are more points coming from the u:

The two points going through the ‘a’ are dropped on the floor. sum/union would have resulting in a bound of 4+2. When there are lots of letter choices on every cell, you can see why max/no mark is a much tighter bound.

It’s important to note that there are two sources of branching in these search trees: (1) being able to go in multiple directions from a cell (i.e. f->u->r or z) and (2) having multiple choices on a cell (i.e. f->a or u). The max/no mark bound sums the scores resulting from choices in case (1) and takes the max of choices in case (2). The sum/union bound takes the sum in both cases.

Permalink Comments off