There Must Be O(n) Ways To Leave Your N-P Completeness

So yesterday we discovered that when your keyboard gets mixed up, all the letters wind up in cycles with other letters, and that you're guaranteed that if you want to type an a, and you type an a and it comes up q on the screen, if you type q and then keep typing what you see, you'll eventually wind up with an a. Is it clear why this is true? I mean, I happen to know myself that it is, but that's only because I have a degree in this crap. It seems like I could be trying to type a and somehow wind up at a dead end where I type a and see q, and then I type q and see z, type z and see x, type x and see q, type q and see z, type z and see x, &c., &c., never actually getting back to a. But we're actually safe from that because in that case typing both a and x would have to produce a q, which means there were two q keys on our original keyboard (which would be, like, totally whack). This same thing prevents there from being a cycle where, like, I want to type an a, it comes up q, I type q and it comes up a, and then I type a and it comes up z, and then I go through an entirely different cycle. In this case that means your keyboard was whack in a different way--when you type the a key, two different letters could come up. If you're trying to type an a, when you finally see a on the screen, you've completed the cycle.

If by some miracle you've followed me to this point, you know the following: each letter of 'dirk' is going to have to be in a cycle with some other letters, and those cycles can be no larger than 26. You also know from yesterday that to finally actually see 'dirk' on the screen, you're going to have to type what you see as many times as the least common multiple of all of the cycles that these letters are in. So if d and i are in 3-cycles, r is in a 7-cycle, and k is in a 10-cycle, you're going to have to type what you see 210 times (lcm of 3, 7, and 10) before all the cycles match up.

There's one more trick to figuring out the actual answer, and that's noticing that you can't, like, have both a 21-cycle and a 22-cycle on your keyboard. That's because you've only got 26 letters and the 21-cycle and the 22-cycle would have to be composed of entirely different letters (or you would run into the same problems we ran into above, where one letter typed two different things, or there were two of the same letter on your keyboard). You could have, say, two different letters in a 21-cycle, but it would have to be the same 21 cycle.

So, finally, here's the ironic and humorous (for a definition of "humorous" that...well, you know) crux of the thing I was trying to get at yesterday (yes, I know. It wasn't worth it). If this were an actual interview question, an interviewer (at least a good one) would consider you to have to solved this problem at this point, even though you haven't actually found the answer. The reason is that this problem is N-P Complete, which is a fancy way of saying that there's no clever algorithm for solving it other than trying all the possible combinations of cycles that fit into 26 keys and seeing which one gives you the answer where you have to type the longest to get your name. Anyway, off the top of my head the biggest answer I can come up with is if d is in a 2-cycle, i is in a 5-cycle, r is in a 7-cycle, and k is in a 9-cycle, which takes 630 tries. That might be wrong, but I'm going to get the job anyway.