So Noah (my fellow coursemate/soulmate) and I recently came 1st in Ireland (and 164th globally) in Google’s annual HashCode competition. We competed from the DCU hub with about 8 other teams, enjoing the perks such as pizza and Google merch. Our code is available on Github.

The Problem Statement

The problem statement is available here. Typically the problem in HashCode takes the form of some large scale optimisation problem, generally something NP-hard. This year was no different.

The challenge was to minimise the latency of fetching videos for a large number of users across a reasonably complex network.

As a quick overview: We were given a number of endpoints, each of which make a known amount of requests for any particular videos. These endpoints are all connected to caches (of fixed size), most are connected to multiple. Storing a video in a cache means that the endpoint can pull the video from there as opposed to the datacenter (which has a higher latency). The goal is to minimise the average latency across all the requests.

We were given four “scenarios” which varied the number of requests, caches, cache latencies, etc. You didn’t have to use the same solution for each of the scenarios (as we ended up not doing), they’d accept the best score for each across all of your submissions and sum the scores to produce the final result.

Our Solution(s)

To call our first solution “basic” would be an understatment. We had learned from previous years that it was always good to get points on the board early. This confirms you have some semblance of an end-to-end pipe, something that would be much harder to debug later on.

This initial solution involved putting each video, as it was read in, into every cache until the caches were full. It netted us a surprising 764,566 points and 8th place on the global tables1. Needless to say it was a little less surprising when we were quickily overtaken.

After that there were three hours of iterative development: trying smart things, trying not so smart things and trying combinations of both. Eventually the solution we ended with up with was cian_is_smart.py (if you’ll excuse the naming convention). This produced a score of 2,285,8912.

We start by reading in all the data using a nice little3 function defined in read_in.py. The letters are defined in the problem statement, the rest are lists of objects corresponding to the type of data.

V, E, R, C, X, videos, endpoints, requests, caches = read()

The next step iterates through each of the caches. For each cache we create a vids_wanted dictionary, this ties a score to each video object for how benificial it would be to the latency to place it in this cache.

That score is calculated by going through each endpoint connected to the cache and for every video that endpoint requests we multiply the number of times it’s requested by the saving in latency if it were to be put in the current cache versus where it would be retrieved from otherwise (be it the datacenter or another cache).

If that was hard to follow… well… the code isn’t great either.

for cache in caches:
    vids_wanted = {}
    for endp in cache.endpoints:
        # lat_to_endp is the latency from cache -> endpoint
        # lat_redux is the total potential latency reduction per video
        lat_to_endp = cache.connected[endp.i]
        for vid, lat_redux in endp.get_wanted_vids(lat_to_endp).items():
            if vid in vids_wanted:
                vids_wanted[vid] += lat_redux
            else:
                vids_wanted[vid] = lat_redux

And (a cleaned version of) the function inside Endpoint:

def get_wanted_vids(self, lat_to_cache):
    wanted = {}
    for req in self.requests:
        current_latency = self.dc_lat  # Latency to datacenter
        if req.video.i in self.cached_vid_ids:
            current_latency = self.cached_vid_ids[req.video.i]
        # If it would be an improvement add it to the wishlist
        if lat_to_cache < current_latency:
            wanted[req.video] = req.num_req * (current_latency - lat_to_cache)
    return wanted

The ending of the solution is fairly predictable, we sort the videos on what makes the best impact and keep adding them to the cache in that order until it’s full. The add_video method in cache reaches back into each endpoint connected to it and updates the best latency for that video for later iterations.

    vids_best_to_worst = sorted(
        vids_wanted,
        key=lambda v: vids_wanted[v],
        reverse=True)
    for vid in vids_best_to_worst:
        if cache.vid_fits(vid):
            cache.add_video(vid)

After the main loop exits the contents of each cache are printed in the format required by HashCode and we’re all done!

Retrospective

So I’ve done out some pros and cons of our approach, hopefully they can help us and maybe other teams improve for later comps.

Pros:

  • We used Github to share code, this made thing very easy when sharing a file or fixing a bug.
  • We made a script for automatically running each of the inputs and zipping the source files. This probably wasn’t worth the time invested but was much more fun than doing it manually. gen_output.py
  • Our more iterative approach probably helped us avoid super awkward bugs and didn’t seem to slow us down.
  • Having each of the data types represented by a class made it much easier to work with (as opposed to the dreaded, and inevitable, 3 dimensional undocumented list structure).

Cons:

  • We didn’t get to do any fun graph stuff, max flow and things.
  • No proper versioning system for our code.4
  • We had no idea how long a particular idea would take to run, it often wasn’t obvious the time complexity of a method.
  • The code had a lot of redundancy, things are very often stored twice and everything points to everything else (given the time constraints you can forgive us I’m sure).

Our winning evening finished with a trip to Doyle’s pub with another team for some (tasteful) gloating.

Reach out to me on Twitter if you spot any of the typos I’ve surely left or just for clarification on anything.

Adiós,

-Cian

  1. This was 30 minutes into the contest. 

  2. Note that our final score was 2,416,068, roughly 130k better. A solution Noah had developed earlier produced a better output for one of the four test cases, I’ll edit with a link when he writes about it. 

  3. The “little” is very sarcastic. Here be dragons 

  4. Our first solution which I mentioned previously was called shove_in.py, our next iteration was shove_in_smarter.py, then followed shove_in_even_smarter.py and it all culminated in shove_in_a_little_smarter.py (after even_smarter’s disastrous results).