Max Unit Submatrix

readme.md

Ruby on Rails Challenge 1 - Dynamic programming

Dynamic programming: Given a matrix consisting of 0's and 1's, find the maximum size sub-matrix consisting of only 1's.

1. Unless you already know, learn what the terms matrix and sub-matrix mean. What is a maximum size sub-matrix? How can you calculate it on paper? Try out a few examples on paper with a small matrix.

2. How can you implement a matrix in Ruby? Don't use a class for this, yet. Try to express this using arrays, hashes, or enumerables, or all of them.

3. Try to give two ways to program the solution. Which of your solutions is faster? Which requires more memory? Explain your answers.

Implementation

Note

It seems that there are two widespread definitions for submatrix, the one provided on Wikipedia and the one provided on Math World. This code uses the definition from Wikipedia.

Implementation

This solution implements two slightly different versions (iterative vs recursive), that use the same logic to remove rows or columns where the first 0 is found --there is almost no difference.

The matrix is represented as an array of arrays, each of which contain 0 or 1.

To find zeros, a simple linear search is run sequentially over each inner array and, when the first 0 is found, the row and column indexes are returned.

Then, the program decides if is better to remove the row or the column, based on the following criteria:

`IF` there are more ones on the row than in the column, remove the column.
`ELSE IF` there are less ones on the row that in the column, remove the row.
`ELSE`
  `IF` there are more zeros on the column than in the row, remove the column.
  `ELSE` remove the row.

When no more zeros are found, the program assumes the maximum unit submatrix has been found.

Validations can be run on the provided array if desired.

Thoughts

Thought that the recursive version would be faster, but seems that the iterative version is faster.

Guess the program may be improved by using a better search algorithm or, per harps, a more sophisticated structure to represent the matrix.

I was also tempted to include the code as an Array refinement...

Benchmark

Sample stats for 10,000 iterations with a 10x10 matrix running benchmark.rb.

Rehearsal -----------------------------------------------------------------------
iterative submatrix                   1.890000   0.000000   1.890000 (  1.890481)
recursive submatrix                   2.360000   0.000000   2.360000 (  2.361244)
iterative submatrix with validation   2.110000   0.000000   2.110000 (  2.116418)
recursive submatrix with validation   2.550000   0.000000   2.550000 (  2.543762)
-------------------------------------------------------------- total: 8.910000sec

                                          user     system      total        real
iterative submatrix                   1.890000   0.000000   1.890000 (  1.888168)
recursive submatrix                   2.320000   0.000000   2.320000 (  2.317262)
iterative submatrix with validation   2.110000   0.000000   2.110000 (  2.110418)
recursive submatrix with validation   2.530000   0.000000   2.530000 (  2.534197)

TODO

• Add specs for both versions by sharing examples.
• Add validaton to reject arrays that contains only zeros.

Original Repo & PR

https://bitbucket.org/akaiiro/exercise-mooquita-ruby-and-rails-challenge/pull-requests/1/solve-1st-challenge-max-unit-submatrix/diff

benchmark.rb

require 'benchmark'

require_relative 'lib/submatrix'

matrix = [
  [1, 1, 0, 0, 1, 1, 0, 0, 1, 0],
  [1, 0, 0, 0, 1, 0, 0, 1, 0, 0],
  [0, 0, 1, 1, 0, 1, 0, 1, 1, 1],
  [1, 1, 1, 1, 1, 0, 0, 0, 0, 1],
  [0, 0, 0, 1, 1, 1, 1, 0, 1, 1],
  [0, 1, 0, 0, 0, 1, 1, 1, 1, 1],
  [1, 0, 0, 0, 0, 0, 0, 1, 1, 0],
  [0, 0, 1, 0, 1, 0, 0, 1, 1, 0],
  [0, 0, 1, 0, 0, 0, 0, 0, 0, 1],
  [1, 0, 0, 1, 1, 1, 0, 1, 1, 1]
]

repetitions = 10_000

Benchmark.bmbm do |x|
  x.report('iterative submatrix') do
    repetitions.times do
      max_unit_submatrix matrix, algorithm: :iterative, run_validations: false
    end
  end

  x.report('recursive submatrix') do
    repetitions.times do
      max_unit_submatrix matrix, algorithm: :recursive, run_validations: false
    end
  end

  x.report('iterative submatrix with validation') do
    repetitions.times do
      max_unit_submatrix matrix, algorithm: :iterative
    end
  end

  x.report('recursive submatrix with validation') do
    repetitions.times do
      max_unit_submatrix matrix, algorithm: :recursive
    end
  end
end

submatrix.rb

require_relative 'validators'

def max_unit_submatrix(matrix, algorithm: :iterative, run_validations: true)
  validate(matrix) if run_validations

  matrix_clone = Marshal.load(Marshal.dump matrix)

  case algorithm
  when :recursive then recursive_max_unit_submatrix! matrix_clone
  when :iterative then iterative_max_unit_submatrix! matrix_clone
  end
end

def recursive_max_unit_submatrix!(matrix)
  unless position = find_first_zero(matrix)
    matrix
  else
    max_unit_submatrix remove_collection!(matrix, position)
  end
end

def iterative_max_unit_submatrix!(matrix)
  while position = find_first_zero(matrix) do
    remove_collection!(matrix, position)
  end

  matrix
end

def find_first_zero(matrix)
  matrix.each_with_index do |row, row_number|
    row.each_with_index do |element, col_number|
      if element == 0
        return { row: row_number, col: col_number  }
      end
    end
  end

  nil
end

def remove_collection!(matrix, position)
  smaller = which_is_smaller(matrix, position[:row], position[:col])
  eval "remove_#{smaller}!(matrix, position[smaller])"
  matrix
end

def which_is_smaller(matrix, row_number, col_number)
  row_size = matrix[row_number].reduce(:+)
  col_size = matrix.reduce(0) { |memo, row| memo += row[col_number] }
  if row_size < col_size
    :row
  elsif row_size > col_size
    :col
  else
    which_has_more_zeros matrix, row_number, col_number
  end
end

def which_has_more_zeros(matrix, row_number, col_number)
  row_count = matrix[row_number].count(0)
  col_count = matrix.count { |row| row[col_number] == 0 }
  row_count>=(col_count) ? :row : :col
end

def remove_row!(matrix, row_number)
  matrix.slice! row_number
end

def remove_col!(matrix, col_number)
  matrix.each { |row| row.slice! col_number }
end

submatrix_spec.rb

require File.expand_path('spec/spec_helper')
require File.expand_path('lib/submatrix.rb')

RSpec.describe 'Matrix Array' do

  describe '#max_unit_submatrix' do

    context 'with a matrix array containing 1 and 0 only' do
      context 'that is an identity' do
        let(:matrix) do
          [
            [1, 1, 1],
            [1, 1, 1],
            [1, 1, 1],
            [1, 1, 1]
          ]
        end

        it 'returns the original unit matrix' do
          expect(max_unit_submatrix matrix).to eql matrix
        end
      end

      context 'that is mixed' do
        context 'with longer columns' do
          let(:matrix) do
            [
              [1, 1, 1, 1, 1],
              [1, 1, 1, 1, 1],
              [1, 0, 1, 1, 1],
              [1, 1, 1, 1, 1]
            ]
          end

          let(:submatrix) do
            [
              [1, 1, 1, 1],
              [1, 1, 1, 1],
              [1, 1, 1, 1],
              [1, 1, 1, 1]
            ]
          end

          it 'returns the biggest possible unit matrix' do
            expect(max_unit_submatrix matrix).to eql submatrix
          end
        end

        context 'with longer rows' do
          let(:matrix) do
            [
              [1, 1, 1, 1],
              [1, 1, 0, 1],
              [1, 1, 1, 1],
              [1, 1, 1, 1],
              [1, 1, 1, 1]
            ]
          end

          let(:submatrix) do
            [
              [1, 1, 1, 1],
              [1, 1, 1, 1],
              [1, 1, 1, 1],
              [1, 1, 1, 1]
            ]
          end

          it 'returns the biggest possible unit matrix' do
            expect(max_unit_submatrix matrix).to eql submatrix
          end
        end

        context 'with several zeros' do
          let(:matrix) do
            [
              [1, 1, 1, 1, 0],
              [1, 1, 0, 1, 1],
              [1, 1, 1, 1, 1],
              [0, 1, 1, 1, 0],
              [0, 1, 1, 1, 1],
              [1, 1, 1, 1, 0]
            ]
          end

          let(:submatrix) do
            [
              [1, 1, 1],
              [1, 1, 1],
              [1, 1, 1],
              [1, 1, 1],
              [1, 1, 1]
            ]
          end

          it 'returns the biggest possible unit matrix' do
            expect(max_unit_submatrix matrix).to eql submatrix
          end
        end
      end

    end

    context 'with a matrix array that contains other values' do
      let(:matrix) do
        [
          [1, 1, 1, 1, 1],
          [1, 1, 1, 1, 1],
          [1, 1, 0, 1, 1],
          [1, 0, 2, 0, 1],
          [1, 1, 0, 1, 1],
          [1, 1, 1, 1, 1]
        ]
      end

      it 'raises argument error' do
        expect { max_unit_submatrix matrix }.to raise_error(ArgumentError)
      end
    end

    context 'with an uneven array' do
      let(:matrix) do
        [
          [1, 1, 1, 1, 1],
          [1, 1, 1, 1, 1],
          [1, 1, 0, 1],
          [1, 0, 1, 0, 1],
          [1, 1, 0, 1, 1],
          [1, 1, 1, 1, 1]
        ]
      end

      it 'raises argument error' do
        expect { max_unit_submatrix matrix }.to raise_error(ArgumentError)
      end
    end

    context 'with an empty matrix' do
      let(:matrix) do
        []
      end

      it 'raises argument error' do
        expect { max_unit_submatrix matrix }.to raise_error(ArgumentError)
      end
    end

    context 'with an array of empty arrays' do
      let(:matrix) do
        [
          [],
          [],
          [],
          []
        ]
      end

      it 'raises argument error' do
        expect { max_unit_submatrix matrix }.to raise_error(ArgumentError)
      end
    end
  end

end

validators.rb

def validate(matrix)
  validate_content matrix
  validate_form    matrix
  validate_values  matrix
end

def validate_content(matrix)
  no_content_in_argument! if matrix.empty?
  no_content_in_argument! if matrix.detect { |row| row.empty? }
end

def validate_form(matrix)
  size = matrix.first.size
  matrix.each do |row|
    uneven_array_as_argument!(row.size, size) unless row.size == size
  end
end

def validate_values(matrix)
  matrix.each_with_index do |row, row_number|
    row.each_with_index do |element, col_number|
      unless [0,1].include? element
        unexpected_value_in_argment! element, row_number, col_number
      end
    end
  end
end

def no_content_in_argument!
  raise ArgumentError,
    "The provided array is empty or contains empty elements."
end

def uneven_array_as_argument!(row_size, size)
  raise ArgumentError,
    "Uneven array. Row size is #{row_size} but size #{size} was expected."
end

def unexpected_value_in_argment!(element, row, col)
  raise ArgumentError,
    "Unexpected element #{element} at row #{row}, column #{col}."
end