Letter Boxed solver

solve.rb

require 'tempfile'

WORDS_FILE = 'words.txt'.freeze
SOLUTIONS_FILE = 'solutions.txt'.freeze

def unique_letters_for_words(words)
  words.join.split('').uniq.sort.join
end

# Ex: verify_solution_against_puzzle(['DISTURB', 'BLACKJACK'], ['JLI', 'CUD', 'BTK', 'ASR'])
def verify_solution_against_puzzle(solution_words, puzzle_sides)
  if (unique_letters_for_words(solution_words) != unique_letters_for_words(puzzle_sides))
    fail 'Invalid solution for puzzle'
  end

  letters = solution_words.join.split('')
  letters.each_with_index do |letter, i|
    next if i == 0

    # Trusting this is only possible for first letters of subsequent words
    next if letter == letters[i-1]

    side = puzzle_sides.find { |s| s.include?(letter) }
    return false if side.include?(letters[i-1])
  end

  true
end

# Populate eligible word hash
# >= 3 letters, no repeat letters
def seed_word_hash!(h)
  File.open(WORDS_FILE).each_line do |line|
    word = line.chomp

    next unless word.length >= 3
    letters = word.split('')
    next unless letters.each_with_index do |letter, i|
      next if i == 0
      break false if letter == letters[i-1]
      break true if i == word.length - 1
    end

    h[word[0]] ||= []
    h[word[0]] << word
  end

  # Sort each letter's words by length (descending) as optimization
  h.each do |k, words|
    h[k] = words.sort_by(&:length).reverse
  end
end

def seed_solution_pairs!(word_hash, solution_hash)
  word_hash.each do |_k, words|
    last_length = 0
    words.each do |word1|
      word_hash[word1[-1]].each do |word2|
        # Risky assumption: every puzzle has a solution < 17 letters
        next unless word1.length + word2.length < 17

        break unless word1.length + word2.length >= 13

        unique_letters = unique_letters_for_words([word1, word2])
        if unique_letters.length == 12
          solution_hash[unique_letters] ||= []
          solution_hash[unique_letters] << [word1, word2]
        end
      end
    end
  end
end

def write_solution_pairs_to_file!(solution_hash)
  File.open(SOLUTIONS_FILE, 'w') do |file|
    solution_hash.each do |unique_letters, solutions|
      solutions.each do |solution|
        file.write([unique_letters, solution[0], solution[1]].join(' '))
        file.write("\n")
      end
    end
  end
end

def load_solution_pairs_from_file!(puzzle_sides)
  h = {}

  Tempfile.create('solutions') do |tempfile|
    tempfile.write(`grep -e ^#{unique_letters_for_words(puzzle_sides)} #{SOLUTIONS_FILE}`)
    tempfile.rewind

    tempfile.each_line do |line|
      words = line.chomp.split(' ')
      h[words[0]] ||= []
      h[words[0]] << [words[1], words[2]]
    end
  end

  h
end

def solve!(puzzle_sides)
  t0 = Time.now

  if (File.exist?(SOLUTIONS_FILE))
    puts 'Loading solution pairs from file...'
    solution_pairs_by_unique_letters = load_solution_pairs_from_file!(puzzle_sides)
    t2 = Time.now
    puts "...done (#{(t2 - t0).round(2)} seconds)\n"
  else
    puts 'Seeding dictionary...'
    word_hash = {}
    seed_word_hash!(word_hash)
    t1 = Time.now
    puts "...done (#{(t1 - t0).round(2)} seconds)\n"

    puts 'Seeding solution pairs...'
    solution_pairs_by_unique_letters = {}
    seed_solution_pairs!(word_hash, solution_pairs_by_unique_letters)
    write_solution_pairs_to_file!(solution_pairs_by_unique_letters)
    t2 = Time.now
    puts "...done (#{(t2 - t1).round(2)} seconds)\n"
  end

  pairs = solution_pairs_by_unique_letters[unique_letters_for_words(puzzle_sides)]
  matches = []

  print "Finding solutions from #{pairs.count} matching pairs"
  if ENV['DEBUG']
    print " (#{pairs.map { |pair| pair.join(' ') }.join(', ')})"
  end
  puts '...'

  pairs.each do |pair|
    if verify_solution_against_puzzle(pair, puzzle_sides)
      matches << pair
    end
  end

  t3 = Time.now
  puts "...done (#{(t3 - t2).round(2)} seconds)\n"

  puts "#{matches.count} matches found:"
  matches.each do |m|
    puts m.join(' ')
  end
end

solve!(ARGV)