Brute-Forcing a Word Puzzle

draft.md

All this week, I've been trying to chip away at Allen R. Morgan's "Twice Removed" puzzle on page 50 of the August 5, 2012 New York Times Magazine. The rules:

For each word below, add the same pair of letters *twice* 
to complete a longer word. For example, if you were given 
MOTE, you would add ON twice to make MONOTONE.

After a few days, I'd found just four of the 24 words. Pathetic. After moping for a bit, I tried brute-forcing the answers. The strategy was simple, but radically different from how you or I would try solving the puzzle by hand. The steps:

1. Get a big list of English words.

2. Select all the words with four more letters than the length of the starting words. E.g., eight-letter words if we're starting with four-letter words.

3. Select the subset of the words from Step 2 that include doubled letter-pairs. In code, this meant words that match this regular expression: /(..).+(\1)/

4. For each of the words from Step 3, subtract the matching letter-pairs.

5. For each of the words from Step 4, see if the shorter version is a real English word — or one of the puzzle's starting words.

The mini-program, written in Ruby, is below. I'm a Ruby novice and wrote the script in haste, so there's plenty of room for improvement. (If you have a better version, send it to me and I'll merge it.)

So, did it work? Pretty much. Using the "12dicts" word list (specifically, the "2of12inf" sublist), the program found 12 of the 14 main four-letter starting words. It even found that two of those words had multiple answers: rise leads to both porpoise and tortoise; and cant leads to both decadent and recreant.

(The answers to two of the 24 starting words, calm and alter, are supposed to lead to "common two-word phrases". I'm leaving these out.)

The program solved only half of five-letter words, but aced the single six-letter and eight-letter words. The full results are below.

BONUS: The program also uncovered some starting words the puzzle didn't use. Try your hand at these:

• cafe
• veer
• nest
• male
• unit
• tong

nytimes-list.txt

lore
hero
cant
sure
sell
kine
peon
lice
alti
rise
link
lira
imam
fone
fence
conic
nurse
vales
retag
stamp
derate
thetical

results.txt

ruby solve.rb --starting-length 4 --dictionary /Users/jsvine/Downloads/12dicts-5.0/2of12inf.txt --starting-words nytimes-list.txt 

Results for 4-letter words -> 8-letter words.
Dictionary: /Users/jsvine/Downloads/12dicts-5.0/2of12inf.txt
12501 with 8 letters
632 with letter-pair doubling
14 with legitimate de-doubled versions

kine -> alkaline
sell -> baseball
cant -> decadent
imam -> flimflam
fone -> footnote
hero -> homeroom
lice -> lenience
lore -> licorice
lira -> literate
alti -> mealtime
rise -> porpoise
cant -> recreant
sure -> saturate
rise -> tortoise

---

ruby solve.rb --starting-length 5 --dictionary /Users/jsvine/Downloads/12dicts-5.0/2of12inf.txt --starting-words nytimes-list.txt 

Results for 5-letter words -> 9-letter words.
Dictionary: /Users/jsvine/Downloads/12dicts-5.0/2of12inf.txt
11623 with 9 letters
903 with letter-pair doubling
3 with legitimate de-doubled versions

nurse -> concourse
fence -> reference
vales -> rivalries

---

ruby solve.rb --starting-length 6 --dictionary /Users/jsvine/Downloads/12dicts-5.0/2of12inf.txt --starting-words nytimes-list.txt 

Results for 6-letter words -> 10-letter words.
Dictionary: /Users/jsvine/Downloads/12dicts-5.0/2of12inf.txt
9694 with 10 letters
1094 with letter-pair doubling
1 with legitimate de-doubled versions

derate -> derivative

---

ruby solve.rb --starting-length 8 --dictionary /Users/jsvine/Downloads/12dicts-5.0/2of12inf.txt --starting-words nytimes-list.txt 

Results for 8-letter words -> 12-letter words.
Dictionary: /Users/jsvine/Downloads/12dicts-5.0/2of12inf.txt
5124 with 12 letters
1170 with letter-pair doubling
1 with legitimate de-doubled versions

thetical -> mathematical

solve.rb

require './libs/trollop' # http://trollop.rubyforge.org/
opts = Trollop::options do
	opt :starting_length, "Number of letters in the short words.", :default => 4
	opt :dictionary, "Path to the dictionary file to use.", :default => "/usr/share/dict/words"
	opt :starting_words, "[optional] Path to file of specific starting words to solve.", :type => String
end

DOUBLING_PATTERN = /(..).+(\1)/
NEWLINE_PATTERN = /[\n\r]+/

dict = File.read opts[:dictionary] 
words = dict.downcase.split NEWLINE_PATTERN

puts "Results for #{opts[:starting_length]}-letter words -> #{opts[:starting_length] + 4}-letter words."
puts "Dictionary: #{opts[:dictionary]}"

longer_words = words.select { |w| w.length == opts[:starting_length] + 4 }
puts "#{longer_words.length} with #{opts[:starting_length] + 4} letters"

shorter_words = if opts[:starting_words]
		File.read(opts[:starting_words]).split NEWLINE_PATTERN
	else
		words.select { |w| w.length == opts[:starting_length] }
	end

has_doubling = longer_words.select { |w| not (w =~ DOUBLING_PATTERN).nil? }
puts "#{has_doubling.length} with letter-pair doubling"

matches = has_doubling.map do |w|
	doubled_letter = w.scan(DOUBLING_PATTERN)[0][0]
	sans_doubling = w.gsub(doubled_letter, "")
	shorter_words.include?(sans_doubling) ? "#{sans_doubling} -> #{w}"  : nil
end.compact

puts "#{matches.length} with legitimate de-doubled versions"

puts matches

I like your brute force method: I had been trying to craft a regular expression to run against a dictionary file but ended up getting stymied. I'll have to see if I can dust it off and make it work...

I see you are using regular expressions. What I meant is that I was trying to find the solution for a given word using a single regular expression match.