Idris Raja

NPR Will Shortz word puzzle 1/16/2011, Solution on GitHub!

In github, hacking, NPR, python, word_puzzle on January 22, 2011 at 12:12 am

This week’s puzzle:

From listener Mike Shteyman of Reisterstown, Md.: Take the first seven letters of the alphabet, A through G, change one of these letters to another letter that is also either A, B, C, D, E, F or G. Rearrange the result to spell a familiar seven-letter word. What word is it?

This puzzle was an easy one to solve with Python and I don’t think I could have solved it the old-fashioned way of ‘only’ using my brain.

I’ve been attemting to solve these puzzles for a few months now, and I’ve had to write certain functions over and over, so I took the time this week to consolidate some of the more common functions I’ve used into a utility file, util.py.

I also went through the awesome Git tutorial Git Immersion, with much thanks to EdgeCase Software Artisans and Jim Weirich. With a decent grasp of the basics of Git, I decided to put all the code up on GitHub here. From now on I’ll use git for any coding I do, and I’ll probably end up hosting a bunch of it as publicly available code on GitHub.

Back to this week’s puzzle – the first step is to create all possible strings that start with ‘abcdefg’ and then swap one of those letters with a letter from the same string. We replace each character (7 total in ‘adcdefg’) with 6 possible replacements (any character expect the original one), and have a total of 42 (6*7) strings to test for anagrams.

Each of the 42 strings has one letter repeated twice. The number of arrangements/anagrams for a string of 7 characters with one repeat is 7!/2! = 2,520.

idris@idris-laptop:~/work/npr_puzzles$ python
Python 2.6.5 (r265:79063, Apr 16 2010, 13:09:56) 
[GCC 4.4.3] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import math
>>> math.factorial(7) / math.factorial(2)
2520

So there are 2,520 * 42 = 105,840 anagrams to look up in the dictionary for existence, which takes less than a second to execute.

The only answer that showed up was “feedbag”, which you can get by replacing the “c” in “abcdefg” with an “e” which gets you ‘abedefg’ which can be rearranged to “feedbag.”

The puzzle said the answer should be “a familiar seven-letter word.” I suppose “feedbag” qualifies if you, like puzzle submitter Mike Shteyman, hail from the unincorporated Maryland town of Reisterstown.

Looking forward to see if the answer is correct, next week’s puzzle, and sharing more code on GitHub!

Advertisements

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

%d bloggers like this: