How I used my Mac to beat my dad at the New York Times six for a spell puzzle

The rules for the game are simple: make as many six-letter words as possible, tracing a direct path. You may use a letter more than once — but not twice in a row.

They say, "Finding 12 words is good; 22 is excellent; 32 is genius."

Will Shortz and the Times's answer list had 37 words.

Six For A Spell NYTimes Puzzle
The New York Times Magazine, Puzzle section.
Sunday, December 18, 2016.

I started off playing by the rules.

I traced words slowly. I came up with 13 before my impatience got the best of me. Then, I decided to write a computer program to help me.

I figured I could make a list of all of the two-letter chains. That wouldn't take long. For example, if you look at the puzzle at the top of the page, there's "IC", "IA", "IN", and "IT". Then "CI, CA, CO, CE". And so forth.

Then, I could chain together all possible six-letter length combinations of two-word combination, making sure that I only appended another chain if the last letter of the previous chain was the first letter of the new chain.

Then, I could filter all my six-letter combinations to see which words were actually in the dictionary.

Here's the code.

require 'pry'
require 'set'

found_words = Set.new

words =  ["ic", "ia", "in", "it", "co", "ce", "ca", "ci", "ac", "ae", "ad", "an", "ei", "ni", "nd", "no", "nt", "to", "tp", "tn", "ti", "ec", "eo", "er", "ed", "ea", "de", "dr", "de", "dp", "do", "dn", "da", "od", "oe", "op", "ot", "on", "oe", "or", "ol", "ro", "re", "rl", "rd", "re", "er", "el", "ep", "eo", "ed", "po", "pe", "pl", "pt", "lo", "lr", "le", "lp","dl","ld"]


dict = Set.new
File.open("/usr/share/dict/words") do |file|
  file.each do |line|
    dict.add line.strip
  end
end



words.each do |word_i|
  words.select{|word| word[0] == word_i[1]}.each do |word_j|
    words.select{|word| word[0] == word_j[1]}.each do |word_k|
      words.select{|word| word[0] == word_k[1]}.each do |word_l|
        words.select{|word| word[0] == word_l[1]}.each do |word_m|
          words.select{|word| word[0] == word_m[1]}.each do |word_n|

            new_word = word_i[0] + word_j[0] + word_k[0] + word_l[0] + word_m[0] + word_n[0];
            found_words.add new_word if dict.include? new_word;

          end

        end
      end
    end
  end
end


puts found_words.to_a.sort

But it's not a perfect solution

Let's run through the problems:

  • The code isn't beautiful
  • The code allows chains that couldn't be traced on the board because in the puzzle, the same letter can appear multiple times in disparate locations

In other words, if I wrote that kind of code in a Google interview, I would be thrown out of the building.

But let's run through the pragmatics:

  • I wrote the code itself in 5-10 minutes
  • Manually running through the list and eliminating the words that were constructed through unnaturally connected chains only took 5-10 minutes
  • I generated 56 words, including two words that were not in my computer's dictionary ("canoer" and "canoed")

Here's a better solution

I posted this thread on Reddit, and /u/Thoth2000 contributed a substantial improvement.

open Batteries

module Graph = Map.Make(Char)
module Dict = Set.Make(String)

let graph =
  let (=>) x y = (x, y) in
  Graph.of_enum @@ List.enum [
    'c' => "iaeo";
    'i' => "cant";
    'a' => "cinde";
    'e' => "cadro";
    'o' => "cerl";
    'n' => "iadOt";
    'd' => "aerEOn";
    'r' => "lEdeo";
    't' => "inOp";
    'O' => "tndEp";
    'E' => "pOdrl";
    'l' => "orEp";
    'p' => "tOEl";
  ]

let dict = File.lines_of "sowpods.txt"
  |> Enum.map String.lowercase |> Dict.of_enum

let rec traverse depth str words =
  if depth = 6 then begin
    let word = String.lowercase str in
    if Dict.mem word dict then Dict.add word words else words
  end else
    let chars = Graph.find str.[0] graph in
    String.fold_left (fun w ch ->
      traverse (depth+1) (String.of_char ch ^ str) w) words chars

let () =
  Enum.fold
    (fun words ch -> traverse 1 (String.of_char ch) words)
    Dict.empty
    (Graph.keys graph)
  |> Dict.iter print_endline

This code properly traverses the graph (using upper- and lowercase to distinguish between the two instances of "o" and "e") and uses the SOWPODS Scrabble dictionary (download the official Scrabble dictionary as a txt file here!) instead of /usr/share/dict/words (which contains a few non-words).

OCaml programmers tend to be talented.

Curious about the words?

Click on one to learn its definition

  • acacin
  • acinic
  • acorea
  • adonin
  • adorer
  • adread
  • anotia
  • antiae
  • candle
  • canoer
  • canoed
  • cantic
  • canton
  • cedrol
  • cicada
  • cinder
  • colder
  • colpeo
  • corded
  • cordel
  • corder
  • cordon
  • dander
  • dandle
  • danton
  • deader
  • decade
  • decani
  • decant
  • decode
  • ecanda
  • eroded
  • intoed
  • lepton
  • niacin
  • nicolo
  • notice
  • odored
  • otiant
  • otitic
  • pedant
  • people
  • peptic
  • podeon
  • podler
  • ponder
  • pontic
  • pontin
  • ponton
  • ptotic
  • reader
  • recant
  • recede
  • record
  • reread
  • tinder
  • titian
  • topepo

All's well that ends well

My dad did get a good laugh once I showed him this post prior to publishing.

In the world of software engineering and full-time employment software programming, you are most often interviewed and assessed on your abilities to solve problems with algorithmic correctness.

In the world of consulting, you are charged with delivering business value in order to resolve your client's problems and improve their business. The 80/20 rule almost always applies: 80% of your benefit comes from 20% of your actions.

Not sure yet?

Download the free chapter on Legal Ideas, and then join our mailing list.
Get the chapters on "Finding Clients" and "Communication" for free.