Puzzling

Nov 11 2013

A few weeks back, I took some time off for a bit of recharging. That gave me some time to do things that might normally get prioritized out of my schedule, like familiarizing myself with other growing startups in the Atlanta area. I set out reading a number of startup blogs when I stumbled across one with a coding puzzle. I read the description and actually closed the tab quickly. I am not a huge fan of puzzles but when in the right mood (and when not constrained by time), I'm susceptible to the DOS attack they can impose on the analytical mind. I almost escaped too, but I had read just enough to think to myself, “oh, that looks like a constraint propagation problem.” That’s when I gave in and just returned to the puzzle; I knew I had been hooked.

To be honest, I'm not particularly good at puzzles but after conducting hundreds of technical interviews in my career, I've become fascinated with how the mind is able to start at "wut?" but eventually end up at a mental model that leads to a solution. Watching people work through my interview questions, I noticed that the first approach that most people take is usually based on a prior experience with a different, but similar problem. Sadly, I also noticed there is a bias toward more recent prior experiences. If the candidate has insertion sort on the brain because of something they did last week, it can be really hard to NOT see a problem as related to insertion sort. Personally, I think many people can discard those biases if given more time. Sadly, more time is something you are rarely at liberty to give in an interview situation. The fact that I had immediately jumped to constraint propagation was fascinating to me. Why had my mind decided to start there? I ended up writing the code partly to see if my initial approach was even sound but also as a kind of self-revenge for all those poor people I've interviewed. (Just to be clear, though, I never asked puzzlers during interviews.)

The problem

There is a backstory here about a puzzle party, but I’ve skipped all that since, you know, this all happened on my week off. Here is the TL;DR version of the problem instead.

We have ten separate lists of symbols.

[:club, :star, :grapes, :seven, :seven] [:cherry, :crown, :spade, :heart, :star] [:club, :horseshoe, :grapes, :bar, :star] [:bell, :cherry, :club, :seven, :grapes] [:horseshoe, :dollar, :club, :diamond, :bar] [:cherry, :diamond, :cherry, :club, :star] [:bar, :horseshoe, :spade, :grapes, :club] [:crown, :diamond, :cherry, :club, :heart] [:spade, :crown, :club, :grapes, :bell] [:seven, :club, :star, :diamond, :bar]

We need to find a way to map each symbol (13 in all) to a unique character such that each of these lists represents a valid word in the North American Competitive Scrabble Word List.

Initial Thoughts

As I mentioned earlier, I quickly realized this problem could be thought of as a Constraint Satisfaction Search. In fact, the whole thing reminded me of a famous piece written by Peter Norvig several years ago about Solving Every Sudoku Puzzle. What I mean by this is that we will have to cover a search space of considerable size, but there are inherit constraints in the way the problem is structured that will allow us to easily eliminate the vast majority of the possibilities without even checking them. As an example, let us say I want to take an approach where I consider every permutation of 5-letter words in the word list. That’s a lot of checking. I would need to do around a whopping 10^32 checks. That number is way bigger than a bread box. But let’s look closer at how we can cheat. As part of the search we will need to, for instance, consider whether the word “glass” works for the first list of symbols. In order for [ :club, :star, :grapes, :seven, :seven ] to map to “glass”, it must be true that :club is “g”, :star is “l” and so on. Propagating these constraints forward as we search means that our search space collapses very quickly. Just considering the constraints imposed by picking a value (“glass”) for the first list of symbols, the possibilities for the third list of symbols ([ :club, :horseshoe, :grapes, :bar, :star ]) reduces from 8938 possibilities to 2 ("gnarl" and "grail").

Representation

It only took me only a few minutes to determine the basic high level approach that I wanted to take, but thinking about the data structures was a bit more involved. The key question I need answered by my choice of data structure is of the form: If [:club, :star, :grapes, :seven, :seven] is "three" and [:cherry, :crown, :spade, :heart, :star] is "flush", can [:club, :horseshoe, :grapes, :bar, :star] be "funky"?

Thinking about this as assignment makes this easy as we need only a pair of dictionaries to keep track of the symbol <=> character mappings that result from the assignment. The next assignment in the search simply accumulates its associated mappings into the same pair of dictionaries. Detecting invalid assignments is also trivial as we simply watch for conflicts when we merge our dictionaries. And lo and behold, if you cover all the rules without any conflicts we have ourselves a solution.

"three"
{ :club   <=> 't',
  :star   <=> 'h',
  :grapes <=> 'r',
  :seven  <=> 'e' }
  
+
"flush"
{ :club   <=> 't',
  :star   <=> 'h',
  :grapes <=> 'r',
  :seven  <=> 'e',
  :cherry <=> 'f',
  :crown  <=> 'l',
  :spade  <=> 'u',
  :heart  <=> 's',
  :star   <=> 'h' }
  
+
"funky"
{ :club   <=> 't',
  :star   <=> 'h',
  :grapes <=> 'r',
  :seven  <=> 'e',
  :cherry <=> 'f',
  :crown  <=> 'l',
  :spade  <=> 'u',
  :heart  <=> 's',
  :star   <=> 'h',
  :club   <=> 'f' }
  

Initial Constraints

Having now formulated this problem as one of constraint satisfaction, it was clear that a number of constraints could be enforced before the searching even begins. This pruning is important as it removes search space that would have to be repeatedly eliminated. That would be wasteful and slow. Before any pruning, there were 8938 possible assignments for each of the 10 lists of symbols but there were two sets of constraints that were pretty straight forward.

The first was simply to eliminate any words that could not be assigned to the list of symbols at all. [ :club, :star, :grapes, :seven, :seven ], for instance, requires a double letter suffix which rules out a lot of assignments. That pass lopped off a significant number of possible assignments.

[ :club, :star, :grapes, :seven, :seven ]
160
[ :cherry, :crown, :spade, :heart, :star ]
5,839
[ :club, :horseshoe, :grapes, :bar, :star ]
5,839
[ :bell, :cherry, :club, :seven, :grapes ]
5,839
[ :horseshoe, :dollar, :club, :diamond, :bar ]
5,839
[ :cherry, :diamond, :cherry, :club, :star ]
209
[ :bar, :horseshoe, :spade, :grapes, :club ]
5,839
[ :crown, :diamond, :cherry, :club, :heart ]
5,839
[ :spade, :crown, :club, :grapes, :bell ]
5,839
[ :seven, :club, :star, :diamond, :bar ]
5,839

For the next set of initial constraints, I considered the character positions where a symbol appears to eliminate some more impossible assignments. Consider that :star appears in the second, third and fifth positions. That means that :star can only be assigned something in the intersection of characters found in the second, third and fifth character positions of all possible words. After filtering out the assignments that missed the boat on this set of constraints, things are looking pretty good for search.

[ :club, :star, :grapes, :seven, :seven ]
134
[ :cherry, :crown, :spade, :heart, :star ]
3,633
[ :club, :horseshoe, :grapes, :bar, :star ]
3,218
[ :bell, :cherry, :club, :seven, :grapes ]
2,708
[ :horseshoe, :dollar, :club, :diamond, :bar ]
4,715
[ :cherry, :diamond, :cherry, :club, :star ]
144
[ :bar, :horseshoe, :spade, :grapes, :club ]
5,083
[ :crown, :diamond, :cherry, :club, :heart ]
4,892
[ :spade, :crown, :club, :grapes, :bell ]
4,631
[ :seven, :club, :star, :diamond, :bar ]
1,633

Putting it all together

The original blog post was written in ruby. Besides a few Rakefiles, I had not written any ruby in about 8 years but I figured it was worth a try. Plus, I discovered that someone went and added eachwithobject to the core libraries since my last ruby adventure. That's pretty helpful.

The result is a bit terse, but not so bad.

And running it gives us…

./solve.rb:129:in `block (2 levels) in <main>': undefined method `[]=' for nil:NilClass (NoMethodError)

Dammit, I mean ... running it gives us...

Solution threficaolusn club => t [:club, :star, :grapes, :seven, :seven] => three star => h [:cherry, :crown, :spade, :heart, :star] => flush grapes => r [:club, :horseshoe, :grapes, :bar, :star] => torch seven => e [:bell, :cherry, :club, :seven, :grapes] => after cherry => f [:horseshoe, :dollar, :club, :diamond, :bar] => ontic diamond => i [:cherry, :diamond, :cherry, :club, :star] => fifth bar => c [:bar, :horseshoe, :spade, :grapes, :club] => court bell => a [:crown, :diamond, :cherry, :club, :heart] => lifts horseshoe => o [:spade, :crown, :club, :grapes, :bell] => ultra crown => l [:seven, :club, :star, :diamond, :bar] => ethic spade => u heart => s dollar => n Solution threficaolusp club => t [:club, :star, :grapes, :seven, :seven] => three star => h [:cherry, :crown, :spade, :heart, :star] => flush grapes => r [:club, :horseshoe, :grapes, :bar, :star] => torch seven => e [:bell, :cherry, :club, :seven, :grapes] => after cherry => f [:horseshoe, :dollar, :club, :diamond, :bar] => optic diamond => i [:cherry, :diamond, :cherry, :club, :star] => fifth bar => c [:bar, :horseshoe, :spade, :grapes, :club] => court bell => a [:crown, :diamond, :cherry, :club, :heart] => lifts horseshoe => o [:spade, :crown, :club, :grapes, :bell] => ultra crown => l [:seven, :club, :star, :diamond, :bar] => ethic spade => u heart => s dollar => p Done ... 1.584249 sec

Clearly, the plan to throw away most of the search space had a significant payoff. In fact, the search is able to cover the whole of the search space by checking only 140,261 possible solutions. That fits pretty nicely in a breadbox. This seems to me a perfectly good way to solve this problem, but again, I fixated on a constrained search pretty quickly. Maybe it works pretty well, but I may have still missed something obvious ... or not so obvious.

The creative pattern matching that goes into finding a solution to a puzzler like this continues to be a mystery to me. I know my general strategy is to get the problem in my head and then leave the computer. I solve problems like this on walks or runs. I think one of the benefits of getting away from the keyboard is it takes away the ability to act on an approach too quickly. As I think back on the interviews I conducted, I think this is one of the big mistakes. The artificial time pressure and the inability to disengage from the social situation never allowed candidates a few minutes to just stare at the problems in their heads. In the end, this was a pretty fun puzzler even for someone that doesn't really enjoy puzzles. But from now on, I'm not reading any more startup blogs on my week off.