Monday, October 26, 2020

Favorite Vampire

I was recently asked who my favorite vampire was.  I said, "the muppet from Sesame Street."

They told me, "he doesn't count!"  I replied, "I assure you he does."
-Anonymous

Monday, October 12, 2020

Well Yes, But Actually No. Matrix Multiplication Gone Horribly Right.

Saw a funny cartoon meme that showed how to do matrix multiplication the "wrong" way.
It made me wonder how many solutions would work using the wrong method the meme outlined. To answer this, I wrote a quick Ruby script to check all possible values for a1, a2 .. d1, d2 in the range 0-9 to see which satisfy the following matrix multiplication:
| a1 b1 | | a2 b2 | = | a3 b3 |
| c1 d1 | | c2 d2 |   | c3 d3 |
where:
a3 = a1 * 10 + a2
etc.
For example:
| 3 6 | | 9 3 | = | 39 63 |
| 4 3 | | 2 9 |   | 42 39 |
or lexically:
| s t | | w x | = | sw tx |
| u v | | y z |   | uy yz |
Assuming we check every possible combination, there would 9^8, or 43,046,721 combinations. That's not too large, and with some early checks, we should be able to significantly prune the search space down to around 100K.

Ignoring the trivial case (all zeroes), there are exactly 100 possible solutions. Of those, 82 have identical "right" diagonals where:
b1 = b2 and c1 = c2
but only 24 have identical "left" diagonals where:
a1 = a2 and d1 = d2
Some questions to think about:
1) Why exactly 100 solutions? It seems too non-random.
2) Why do so many (82) have matching "right" diagonals?
3) Are some solutions "duplicates" because of rotations, transposition, etc.?
4) Would you see similar numbers for 3x3 matrices?
| a b c | | j k l | = | aj bk cl |
| d e f | | m n o |   | dm en fo |
| g h i | | p q r |   | gp hq ir |
For those interested, here is the Ruby code I used:
#!/usr/bin/env ruby

count = 0
ldiags = 0
rdiags = 0

(1..9).each do |a1|
   (1..9).each do |b1|
      (1..9).each do |c1|
         (1..9).each do |d1|
            (1..9).each do |a2|
               a3x = (a1 * 10) + a2  # expected a3

               # actual a3 = (a1 * a2) + (b1 * c2)
               # so if (a1 * a2) is already larger
               # than our expected (a3x), we can 
               # skip checking anything else 
               next if (a1 * a2) > a3x

               (1..9).each do |b2|
                  b3x = (b1 * 10) + b2  # expected b3

                  # actual b3 = (a1 * b2) + (b1 * d2)
                  # so if (a1 * b2) is already larger
                  # than our expected (b3x), we can 
                  # skip checking anything else 
                  next if (a1 * b2) > b3x

                  (1..9).each do |c2|
                     a3 = (a1 * a2) + (b1 * c2)  # actual a3
                     next if a3 != a3x

                     c3x = (c1 * 10) + c2  # expected c3

                     c3 = (c1 * a2) + (d1 * c2)  # actual c3
                     next if c3 != c3x

                     (1..9).each do |d2|
                        b3 = (a1 * b2) + (b1 * d2)  # actual b3
                        next if b3 != b3x

                        d3x = (d1 * 10) + d2  # expected d3

                        d3 = (c1 * b2) + (d1 * d2)  # actual d3
                        next if d3 != d3x

                        # found a solution
                        count += 1
                        puts count
                        puts "| #{a1} #{b1} | | #{a2} #{b2} | = | #{a3} #{b3} |\n"
                        puts "| #{c1} #{d1} | | #{c2} #{d2} |   | #{c3} #{d3} |\n"

                        if (a1 == a2) && (d1 == d2)
                           ldiags += 1
                        end
                        if (b1 == b2) && (c1 == c2)
                           rdiags += 1
                        end
                     end
                  end
               end
            end
         end
      end
   end
end
         
puts "count:  #{count}"
puts "ldiags:  #{ldiags}"
puts "rdiags:  #{rdiags}"
PS. I found this as well. Apparently this meme spawned lots of interest. https://codegolf.stackexchange.com/questions/211918/bad-matrix-multiplication-that-gives-the-right-answer