Skip to content

Instantly share code, notes, and snippets.

@Nikamura

Nikamura/solve.rb

Created February 11, 2016 21:43
Show Gist options
  • Save Nikamura/ad7b52368004bc9548b0 to your computer and use it in GitHub Desktop.
Save Nikamura/ad7b52368004bc9548b0 to your computer and use it in GitHub Desktop.
Download ZIP
Hash code 2016 solution in Ruby 123665 points
Raw
solve.rb
require 'JSON'
rows = 0
cols = 0
no_drones = 0
deadline = 0 # 1000000
max_load = 0
number_of_producs = 0
weights = []
no_of_warehouses = 0
warehouses = []
orders = []
drones = []
no_of_orders = 0
def ea(x1, y1, x2, y2)
Math.sqrt((x1.to_i - x2.to_i) ** 2 + (y1.to_i - y2.to_i) ** 2).ceil
end
class Warehouse
attr_accessor :id
attr_accessor :x
attr_accessor :y
attr_accessor :products
def can_fulfill?(item_id, quantity)
if (product = products[item_id])
if product >= quantity
true
else
false
end
else
false
end
end
def can_complete_order?(order)
can_complete = []
order.products.each do |item_id, quantity|
can_complete << can_fulfill?(item_id, quantity)
end
!can_complete.include?(false)
end
def take(item_id, quantity)
fail unless can_fulfill?(item_id, quantity)
products[item_id] -= quantity
products.delete(item_id) if products[item_id] == 0
end
end
class Order
attr_accessor :id
attr_accessor :x
attr_accessor :y
attr_accessor :products
attr_accessor :completed
def to_json
{id: id, x: x, y: y, products: products}
end
def take(item_id, quantity)
products[item_id] -= quantity
products.delete(item_id) if products[item_id] == 0
end
end
class Drone
attr_accessor :id
attr_accessor :warehouse
attr_accessor :capacity
attr_accessor :carrying
attr_accessor :x
attr_accessor :y
attr_accessor :traveled
def can_carry?(weight)
puts capacity
puts weight
capacity >= weight
end
end
files = %w(busy_day mother_of_all_warehouses redundancy)
File.readlines(files[2] + '.in').each_with_index do |line, line_no|
if line_no == 0
rows, cols, no_drones, deadline, max_load = line.split(" ")
no_drones.to_i.times do
drones << Drone.new
end
end
if line_no == 1
number_of_producs = line.to_i
end
if line_no == 2
weights = line.split(" ")
end
if line_no == 3
no_of_warehouses = line.to_i
end
line_split ||= no_of_warehouses * 2 + 4 if no_of_warehouses
next unless line_no > 3
if line_no < line_split
if line_no.even?
warehouse = Warehouse.new
warehouse.x = line.split(" ")[0]
warehouse.y = line.split(" ")[1]
warehouses << warehouse
else
warehouse = warehouses[warehouses.count - 1]
warehouse.products = Hash.new
line.split(" ").each_with_index do |quantity, item_id|
warehouse.products[item_id] = quantity.to_i if quantity.to_i > 0
end
warehouse.id = warehouses.count - 1
warehouses[warehouses.count - 1] = warehouse
end
end
if line_no == line_split
no_of_orders = line.to_i
end
if line_no > line_split
l = (line_no - line_split) % 3
if l == 1
order = Order.new
order.x = line.split(" ")[0]
order.y = line.split(" ")[1]
order.id = (line_no - line_split - 1).div(3)
orders << order
end
if l == 2
# no_of_ordered_products
end
if l == 0
order = orders[orders.count - 1]
order.products = Hash.new
# order.id = orders.count - 1
line.split(" ").each do |item|
order.products[item.to_i] ||= 0
order.products[item.to_i] += 1
end
order.completed = false
orders[orders.count - 1] = order
end
end
end
# All drones are at the first location
drones.each_with_index do |drone, index|
drone.id = index
drone.x = warehouses[0].x
drone.y = warehouses[0].y
drone.capacity = max_load
drone.traveled = 0
end
cmds = []
orders.sort! do |x, y|
x.products.count <=> y.products.count
end
sort = 0
orders.sort! do |x, y|
ea1 = ea(x.x, x.y, warehouses[sort].x, warehouses[sort].y)
ea2 = ea(y.x, y.y, warehouses[sort].x, warehouses[sort].y)
ea1 <=> ea2
end
warehouses.sort! do |x, y|
ea1 = ea(x.x, x.y, warehouses[sort].x, warehouses[sort].y)
ea2 = ea(y.x, y.y, warehouses[sort].x, warehouses[sort].y)
ea1 <=> ea2
end
orders.each do |o|
o.products.sort_by do |item_id, quantity|
weights[item_id] * quantity
end
end
orders.each do |order|
products = order.products
current_drone = 0
products.each do |item_id, quantity|
max_quantity = max_load.to_i.div(weights[item_id].to_i)
while quantity > 0
pick = max_quantity > quantity ? quantity : max_quantity
s = []
i = 0
warehouses.each do |wh|
next unless wh.can_fulfill?(item_id, 1)
while true
drone = drones[current_drone]
total_dist = ea(drone.x, drone.y, wh.x, wh.y) + ea(wh.x, wh.y, order.x, order.y) + 2
if drone.traveled + total_dist < deadline.to_i
break
end
current_drone += 1
current_drone %= no_drones.to_i
i += 1
break if i > no_drones.to_i
end
break if i > no_drones.to_i
if wh.products[item_id] < pick
pick = wh.products[item_id]
end
s << { wh: wh, drone: drone, dist: total_dist }
end
s.sort! do |x, y|
x.fetch(:dist) <=> y.fetch(:dist)
end
wh = s[0].fetch(:wh)
drone = s[0].fetch(:drone)
dist = s[0].fetch(:dist)
cmds << "#{drone.id} L #{wh.id} #{item_id} #{pick}"
wh.take(item_id, pick)
cmds << "#{drone.id} D #{order.id} #{item_id} #{pick}"
order.take(item_id, pick)
drone.traveled += dist
drone.x = order.x
drone.y = order.y
current_drone += 1
current_drone %= no_drones.to_i
quantity -= pick
end
end
end
puts cmds.count
puts cmds.join("\n")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment