Help Me Grow Carrots

I've used Divide and Conquer approach.

Key Idea

Divide the matrix into two halves left and right, and now biggest rectangle occurring in the matrix is one of the following:

1. The biggest rectangle completely residing in left matrix

2. The biggest rectangle completely residing in right matrix

3. The biggest rectangle residing partially in left and partially in right matrix

Run Time Analysis

Its $O(n^2)$ because the algorithm follows $T(n) = 4 \cdot T[\frac{n}{4}] + O(n^2)$ , where $T(n)$ is the number of steps for matrix of size $n\times n$ .

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101

# A matrix library like NumPy in Python
require 'nmatrix'

# Generate a 1000x1000 matrix filled with 0's
matrix = NMatrix.new [1000, 1000], Array.new(1e6, 0)

# Read points from file
points = File.read('points.txt').
              split(/[^\d]/).
              reject(&:empty?).
              map(&:to_i)

# For all given points set value to 1 indicating obstacle
points.each_slice(2) do |i, j|
  matrix[i, j] = 1
end ;

# Fix the maximum number of rectangular blocks possible
def max_blocks matrix
  # Base case
  if matrix.rows == matrix.cols && matrix.rows == 1
    matrix[0, 0] == 0 ? 1 : 0
  # Columns > Rows
  # 1. Split to two matrices
  # 2. Find max_blocks in left
  # 3. Find max_blocks in right
  # 4. Find max_blocks occuring in both left and right
  # 5. Fid max of 2, 3, and 4 above
  elsif matrix.cols >= matrix.rows
    left, right = split_matrix matrix
    middle_score = score_at_middle matrix
    [max_blocks(left), max_blocks(right), middle_score].max
  # Row > Columns
  # Transpose the matrix and find its max_blocks
  else
    max_blocks matrix.transpose
  end
end

# Split matrix to left and right
def split_matrix matrix
  split_at = matrix.cols/2
  [
    matrix[0..-1, 0..split_at-1],
    matrix[0..-1, split_at..matrix.cols-1]
  ]
end

# Find the score when rectangle occurs partially in 
# left and partially in right
def score_at_middle matrix
  best = 0
  left, right = split_matrix matrix
  left_scores = all_left_scores left
  right_scores = all_right_scores right
  n = matrix.rows
  (0..n-1).each do |start|
    (start..n-1).each do |stop|
      min_left_dist = (start..stop).map { |i| left_scores[i] }.min
      min_right_dist = (start..stop).map { |i| right_scores[i] }.min
      next if min_left_dist == 0 or min_right_dist == 0
      current_score = (min_left_dist + min_right_dist)*
        (stop-start+1)
      best = current_score if current_score > best
    end
  end
  best
end

# Find number of consecutive zeros from right side
def all_left_scores matrix
  left_scores = {}
  matrix.rows.times do |r|
    row = matrix[r, 0..-1]
    score = 0
    row.to_a.reverse.each do |element|
      break if element == 1
      score += 1
    end
    left_scores[r] = score
  end
  left_scores
end

# Find number of consecutive zeros from left side
def all_right_scores matrix
  right_scores = {}
  matrix.rows.times do |r|
    row = matrix[r, 0..-1]
    score = 0
    row.to_a.each do |element|
      break if element == 1
      score += 1
    end
    right_scores[r] = score
  end
  right_scores
end

answer = max_blocks matrix
# => 9916