Okay, now wipe the tears of mirth from your eyes. Now allow into the back of your consciousness the creeping realization that there will always exist entire classes of people who, while technically speaking the same language, could never make themselves understood across strange divides of culture, jargon, and/or pidgin. Further reflect that perhaps this construction, this divide of meaning, is, in fact, the general state of humanity. Wonder if you can ever truly make yourself "understood." Collapse in a nervous wreck fueled by abstract absurdism and existential angst. Then become bored by this line of thinking and go on to wonder about something else.

Anyway, in an equally hilarious coincidence, this makes for a nice segué straight into the solution to the interview question I posted a couple of weeks back, about which I'm sure you've been wracking your brains. As you'll see, there are some similarities between the problem stated in the cartoon (finding an order that totals exactly $13.05 by ordering from a menu) and the interview question. Then I'll talk about N-P Completeness, and then no one will actually be reading this blog because the intersection of the set of people who read this blog and people who read about N-P completion on blogs consists, surprisingly, of only myself.

As of this, the first sentence of this paragraph, I don't actually know the solution to the keyboard problem, but I'm planning to derive it in the process of the writing. As such, my actual "answer" may be "incorrect." But the solution I give will be undeniably truthy. To review: your name is Dirk. Somebody switched all the letters on your keyboard. You hunt and peck out your name and it comes up 'flrp', so you hunt and peck 'flrp' and it comes up something else. How long until you get "dirk" to appear?

The first key thing to this problem is to realize that the letters have to get switched in "cycles" with other letters. That is, if you type 'a', and 'b' comes up, and then you type 'b' and 'c' comes up, and so on, eventually you

*must*produce an 'a'. The reason for this is that you've got 26 keys, and after you scramble them, they all have to go some place and every space in the keyboard can only have one key in it (this is called the "pigeonhole principle," and it's the basis for an entire branch of mathematics). Let's consider a really simple case--somebody scrambled up the keys and put them back, but miraculously everything ended up in the same place except that the 'a', 'b', 'c', and 'd' keys got switched with each other (a is where b was, b is where c was, c is where d was, d is where a was). So you're when you use your method you're going to see this:

- airk
- birk
- cirk
- dirk

- ajsl
- bktm
- clun
- dmvo

- 20: dgpi
- 21: ahqj
- 22: birk
- 23: cjsl...

- 41: afoh
- 42: bgpi
- 43: chqj
- 44: dirk

## 2 comments:

Embarrassingly, you're going to have to double your estimate of the size of the intersection of the set of people who read this blog and people who read about N-P completion on blogs.

I forwarded this to my brother-in-law, and his response was "This was the best email I have ever received ever."

Post a Comment