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

6 thoughts on “Google HashCode 2016, Qualification Round [w/ code]

  1. nasvera

    #Hashcode2016, was very interning, it also make me look like a new born baby in the programming word, wooo, at first i understood the task perfectly, i began to solve it with my paper and pen, not until about 30min of the start time i check the judge system to my surprise some teams are having 12078 pint, i was discourage, and now i and my time need to create a program to help us out, but we could not come up with any. we just have to accept the challenge. and you Mr Alvise, i see you as a geek, have benign following your post right form time..i’ ll like you to see me through(teach/put me through ) the code jam.
    thanks.
    sing: Nasir Zakka.

    Like

    Reply
    1. Alvise Post author

      Hi Nasir! This challenge was harder to code than to think, or at least that’s how I felt before and after. If you want to solve the problem then I would suggest you divide the challenge in steps. For example (supposed you loaded the data correctly already), try serving ONLY the FIRST order, with ONLY the FIRST drone from ONLY the first WAREHOUSE, loading and unloading sequentially (Load->Unload->Load…) ONLY the ONE object of the order (I assume is possible, to be sure you can try this on the map mother_of_all_warehouse..). When this is done, and your output is accepted by the judge system, start using more orders and choosing always the one closest to the warehouse you are closest to. And so on…

      Like

      Reply
    1. Alvise Post author

      Really really code that was written on the go, plus I’m struggling with WordPress.com, code management is just awful. But thanks, appreciated you checking this out!

      Like

      Reply
  2. Shaibu Shaibu

    wow that is really really amazing. I also participated this year though my team could not submit on time which leaves me to ask “how were you guys able to solve the task and submit under a very short time??” I mean it took my team quite a long while to fully grab the task and handle the input files. Seriously, any tips or tricks as to how you guys were able to code this stuff so fast??

    Like

    Reply
    1. Alvise Post author

      Hi Shaibu thanks for checking my blog out! As I wrote above, we did submit a good solution but was way lower than the results in the image. The fact is that there was a bug in the code (specifically a ‘break’ in the wrong loop) that we fixed 30 seconds before deadline: once solved we were not able to upload the results as time went off while loading the output files! Anyway, there were also teams able to submit a solution after few hours and that was impressive. My personal opinion is that you should have started with a strong class division. For example, creating a function that would update a energy cost of each order in relation to each warehouse, and after another function for the energy of the ware house. With those two functions working (and being sure input are read right), it would have been matters of just using them right. Overall, with a well explanatory code, tested by steps, it would have been possible. Tips? Always divide a big problem into smaller one, and try to code/debug each fragment separate or incrementally!

      Like

      Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s