R

#### Ruby Quiz

combinations, even for small word sets, because each term can be repeated.

To handle this, most brave souls who solved the quiz used some matrix

transformations from linear algebra for solving a system of linear equations.

This makes it possible to find solutions in reasonable time, but I had to drag

out the math textbooks to decode the solutions.

Let's take a look into one such solution by Eric I.:

require 'mathn'

CompactOutput = false

# calculate the least common multiple of one or more numbers

def lcm(first, *rest)

rest.inject(first) { |l, n| l.lcm(n) }

end

# ...

This should be pretty easy to digest. The mathn library is pulled in here to

get more accurate results in the calculations the code will be doing, a constant

selects the desired output mode, and a shortcut is defined for applying lcm()

over an Array of numbers.

The next method is where all the action is, so let's take that one slowly:

# ...

# Returns nil if there is no solution or an array containing two

# elements, one for the left side of the equation and one for the

# right side. Each of those elements is itself an array containing

# pairs, where each pair is an array in which the first element is the

# number of times that word appears and the second element is the

# word.

def solve_to_array(words)

# clean up word list by eliminating non-letters, converting to lower

# case, and removing duplicate words

words.map! { |word| word.downcase.gsub(/[^a-z]/, '') }.uniq!

# ...

The first comment does a good job of describing the result this method will

eventually produce, so you may want to glance back to it when we get that far.

The first set of operations is the word normalization process right out of the

quiz. This code shouldn't scare anybody yet. (Just a quick side note though,

it is possible to use delete("^a-z") here instead of the gsub() call.)

One more easy bit of code, then we will ramp things up:

# ...

# calculate the letters used in the set of words

letters = Hash.new

words.each do |word|

word.split('').each { |letter| letters[letter] = true }

end

# ...

This code just makes a list of all letters used in the word list. (Only the

keys() of the Hash are used.) To see what that's for, we need to dive into the

math:

# ...

# create a matrix to represent a set of linear equations.

column_count = words.size

row_count = letters.size

equations = []

letters.keys.each do |letter|

letter_counts = []

words.each { |word| letter_counts << word.count(letter) }

equations << letter_counts

end

# ...

This code build the matrix we are going to work with to find answers. Each

column in the matrix represents a word and each row a letter. The numbers in

the matrix then are just a count of the letter in that word. For example, using

the quiz equation this code produces the following matrix:

v

o

l m

d a r

e r i

l m v d

o o t o d

a r r o l l

i m d t m o e

+--------------

v | 0 0 0 1 0 1 0

l | 0 0 1 1 0 1 1

a | 0 1 0 0 0 1 0

m | 0 1 0 1 1 1 0

d | 0 0 1 1 0 0 2

o | 0 0 1 2 1 2 0

e | 0 0 0 1 0 0 1

r | 0 0 1 1 0 1 1

t | 0 0 0 1 1 0 0

i | 1 0 0 0 0 0 1

If you glance back at the code now, it should be pretty clear how it builds the

matrix as an Array of Arrays.

Now we're ready to manipulate the matrix and this is the first chunk of code

that does that:

# ...

# transform matrix into row echelon form

equations.size.times do |row|

# re-order the rows, so the row with a value in then next column

# to process is above those that contain zeroes

equations.sort! do |row1, row2|

column = 0

column += 1 until column == column_count ||

row2[column].abs != row1[column].abs

if column == column_count : 0

else row2[column].abs <=> row1[column].abs

end

end

# figure out which column to work on

column = (0...column_count).detect { |i| equations[row]

*!= 0 }*

break unless column

# transform rows below the current row so that there is a zero in

# the column being worked on

((row + 1)...equations.size).each do |row2|

factor = -equations[row2][column] / equations[row][column]

(column...column_count).each do |c|

equations[row2][c] += factor * equations[row][c]

end

end

end

# ...

Now you really don't want me to describe that line by line. Trust me. Instead,

let me sum up what it does.

This code transforms the matrix into row echelon form, which says that higher

rows in the matrix have entries in further left columns and that the first

significant entry in a row is preceded only by zeros. That sounds scarier than

it is. Here's the transformed matrix (without the labels this time):

1 0 0 0 0 0 1

0 1 0 1 1 1 0

0 0 1 2 1 2 0

0 0 0 -1 -1 -2 2

0 0 0 0 -1 -2 3

0 0 0 0 0 -2 2

0 0 0 0 0 0 0

0 0 0 0 0 0 0

0 0 0 0 0 0 0

0 0 0 0 0 0 0

The why behind this transformation is that its the first step in solving for our

equation.

On to the next bit of code:

# ...

# only one of the free variables chosen randomly will get a 1, the

# rest 0

rank = equations.select { |row| row.any? { |v| v != 0 }}.size

free = equations[0].size - rank

free_values = Array.new(free, 0)

free_values[rand(free)] = 2 * rand(2) - 1

# ...

This bit of math uses the rank of the matrix to determine the free variables it

will solve for. Free variables are just placeholders for substitutions in our

system of equations. More concretely, they are where one or more words will be

inserted in our string equations.

Setting a single value to one, as the comment mentions, is basically preparing

to to work with one word at a time. That's why the others are zeroed out.

One more variable is prepared:

# ...

values = Array.new(equations[0].size) # holds the word_counts

# ...

As the comment explains, this will eventually be the counts for each word.

OK, here's the last big bit of math:

# ...

# use backward elimination to find values for the variables; process

# each row in reverse order

equations.reverse_each do |row|

# determine number of free variables for the given row

free_variables = (0...column_count).inject(0) do |sum, index|

row[index] != 0 && values[index].nil? ? sum + 1 : sum

end

# on this row, 1 free variable will be calculated, the others will

# get the predetermined free values; the one being calculated is

# marked with nil

free_values.insert(rand(free_variables), nil) if free_variables > 0

# assign values to the variables

sum = 0

calc_index = nil

row.each_index do |index|

if row[index] != 0

if values[index].nil?

values[index] = free_values.shift

# determine if this is a calculated or given free value

if values[index] : sum += values[index] * row[index]

else calc_index = index

end

else

sum += values[index] * row[index]

end

end

end

# calculate the remaining value on the row

values[calc_index] = -sum / row[calc_index] if calc_index

end

# ...

This elimination is the second and final matrix transform leading to a solution.

The code works through each row or equation of the matrix, determining values

for the free variables.

Again this process is much more linear algebra than Ruby, so I won't bother to

break it down line by line. Just know that the end result of this process is

that values now holds the counts of the words needed to solve quiz. Positive

counts belong on one side of the equation, negative counts on the other.

This is the code that breaks down those counts:

# ...

if values.all? { |v| v } && values.any? { |v| v != 0 }

# in case we ended up with any non-integer values, multiply all

# values by their collective least common multiple of the

# denominators

multiplier =

lcm(*values.map { |v| v.kind_of?(Rational) ? v.denominator : 1 })

values.map! { |v| v * multiplier }

# deivide the terms into each side of the equation depending on

# whether the value is positive or negative

left, right = [], []

values.each_index do |i|

if values

break unless column

# transform rows below the current row so that there is a zero in

# the column being worked on

((row + 1)...equations.size).each do |row2|

factor = -equations[row2][column] / equations[row][column]

(column...column_count).each do |c|

equations[row2][c] += factor * equations[row][c]

end

end

end

# ...

Now you really don't want me to describe that line by line. Trust me. Instead,

let me sum up what it does.

This code transforms the matrix into row echelon form, which says that higher

rows in the matrix have entries in further left columns and that the first

significant entry in a row is preceded only by zeros. That sounds scarier than

it is. Here's the transformed matrix (without the labels this time):

1 0 0 0 0 0 1

0 1 0 1 1 1 0

0 0 1 2 1 2 0

0 0 0 -1 -1 -2 2

0 0 0 0 -1 -2 3

0 0 0 0 0 -2 2

0 0 0 0 0 0 0

0 0 0 0 0 0 0

0 0 0 0 0 0 0

0 0 0 0 0 0 0

The why behind this transformation is that its the first step in solving for our

equation.

On to the next bit of code:

# ...

# only one of the free variables chosen randomly will get a 1, the

# rest 0

rank = equations.select { |row| row.any? { |v| v != 0 }}.size

free = equations[0].size - rank

free_values = Array.new(free, 0)

free_values[rand(free)] = 2 * rand(2) - 1

# ...

This bit of math uses the rank of the matrix to determine the free variables it

will solve for. Free variables are just placeholders for substitutions in our

system of equations. More concretely, they are where one or more words will be

inserted in our string equations.

Setting a single value to one, as the comment mentions, is basically preparing

to to work with one word at a time. That's why the others are zeroed out.

One more variable is prepared:

# ...

values = Array.new(equations[0].size) # holds the word_counts

# ...

As the comment explains, this will eventually be the counts for each word.

OK, here's the last big bit of math:

# ...

# use backward elimination to find values for the variables; process

# each row in reverse order

equations.reverse_each do |row|

# determine number of free variables for the given row

free_variables = (0...column_count).inject(0) do |sum, index|

row[index] != 0 && values[index].nil? ? sum + 1 : sum

end

# on this row, 1 free variable will be calculated, the others will

# get the predetermined free values; the one being calculated is

# marked with nil

free_values.insert(rand(free_variables), nil) if free_variables > 0

# assign values to the variables

sum = 0

calc_index = nil

row.each_index do |index|

if row[index] != 0

if values[index].nil?

values[index] = free_values.shift

# determine if this is a calculated or given free value

if values[index] : sum += values[index] * row[index]

else calc_index = index

end

else

sum += values[index] * row[index]

end

end

end

# calculate the remaining value on the row

values[calc_index] = -sum / row[calc_index] if calc_index

end

# ...

This elimination is the second and final matrix transform leading to a solution.

The code works through each row or equation of the matrix, determining values

for the free variables.

Again this process is much more linear algebra than Ruby, so I won't bother to

break it down line by line. Just know that the end result of this process is

that values now holds the counts of the words needed to solve quiz. Positive

counts belong on one side of the equation, negative counts on the other.

This is the code that breaks down those counts:

# ...

if values.all? { |v| v } && values.any? { |v| v != 0 }

# in case we ended up with any non-integer values, multiply all

# values by their collective least common multiple of the

# denominators

multiplier =

lcm(*values.map { |v| v.kind_of?(Rational) ? v.denominator : 1 })

values.map! { |v| v * multiplier }

# deivide the terms into each side of the equation depending on

# whether the value is positive or negative

left, right = [], []

values.each_index do |i|

if values

*> 0 : left << [values**, words**]*

elsif valueselsif values

*< 0 : right << [-values**, words**]*

end

end

[left, right] # return found equation

else

nil # return no found equation

end

end

# ...

Assuming we found a solution, this code divides the words to be used into two

groups, one for each side of the equation. It divides based on the positive and

negative counts I just explained in values and the end result was described in

that first comment at the top of this long method.

With the math behind us, the rest of the code is easy:

# ...

# Returns a string containing a solution if one exists; otherwise

# returns nil. The returned string can be in either compact or

# non-compact form depending on the CompactOutput boolean constant.

def solve_to_string(words)

result = solve_to_array(words)

if result

if CompactOutput

result.map do |side|

side.map { |term| "#{term[0]}*\"#{term[1]}\"" }.join(' + ')

end.join(" == ")

else

result.map do |side|

side.map { |term| (["\"#{term[1]}\""] * term[0]).join(' + ') }.

join(' + ')

end.join(" == ")

end

else

nil

end

end

# ...

This method just wraps the previous solver and transforms the resulting Arrays

into the quiz equation format. Two different output options are controlled by

the constant we saw at the beginning of the program.

Here's the final piece of the puzzle:

# ...

if __FILE__ == $0 # if run from the command line...

# collect words from STDIN

words = []

while line = gets

words << line.chomp

end

result = solve_to_string(words)

if result : puts result

else exit 1

end

end

This code just brings in the word list, taps the solver to do the hard work, and

sends back the results. This turns the code into a complete solution.

My thanks to all of you who know math so much better than me. I had to use math

books and my pet math nerd just to breakdown how these solutions worked.

Tomorrow we return to easier problems, pop quiz style...end

end

[left, right] # return found equation

else

nil # return no found equation

end

end

# ...

Assuming we found a solution, this code divides the words to be used into two

groups, one for each side of the equation. It divides based on the positive and

negative counts I just explained in values and the end result was described in

that first comment at the top of this long method.

With the math behind us, the rest of the code is easy:

# ...

# Returns a string containing a solution if one exists; otherwise

# returns nil. The returned string can be in either compact or

# non-compact form depending on the CompactOutput boolean constant.

def solve_to_string(words)

result = solve_to_array(words)

if result

if CompactOutput

result.map do |side|

side.map { |term| "#{term[0]}*\"#{term[1]}\"" }.join(' + ')

end.join(" == ")

else

result.map do |side|

side.map { |term| (["\"#{term[1]}\""] * term[0]).join(' + ') }.

join(' + ')

end.join(" == ")

end

else

nil

end

end

# ...

This method just wraps the previous solver and transforms the resulting Arrays

into the quiz equation format. Two different output options are controlled by

the constant we saw at the beginning of the program.

Here's the final piece of the puzzle:

# ...

if __FILE__ == $0 # if run from the command line...

# collect words from STDIN

words = []

while line = gets

words << line.chomp

end

result = solve_to_string(words)

if result : puts result

else exit 1

end

end

This code just brings in the word list, taps the solver to do the hard work, and

sends back the results. This turns the code into a complete solution.

My thanks to all of you who know math so much better than me. I had to use math

books and my pet math nerd just to breakdown how these solutions worked.

Tomorrow we return to easier problems, pop quiz style...