VERY SLOW

anagrams_280.rb

require 'set'

# monkey path String for simplicity and readability
class String
  def normalized
    # replace all non-alphabet characters with nothing
    downcase.gsub(/[^[:alpha:]]/, '')
  end

  def anagram_id
    char_counts = {}

    # when working out combination difference from string anagram_id
    # the resulting hash is keyed by symbol
    normalized.chars.map(&:to_sym).each do |char|
      if char_counts[char].nil?
        char_counts[char] = 1
      else
        char_counts[char] += 1
      end
    end

    char_counts
  end
end

# hash of words keyed by their anagram_id for determining equality
WORDS = File.read('enable1.txt')
  .split("\n")
  .map { |line| line.delete "\r" }
  .reduce({}) do |result, word|
    result.tap do
      if result[word.anagram_id]
        result[word.anagram_id].push word
      else
        result[word.anagram_id] = [word]
      end
    end
  end

class Anagram
  attr_reader :input

  def initialize(str)
    @input = str
  end

  def self.match(anagram_id)
    WORDS.fetch(anagram_id, [])
  end

  def matches
    # resulting array might include input
    # so should filter out
    return Anagram.match(input) if input.size <= 4

    result = []

    largest_perm_size = (input.size.even? ? (input.size / 2) : ((input.size / 2) + 1))
    range = 3..largest_perm_size

    combinations(range)
      .map { |pair| pair.map(&Anagram.method(:match)) }
      .reject { |(left, right)| left.empty? || right.empty? } # no match for either side means not an anagram
      .each do |pair|
        # ensure iterating from largest matched collection
        small, large = pair.sort_by(&:size)

        large.each do |word|
          small.each { |other_word| result.push "#{word} #{other_word}" }
        end
      end
    
    result
  end

  def combinations(range)
    result = []

    range.each do |size|
      puts "checking #{size}"
      combs = input.chars
        .permutation(size) # no guarantee for the order in which yielded; assume unordered
        .map { |combination| combination.join.anagram_id }
        .to_set # although permutations will be unique, they might produce duplicate anagram_id
      
      puts "Combination size: #{combs.size}"
      combs.each do |left|
        difference = input.anagram_id.to_a - left.to_a
        pair = [left, Hash[difference]]

        # only an issue for strings of even length
        in_result = result.include?(pair) || result.include?(pair.reverse)

        result.push pair unless in_result
      end
    end

    result
  end
end

require 'pry'
pry