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

About these ads
Tagged with:

One Response

Subscribe to comments with RSS.

  1. James said, on 04.27.09 at 7:35 pm

    This is awesome. I’ve wanted to build a web mashup language for a long time that would use |, > to chain together calls to services/web widgets…b/c i like the simplicity.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.