## mark a section (Learn more)

#!/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

This paste will be private.