Advent of Code 2018

Advent of Code is an awesome beginner-level programming competition happening every December. Unlike a standard programming competition with 5 or 6 problems, AoC publishes 2 problems each day for 25 days, totaling 50 problems, touching a variety of programming topics. It is perfect for anyone wanting to brush up on their programming skills (me), or learn a new programming language (also me).

Having said that, this year I’ve decided to learn a new programming language, specifically Go. Many great open source tools, such as Terraform, Docker, and Kubernetes, are completely written in Go, and many more are published every day, so these new skills will not stay unused.

Without further ado, here are my solutions to this year’s problems: https://gitlab.com/IgnasK/advent-of-code-2018.

Notable solutions

I am going to highlight some notable problems which I had problems with, or if I am particularly proud with their solutions.

Day 3: No Matter How You Slice It

This problem boils down to keeping track of overlaping rectangles on a grid, and counting the area where at least 2 rectangles overlap.

Since the problems are getting progressively more difficult through the competition, the problem itself is easy and able to be solved with brute force, or dynamic programming. I, however, saw an opportunity to use one of my favourite data structures: Fenwick Tree.

Fenwick tree allows for quick O(log n) range updates and prefix sums, but most importantly (jokingly), the code is very compact:

type Fenwick struct {
    arr []int
}

func (f *Fenwick) Update(x int, value int) {
    x++
    for ; x < len(f.arr); x += x & (-x) {
        f.arr[x] += value
    }
}

func (f *Fenwick) UpdateRange(start int, end int, value int) {
    f.Update(start, value)
    f.Update(end, -value)
}

func (f *Fenwick) Get(x int) int {
    x++
    sum := 0
    for ; x > 0; x -= (x & -x) {
        sum += f.arr[x]
    }
    return sum
}

func NewFenwick(size int) *Fenwick {
    return &Fenwick{arr: make([]int, size+1)}
}

Day 10: The Stars Align

Problem on Day 10 was highly non-standard: You are given a set of 2D points with velocities, and asked to figure out what word do these points spell out when they cluster close to each other.

Unlike every other solution for this competition, this one is completely visual. I have simulated point movement until their bounding box was small enough, and then relied on my eyes to pick out the solution. Although that has worked, I am still intrigued whether there are any simple ways to this whole problem automatically, letting the program recognise the patterns without human help.

Day 15: Beverage Bandits

This is by far the most tedious problem of the competition, taking me almost 6 hours to solve, and in the end I had to consult Reddit to find the final bug. My final solution is 464 lines of Go code.

Days 16, 19 and 21: Chronal Device

These 3 problems explored an unknown instruction set (likely inspired by Christopher Domas talk about Hardware Backdoors in x86, highly recommend watching it), and interpreting it.

Although it is possible to solve these problems using a simple interpreter, I have decided to go a bit further and wrote a transpiler to Go, which is available here. It has cut down execution time of Day 19 second part from 1m32s all the way down to 250ms - 99.7% reduction in runtime.