Two Guys Arguing

my word shift solution

Posted in challenge by youngnh on 04.14.09

I’m a bit obsessed with the unix programs tr, uniq, sort and paste after reading Unix for Poets in college, and Ben’s problem falls very nicely into the category of problems that these programs solve effortlessly.

The basic algorithm I decided to implement is plain-english simple: take a dictionary of words, transform all of them by shifting their characters and then removing any words that are no longer in that same dictionary.

Step 1: Move characters to the right. The unix program tr does nothing but this:

tr 'qwertyuiop' 'wertyuiop['

will translate just the first row of characters

tr 'qwertyuiopasdfghjklzxcvbnm1234567890' 'wertyuiop[sdfghjkl;xcvbnm,234567890-'

Each letter in tr‘s first argument gets replaced with the corresponding letter in the second argument.  The above command will shift all three rows of letters and the top row of number keys.  I’m going to write a truncated version for the rest of the post to save me some typing.

Step 2: Remove any words that aren’t in the dictionary.  For this step, I used cat to append the list of actual words to our list of translated words, like so:

cat dict | tr 'qwerty' 'wertyu' | cat - dict

Once you have a big long list of words and non-words, you want to sort them all which has the effect of putting any actual words created by shifting right next to a real word from the dictionary file.  The program uniq has a flag to print only duplicates that appear in its input.

cat dict | tr 'qwerty' 'wertyu' | cat - dict | sort | uniq -d

That’s it, go make yourself a drink.

Well….its kinda hard to look at that list and be confident that our little unix one-liner did its job.  (bb? is that even a word?) It would help a great deal if we could see what original hand positions were translated to form these new words. In other words, what words did we think we were typing?  To do this, I’d like to take our shifted words file, shift them back and then display both lists side by side.

To redirect output to a file, we use >.  To shift back we’ll use tr again and finally for the side by side display we’ll use paste.  You can swap the arguments to tr and that will take care of the leftward shift.
Our full program then becomes:

cat dict | tr 'qwerty' 'wertyu' | cat - dict | sort | uniq -d > shifted.txt
cat shifted.txt | tr 'wertyu' 'qwerty' | paste - shifted.txt

Simple. On my modest machine, this runs over a 120K dictionary just under 3 seconds. Some of my favorites:

sweet -> derry
waxier -> escort
awed -> serf
dye -> fur
gust -> hidy
rust -> tidy
tyer -> yurt

Tagged with:
Follow

Get every new post delivered to your Inbox.