I just got sucked into Peter Norvig‘s Let’s Code About Bike Locks. If you haven’t read that yet, read it first, at least the beginning. Otherwise this will make no sense.

The strategy of starting from the first tumbler and then calculating the subsequent ones seemed like it could be improved on. What if we looked at all the four-letter English words, and chose the most common letter, on any tumbler, fixed that letter on its tumbler, and then continued on to the second most common letter, on any tumbler, and so on? How well could we do?

So I coded it up, and here’s the result, a lock that can make 1,410 words from Norvig’s list at http://norvig.com/ngrams/words4.txt, 170 more words than his best:

Lock: ABCDGLMPRST AEHILNORUY ACEILMNORST ADEKLNORSTY

I believe Norvig’s strategy of improving a lock with random permutations also would be less likely to improve on this lock. Changing any letter would, by definition, be choosing a letter that occurs in that position in fewer words. However, it’s still possible to improve; there might be some better letter choices that, while poorer overall, are still better for the specific other letters already chosen for the other tumblers.

Update 15 Jun 2015: Someone was wrong on the internet and this time it was me! Astute readers will notice that a tiny off-by-one bug in my implementation (see the fifth revision) led it to generate a lock with three tumblers with eleven letters each, and one tumbler with ten letters.

The new best lock from this implementation only generates 1,161 words, leaving Norvig’s solution the best still:

Lock: ABCDLMPRST AEHILNORUY AEILMNORST ADEKLNOSTY