anagram

#!/usr/bin/env ruby
##############################################################################################
require 'readline'
require 'set'
##############################################################################################

class NilClass
  def blank?; true; end
end

class String
  def blank?; strip == ""; end
end

class Hash
  def self.of_arrays; new {|h,k| h[k] = [] }; end
end

##############################################################################################

class Array

  #
  # Remove one instance of each letter in "letters" from the array.
  #
  # (i.e. different from "array - letters", which removes ALL copies
  #  of each letter in "letters" from the array.)
  #
  def without(letters)
    grouped = group_by { |letter| letter }

    letters.each do |letter|
      if group = grouped[letter]
        group.pop
      else
        raise "Error: tried to remove #{letter.inspect} from #{self.inspect}"
      end
    end

    grouped.values.flatten
  end

end

##############################################################################################

def time(msg)
  $stderr.print "* #{msg}..."
  start = Time.now
  yield
  $stderr.puts "done! (elapsed: %0.5f)" % (Time.now - start)
end

##############################################################################################

class Anagrammer

  attr_accessor :words, :grouped

  # todo: word frequencies so all these awful long tail
  #       three letter words don't dominate the results
  SHORTWORDS = %w[
    a in be to if in of at it ho no ye yo we
    so um uh us vs ya am he jr me mr ms oz do
    go hi id is km lb kg ow ox oh oi my ma 
    wbs bws wbn sbw ues ris sne ens ner ern nid
    eds nbw udi isu uds iru uis wid uws wus
    urs usr bre ber rus reb erb ids wud dws wds
    bur ube bes dur
  ]

  LOOKUP_TABLE_FILE = File.expand_path("~/.cache/anagram.lookup.table")

  def load_words_file(path="/usr/share/dict/words")
    return nil unless File.exist? path
    print " from #{path}"
    Enumerator.new do |y|
      open(path).each { |word| y << word }
    end
  end

  def load_wikt_file(path=File.expand_path("~/.cache/wikt/wikt.idx"))
    return nil unless File.exist? path
    print " from #{path}"
    Enumerator.new do |y|
      open(path).each { |line| y << line.split("\t").first }
    end
  end

  def initialize
    if File.exist?(LOOKUP_TABLE_FILE)
      time("Loading word lookup table from #{LOOKUP_TABLE_FILE}") do
        @grouped = open(LOOKUP_TABLE_FILE) { |f| Marshal.load f }
      end
    else
      time("Generating word lookup table") do
        @grouped = Hash.of_arrays
        @wordcount = 0
        group_proc = proc do |word|
          @grouped[word.chars.sort] << word
          @wordcount += 1
        end

        unless words = (load_wikt_file || load_words_file)
          puts "Error: couldn't find a wordlist."
          exit 1
        end

        words.
          map    { |w| w.chomp.chomp("'s") }.
          select { |w| w.size > 2 and w.upcase != w }.
          map    { |l| l.downcase }.
          each   &group_proc

        SHORTWORDS.each &group_proc

        print "\n  |_ #{@wordcount} words loaded..."
      end

      time("Saving to #{LOOKUP_TABLE_FILE}...") do
        @grouped.default_proc = nil
        File.write(LOOKUP_TABLE_FILE, Marshal.dump(@grouped))
      end if false
    end
  end

  #
  # Generates anagrams given a *sorted* array of letters
  #
  def words_from(letters)
    return to_enum(:words_from, letters) unless block_given?

    # letters = letters.sort

    letters.size.downto(1) do |n|
      letters.combination(n) do |perm| # NB: combination() thoughtfully returns the letters in sorted order! :D
        if words = @grouped[perm]
          remaining = letters.without(perm)

          words.each do |word|
            if remaining.any?
              words_from(remaining).each { |subword| yield "#{word} #{subword}" }
            else
              yield word
            end
          end
        end
      end
    end
  end

  #
  # Given a string, prints out all anagrams.
  #
  def solve!(phrase)
  IO.popen(["fzf"], "w") do |fzf|
    found  = Set.new

    # $stderr.puts "# Searching for anagrams of #{phrase.inspect}..."
    letters = phrase.downcase.scan(/\w/).sort

    words_from(letters).each do |solution|
      words = solution.split.sort
      unless found.include? words
        found.add(words)
        fzf.puts solution
      end
    end

    fzf.puts
  end
  rescue Errno::EPIPE
    # STDOUT was closed before execution completed
    exit 74 # EX_IOERR
  rescue Interrupt
    $stderr.puts "Interrupted"
  end

end

##############################################################################################

if $0 == __FILE__
  anagrammer = Anagrammer.new

  if ARGV.any?
    phrase = ARGV.join(" ")
    anagrammer.solve!(phrase)
  end

  if $stdout.isatty
    loop do
      puts "Enter another anagram (or hit ENTER to exit)"
      phrase = Readline.readline("> ", true)
      exit if phrase.blank?
      anagrammer.solve!(phrase)
    end
  end
end