# Coding is fun

Like all programmers, I get pleasure from writing code and solving problems. Sometimes I code just for fun. Today was one of those days. I thought I would share my results with you.

 I was browsing the web and I came upon the image of an old padlock similar to the one on the left. It reminded me of a word puzzle I once read about that I had been meaning to solve, but never got around to. Some people have difficulty remembering numbers and, to them, a combination padlock using entirely numeric digits presents a challenge. These people might find more utility in a padlock whose combination is composed of letters so that a memorable word can be selected as the password. An example padlock using seven barrels is shown here. At first glance, it may appear that a combination lock using letters is much more secure than one using numbers because of the vastly increased number of combinations it affords. In theory this is true, and if the combination of the letter padlock is selected entirely at random then it produces a vastly expanding number of permutations.

For a seven barrel example, a numeric only combination lock has 10 x 10 x 10 x 10 x 10 x 10 x 10 = 10,000,000 combinations. One using letters has 26 x 26 x 26 x 26 x 26 x 26 x 26 = 8,031,810,176 combinations.

In reality, however, a random combination is not used, and instead the tumblers are typically set to create a memorable word.

Using a very complete online dictionary, I was able to find just 23,109 distinct seven letter words in the English language. This represents a meagre 0.000288% of the addressable space. It's an illusion of security, and one that social-engineering hackers exploit. Sometime soon I'll write another posting on the (lack) of entropy in most passwords, but I'm getting futher and further away from today's puzzle …

### The puzzle

 Given a padlock (I believe the original problem stated it had five barrels, like the example here on the right), the puzzle was to find a pair of English words such that, when one the words was selected in the gate, the other word could be found somewhere on the barrel. For example, if the word FIZZY appeared in the lock gate, then a few letters around the barrel it would be possible to find the word KNEED.
 How would we go about solving this problem? Well, we could brute force all combinations of letters, check for a valid word and then see if this happens to generate any other words, but here I am using "could" in the politest way possible. Anybody who codes a solution this way should really not be coding! We need a much more elegant (and faster) solution. We can do much better …

### The process

Glancing at the padlock we see that the wheels are labeled in the same order. What this means is that, however the barrels are rotated, each adjacent barrel maintains the same relative (delta) between the pair of letters either side. What this means is that the two words (or more) in the solution to the puzzle must have the same relative spacing between their letters.

The diagram above shows this in pictures.

Staring with the letter "F" in FIZZY, we see that there is a delta of three letters to get to "I", then another seventeen letters to get to "Z". Since there are two letter "Z"s in a row, there is no delta, and finally to get from "Z" to the "Y" we need to step back one letter.

So now, we have an encoding for the word FIZZY, and it's +3, +17, 0, -1. (After the first letter, we go on 3 letters, then on 17, then repeat the same letter, and finally go back one). All words that appear on the barrel at the same time will have the same encoding. Computer guys like to call this a HASH FUNCTION, it's a repeatable encoding/index system.

Time for a bit of house keeping. Negative numbers can be a bother to work with, and also since there are only 26 letters in the alphabetic, if we're looking for, for instance, the letter that is +17 past the letter "T", we're going to shoot past the end!

Thankfully, both these issues can be solved by the use of Modulo-26 counting. This is analogous to the odometers of days of old. We just wrap around. If a letter goes off the end, past "Z", we simply subtract 26 and start again at the letter "A". In this way, subtracting one from a letter is really just the same as adding twenty five (going around the clock as needed).

### Encoding

One more step to go, then we have everything lined up. It is possible to work with the number chain +3, +17, 0, -1 to search for candidate words but it complicates things to have to work with more than one value (meaning it's not elegant coding).

Those blessed with some math experienced will realize that we could encode this HASH value into a single numeric field using base-26 numbers. This is a very elegant solution, and in any interview I'd give you top marks for proposing that solution.

 What I elected to do is use letters to represent my number base (can you can see it's the same thing?) In my encoding, A=0, B=1, C=2 … Z=25. (It really does not matter what encoding you use as long as it is repeatable). So for the word FIZZY, the encoding is DRAZ. All words that appear on the tumbler at the same time as FIZZY have the encoding of DRAZ. Ok, we've just turned onto finals. We download a database of words from the web, store it in our favourite database tool (I use Microsoft SQL Server), add a column for the encoding and pre-compute all the deltas values.

Now it's a simple query (fast) query to find the all rows with duplicate encoded values. "Done!"

# Results

I used a database containing approximately 170k English words. Below are the results.

### Seven Letter Soutions

I found two seven barrel solutions:

SULPHUR with PRIMERO

NOWHERE with ABJURER

### Six Letter Soutions

There are eleven six barrel solutions:

TUFFET with STEEDS

INKIER with PURPLY

MUUMUU with WEEWEE

GRUNGY with ALOHAS

BOUFFE with ANTEED

HUSHED with BOMBYX

MANFUL with THUMBS

PEPPER with LALLAN

FUSION with LAYOUT

KERNEL with GANJAH

DAWTED with SPLITS

### Five Letter Soutions

There are 93 five barrel solutions:

 HINTS and STYED DELED and STATS STEER and TUFFS TUMMY and NOGGS NONET and UVULA MOTTE and GINNY MOCHA and SUING SURGY and MOLAS ADDER and BEEFS FILLS and LORRY LOTTE and FINNY BENNI and RUDDY KNEED and FIZZY GLARY and PUJAH PULPY and VARVE PUNTY and JOHNS INGOT and CHAIN DIDOS and PUPAE CHEER and JOLLY HOTEL and OVALS GNARR and AHULL GNARL and XERIC NULLS and TARRY TASSE and HOGGS HOLLY and BIFFS TAZZE and NUTTY MUFFS and SALLY SARIN and MULCH MULES and SARKY SASSY and MUMMS MUNCH and SATIN GOLLY and MURRE GOLEM and MURKS LUFFS and RALLY RALPH and OXIME RAPHE and CLASP RATAN and VEXER VEALY and OXTER LUTEA and PYXIE TELOI and WHORL TENET and ALULA GREEN and TERRA DOLLS and WHEEL EPOCH and ALKYD CORKY and WILES WIVER and FRENA FRERE and SERER COGON and SEWED SECCO and COMMY BOURG and VIOLA BOLLS and HURRY MARRY and GULLS GULPS and MARVY OCTAD and DRIPS GULFS and MARLY MASSE and GUMMY GUNNY and MATTE APTLY and TIMER CRAAL and PENNY PERRY and CREEL CREDO and SHUTE LATTE and FUNNY LATER and SHALY LATEX and SHALE TIFFS and SHEER TIGER and PECAN RIVER and ARENA CUBED and MELON CURLY and WOLFS WOMBS and CUSHY BUFFI and HALLO HARRY and BULLS BUNNY and SLEEP BUTYL and HAZER GANJA and KERNE GASSY and SMEEK FADGE and TORUS TOUCH and FAGOT JERKY and SNATH SNEER and TOFFS SORRY and MILLS LINUM and ROTAS HERMS and DANIO EBONY and UREDO DATED and SPITS SPOTS and DAZED ECHES and KINKY JIMMY and POSSE JINNS and POTTY POTTO and JINNI BAIZA and TSARS BANJO and FERNS SETAL and AMBIT

### Four Letter Soutions

There are 331 four barrel solutions, including 15 where there are triple words on the barrel.

 DEED and ABBA and NOON BEEF and LOOP and PSST PYIC and RAKE and FOYS PAPA and JUJU and DODO NAAN and ANNA and BOOB ASCI and SKUA and MEOU EAUX and OKEH and SOIL DADO and AXAL and HEHS PREX and YANG and WYLE GLIB and JOLE and ZEBU YETI and FLAP and SYNC LANE and SHUL and PERI PERK and SHUN and LANG FUJI and APED and PETS BYRE and KHAN and SPIV