OaO Presents: Enhanced Hilarity For Nerds™

Today's Hilarity For Nerds™ is a link to today's XKCD cartoon. Go and read it, then come back.

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

So the answer in this case was 4. The letters a through d made a "4-cycle," and every other letter was, essentially, switched with itself (a "1-cycle"). Now let's take the same example, but instead of e-z staying the same, let's imagine they all got switched by one letter, too (e is where f was, f is where g was, &c., &c....y is where z was, and z is where e was). So we've got one 4-cycle and one 22-cycle. Watch what happens:

• ajsl
  
• bktm
• clun
• dmvo

Crap! We got back to 'd' for the first letter, but none of the other letters are right. They're all in a 22-cycle, so we're going to have to do this 22 times to get back to the start...

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

Double crap! At try number 22 we had the 'i','r', and 'k' right, but now the d isn't right. We keep going...

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

Ahhh. At last. It took 44 times. Hey...that's funny, 44 happens to be the least common multiple of 4 and 22. I wonder if that means something? Also meaningful is that this took way too long to write, and it's way too long to read, and I might actually trick you into reading more of it if I continued it tomorrow and titled it with some catchy pop-culture reference or something. Plus then I could say something like, "I've given you hints to the full solution so you can work on it some more yourself." Or whatever.