#!/usr/bin/env ruby
# big_city.rb version 6
# A solution to Google Code Jam practice problem A - Big City Skyline
# By Bill Burcham http://www.workingwithrails.com/person/5562-bill-burcham
class Object # all classes inherit from object so this available anywhere.
  def returning(value)
    yield(value)
    value
  end
end
class Skyline
  @@largest_so_far = 0
  def initialize( buildings, largest_so_far = 0)
    @buildings = buildings
    @@largest_so_far = largest_so_far
    @shortest_index = @tallest_index = 0
    @width = 0
    shortest_height = tallest_height = (@buildings.first ? @buildings.first.last : 0)
    @buildings.each_index() do |i|
      @width += @buildings[i].first
      if @buildings[i].last < shortest_height
        shortest_height = @buildings[i].last
        @shortest_index = i
      end
      if @buildings[i].last > tallest_height
        tallest_height = @buildings[i].last
        @tallest_index = i
      end
    end
  end
  def find_largest_rectangle
    if num_buildings > 0 && width * max_height > @@largest_so_far
      find_largest_rectangle_no_prune
    else
      @@largest_so_far
    end
  end
  def find_largest_rectangle_no_prune
    [ area, left_of_shortest.find_largest_rectangle, right_of_shortest.find_largest_rectangle ].max
  end

  private

  def num_buildings
    @buildings.size
  end
  def left_of_shortest
    Skyline.new( @shortest_index < 1 ? [] : @buildings.slice( 0..@shortest_index-1), @@largest_so_far)
  end
  def right_of_shortest
    Skyline.new( @shortest_index >= @buildings.size - 1 ? [] : @buildings.slice( @shortest_index+1..@buildings.size-1), @@largest_so_far)
  end
  def area
    returning min_height * width do |a|
      @@largest_so_far = a if a > @@largest_so_far
    end
  end
  def min_height
    @buildings[@shortest_index].last
  end
  def max_height
    @buildings[@tallest_index].last
  end
  def width
    @width
  end
end

skylines = [ Skyline.new( [[5,7], [ 1,20], [3,5], [6,3], [2,10]]), Skyline.new( [[5,7], [ 3,20], [3,5], [6,3], [2,10]])]
skylines.each do |skyline|
  size = skyline.find_largest_rectangle
  puts "Largest rectangle has area: #{size}"
end
[1,10,100,1000,10000,100000,1000000,10000000].each do |big_n|
  buildings = (1..big_n).collect do |n|
    [ (rand * 1000).to_i, (rand * 100000000).to_i]
  end
  start = Time.now
  size = Skyline.new( buildings).find_largest_rectangle
  puts "Largest rectangle for random skyline of size #{big_n} is #{size} and took #{ Time.now - start} seconds to compute with pruning"
  start = Time.now
  size_no_prune = Skyline.new( buildings).find_largest_rectangle_no_prune
  puts "Largest rectangle for random skyline of size #{big_n} is #{size_no_prune} and took #{ Time.now - start} seconds to compute with NO pruning"
  puts "Pruning code disagrees with non-pruning code!" if size != size_no_prune
end