solutions for https://adventofcode.com/
day 17 Julia: metaprogramming instead of hardcoding neighbours
day 25: update README
day 25: Julia, Rust


browse  log 



You can also use your local clone with git send-email.

#Advent of code 2020 solutions

This repo contains my solutions to Advent of Code 2020. Programs are written in Julia and Rust (and possibly Haskell, Z3).

For all programs, I try to avoid using third-party libraries. For Julia and Haskell, this is an aspiration rather than a hard rule. For Rust programs however, it is a hard rule since I am still learning the language.

Below are notes about the solutions.

#Day 1

Julia, Rust

Nested loop over the array, making sure to only check each unordered pair/triple once.


List comprehension.

Z3 with Python

Input numbers (constants) are n_1, …, n_N. Variables are b_1, … b_N ∈ {0, 1}. We need to solve b_1 * n_1 + … + b_N * n_N == 2020 such that b_1 + … + b_N is 2 (or 3 for part 2) and then return the product of { n_i : b_i = 1 }.

#Day 2


The hard part is to parse the file. It helps not to forget about regular expressions.


Megaparsec is neat.


That parsing code is ugly. That's what you get for sticking to the standard library.

#Day 3

Julia, Rust

Modular arithmetic.

Bonus: Z3

This finds a slope for which you do not hit any trees. It does take a while though. For example, the slope (5, 2) means you do not hit a tree in the given test case.

I since realized that the solution can be brute-forced: Slope (dx+width, dy) is equivalent to (dx, dy), so only w*h slopes need to be checked.

#Day 4


More regular expressions.

I suppose TDD helps here as well.


Lots of parsing, lots of matching.


Julia, Rust, Haskell

The seat spec is the binary decomposition of the seat id.


Julia, Rust, Haskell

Just set union/intersection.

#Day 7

Julia, Rust

First build a graph from the input: Nodes are the bag color, connections are given by the "has to contain" relation (tagged with the number of bags required).

For part 1, invert the direction of each connection and forget the numbers. Start at the "shiny gold" bag, move along the connections until the graph is exhausted. Meanwhile, count the number of unique nodes encountered.

For part2, start at "shiny gold" and compute the number of bags required recursively (by following the original graph).

#Day 8

Julia, Rust

Build a VM. Run it. Keep record of visited instruction pointers to detect loops.

#Day 9

Julia, Haskell

Just compute all the sums. Ineffecient but straightforward.


Part 1 is a dumb loop. Part 2 is a sliding window sum.

#Day 10


Recursion for part 1. Dynamic programming for part 2: From the final adapter, we can only connect the device; for every adapter with a lower rating, the number of combinations to reach the device is the sum of combinations for all adapters that we can connect to that adapter; the number of combinations for the outlet is the sum of combinations for the devices with ratings 1, 2, or 3 (whichever we carry with us).


Count all the deltas for part1: We can assume a solution exists (because the puzzle asks for one), and we cannot go back to a lower rating adapter from a higher one, i.e. all adapter must be in order. Same dynamic programming approach for part 2.

#Day 11

Julia, Rust

The main logic is brute force, but I defined a bunch of useless types.

#Day 12

Julia, Rust

Uses complex numbers for direction instead of conditionals.

#Day 13

Julia, Rust

Part 1: The remainding time is bus_period - mod(timestamp, bus_period).

Part 2: Solve the system of linear congruences using the chinese remainder theorem. Avoid overflow.

#Day 14

Julia, Rust

Bit-fiddling and hashmaps.

#Day 15

Julia, Rust, Haskell

Brute force. Turn counts are saved in a hashmap (Julia), a vector (Rust), and a binary tree (Haskell).

#Day 16

Julia, no Rust today.

Part one is parsing (which is a pain).

Part two is the simplest greedy algorithm I could think of: If there is an index for which only one rule applies, match the two. Remove that rule from all other indices to which it potentially applies. Repeat until done.

#Day 17

It's the Game of Life.

Julia, with a pre-allocated array and hardcoded neighbours.

Rust, with a hashset of active points. Thanks to Rust traits, it can be made to work for arbitrary graphs. I didn't bother parsing the input though and hardcoded the glider instead.

#Day 18

Julia, Rust

Both programs solve the problem with Dijkstra's Shunting Yard Algorithm.

The Rust program doesn't actually parse the input; it just parses a hardcoded already-tokenized expression.

#Day 19


The rules describe a grammar in weak Chomsky Normal Form (CNF). The rules are parsed, and transformed into proper CNF. Finally, each message is verified with the CYK algorithm. This program is very slow, taking ~30 seconds for both parts.

#Day 20


I assume that the tiles can only be arranged one way (modulo Euclidean isometries of the whole image). Edges are turned into 10 bit ints by interpreting each pixel into a bit; edges are uniquely identified by the smaller of their two ints. Edges are identified by the fact that they have exactly two edges in common with the collection of all other card.

Part 2 is not done yet.

#Day 21


Part one is basic set theory (once you get past the weird requirements). Part two is greedy matching just like day 16.

#Day 22

Julia, Rust

The Rust version is much faster than the Julia version because it skips sub-games where player one holds the highest card, since player one will definitely wins those sub-games.

#Day 23

Julia, Rust

Linked lists. Since all node values are known, it does not have to be save explicitely. Instead, we can save the nodes in a dense array, where each index is the node value (number) and the value at that index is the next node (number of clockwise cup).


Same with an IntMap.

#Day 24

Julia, Rust

Bravais lattice coordinates and hashsets. The Rust version reuses logic from day 17.

#Day 25

Julia, Rust

Compute the discrete log of the first number by brute force trial; raise the second number to that power.