Tag Archives: #hashcode2016 Google Hashcode Python Online Qualification

Google HashCode 2016, Qualification Round [w/ code]

Hello everyone!

Alvise here, I wanted to post online my solution for the qualification round of the 2016 Google HashCode challenge that took place yesterday (consider leaving a feedback as a comment) !

First things first: if you havent, HERE is the PDF with the instructions that were given us, if you did not took part in the challenge, I recommend you try it out.

Few words on the solution then: me and my team tried VERY hard to get the big picture and to produce a decent solution, but in the end this was what killed us: the right approach would have been an incremental solution: start easy, start VERY easy, and then go for it. The few points we got where thanks to Paolo Montesel: after few seconds of the deadline we were able to get a nicer result, but of course, time was out.

Lets talk about the logic behind what would have been a good starting point:

  1. At each time-step, for each order select the most appropriate warehouse (distance > object availability)
  2. For each drone, if the drone is free (not busy doing something), select the warehouse closest to him, and the most easy order from that warehouse
  3. Deliver that order, make the drone busy for the right amount of turns

Pretty easy, no optimization needed, and a solution with this steps would have allowed you to get in the 300th position. After this, become optimizing which warehouse for which drone, selecting always the shortest order, try to finish orders sooner as possible, etc..

Here the resulting scores of the code you will find at the bottom:

score

The code is available here:


#!/usr/bin/env python

"""
Google #Hashcode 2016, Qualification Round, Team #############

Beware, this is the worst code I've written in my
entire life. It's also full of bugs and hacks.
- Paolo MONTESEL
"""

import math
import random
import sys

history = list()

class Position:
    def __init__(self, y, x):
        self.y = y
        self.x = x

    def distance(self, obj):
        return distance(self.y, self.x, obj.y, obj.x)

class Drone(Position):
    def __init__(self, name, y, x, max_weight, max_item):
        self.name = name
        self.y = y
        self.x = x
        self.max_weight = max_weight
        self.weight = 0
        self.loaded_items = [0] * max_item
        self.loaded_weight = 0
        self.waits = 0

    def __str__(self):
        return "<drone {} {}>".format(self.y, self.x)

    def __repr__(self):
        return self.__str__()

    def deliver(self, order):
        wait_time = self.distance(order) + 1

        for item_id, item_count in enumerate(self.loaded_items):
            if item_count <= 0: continue order.items[item_id] -= self.loaded_items[item_id] history.append("{} D {} {} {}".format(self.name, order.name, item_id, self.loaded_items[item_id])) self.loaded_items[item_id] = 0 # break self.loaded_weight = self.update_loaded_weight() self.waits += wait_time def load(self, item_id, item_count, order): closest_warehouse_distance = None closest_warehouse = None calc_weight = weights[item_id] * item_count if calc_weight + self.loaded_weight >= self.max_weight:
            return False

        for w in warehouses:
            if w.can_fulfill(item_id, item_count):
                if closest_warehouse is None or self.distance(w) < closest_warehouse_distance: closest_warehouse = w closest_warehouse_distance = self.distance(w) if closest_warehouse is not None: self.loaded_weight += calc_weight self.waits += self.distance(closest_warehouse) + 1 closest_warehouse.reserve(item_id, item_count) self.load_item(item_id, item_count) history.append("{} L {} {} {}".format(self.name, closest_warehouse.name, item_id, item_count)) for added_item_id in xrange(KINDS): added_item_count = order.items[added_item_id] added_weight = added_item_count * weights[added_item_id] if added_item_id != item_id and added_item_count > 0 and closest_warehouse.can_fulfill(added_item_id, added_item_count) > 0 and \
                                        added_weight + self.loaded_weight < self.max_weight: self.loaded_weight += added_weight self.load_item(added_item_id, added_item_count) closest_warehouse.reserve(added_item_id, added_item_count) history.append("{} L {} {} {}".format(self.name, closest_warehouse.name, added_item_id, added_item_count)) return True return False def load_item(self, item_id, item_count): self.loaded_items[item_id] += item_count def step(self, t, orders): if self.waits > 0:
            self.waits -= 1
            return

        found = False
        for order in orders:
            for item_id, item_count in enumerate(order.items):
                if item_count > 0 and self.load(item_id, item_count, order):
                    found = True
                    self.deliver(order)
                    break
            if found:
                break

    def update_loaded_weight(self):
        ret = 0
        for item_id, item_count in enumerate(self.loaded_items):
            ret += item_count * weights[item_id]

        return ret


class Warehouse(Position):
    def __init__(self, name, y, x, max_items):
        self.name = name
        self.y = y
        self.x = x
        self.items = [0] * max_items

    def add_item(self, item_id, item_count):
        self.items[item_id] = item_count

    def can_fulfill(self, item_id, item_count):
        return self.items[item_id] >= item_count

    def reserve(self, item_id, item_count):
        self.items[item_id] -= item_count

        if self.items[item_id] < 0:
            exit(-1)

    def __str__(self):
        return "<WH {} {} {}>".format(self.y, self.x, self.items)

    def __repr__(self):
        return self.__str__()


class Order(Position):
    def __init__(self, name, y, x, max_items):
        self.name = name
        self.y = y
        self.x = x
        self.items = [0] * max_items

    def __str__(self):
        return "<Order {} {} {} {}>".format(self.y, self.x, len(self.items), self.items)

    def __repr__(self):
        return self.__str__()

    def add_item(self, kind, count):
        if kind not in self.items:
            self.items[kind] = 0
        self.items[kind] += count


def parse_line(line):
    return map(int, line.strip().split())


def distance(r1, c1, r2, c2):
    return math.ceil(math.sqrt((r1- r2) ** 2 + (c1 - c2) ** 2))

in_file = open(sys.argv[1], "rb")

M, N, DRONES, TURNS, MAX_LOAD = parse_line(in_file.readline())
KINDS = parse_line(in_file.readline())[0]

print M, N, DRONES, TURNS, MAX_LOAD
print "KINDS:", KINDS

weights = parse_line(in_file.readline())
print "WEIGHTS:", len(weights)

WAREHOUSES = parse_line(in_file.readline())[0]

print "WAREHOUSES:", WAREHOUSES

warehouses = list()
for i in xrange(WAREHOUSES):
    row, col = parse_line(in_file.readline())
    warehouse = Warehouse(i, row, col, KINDS)

    items_count = parse_line(in_file.readline())
    for item_id, item_count in enumerate(items_count):
        warehouse.add_item(item_id, item_count)

    warehouses.append(warehouse)

ORDERS = parse_line(in_file.readline())[0]
print "ORDERS:", ORDERS

orders = list()
for i in xrange(ORDERS):
    row, col = parse_line(in_file.readline())
    num_items = parse_line(in_file.readline())[0]
    kinds = parse_line(in_file.readline())

    order = Order(i, row, col, KINDS)
    for kind in kinds:
        order.add_item(kind, 1)

    orders.append(order)

drones = list()
for i in xrange(DRONES):
    drones.append(Drone(i, warehouses[0].y, warehouses[0].x, MAX_LOAD, KINDS))

try:
    for turn in xrange(TURNS):
        random.shuffle(drones)
        for drone in drones:
            drone.step(turn, orders)

        out = open(sys.argv[1] + ".out", "wb")
        out.write("{}\n".format(len(history)))
        for h in history:
            out.write(h + "\n")
        out.close()

        for i, order in enumerate(orders[:]):
            if sum(order.items) == 0:
                orders.remove(order)

        if turn % 100 == 0:
            print "TURN:", turn
            print len(orders), sum([1 if drone.waits > 0 else 0 for drone in drones])

        if len(orders) <= 0:
            break

except KeyboardInterrupt:
    pass

 

Thanks again to my team, here their contacts!

mail

See you soon and if you want, leave a comment on how your #hashcode2016 went!

12729301_10206716077713709_1231853888550121293_n

Advertisements