Advent of Code

github

This December there was another edition of Advent of Code. This time I decided I would take it seriously and do all the challenges. Here are my notes on the experience.

Post illustration

Advent of Code is an event of small programming puzzles targetting various skill-sets and levels. It takes its inspiration from Advent calendars and presents a story about how Santa needs our help to save Christmas. Each day between December 1 and 25 a new challenge is released. A challenge has two puzzles linked together thematically with the second one being unlocked only after the first is completed. For every puzzle you solve you get a star of a total of 50 available.

Puzzles are solved by processing a given input and inserting an output. Inputs are generally long lists of numbers or strings with many inputs being generated and given to different users. Outputs are usually integer numbers or, more rarely, strings. There are no interpreters or compilers running on the platform that take your source code, so problems can be solved in any programming language or even by hand. Many people take this opportunity to learn new languages or sharpen their knowledge on one they already knew.

It was created by Eric Wastl in 2015. He created it because of his passion for programming puzzles and a desire to help people learn to become better programmers. They usually take three or four months of all his spare time to make.

The difficulty of the challenges is finely tuned: Weekends usually get more labour-intensive exercises compared to weekdays; challenges get harder as the event progresses but there are a few easier breathers thrown in the middle to prevent burnout. The 2-part nature of each day challenge is also explored in an interesting way. Sometimes the second part builds on the first seamlessly but other times key requirements change suddenly, simulating what happens in the real world with actual clients.

I’ve participated in Advent of Code in the past, solving some challenges back in 2015, 2016 and 2018 but I never took it all through the end. I’ve made it a goal this year to finish them all and do so in Ruby, being as idiomatic as I could. Here are my solutions.

There’s a competitive aspect to the challenges: Solve them quick enough and you’ll get in the top of the global leaderboard. Each day they’re unlocked at midnight EST/UTC-5 though, because that was the time Eric - being from New York - could be awake and handle any problems that might occur. That’s 5 AM in my time zone, so I’ve largely skipped the competition part of it.

Some people integrate advent of code into their morning routine

You can also use private leaderboards. I had some friends participating this year, gathered around the one Hugo Peixoto set up. Everyone in it was super-smart, and there was a wide array of languages being used like Rust, Scala or Python. It was fun to see how people approached problems and being offered feedback on my code. The community at large is very supportive and welcoming as well, with its subreddit getting lots of activity during the month.

Spoilers below

This year there was a healthy mix of domains in the challenges. Solving them required recursion, cellular automata, regex, number theory and more. As the problems grew more complex (specially on part 2 of every challenge), more attention to how your algorithm was built and what data structures it used was needed to solve them in a timely manner.

Solving the challenges was made much easier for me by ruby’s super complete Enumerable mixin, available on the Array and Hash classes. All of the exercises called, in one way or another, for transforming, filtering or aggregating data and having methods like map, select or reduce built-in the language really helps.

lines = File.readlines(ARGV[0]).map(&:strip)

indexed_lines = lines.each_with_index

w = lines.first.size

p indexed_lines.count { |line, i| line[i * 3 % w] == '#' }

p [[1,1],[3,1],[5,1],[7,1],[1,2]]
    .map { |right, down|
        indexed_lines
            .count { |line, i| i % down == 0 && line[(i / down) * right % w] == '#' }
    }
    .reduce(:*)
Day 3's solution had you counting the trees (represented by the # character) in Santa's way as he descended a mountain with his sled

I’ve also learned a couple new things in ruby, like the intersection and union array operators. They came in handy for day 21’s Allergen Assessment.

There were some fun optimizations to grab in the challenges. For instance, day 17 called for implementing Conway’s Game of Life across 3 and 4 dimensions for a few cycles and then count the number of cells in an active state. Since cell-state changes are symmetrical across planes, you can skip calculating a heavy chunk of cell changes and simply multiply the count by 2 or 4, according to the current plane slice and number of dimensions.

Patience and careful reading of the challenges also helps. In day 20 aptly named Jurassic Jigsaw, a list of puzzle pieces was provided and in part A you were supposed to find the tiles that ended up on the corners of the puzzle. My first go was to try and get all possible arrangements of tiles using permutation and then find out if they matched, but rereading the challenge you find out that each tile edge can only match another’s, so finding out what the corner pieces are is simply a matter of finding the tiles whose edges match only 2 other tiles’ edges.

def mirror(piece)
    piece.map(&:reverse)
end

def get_border_right(piece)
    piece.map { |y| y.chars[-1] }.join
end

def get_border_down(piece)
    piece[-1]
end

def get_border_left(piece)
    piece.map { |y| y.chars[0] }.join
end

def get_border_up(piece)
    piece[0]
end

def get_piece_borders(piece)
    [get_border_up(piece), get_border_down(piece), get_border_left(piece), get_border_right(piece)]
end

def pieces_interlock(tile, neighbour)
    [tile, mirror(tile)].any? { |t| t.any? { |border| neighbour.any? { |nborder| border == nborder } } }
end

def is_corner(key, tiles)
    number_tiles_interlocked = 0

    (tiles.keys - [key]).each do |other_key|
        number_tiles_interlocked += 1 if pieces_interlock(tiles[key], tiles[other_key])

        break if number_tiles_interlocked > 2
    end

    return number_tiles_interlocked == 2
end

def part_a(tiles)
    corners = {}

    tiles.keys.each do |key|
        if is_corner(key, tiles)
            corners[key] = tiles[key] 

            return corners.keys.reduce(:*) if corners.size == 4
        end
    end
end

input = File.read(ARGV[0]).split("\n\n").map { |x| x.split("\n") }

tiles = input
        .map { |x| [x[0].sub('Tile ', '').sub(':', '').to_i, x[1..-1]]}
        .to_h { |t, x| [t, get_piece_borders(x)]}

p part_a(tiles)
Snippet from day 20's solution

The importance of data structures was also put in evidence: Things that I’d normally use arrays for (like 2d boards, for example) were solved much quickly using hashes and I ended up using them in some way or form in 8 of the 25 days. They were also useful for caching data that was already evaluated, in exercises where you had to backtrack.

Day 23 was the most prominent example of their importance. In this puzzle you had to keep track of numbers shifted around in a circle in specific patterns. Part A could easily be solved with array manipulation, but that method was unbearably slow on part B, where the number of moves increased exponentially. I ended up needing to implement a circular buffer structure and make use of caching to solve it quickly.

I had a lot of fun with this year’s challenges and I’m looking forward for 2021’s advent. Hope I’ll see you there too.