From: Paolo Negri <hungrylist@...>
Date: 2007-02-05T00:19:30+09:00
Subject: Re: String Equations (#112)

here's my solution for this quiz
It's quite slow, so you may want to tweak LENGTH_LIMIT constant to
have the script running in a reasonable time.
If you want to use this script to find equations for all the terms in
wikipedia you may want to look at some other solution.
It should behave as required from the original quiz.
I don't think it respects all the rules added after the original quiz
requirement :)

With this word list

bici
bwu
ha
bwuhahahahahaha
boci
cibo
bibo
bocibici
bibobici
ci
bo

produces 166 equations

Any comment is really welcome. Thanks for the fun.

#!/usr/bin/env ruby
require 'set'
words = $stdin
#a version of hash that supports + - / %
class AlgHash < Hash
  def initialize(default = 0)
    super(default)
  end
  def keys
    super.to_set
  end
  alias len length
  %w(+ - % /).each do |sign|
    eval <<-END_EVAL
      def #{sign}(other)
        res = AlgHash.new
        total_keys = self.keys + other.keys
        total_keys.each {|k| res[k] = self[k] #{sign} other[k]}
        res
      end
    END_EVAL
  end
  def base?(other)
    other = other.signature unless other.respond_to? :keys
    return false unless self.keys == other.keys
    res = other % self
    if res.values.uniq == [0]
      if (multiplier = (other / self).values.uniq).size == 1
        multiplier.first
      end
    end
  end
end
#some utility modules we want for our special version of string
#and for Arrays
#we want to have some methods used in Set available for arrays and string
module SpecComp

  def multiple?(other)
    return false unless (self.len % other.len) == 0
    if (self.signature % other.signature).values.uniq == [0] &&
      (multiplier = (self.signature / other.signature).values.uniq).size == 1
      multiplier.first
    else
      false
    end
  end

  def base?(other)
    other.multiple?(self)
  end

  def minus(other)
    (self.signature - other.signature).delete_if {|k, v| v == 0}
  end


  %w(subset? superset? intersection).each do |comp_method|
    eval <<-END_EVAL
      def #{comp_method}(other)
        return self.origin.send("#{comp_method}", other.origin)
      end
    END_EVAL
  end

end
#a rich indexed version of string
#every string is lowercase and non alphanumeric chars are stripped
#every string has a signature which is hash with letters as keys and number
#of occurrences of the letter as values
#some arithmetics is possible on the signature of the strings
#the string reply to some Set class method that will be useful when we'll
#compare string groups
class HashedString
  attr_accessor :signature, :origin, :len
  include SpecComp
  def initialize(string)
    @signature = AlgHash.new
    sane_string = string.downcase.unpack('c*')
    sane_string.delete_if {|c| c < 49 || c > 122}
    sane_string.each {|c| @signature[c] = @signature[c] + 1}
    @len = sane_string.length
    @sym = sane_string.pack('c*').to_sym
    @origin = [@sym].to_set
  end

  def ==(other)
    self.signature == other.signature && self.origin != other.origin
  end

  def +(other)
    [self] + other
  end

  def *(integer)
    ret = []
    integer.times {ret += self}
    ret
  end

  def to_s
    return "\"#{@sym.to_s}\""
  end

  def to_ary
    [self]
  end

  def to_sym
    @sym
  end
end
#Array have signature too
class Array
  include SpecComp
  def to_s
    (self.map {|w| w.to_s}).join(' + ')
  end
  def signature
    @signature ||= self.inject(AlgHash.new) {|sum, element| sum +
element.signature}
  end
  def origin
    @origin ||= (self.map {|element| element.to_sym}).to_set
  end
  def len
    @len ||= self.inject(0) {|len, element| len + element.len}
  end
end
#the anagram finder
#LENGTH_LIMIT is necessary if you don't want your PC busy for years
class EquationFinder
  LENGTH_LIMIT = 1000
  attr_reader :success
  def initialize(words_list)
    @words_list = words_list.to_a.map! {|w| HashedString.new(w)}
    @search_hash = Hash.new() {|h, k| h[k] = []}
      @words_list.each_with_index do |word, index|
      @search_hash[word.signature.keys.to_a.sort] << word
      to_add = []
      @search_hash.each_value do |other_words|
        other_words.each do |other_word|
          if !word.subset?(other_word) && (other_word.origin.size <
LENGTH_LIMIT)
            sum = word + other_word
            to_add << sum
          end
        end
      end
      to_add.each {|v| @search_hash[v.signature.keys.to_a.sort] << v}
    end
  end
  def write_equation(left_string, right_string)
    @success = 0 unless @success
    puts left_string.to_s + " == " + right_string.to_s
  end
  def find
    @search_hash.each_value do |homogeneus_words_list|
      homogeneus_words_list.size.times do
        word = homogeneus_words_list.pop
        find_equation_in_array(word, homogeneus_words_list)
      end
    end
  end
  def find_equation_in_array(word, array)
    array.each { |other_word| equation(word, other_word) }
  end
  def equation(left, right)
    if right.intersection(left).empty?
      if left == right
        write_equation(left, right)
      elsif multiplier = left.multiple?(right)
        write_equation(left, right * multiplier)
      elsif multiplier = left.base?(right)
        write_equation(left * multiplier, right)
      else
        try_other_formulas(left, right)
      end
    end
  end
  def try_other_formulas(left, right)
    short, long = [left, right].sort! {|a, b| a.len <=> b.len}
    short = [short] if short.instance_of? HashedString
    #begin
      return false if (short.collect {|o| o.len}).min > (long.len/2)
    #rescue
    #  p short
    #  p short.origin
    #  raise
    #end
    difference = (long.minus short)
    short.each do |short_origin|
      if multiplier = (short_origin.signature.base? difference)
        write_equation((short + short_origin * multiplier), long) if
multiplier > 0
      end
    end
  end
end
finder = EquationFinder.new($stdin)
finder.find
exit(finder.success || 1)