Gavin Kistner
6/8/2005 2:24:00 PM
(This isn't a library I plan on maintaining, but ANN felt like the
right prefix for offering up code for mass enjoyment.)
At work yesterday I needed to do some algebra on some matrix math to
reverse-derive a value. (To be specific, I needed to figure out how
to draw the three euler rotation values out of a ZXY rotation
matrix.) After spending 2 minutes writing out equations and fearing I
was making a mistake, I turned to Excel and some stupid text
manipulation to produce my formulae. After 10 minutes of messing
around, I got the answer wrong anyhow.
I decided to write a little Ruby library to do the task for me. I
wrote a matrix class which knows how to do matrix math on strings,
producing formulae from them. After the initial pass produced a lot
of values like "0*sinX" and "0 + 0 + 1*(sinX)" I made it a bit
smarter, so that 0s and 1s properly simplify the equations during
calculation.
It doesn't produce perfectly-reduced equations by any means, but it
did the trick. In the end, I got my result :)
Sample output follows, followed by the code itself. Enjoy!
M1:
---------------------------------------------------------------------
0 | 1 | 2
3 | 4 | 5
M2:
---------------------------------------------------------------------
x | y | z
3q | 4r | 5s
M1 scaled by 2:
---------------------------------------------------------------------
0 | 2 | 4
6 | 8 | 10
M2 scaled by 2:
---------------------------------------------------------------------
x * 2 | y * 2 | z * 2
3q * 2 | 4r * 2 | 5s * 2
M1 + M2:
---------------------------------------------------------------------
x | 1 + y | 2 + z
3 + 3q | 4 + 4r | 5 + 5s
X:
------------------------------------------------------------------------
-----
1 | 0 | 0
0 | cosX | sinX
0 | -sinX | cosX
Y:
------------------------------------------------------------------------
-----
cosY | 0 | -sinY
0 | 1 | 0
sinY | 0 | cosY
Z:
------------------------------------------------------------------------
-----
cosZ | sinZ | 0
-sinZ | cosZ | 0
0 | 0 | 1
X - Y:
------------------------------------------------------------------------
-----
1 - cosY | 0 | sinY
0 | cosX - 1 | sinX
-sinY | -sinX | cosX - cosY
X * Y * Z:
------------------------------------------------------------------------
-----
cosY * cosZ | cosY *
sinZ | -sinY
((sinX * sinY) * cosZ) + (cosX * -sinZ) | ((sinX * sinY) * sinZ) +
(cosX * cosZ) | sinX * cosY
((cosX * sinY) * cosZ) + (-sinX * -sinZ) | ((cosX * sinY) * sinZ) + (-
sinX * cosZ) | cosX * cosY
Z * X * Y:
------------------------------------------------------------------------
-----
(cosZ * cosY) + ((sinZ * sinX) * sinY) | sinZ * cosX | (cosZ * -
sinY) + ((sinZ * sinX) * cosY)
(-sinZ * cosY) + ((cosZ * sinX) * sinY) | cosZ * cosX | (-sinZ * -
sinY) + ((cosZ * sinX) * cosY)
cosX * sinY | -sinX
| cosX * cosY
stringmatrix.rb
------------------------------------------------------------------------
-----
# A two-dimensional matrix of arbitrary size, with common matrix
# math methods. When entries in the matrix are strings, the math
# methods produce strings representing the equation.
#
# Strings and numbers mix nicely so that multiplying by 0 wipes
# out the string properly, and multiplying by 1 or adding 0
# leaves the original unchanged.
#
# For example:
# x = StringMatrix.parse <<END
# 1 0 0
# 0 cosX sinX
# 0 -sinX cosX
# END
#
# y = StringMatrix.parse <<END
# cosY | 0 | -sinY
# 0 | 1 | 0
# sinY | 0 | cosY
# END
#
# puts x, ' ', y, ' ', x - y, ' ', x * y
#
# #=> 1 | 0 | 0
# #=> 0 | cosX | sinX
# #=> 0 | -sinX | cosX
# #=>
# #=> cosY | 0 | -sinY
# #=> 0 | 1 | 0
# #=> sinY | 0 | cosY
# #=>
# #=> 1 - cosY | 0 | sinY
# #=> 0 | cosX - 1 | sinX
# #=> -sinY | -sinX | cosX - cosY
# #=>
# #=> cosY | 0 | -sinY
# #=> sinX * sinY | cosX | sinX * cosY
# #=> cosX * sinY | -sinX | cosX * cosY
class StringMatrix
# Add two values intelligently
def self.add( v1, v2 )
if v1==0
v2
elsif v2==0
v1
elsif Numeric===v1 && Numeric===v2
v1+v2
else
self.operator_join( v1, v2, '+' )
end
end
# Subtract two values intelligently
def self.subtract( v1, v2 )
if v2==0
v1
elsif v1==0
if v2 =~ /^-\((.+)\)$/ || v2 =~ /^-(.+)$/
$1
elsif v2 =~ /\s/
"-(#{v2})"
else
"-#{v2}"
end
elsif Numeric===v1 && Numeric===v2
v1-v2
else
self.operator_join( v1, v2, '-' )
end
end
# Multiply two values intelligently
def self.multiply( v1, v2 )
if v1==1
v2
elsif v2==1
v1
elsif v1==0 || v2==0
0
elsif Numeric===v1 && Numeric===v2
v1*v2
else
self.operator_join( v1, v2, '*' )
end
end
# Join two values semi-intelligently
def self.operator_join( v1, v2, op_str )
out = ( Numeric === v1 || v1 =~ /^\S+$/ ) ? "#{v1}" : "(#{v1})"
out << " #{op_str} "
out << ( ( Numeric === v2 || v2 =~ /^\S+$/ ) ? "#{v2}" : "(#
{v2})" )
end
attr_reader :width, :height
# Creates a new matrix of the specified _width_ and _height_,
optionally
# specifying a _default_value_ to fill each cell.
def initialize( width, height, default_value='' )
@width = width
@height = height
@values = Array.new( width ){ Array.new(height)
{ default_value } }
end
# Reads the value from column _x_, row _y_.
#
# StringMatrices are 1-based, not zero-based.
# (The first item in the matrix is 1,1 and the last is
_width_,_height_)
def []( x, y )
if !y
@values[ x-1 ].dup
elsif !x
a = []
1.upto(@width){ |x|
a << @values[ x-1 ][ y-1 ]
}
a
else
@values[ x-1 ][ y-1 ]
end
end
# Sets the value in column _x_, row _y_ to _val_.
#
# StringMatrices are 1-based, not zero-based.
# (The first item in the matrix is 1,1 and the last is
_width_,_height_)
def []=( x, y, val )
@values[ x-1 ][ y-1 ] = val
end
# Adds the supplied _right_matrix_ from the current matrix
# and returns the result. (The original matrix is not modified.)
def +( right_matrix )
raise "Size mismatch" if width != right_matrix.width ||
height != right_matrix.height
out = self.class.new( width, height )
1.upto( @height ){ |y|
1.upto( @width ){ |x|
out[ x, y ] = self.class.add( self[ x, y ],
right_matrix[ x, y ] )
}
}
out
end
# Subtracts the supplied _right_matrix_ from the current matrix
# and returns the result. (The original matrix is not modified.)
def -( right_matrix )
raise "Size mismatch" if width != right_matrix.width ||
height != right_matrix.height
out = self.class.new( width, height )
1.upto( @height ){ |y|
1.upto( @width ){ |x|
out[ x, y ] = self.class.subtract( self[ x, y ],
right_matrix[ x, y ] )
}
}
out
end
# Performs matrix multiplication between the two matrices.
# (The original matrix is not modified.)
def *( right_matrix )
raise "Size mismatch" if width != right_matrix.height ||
height != right_matrix.width
out = self.class.new( width, height )
1.upto( @height ){ |y|
1.upto( @width ){ |x|
row = self[ nil, y ]
col = right_matrix[ x, nil ]
val = row.zip( col ).inject( 0 ){ |sum, pair|
self.class.add( sum, self.class.multiply( *pair ) )
}
out[ x, y ] = val
}
}
out
end
# Scales the matrix, multiplying each value by _scale_value_ and
returning
# the resulting matrix.
# (The original matrix is not modified.)
def scale( scale_value )
out = self.class.new( width, height )
1.upto( @height ){ |y|
1.upto( @width ){ |x|
out[ x, y ] = self.class.multiply( self[ x, y ],
scale_value )
}
}
out
end
# Parses a multi-line string for use as a StringMatrix
#
# Lines in the string may be delimited by tabs, vertical bars,
or commas.
# The most common item is used as the separator; if none of the
above are
# present in the string, spaces are used.
def self.parse( raw_str )
best_count = 1
split_char = [ "\t", '|', ',' ].inject( ' ' ){ |split_char,
char|
count = raw_str.scan( char ).length
if count > best_count
best_count = count
char
else
split_char
end
}
values = []
y = 0
raw_str.each_line{ |line|
line.split( split_char ).each_with_index{ |val, x|
val.strip!
( values[ x ] ||= [] )[ y ] = case val
when /^\d+$/ then val.to_i
when /^\d+\.\d+$/ then val.to_f
else val
end
}
y += 1
}
width = values.length
height = y
out = self.new( width, height, '' )
1.upto( height ){ |y|
1.upto( width ){ |x|
out[ x, y ] = values[ x-1 ][ y-1 ]
}
}
out
end
def to_s( no_padding=false )
out = ''
column_widths = @values.collect{ |col|
no_padding ? 0 : col.inject(0){ |max_len,val|
len = val.to_s.length
max_len > len ? max_len : len
}
}
1.upto(@height){ |y|
1.upto(@width){ |x|
out << self[ x, y ].to_s.centered_in( column_widths
[ x-1 ] )
out << " | " unless x == @width
}
out << "\n" unless y == @height
}
out
end
end
class String
# Returns a copy of the string, centered (by padding both sides
with spaces)
# within the specified width.
#
# If width is smaller than the length of the string, the string
itself is returned.
def centered_in( width )
out = self.dup
remains = width - out.length
if remains > 0
back = remains / 2
front = remains - back
out = " "*front + out + " "*back
end
out
end
end
if $0 == __FILE__
m1 = StringMatrix.parse( "0,1,2\n3,4,5" )
m2 = StringMatrix.parse( "x,y,z\n3q,4r,5s" )
puts <<-ENDOUTPUT
M1:
---------------------------------------------------------------------
#{ m1 }
M2:
---------------------------------------------------------------------
#{ m2 }
M1 scaled by 2:
---------------------------------------------------------------------
#{ m1.scale( 2 ) }
M2 scaled by 2:
---------------------------------------------------------------------
#{ m2.scale( 2 ) }
M1 + M2:
---------------------------------------------------------------------
#{ m1 + m2 }
ENDOUTPUT
x = StringMatrix.parse <<-ENDMATRIX
1 0 0
0 cosX sinX
0 -sinX cosX
ENDMATRIX
y = StringMatrix.parse <<-ENDMATRIX
cosY | 0 | -sinY
0 | 1 | 0
sinY | 0 | cosY
ENDMATRIX
z = StringMatrix.parse <<-ENDMATRIX
cosZ sinZ 0
-sinZ cosZ 0
0 0 1
ENDMATRIX
puts <<-ENDOUT
X:
------------------------------------------------------------------------
-----
#{x}
Y:
------------------------------------------------------------------------
-----
#{y}
Z:
------------------------------------------------------------------------
-----
#{z}
X - Y:
------------------------------------------------------------------------
-----
#{x-y}
X * Y * Z:
------------------------------------------------------------------------
-----
#{x*y*z}
ENDOUT
end