five by five, redux - blacksmith gunpowdery II

5x5.rb

#!/usr/bin/ruby
# (c) 2021 stephan.com
# Find to N words of M letters, all unique
#
# No five-letter/five-word set exists, but there is a single
# result for two words of ten letters: blacksmith gunpowdery

require 'Set'
require 'progress_bar'

DICTIONARY_PATH = '/usr/share/dict/words'.freeze
WORDS_COUNT = 2
WORD_LENGTH = 10

@bar = ProgressBar.new
@compare_matrix = Hash.new { |hash, key| hash[key] = Set.new }
@results = []

# patches to string
class String
  def disjoint?(other)
    (chars & other.chars).empty?
  end

  def chars_uniq?
    chars.uniq == chars
  end
end

def dictionary
  @dictionary ||= File.readlines(DICTIONARY_PATH)
                      .map(&:strip)
                      .map(&:downcase)
                      .select { |word| word.length == WORD_LENGTH && word.chars_uniq? }
end

# sentence is an array of the words so far
def find_words(okwords = dictionary, sentence = [])
  @bar.increment! if sentence.length == 1
  @results << sentence.join(' ') and return if sentence.length >= WORDS_COUNT

  okwords.map { |word| sentence + [word] }.each do |new_sentence|
    find_words(new_sentence.map { |w| @compare_matrix[w] }.reduce(:&), new_sentence)
  end
end

# for each word, construct a list of words that have no common characters
def build_table
  @bar.max = dictionary.count
  @bar.puts 'building table.'
  wordlist = dictionary.dup

  until wordlist.empty?
    @bar.increment!
    word = wordlist.shift
    wordlist.each do |other|
      @compare_matrix[word] << other if word.disjoint?(other)
    end
  end

  @bar.puts 'table complete'
  @bar.count = 0
end

if WORDS_COUNT * WORD_LENGTH > ('a'..'z').count
  raise "Impossible to find #{WORDS_COUNT} words of #{WORD_LENGTH} unique characters"
end

build_table
find_words

puts "Found #{@results.count} result(s)"
@results.each { |r| puts r }

I was looking at the original version of this, written 14 years ago, and wanted to see how much I'd learned since then.

In addition to being a bit shorter, this version includes a progress bar (don't forget gem install progress_bar) and appears to be much faster, at least for the 2x10 case, which took 25.3 seconds on my machine in the original version, and now runs in 6.6 seconds. So about 4x faster, though i suspect most of that is building the table.

If I were really doing this right, I'd wrap it all in a class, give it command line options, etc, etc, but this is enough for a small exercise.

timing for the 5x5 test returning zero results: 13160 seconds == 3 hours 40 minutes. I don't have anything to compare that to, though.