#! /usr/bin/env ruby

require 'set'

if ARGV.length != 1
    abort("Incorrect arguments - needs input file")
elsif not File.exist? (ARGV[0])
abort("File #{ARGV[0]} did not exist")
end

file = ARGV[0]

Block = Struct.new(:id, :x, :y, :z)
SupportedBy = Struct.new(:blocks, :z)
supports = Hash.new
supported_by = Hash.new

blocks = File.open(file, "r").each_line(chomp: true).with_index.map do |line, id|
    block_start, block_end = line.split("~")
    start_x, start_y, start_z = block_start.split(",")
    end_x, end_y, end_z = block_end.split(",")
    supports[id] = []
    Block.new(id, start_x.to_i..end_x.to_i, start_y.to_i..end_y.to_i, start_z.to_i..end_z.to_i)
end

def height_sort(a,b)
    if a.z.first == b.z.first
        # Make it a stable sort
        a.y.first == b.y.first ? a.x.first <=> b.x.first : a.y.first <=> b.y.first
    else
        a.z.first <=> b.z.first
    end
end

blocks.sort! {|a,b| height_sort(a, b)}

def overlap?(range_1, range_2)
    range_1.include?(range_2.first) || range_1.include?(range_2.last) || range_2.include?(range_1.first) || range_2.include?(range_1.last)
end

blocks.reduce([]) do |lower_blocks, block|
    support_blocks = lower_blocks.reduce(SupportedBy.new([], 0)) do |candidate_supports, lower_block|
        if overlap?(block.x, lower_block.x) && overlap?(block.y, lower_block.y)
            if lower_block.z.last > candidate_supports.z
                SupportedBy.new([lower_block], lower_block.z.last)
            elsif lower_block.z.last == candidate_supports.z
                candidate_supports.blocks << lower_block
                candidate_supports
            else
                candidate_supports
            end
        else
            candidate_supports
        end
    end
    drop = block.z.first - support_blocks.z - 1
    block.z = (support_blocks.z+1)..(support_blocks.z+block.z.size)
    support_blocks.blocks.each {|support| supports[support.id] << block}
    supported_by[block.id] = support_blocks.blocks
    lower_blocks << block
    lower_blocks
end

disintegratable = supports.filter {|block_id, supports_list| supports_list.all? {|supported| supported_by[supported.id].length > 1} }

puts "#{disintegratable.length} disintegratable blocks"

def find_droppers(id, supports, supported_by, dropping, cache)
    new_drops = supports[id].filter do |block|
        (Set.new(supported_by[block.id].map(&:id)) - dropping).length == 0
    end
    dropping = dropping + new_drops.map(&:id)
    new_drops.each do |supported_block|
        cache_key = [supported_block.id, Set.new(supported_by[supported_block.id].map(&:id)) & dropping]
        if cache.include?(cache_key)
            dropping += cache[cache_key]
            #puts "Got #{cache[cache_key]} for #{cache_key}"
        else
            supported_droppers = find_droppers(supported_block.id, supports, supported_by, dropping, cache)
            cache[cache_key] = supported_droppers
            #puts "Caching #{supported_droppers} for #{cache_key} while dropping #{dropping}"
            dropping += supported_droppers
        end
    end
    dropping - [id]
end

cascade = Hash.new
cache = Hash.new

blocks.reverse.each do |block|
    id = block.id
    cascade[id] = find_droppers(id, supports, supported_by, Set.new([id]), cache)
end

puts "Dropping a total of #{cascade.values.map{|val| val.length}.sum} blocks"