From: Gavin Kistner <gavin@...>
Date: 2005-06-08T23:23:31+09:00
Subject: [ANN] StringMatrix

(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