day 17 Julia: metaprogramming instead of hardcoding neighbours
day 25: update README
day 25: Julia, Rust
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.
Nested loop over the array, making sure to only check each unordered pair/triple once.
List comprehension.
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 }.
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.
Modular arithmetic.
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.
More regular expressions.
I suppose TDD helps here as well.
Lots of parsing, lots of matching.
The seat spec is the binary decomposition of the seat id.
Just set union/intersection.
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).
Build a VM. Run it. Keep record of visited instruction pointers to detect loops.
Just compute all the sums. Ineffecient but straightforward.
Part 1 is a dumb loop. Part 2 is a sliding window sum.
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.
The main logic is brute force, but I defined a bunch of useless types.
Uses complex numbers for direction instead of conditionals.
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.
Bit-fiddling and hashmaps.
Brute force. Turn counts are saved in a hashmap (Julia), a vector (Rust), and a binary tree (Haskell).
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.
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.
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.
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.
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.
Part one is basic set theory (once you get past the weird requirements). Part two is greedy matching just like day 16.
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.
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.
Bravais lattice coordinates and hashsets. The Rust version reuses logic from day 17.
Compute the discrete log of the first number by brute force trial; raise the second number to that power.