Submission for E La Carte coding challenge by @patio11

count_rectangle_area.rb

#Hiya guys,
#I'm Patrick McKenzie (patio11 on HN) and I'm doing this just out of joy of programming puzzles.
#Not really looking for a job at the moment.
#
#I've taken some liberty with standard Ruby programming conventions to make this one file without
#dependencies, for the ease of you actually running it.  It is the result of a very hack-in-progress
#sort of workflow.  A git repo showing my work in stages might be more interesting but, well,
#hard to submit that into the form.


#CODE BEGINS:

#Given an array of Ps and Os, counts size of rectangle with largest width starting
#at top-left corner identified by start_x and start_y composed of only the specified character.
#
#Contiguous restaurants must be in a rectangle per problem description (thank God -- otherwise
#this problem would require me to write a breadth first search), which means we don't have to
#worry about shapes like:
#
#PPP
# PP
# P
#
#
# There are shapes which would confuse algorithms if you only considered each point
# once without backtracking.  For example:
#
#PP
#PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP
#PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP
#
#might get interpreted as a 2x3 rectangle and a 2xlots rectangle instead of a
#2x(lots+2) rectangle with some irrelevant cruft nearby.  We don't want to do that,
#and cycles are cheap, so we'll just calculate the largest rectangle extending first right
#and then down from each possible starting point on the grid.


def size_of_widest_rectangle(location_array, start_x, start_y, search_character = "P")

  return 0 if location_array[start_y][start_x] != search_character

  #First, we'll find the width of rectangle's top.  Remember, we're maximizing for this first.
  top_row = location_array[start_y]
  current_x = start_x
  while ((current_x + 1 < top_row.length) && (top_row[current_x + 1] == search_character))
    current_x += 1
  end

  rectangle_width = current_x - start_x + 1

  #Now, we'll just count how many rows we can add where everything between start_x and current_x is P.
  #Handily, ruby gives us expressive ways to do this, so I don't have to write the (faster, but lengthier)
  #array access code myself.

  current_y = start_y
  while (current_y + 1 < location_array.length)
    candidate_row = location_array[current_y + 1]
    if candidate_row[start_x..current_x].uniq == [search_character]
      current_y += 1
    else
      #We tried taking the next line but it had an extraneous character somewhere.
      #Oh well, we've got the largest rectangle possible now.
      break
    end
  end

  rectangle_height = current_y - start_y + 1

  return rectangle_width * rectangle_height
end


#Reads specified file in, converts into array of characters.  Strips whitespace and anything not O or P.
#Technically could use array of strings, but would require changing syntax of above method in midstream.
#e.g. if file is
#
#POP
#PPP
#
#then I want [%w{P O P}, %w{P P P}]
def load_data_file(filename)
  File.readlines(filename).map {|line| line.gsub(/[^PO]/, "").split("")}
end

#A helper method so we can embed test cases directly in code.  Assumes test case format will be like this:
#test_case = <<TEST_CASE
#POPO
#PPPP
#TEST_CASE
def make_string_literal_into_test_map(test_string)
  test_string.gsub(/[^OP]+\n/m, "").split("\n").map {|line| line.gsub(/[^OP]/, "").split("")}
end

#Braindead method, but minimizes dependencies.  In a real application, I'd be using
#a real testing library like runit, but I want to give you guys a single flat file that works
#no matter what you have in your environment.
def assert(predicate, message_on_failed_assertion = "Assertion failed.")
  raise message_on_failed_assertion unless predicate
end

test_case = <<TEST_CASE
  POPP
  PPPP
TEST_CASE

test_array = make_string_literal_into_test_map(test_case)

assert test_array.length == 2, "make_string_literal_into_test_map did not count number of rows correctly"
assert test_array[0].length == 4, "make_string_literal_into_test_map did not count number of columns correctly"
assert test_array[0][1] == "O", "make_string_literal_into_test_map is not producing output which lines up with expectations"


#Now that we have a way of testing things, let's create a quick sample grid:
#In a real assignment I would be a little more thorough with testing this, but here I just
#threw together something which included odd shapes of Ps that would probably break a busted
#algorithm.

test_city = <<TEST_CASE
  POOP
  PPPO
  PPOO
  POPP
TEST_CASE

test_city_array = make_string_literal_into_test_map(test_city)

#I calculated these by hand.
correct_rectangle_sizes = [4, 0, 0, 1,
                          3, 2, 1, 0,
                          2, 1, 0, 0,
                          1, 0, 2, 1]


(0..15).each do |tested_rectangle_index|
  start_x = tested_rectangle_index % 4
  start_y = tested_rectangle_index / 4
  assert correct_rectangle_sizes[tested_rectangle_index] == size_of_widest_rectangle(test_city_array, start_x, start_y), 
    "The rectangle starting at (#{start_x}, #{start_y}) was not calculated correctly."
end

puts "Assertions all passed successfully, so we haven't made a horrific error (yet)!  Loading the data file."


assert (ARGV.length == 1) && File.exists?(ARGV[0]), "Usage: ruby script-name.rb path/to/city_grid.txt"


location_array = load_data_file(ARGV[0])

#This could be easily done via a loop which kept track of the currently observed maximum, avoiding
#a sort, but I wanted to keep some data around for sanity checking purposes, and ruby sort on
#a million elements is cheap for my computer to do, so I'll do it the easy-for-me way.

#Format: a list of [count, top_x, top_y] triplets.
counts_of_contiguous_sizes = []

puts "Counting sizes of rectangles"
current_y = 0
while (current_y < location_array.length)
  current_x = 0
  while (current_x < location_array[current_y].length)
    size = size_of_widest_rectangle(location_array, current_x, current_y)
    counts_of_contiguous_sizes << [size, current_x, current_y]
    current_x += 1
  end
  current_y += 1
  puts "Just finished line #{current_y}" if (current_y % 500 == 0)
end

#Sort rectangles in descending order of area
counts_of_contiguous_sizes.sort! {|a, b| a[0] <=> b[0]}.reverse!

#Show five largest rectangles for quick smoke test inspection.
#puts counts_of_contiguous_sizes[0..5].map {|solution| solution.inspect}

top_result = counts_of_contiguous_sizes[0]
puts "Largest rectangle area is #{top_result[0]}"

#For visual verification purposes, I printed out the largest rectangle and hand inspected it.
#puts (0..(location_array[0].length - 1)).map {|i| i}.inspect
#location_array[(top_result[2]..(top_result[2] + 12))].each {|line| puts line.inspect}