`day 17 Julia: metaprogramming instead of hardcoding neighbours`
`day 25: update README`
`day 25: Julia, Rust`

trunk
browse  log

clone

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

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

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

Julia

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

Megaparsec is neat.

Rust

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

#Day 3

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

Julia

More regular expressions.

I suppose TDD helps here as well.

Rust

Lots of parsing, lots of `match`ing.

#Day5

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

#Day6

Just set union/intersection.

#Day 7

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

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

#Day 9

Just compute all the sums. Ineffecient but straightforward.

Rust

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).

Rust.

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

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

#Day 12

Uses complex numbers for direction instead of conditionals.

#Day 13

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

Bit-fiddling and hashmaps.

#Day 15

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

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

Julia

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

Julia

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

Julia

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

#Day 22

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

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`.