From: Sander Land <sander.land@...>
Date: 2007-02-05T00:39:22+09:00
Subject: Re: [QUIZ] String Equations (#112)

Here is my solution.
It generates 26 equations (1 per character) in matrix form.
If the nullity of this matrix is zero then the only solution is the
zero solution (no words on either side), which is invalid.
If it is > 0 then there are infinitely many solutions, any vector of
integers in the null space corresponds to one of them.

The way to generate such a solution is:
(1) Find a vector in the null space using Rationals
(2) Multiply it with large enough number (least common multiple of the
denominators) such that all the Rationals turn into integers.
(3) All the negative numbers are counts for words on the left side,
positive for words on the right side.

Step (1) would take more time than I have right now, so I tried
searching for a library. But anything that calculates a basis for the
null space has no support for Rationals and using floats makes step
(2) pretty much impossible. So my code just returns if an equation
exists instead of generating one.

One last remark about my code: it uses Matrix#rank, which seems to be
bugged. To run it you may need to patch your matrix.rb file (see
http://www.ruby-forum.com/topic/96387)

code:

require 'matrix'

class String
  def to_freq
    ('a'..'z').map{|c| Rational(count(c)) }  # use Rational for
stability in calculating rank
  end
end

def has_string_eqn(words)
  table = words.uniq.map{|w| w.downcase.gsub(/[^a-z]/,'').to_freq }.transpose
  nullity = words.length - Matrix[*table].rank
  return nullity > 0
end