From: Daniel Lucraft <dan@...>
Date: 2007-02-05T02:12:56+09:00
Subject: Re: String Equations (#112)

Sander Land wrote:
> Step (1) would take more time than I have right now, so I tried

I guess I have too much time on my hands :) This is a solver for 
homogenous systems of linear equations: http://pastie.caboo.se/37827

It reduces the matrix to row echelon form, and then reads off the 
solutions from the non-unitary columns, multiplying them up to make them 
integral. It's probably not that robust in the case of degenerate or 
edge case matrices, but it works for solving the word equations. 
Obviously there are infinite solutions, so it returns the largest set of 
linearly independent solutions. It was fun to make, I had to dig out the 
linear algebra textbook I've had since my undergrad days.

And this is the solution that uses it. It does exactly the same thing as 
Sander's in making the matrix, and then just uses the linear solver and 
translates the solutions into word equations.

Fun quiz!

Daniel

# WordEquations
#
# $ cat test.txt
# i
# am
# lord
# voldemort
# tom
# marvolo
# riddle
# $ cat test.txt | ruby quiz112.rb
# i + am + lord + voldemort == tom + marvolo + riddle
#
# Prints equation closest to 80 chars in length.
#
# Also:
# $ cat test.txt | ruby quiz112.rb shortest
# $ cat test.txt | ruby quiz112.rb longest
# $ cat test.txt | ruby quiz112.rb all
#
# Generates word equations by solving the equivalent
# homogenous linear equations. E.g.
#
# a = hohoho
# b = h
# c = oo
# d = ho
# ->
# h's:   3a + b +    + d = 0
# o's:   3a +     2c + d = 0
# ->
# solutions:
#  [-2, 6, 3, 0] & [-1, 0, 0, 3]
# ->
# hohoho+hohoho == h+h+h+h+h+h+oo+oo+oo
# hohoho        == ho+ho+ho

require 'homogenouslinearsolver'

class WordEquations
  def self.word_problem(words)
    words = words.map {|word| word.downcase.match(/\w+/); $&}.uniq
    words = words.select{|w| w}

    rows = ('a'..'z').map do |l|
      words.map {|word| Rational(word.count(l), 1) }
    end
    solutions = HomogenousLinearSolver.solve(Matrix[*rows])

    # if solution value is negative, add the word to the left side,
    # otherwise add to the right.
    solutions.collect do |sol|
      left_words = []
      right_words = []
      sol.each_with_index do |val, i|
        if val < 0
          left_words += [words[i]]*(val*-1)
        elsif val > 0
          right_words += [words[i]]*val
        end
      end
      left_words.join(" + ") +
        " == " + right_words.join(" + ")
    end
  end
end

if ARGV[0] == "test"
  require 'test/unit'

  class String
    def sorted
      (unpack('c*').sort).pack('c*')
    end
  end

  class TestWordEquations < Test::Unit::TestCase
    def test_hohoho
      words = %w{hohoho h oo}
      assert_equal ["hohoho + hohoho == h + h + h + h + h + h + oo + oo 
+ oo"],
      WordEquations.word_problem(words)
    end

    def test_get_words_harry_potter
      words = %w{i am lord voldemort tom marvolo riddle}
      assert_equal ["i + am + lord + voldemort == tom + marvolo + 
riddle"],
      WordEquations.word_problem(words)
    end

    def test_get_words_me
      words = %w{daniel lucraft fluent radical}
      assert_equal ["daniel + lucraft == fluent + radical"],
      WordEquations.word_problem(words)
    end

    def test_get_words_evil!
      words = %w{bwu ha bwuhahahahaha}
      assert_equal ["bwu + ha + ha + ha + ha + ha == bwuhahahahaha"],
      WordEquations.word_problem(words)
    end

    def test_get_words_1
      words = %w{dormitory dirty room}
      assert_equal ["dormitory == dirty + room"],
      WordEquations.word_problem(words)
    end

    def test_get_words_2
      words = %w{statue of liberty built to stay free}
      assert_equal ["statue + of + liberty == built + to + stay + 
free"],
      WordEquations.word_problem(words)
    end

    def test_get_words_3
      words = %w{hohoho h oo ho}
      assert_equal ["hohoho + hohoho == h + h + h + h + h + h + oo + oo 
+ oo",
                    "hohoho == ho + ho + ho"], 
WordEquations.word_problem(words)
    end

    def test_no_solutions
      words = %w{foo bar}
      assert_equal [], WordEquations.word_problem(words)
    end

    def test_long
      words = %w[My experience in Amsterdam is that cyclists ride where 
the hell they like and aim in a state of rage at all pedestrians while 
ringing their bell loudly, the concept of avoiding people being foreign 
to them. My dream holiday would be a ticket to Amsterdam, immunity from 
prosecution and a baseball bat- Terry Pratchett]
      results = WordEquations.word_problem(words).sort_by{|eq| 
-eq.length}
      result = results[0]
      assert_equal "my + my + my + my + my + my + my + my + my + my + my 
+ "+
        "my + my + my + my + my + my + my + my + my + my + my + my + my 
+ "+
        "my + my + my + my + my + my + my + my + my + my + in + in + in 
+ "+
        "in + in + in + in + in + is + is + is + is + is + is + is + is 
+ "+
        "is + is + is + is + is + that + that + that + that + ride + 
ride + "+
        "ride + ride + ride + ride + ride + ride + ride + the + the + 
the + "+
        "the + the + the + the + the + the + the + the + the + the + the 
+ "+
        "the + the + the + the + the + the + the + the + the + the + the 
+ "+
        "the + the + the + the + the + the + the + the + the + the + a + 
a + "+
        "a + a + a + a + a + a + a + a + a + a + a + a + a + a + a + a + 
a + "+
        "a + a + a + a + a + a + a + a + a + a + a + a + a + a + a + a + 
a + "+
        "a + a + loudly + loudly + loudly + loudly + concept + concept + 
"+
        "concept + concept == amsterdam + amsterdam + amsterdam + "+
        "amsterdam + amsterdam + cyclists + cyclists + hell + hell + 
hell + "+
        "they + they + they + they + they + they + they + they + they + 
"+
        "they + they + they + they + they + they + they + they + they + 
"+
        "they + they + they + they + they + they + they + they + they + 
"+
        "they + they + they + they + they + they + they + they + they + 
"+
        "and + and + and + and + and + and + and + and + aim + aim + aim 
+ "+
        "aim + aim + aim + aim + aim + aim + aim + aim + aim + aim + aim 
+ "+
        "aim + aim + aim + aim + aim + aim + aim + aim + aim + aim + "+
        "prosecution + prosecution + prosecution + prosecution",
        result
      sides = result.split("==")
      sides.map! {|side| side.delete("+").delete(" ")}
      left = sides[0]
      right = sides[1]
      assert left.sorted == right.sorted
    end
  end
else
  results = WordEquations.word_problem(STDIN.read.split).sort_by{|eq| 
-eq.length}
  if results == []
    exit(1)
  else
    if ARGV[0] == "longest"
      puts results.first
    elsif ARGV[0] == "shortest"
      puts results.last
    elsif ARGV[0] == "all"
      results.each {|r| puts r; puts}
    else
      puts results.sort_by{|eq| (80-eq.length).abs}.first
    end
    exit(0)
  end
end



-- 
Posted via http://www.ruby-forum.com/.