~quf/computers-are-fast-2020

6f56515ee701ac939760796fdeaa1811e518f73f — Lukas Himbert 1 year, 9 months ago 29f9417 trunk
Draw the rest of the fine owl.
M .builds/alpine.yml => .builds/alpine.yml +55 -0
@@ 74,3 74,58 @@ tasks:
     tcc -run src/14.c < testinputs/14 | tee out
     cmp out testoutputs/14
     rm out
 - run-15: |
     cd computers-are-fast-2020
     tcc -run src/15.c < testinputs/15 | tee out
     cmp out testoutputs/15
     rm out
 - run-16: |
     cd computers-are-fast-2020
     tcc -run src/16.c < testinputs/16 | tee out
     cmp out testoutputs/16
     rm out
 - run-17: |
     cd computers-are-fast-2020
     tcc -run src/17.c < testinputs/17 | tee out
     cmp out testoutputs/17
     rm out
 - run-18: |
     cd computers-are-fast-2020
     tcc -run src/18.c < testinputs/18 | tee out
     cmp out testoutputs/18
     rm out
 - run-19: |
     cd computers-are-fast-2020
     tcc -run src/19.c < testinputs/19 | tee out
     cmp out testoutputs/19
     rm out
 - run-20: |
     cd computers-are-fast-2020
     tcc -run src/20.c < testinputs/20 | tee out
     cmp out testoutputs/20
     rm out
 - run-21: |
     cd computers-are-fast-2020
     tcc -run src/21.c < testinputs/21 | tee out
     cmp out testoutputs/21
     rm out
 - run-22: |
     cd computers-are-fast-2020
     tcc -run src/22.c < testinputs/22 | tee out
     cmp out testoutputs/22
     rm out
 - run-23: |
     cd computers-are-fast-2020
     tcc -run src/23.c < testinputs/23 | tee out
     cmp out testoutputs/23
     rm out
 - run-24: |
     cd computers-are-fast-2020
     tcc -run src/24.c < testinputs/24 | tee out
     cmp out testoutputs/24
     rm out
 - run-25: |
     cd computers-are-fast-2020
     tcc -run src/25.c < testinputs/25 | tee out
     cmp out testoutputs/25
     rm out

M .builds/archlinux.yml => .builds/archlinux.yml +66 -0
@@ 89,3 89,69 @@ tasks:
     env ASAN_OPTIONS=detect_leaks=0 bin/14 < testinputs/14 | tee out
     cmp out testoutputs/14
     rm out
 - run-15: |
     cd computers-are-fast-2020
     CC=gcc CFLAGS=-fsanitize=address,undefined make bin/15
     bin/15 < testinputs/15 | tee out
     cmp out testoutputs/15
     rm out
 - run-16: |
     cd computers-are-fast-2020
     CC=gcc CFLAGS=-fsanitize=address,undefined make bin/16
     bin/16 < testinputs/16 | tee out
     cmp out testoutputs/16
     rm out
 - run-17: |
     cd computers-are-fast-2020
     CC=gcc CFLAGS=-fsanitize=address,undefined make bin/17
     bin/17 < testinputs/17 | tee out
     cmp out testoutputs/17
     rm out
 - run-18: |
     cd computers-are-fast-2020
     CC=gcc CFLAGS=-fsanitize=address,undefined make bin/18
     bin/18 < testinputs/18 | tee out
     cmp out testoutputs/18
     rm out
 - run-19: |
     cd computers-are-fast-2020
     CC=gcc CFLAGS=-fsanitize=address,undefined make bin/19
     bin/19 < testinputs/19 | tee out
     cmp out testoutputs/19
     rm out
 - run-20: |
     cd computers-are-fast-2020
     CC=gcc CFLAGS=-fsanitize=address,undefined make bin/20
     bin/20 < testinputs/20 | tee out
     cmp out testoutputs/20
     rm out
 - run-21: |
     cd computers-are-fast-2020
     CC=gcc CFLAGS=-fsanitize=address,undefined make bin/21
     bin/21 < testinputs/21 | tee out
     cmp out testoutputs/21
     rm out
 - run-22: |
     cd computers-are-fast-2020
     CC=gcc CFLAGS=-fsanitize=address,undefined make bin/22
     bin/22 < testinputs/22 | tee out
     cmp out testoutputs/22
     rm out
 - run-23: |
     cd computers-are-fast-2020
     CC=gcc CFLAGS=-fsanitize=address,undefined make bin/23
     bin/23 < testinputs/23 | tee out
     cmp out testoutputs/23
     rm out
 - run-24: |
     cd computers-are-fast-2020
     CC=gcc CFLAGS=-fsanitize=address,undefined make bin/24
     bin/24 < testinputs/24 | tee out
     cmp out testoutputs/24
     rm out
 - run-25: |
     cd computers-are-fast-2020
     CC=gcc CFLAGS=-fsanitize=address,undefined make bin/25
     bin/25 < testinputs/25 | tee out
     cmp out testoutputs/25
     rm out

M .builds/freebsd.yml => .builds/freebsd.yml +66 -0
@@ 86,3 86,69 @@ tasks:
     bin/14 < testinputs/14 | tee out
     cmp out testoutputs/14
     rm out
 - run-15: |
     cd computers-are-fast-2020
     make bin/15
     bin/15 < testinputs/15 | tee out
     cmp out testoutputs/15
     rm out
 - run-16: |
     cd computers-are-fast-2020
     CFLAGS=-Wno-missing-braces make bin/16
     bin/16 < testinputs/16 | tee out
     cmp out testoutputs/16
     rm out
 - run-17: |
     cd computers-are-fast-2020
     make bin/17
     bin/17 < testinputs/17 | tee out
     cmp out testoutputs/17
     rm out
 - run-18: |
     cd computers-are-fast-2020
     CFLAGS=-Wno-missing-braces make bin/18
     bin/18 < testinputs/18 | tee out
     cmp out testoutputs/18
     rm out
 - run-19: |
     cd computers-are-fast-2020
     CFLAGS=-Wno-missing-braces make bin/19
     bin/19 < testinputs/19 | tee out
     cmp out testoutputs/19
     rm out
 - run-20: |
     cd computers-are-fast-2020
     CFLAGS=-Wno-missing-braces make bin/20
     bin/20 < testinputs/20 | tee out
     cmp out testoutputs/20
     rm out
 - run-21: |
     cd computers-are-fast-2020
     make bin/21
     bin/21 < testinputs/21 | tee out
     cmp out testoutputs/21
     rm out
 - run-22: |
     cd computers-are-fast-2020
     make bin/22
     bin/22 < testinputs/22 | tee out
     cmp out testoutputs/22
     rm out
 - run-23: |
     cd computers-are-fast-2020
     make bin/23
     bin/23 < testinputs/23 | tee out
     cmp out testoutputs/23
     rm out
 - run-24: |
     cd computers-are-fast-2020
     make bin/24
     bin/24 < testinputs/24 | tee out
     cmp out testoutputs/24
     rm out
 - run-25: |
     cd computers-are-fast-2020
     make bin/25
     bin/25 < testinputs/25 | tee out
     cmp out testoutputs/25
     rm out

M .builds/openbsd.yml => .builds/openbsd.yml +66 -0
@@ 86,3 86,69 @@ tasks:
     bin/14 < testinputs/14 | tee out
     cmp out testoutputs/14
     rm out
 - run-15: |
     cd computers-are-fast-2020
     make bin/15
     bin/15 < testinputs/15 | tee out
     cmp out testoutputs/15
     rm out
 - run-16: |
     cd computers-are-fast-2020
     make bin/16
     bin/16 < testinputs/16 | tee out
     cmp out testoutputs/16
     rm out
 - run-17: |
     cd computers-are-fast-2020
     make bin/17
     bin/17 < testinputs/17 | tee out
     cmp out testoutputs/17
     rm out
 - run-18: |
     cd computers-are-fast-2020
     make bin/18
     bin/18 < testinputs/18 | tee out
     cmp out testoutputs/18
     rm out
 - run-19: |
     cd computers-are-fast-2020
     make bin/19
     bin/19 < testinputs/19 | tee out
     cmp out testoutputs/19
     rm out
 - run-20: |
     cd computers-are-fast-2020
     make bin/20
     bin/20 < testinputs/20 | tee out
     cmp out testoutputs/20
     rm out
 - run-21: |
     cd computers-are-fast-2020
     make bin/21
     bin/21 < testinputs/21 | tee out
     cmp out testoutputs/21
     rm out
 - run-22: |
     cd computers-are-fast-2020
     make bin/22
     bin/22 < testinputs/22 | tee out
     cmp out testoutputs/22
     rm out
 - run-23: |
     cd computers-are-fast-2020
     make bin/23
     bin/23 < testinputs/23 | tee out
     cmp out testoutputs/23
     rm out
 - run-24: |
     cd computers-are-fast-2020
     make bin/24
     bin/24 < testinputs/24 | tee out
     cmp out testoutputs/24
     rm out
 - run-25: |
     cd computers-are-fast-2020
     make bin/25
     bin/25 < testinputs/25 | tee out
     cmp out testoutputs/25
     rm out

M README.md => README.md +205 -27
@@ 3,7 3,7 @@ Computers are fast.

Or: C is my favourite scripting language

The goal of this project is to solve all parts of [Advent of Code 2020](https://adventofcode.com/2020/):
The goal of this project was to solve all parts of [Advent of Code 2020](https://adventofcode.com/2020/):

- With no dependencies other than a C99 compiler and libc,^(1,2)
- where every solution compiles and runs in 1 s or less,^3


@@ 11,11 11,9 @@ The goal of this project is to solve all parts of [Advent of Code 2020](https://
- while running single-threaded, and
- never exceeding 256 MiB memory use.^(3,4)

Stretch goal: Total time does not exceed 1 second.

^1 and, optionally, make.

^2 Some programs contain commonly held assumptions, like "`uint32_t` is available", or "exit code 0 signal success", or "the stack doesn't overflow".
^2 Some programs contain commonly held assumptions, like "`uint32_t` is available", or "exit code 1 signals failure", or "the stack doesn't overflow".
   The programs may cause undefined behaviour if the input is not an unmodified one from AoC 2020.
   If undefined behaviour (such as signed integer overflow) does occur for an unmodified AoC 2020 input, that's a bug and I'd like to know about it.



@@ 23,27 21,75 @@ Stretch goal: Total time does not exceed 1 second.

^4 virtual memory.


Results
-------

The project goal was almost, but not quite, achieved.

Every day runs in less than one second, and the total runtime is less than two seconds.
All but three of the programs compile and run faster than it takes Python just to start up and do literally nothing (i.e. 35 ms).
The memory limit was no problem either: only day 5 comes somewhat close to the limit, needing 120 MiB.

I was only able to get the runtime for day 15 below one second consistently by implementing the hot loop in inline assembly.
The program is still portable as the inline assembly is only used by TCC under amd64 and all other compilers fall back to plain C, but this version is not fast enough unless with compiled with heavy optimization options, which take too long at compile time.

The final compile/runtimes (on my laptop, best of ten) are as follows:

    Day 01: 2.73 ms
    Day 02: 2.88 ms
    Day 03: 3.49 ms
    Day 04: 4.69 ms
    Day 05: 2.84 ms
    Day 06: 2.98 ms
    Day 07: 5.03 ms
    Day 08: 4.43 ms
    Day 09: 3.02 ms
    Day 10: 3.06 ms
    Day 11: 31.9 ms
    Day 12: 3.2 ms
    Day 13: 3.18 ms
    Day 14: 19.9 ms
    Day 15: 906 ms
    Day 16: 4.99 ms
    Day 17: 36.7 ms
    Day 18: 3.54 ms
    Day 19: 4.68 ms
    Day 20: 20 ms
    Day 21: 4.86 ms
    Day 22: 11.4 ms
    Day 23: 590 ms
    Day 24: 38.8 ms
    Day 25: 13.3 ms
    Total: 1.91 s

Day 15 is responsible for 47% of the runtime, and day 23 is responsible for another 31%.
The remaining 23 days only take 240 ms to run.

Note that the total runtime is the smallest of ten complete runs, not the sum of individual best times.
The latter is about 200 ms shorter than the former.

How to run
----------

First, copy or link the inputs files in the subfolder `inputs/`, with names `01`, `02`, …

Then, if you're on a POSIX-y system and have `tcc` installed, run the following to measure runtime:
First, copy or link the inputs files in the subfolder `inputs/`, with names `01`, `02`, …, 25.
Then, if you're on a POSIX-y system and have `tcc` installed, the following will compile and run all programs and measure the completion time:

```
$ tcc -run time.c
$ tcc -run run-all.c
```

Alternatively, and this will be much slower, run:
Alternatively, if you have a C compiler and `make` installed, run:

```
$ time make
```

This will be much slower.
Some compilers (e.g. clang on FreeBSD) may refuse to compile some programs because the makefile invokes the compiler with very strict error conditions.
These errors are probably harmless suggestions and invoking `make` with the environment variable `CFLAGS=-Wno-error` should produce working executables.

To run a program individually (e.g. to see the solutions), run:
To run a program individually, run:

```
$ tcc -run src/01.c < inputs/01


@@ 61,6 107,12 @@ To run each program repeatedly and print the best time, run:
$ tcc -Drepeat=10 -run time.c
```

If you only have `make`, you will need to make do with this (again, it will be much slower):

```
$ time make clean run-01
```

Track/limit allocations
-----------------------



@@ 68,19 120,6 @@ Track allocations with `make bin/01 && valgrind bin/01 < inputs/01`.

Enforce memory limit with `ulimit -v 262144` (bash/fish shell on linux).

Track partial runtimes
----------------------

```
$ tcc -run time.c
```

Or (this will be slower):

```
$ time make clean run-01
```

[Day 1](src/01.c)
-----------------



@@ 100,14 139,14 @@ Modular arithmetic.
[Day 4](src/04.c)
-----------------

Just read and validate input.
Read and validate input.

[Day 5](src/05.c)
-----------------

Seat specs are binary expansions of seat IDs.

The largest seat ID is pow(2, strlen(input)), so we can use statically allocate a bit vector that stores the IDs to avoid sorting.
The input is implicitely sorted by setting indices in a bool table.

[Day 6](src/06.c)
-----------------


@@ 166,7 205,7 @@ Part 2: Sliding window sum.
[Day 10](src/10.c)
------------------

Read the adapter joltages into a bool table; this avoids having to sort them.
Read the adapter joltages into a bool table; this implicitely sorts them.

Part 1: Count the jolt differences.



@@ 187,7 226,7 @@ Optimizations:
[Day 12](src/12.c)
------------------

Just a bit of basic analytic geometry.
Basic analytic geometry.

[Day 13](src/13.c)
------------------


@@ 210,3 249,142 @@ When computed naively, interim values can become very large (~80 bits), so some 
Memory is saved in a hashmap.

A previous version used a more elegent sparse binary tree, but this was slower by a factor of > 2.

[Day 15](src/15.c)
------------------

The sequence is a variant of the Van Eck sequence, of which not much is known apparently.
There doesn't appear to be any way to get the answer other than the obvious.

**Caveat**:
I was unable to optimize the program to run in less than one second with just plain C99.
After rewriting the hot loop in amd64 asm, it does run in less than one second on my laptop.
Only TCC under amd64 makes use of this; all other compilers will use the slightly slower generic C implementation.

[Day 16](src/16.c)
------------------

Parsing is the most difficult part again.

Part 2 is solved with a greedy algorithm that looks for a rule that can only fit to one field, then removes that possibility from the possibilities for all other rules, and repeats.
This works since the assignment is unique.

[Day 17](src/17.c)
------------------

These are the rules Conway's game of life.

Cell status is saved in an array of appropriate size.
For performance, the sum over all neighbours is computed branchlessly, with the loop unrolled.
A progressively larger size of the grid is looped over on every iteration as the size in each dimension can grow at most by one per step.

This problem seems to benefit very much from compiler optimizations.
`gcc -O1` produces an exectuable that is about 4 to 5 as fast as one produces by `gcc -O0` (or `tcc`).
Perhaps this is a cue that my approach can be improved, but I don't see how.

Alternatively, a hashtable might be beneficial for performance since the number of active cells is a very small proportion of the grid.
I can't be bothered to try that though.

[Day 18](src/18.c)
------------------

Expressions are transformed and evaluated using a variant of the shunting yard algorithm with an inlined evaluator.

[Day 19](src/19.c)
------------------

The given rules describe a context-free grammar.
In part one, it is even finite, as the rules are acyclic.

A general approach for part two would require a general CGF recognizer, such as the Earley or CYK algorithms.
These are too slow for our purposes, so we have to take advantage of the structure of the input.
It appears that all inputs have the following properties:

- Rule `0`, the starting production, is `0: 8 11`; rule `8` is `8: 42`; rule `11` is `11: 42 31`

- Rules `42` and `31`, which are the only ones referred to by `8` and `11` (other than themselves) directly, produce a finite (and rather small) language.

The latter property allows for the generation of a finite list of all strings produced by rules `42` and `31`; let `S_42` and `S_31` these two sets.

In part 1, rule `0` produces the language `S_42^2 S_31`.
In part 2, rule `0` produces the language `∪_{n,m} S_42^(n+m) S_31^n`.

Computing `S_31` and `S_42`, then checking this property is reasonably straightforward.

For further optimization, note that the alphabet is binary, and all strings in `S_31` and `S_42` have length `8`.
Moreover, `S_31` and `S_42` both contain 128 strings and are disjoint.
As a result, each string in `S_42` and `S_31` can be represented by one byte; valid strings can be compressed cleanly into bytestrings by replacing `a` with a zero-bit and `b` by a one-bit.
Indeed, all messages in the input can, since they are all a multiple of eight characters long.

[Day 20](src/20.c)
------------------

This is the absolute worst.

- Read the tiles into a list.
  Convert image data into binary.
  Remove the edge of the tile data.
  For faster matching, turn each edge into a 10 bit number (identifying '#' and 1, '.' and 0), in both clockwise and counterclockwise direction.

- Find a tile for which exactly two edges (in counterclockwise direction only) match at least one other tile.
  (Luckily, such a tile exists.)
  This is a corner tile; put it in a grid at position (0, 0).
  Orient it such that the two edges which have a match point down and right (towards growing array indices).
  Save the orientation.

- Fill the first row: Find a match for the right edge of the previous tile and reorient it to match.

- Fill all other rows: For each position, find a match for the bottom edge of the tile above.

This procedure ultimately matches all tiles because each match is unique (modulo flippin or rotating the whole grid of tiles together).

Now we can solve part one by multiplying the values of the corner tiles.

- For part 2, fix the orientation of the data of every tile; then join all tile data together in a big array.

- Then convolve the complete picture with the monster image and find points where the result is fifteen (the number of set bits in the "monster kernel").
  The convolution is done naively, because I will *not* implement FFT for a puzzle that's already way too finicky to be fun just to potentially make it slightly faster.
  Any such point is a monster; remove the corresponding bits.

- Repeat the above with different monster orientations until at least one match is found.

- Count the remaining set image bits.

There's probably some untapped optimization potential and the code is not as general as one might hope, but I can hardly express how done I am with it, especially since it already only takes a rather small proportion of the total runtime.

[Day 21](src/21.c)
------------------

This one is conceptually the same as day 16.
It's more difficult because the numbers are bigger.

[Day 22](src/22.c)
------------------

Sub-games can be skipped if player 1 holds the highest card (in the decks of the sub-game) for a significant speedup.
Otherwise, just do the thing.
Previous deck arrangements are saved in a hashset.

[Day 23](src/23.c)
------------------

The cups are stored in an array.
The array index is the cup value (`array[0]` is the cup labelled 1, `array[1]` is the cup labelled 2, etc.); the array stores the index of the cup clockwise from it.
This allows for constant-time removal and insertion of cups, tracking the next cup, and locating the cup labelled 1.

[Day 24](src/24.c)
------------------

Tiles are identified by their coeffients with respect to a Bravais basis:

![a hexagonal lattice with few points and coordinates marked: the center coordinate is (0, 0); east is (1, 0); north-east is (0, 1); north-west is (1, -1), etc.](./basis-24.png)

Points are saved in a dense array.

Possible optimizations include: Using a hashmap; precomputing neighbours.

[Day 25](src/25.c)
------------------

The problem is to compute the discrete logarithm in a prime number field.
It is solved with the baby step giant step algorithm.

A basis-24.png => basis-24.png +0 -0
M makefile => makefile +89 -1
@@ 3,7 3,7 @@
COMPILE = $(CC) -std=c99 -O0 -W -Wall -Wextra -pedantic -pedantic-errors -Werror -Wfatal-errors $(CFLAGS) $(LDFLAGS)

.PHONY: run
run: run-01 run-02 run-03 run-04 run-05 run-06 run-07 run-08 run-09 run-10 run-11 run-12 run-13 run-14
run: run-01 run-02 run-03 run-04 run-05 run-06 run-07 run-08 run-09 run-10 run-11 run-12 run-13 run-14 run-15 run-16 run-17 run-18 run-19 run-20 run-21 run-22 run-23 run-24 run-25

.PHONY: run-01
run-01: bin/01


@@ 117,6 117,94 @@ bin/14: src/14.c
	mkdir -p bin
	$(COMPILE) src/14.c -o bin/14

.PHONY: run-15
run-15: bin/15
	bin/15 < inputs/15

bin/15: src/15.c
	mkdir -p bin
	$(COMPILE) src/15.c -o bin/15

.PHONY: run-16
run-16: bin/16
	bin/16 < inputs/16

bin/16: src/16.c
	mkdir -p bin
	$(COMPILE) src/16.c -o bin/16

.PHONY: run-17
run-17: bin/17
	bin/17 < inputs/17

bin/17: src/17.c
	mkdir -p bin
	$(COMPILE) src/17.c -o bin/17

.PHONY: run-18
run-18: bin/18
	bin/18 < inputs/18

bin/18: src/18.c
	mkdir -p bin
	$(COMPILE) src/18.c -o bin/18

.PHONY: run-19
run-19: bin/19
	bin/19 < inputs/19

bin/19: src/19.c
	mkdir -p bin
	$(COMPILE) src/19.c -o bin/19

.PHONY: run-20
run-20: bin/20
	bin/20 < inputs/20

bin/20: src/20.c
	mkdir -p bin
	$(COMPILE) src/20.c -o bin/20

.PHONY: run-21
run-21: bin/21
	bin/21 < inputs/21

bin/21: src/21.c
	mkdir -p bin
	$(COMPILE) src/21.c -o bin/21

.PHONY: run-22
run-22: bin/22
	bin/22 < inputs/22

bin/22: src/22.c
	mkdir -p bin
	$(COMPILE) src/22.c -o bin/22

.PHONY: run-23
run-23: bin/23
	bin/23 < inputs/23

bin/23: src/23.c
	mkdir -p bin
	$(COMPILE) src/23.c -o bin/23

.PHONY: run-24
run-24: bin/24
	bin/24 < inputs/24

bin/24: src/24.c
	mkdir -p bin
	$(COMPILE) src/24.c -o bin/24

.PHONY: run-25
run-25: bin/25
	bin/25 < inputs/25

bin/25: src/25.c
	mkdir -p bin
	$(COMPILE) src/25.c -o bin/25

.PHONY: clean
clean:
	-rm -rf bin

A run-all.c => run-all.c +172 -0
@@ 0,0 1,172 @@
#define _XOPEN_SOURCE 600
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>
#include <assert.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <sys/types.h>
#include <unistd.h>
#include <string.h>
#include <errno.h>
#include <stdarg.h>
#include <sys/wait.h>

typedef struct {
  struct timespec start;
  struct timespec stop;
} timer;

void timer_start(timer *t) {
  clock_gettime(CLOCK_REALTIME, &t->start);
}

void timer_stop(timer *t) {
  clock_gettime(CLOCK_REALTIME, &t->stop);
}

double timer_delta_ns(timer *t) {
  double delta_ns = (double) t->stop.tv_nsec - (double) t->start.tv_nsec;
  double delta_s = (double) t->stop.tv_sec - (double) t->start.tv_sec;
  return delta_ns + 1e9 * delta_s;
}

void print_delta_ns(FILE *f, double ns) {
  if (ns >= 1e9) {
    /* seconds */
    fprintf(f, "%0.3lg s", ns * 1e-9);
  }
  else if (ns >= 1e6) {
    fprintf(f, "%0.3lg ms", ns * 1e-6);
  }
  else if (ns >= 1e3) {
    fprintf(f, "%0.3lg us", ns * 1e-3);
  }
  else {
    fprintf(f, "%0.3lg ns", ns);
  }
}

double smallest(const double *numbers, size_t n) {
  double min = numbers[0];
  for (size_t i = 1; i < n; ++i) {
    if (numbers[i] < min) {
      min = numbers[i];
    }
  }
  return min;
}

char *my_asprintf(const char *fmt, ...) {
  va_list args;
  /* calculate size */
  va_start(args, fmt);
  int n = vsnprintf(NULL, 0, fmt, args);
  va_end(args);
  /* allocate */
  size_t size = (size_t) n + 1; // + 1 for final \0.
  char *buf = malloc(size);
  assert(buf != NULL);
  /* print */
  va_start(args, fmt);
  n = vsnprintf(buf, size, fmt, args);
  va_end(args);
  /* check and return */
  assert(n >= 0);
  return buf;
}

bool run_day(unsigned day) {
  /* tries to run; return true if successful, false if the source file does not exist; aborts in case of any other problem */
  char *exe_fn = my_asprintf("src/%02u.c", day);
  char *inp_fn = my_asprintf("inputs/%02u", day);
  /* check if source code exists */
  struct stat buf;
  if (stat(exe_fn, &buf) != 0) {
    if (errno == ENOENT) {
      free(exe_fn);
      free(inp_fn);
      return false;
    }
    else {
      fprintf(stderr, "Day %02u ERROR: %s\n", day, strerror(errno));
      abort();
    }
  }
  /* Open input */
  int inp_fd = open(inp_fn, O_RDONLY);
  if (inp_fd < 0) {
    if (errno == ENOENT) {
      free(exe_fn);
      free(inp_fn);
      return false;
    }
    else {
      fprintf(stderr, "Day %02u ERROR: Could not open input file: %s\n", day, strerror(errno));
      abort();
    }
  }
  /* fork & exec */
  pid_t pid;
  if ((pid = fork()) == 0) {
    /* child: replace stdin with the input, stdin & stdout with /dev/null; then exec */
    if (dup2(inp_fd, 0) < 0) {
      fprintf(stderr, "IO redirect error: %s\n", strerror(errno));
      abort();
    }
    char * const args[] = { "tcc", "-run", exe_fn, NULL };
    assert(execvp("tcc", args) == 0);
  }
  else if (pid > 0) {
    /* parent, success */
    int status;
    assert(wait(&status) == pid);
    if (status != 0) {
      fprintf(stderr, "Day %02u ERROR: Program exit code %d.\n", day, status);
      abort();
    }
  }
  else {
    /* parent, failure */
    fprintf(stderr, "Day %02u ERROR: fork() failed: %s\n", day, strerror(errno));
    abort();
  }
  assert(close(inp_fd) == 0);
  free(inp_fn);
  free(exe_fn);
  return true;
}

int main(void) {
  timer t;
  timer_start(&t);
  for (unsigned day = 1; day <= 25; ++day) {
    printf("======= Day %02u =======\n", day);
    timer t;
    timer_start(&t);
    if (fflush(stdout) != 0) {
      fprintf(stderr, "Output error: %s\n", strerror(errno));
      return EXIT_FAILURE;
    }
    bool success = run_day(day);
    if (!success) {
      printf("MISSING\n");
    }
    if (fflush(stdout) != 0) {
      fprintf(stderr, "Output error: %s\n", strerror(errno));
      return EXIT_FAILURE;
    }
    timer_stop(&t);
    if (success) {
      printf("Took ");
      print_delta_ns(stdout, timer_delta_ns(&t));
      printf(".\n");
    }
  }
  timer_stop(&t);
  printf("Total runtime: ");
  print_delta_ns(stdout, timer_delta_ns(&t));
  printf("\n");
  return 0;
}

M src/01.c => src/01.c +4 -4
@@ 5,7 5,7 @@

#define N 2020

void day1_part1(const unsigned int *numbers, const bool *lookup_table, size_t len) {
void part1(const unsigned int *numbers, const bool *lookup_table, size_t len) {
  for (size_t i = 0; i < len; ++i) {
    unsigned int x = numbers[i];
    if (lookup_table[N - x]) {


@@ 15,7 15,7 @@ void day1_part1(const unsigned int *numbers, const bool *lookup_table, size_t le
  }
}

void day1_part2(const unsigned int *numbers, const bool *lookup_table, size_t len) {
void part2(const unsigned int *numbers, const bool *lookup_table, size_t len) {
  for (size_t i = 0; i < len; ++i) {
    unsigned int x = numbers[i];
    for (size_t j = i; j < len; ++j) {


@@ 59,8 59,8 @@ int main(void) {
  }

  /* run search */
  day1_part1(numbers, lookup_table, len);
  day1_part2(numbers, lookup_table, len);
  part1(numbers, lookup_table, len);
  part2(numbers, lookup_table, len);

  return 0;
}

M src/04.c => src/04.c +13 -10
@@ 3,11 3,8 @@
#include <stdbool.h>
#include <errno.h>
#include <string.h>
#include <assert.h>
#include <ctype.h>

#define BUFSIZE 100
#define BUFSIZE_S "100"
#include <errno.h>

size_t find_whitespace(const char *buf) {
  size_t i = 0;


@@ 23,7 20,10 @@ size_t find_colon(const char *buf) {

void *xmalloc(size_t size) {
  void *ret = calloc(size, 1);
  assert(ret);
  if (!ret) {
    fprintf(stderr, "Allocation error: %s\n", strerror(errno));
    exit(EXIT_FAILURE);
  }
  return ret;
}



@@ 130,8 130,8 @@ int main(void) {
  size_t valid2 = 0;
  struct passport p = { 0, };
  while (true) {
    char buffer[BUFSIZE+1] = { 0, }; /* BUFSIZE+1 ensures that the line ends with two null bytes */
    if (fgets(buffer, BUFSIZE, stdin) == NULL) {
    char buffer[100] = { 0, };
    if (fgets(buffer, (sizeof buffer) - 1, stdin) == NULL) { /* BUFSIZE-1 ensures that the line ends with two null bytes */
      if (ferror(stdin)) {
        fprintf(stderr, "Read error: %s\n", strerror(errno));
        return EXIT_FAILURE;


@@ 139,9 139,12 @@ int main(void) {
      break;
    }
    size_t bufsize = strlen(buffer);
    assert(bufsize > 0);
    if (bufsize == 0) {
      fprintf(stderr, "Error: empty input line.\n");
      return EXIT_FAILURE;
    }
    if (buffer[bufsize-1] != '\n') {
      fprintf(stderr, "Line too long, longer than %d.\n", BUFSIZE);
      fprintf(stderr, "Line too long.\n");
      return EXIT_FAILURE;
    }



@@ 161,7 164,7 @@ int main(void) {
    }

    char *buf = buffer;
    while (*buf) { /* this loop relies on buf ending in two null bytes (or a space and a null byte) */
    while (*buf) { /* this loop relies on buf ending in two null bytes or a space and a null byte */
      /* find colon, which gives the end of the key */
      size_t k_len = find_colon(buf);
      char **entry = NULL;

M src/05.c => src/05.c +4 -8
@@ 3,18 3,14 @@
#include <string.h>
#include <errno.h>

#define BUFSIZE 10
#define BUFSIZE_S "10"

int main(void) {
  bool assigned[1024] = { 0, };
  unsigned min = 65535;
  unsigned max = 0;

  /* read input and get min and max id */
  int ret = 0;
  char buf[BUFSIZE+1];
  while ((ret = scanf("%"BUFSIZE_S"s\n", buf)) > 0) {
  char buf[11];
  while (fgets(buf, sizeof buf, stdin) != NULL) {
    unsigned id = 0;
    for (size_t i = 0; buf[i]; ++i) {
      id = id << 1 | (buf[i] == 'B' || buf[i] == 'R');


@@ 33,8 29,8 @@ int main(void) {
      max = id;
    }
  }
  if (ret != EOF) {
    fprintf(stderr, "Error: %s.\n", strerror(errno));
  if (ferror(stdin) || !feof(stdin)) {
    fprintf(stderr, "Input error: %s.\n", strerror(errno));
    return 1;
  }


M src/06.c => src/06.c +11 -13
@@ 1,27 1,25 @@
#include <stdio.h>
#include <inttypes.h>
#include <stdbool.h>
#include <errno.h>
#include <string.h>
#include <assert.h>
#include <limits.h>

#define ANSWERS_ALL_INIT 0x03ffffff /* bits 0 to 25 set */

uint16_t count_ones(uint32_t x) {
  uint16_t sum = 0;
  for (size_t i = 0; i < CHAR_BIT * sizeof x; ++i) {
unsigned count_ones(unsigned long x) {
  unsigned sum = 0;
  for (size_t i = 0; i < 26; ++i) {
    sum += (x >> i) & 1;
  }
  return sum;
}

int main(void) {
  uint16_t sum1 = 0;
  uint16_t sum2 = 0;
  unsigned sum1 = 0;
  unsigned sum2 = 0;

  uint32_t answers_any = 0;
  uint32_t answers_all = ANSWERS_ALL_INIT;
  unsigned long answers_any = 0;
  unsigned long answers_all = ANSWERS_ALL_INIT;
  bool group_empty = true;

  while (1) {


@@ 49,10 47,10 @@ int main(void) {
    else {
      /* got answer line */
      group_empty = false;
      uint32_t answers = 0;
      unsigned long answers = 0;
      for (size_t i = 0; buf[i]; ++i) {
        if ('a' <= buf[i] && buf[i] <= 'z') {
          answers |= ((uint32_t) 1) << (buf[i] - 'a');
          answers |= ((unsigned long) 1) << (buf[i] - 'a');
        }
      }
      answers_any |= answers;


@@ 60,8 58,8 @@ int main(void) {
    }
  }

  printf("%"PRIu16"\n", sum1);
  printf("%"PRIu16"\n", sum2);
  printf("%u\n", sum1);
  printf("%u\n", sum2);

  return 0;
}

M src/07.c => src/07.c +15 -14
@@ 5,6 5,8 @@
#include <string.h>
#include <errno.h>

#define LENGTH(a) (sizeof (a) / sizeof *(a))

#define die(...) do { \
    fprintf(stderr, __VA_ARGS__); \
    exit(EXIT_FAILURE); \


@@ 74,7 76,6 @@ size_t next_line(const char *s) {
void read_input(rule_t *rules_contains, rule_t *rules_contained) {
  char line[1<<8];
  while (fgets(line, sizeof line, stdin) != NULL) {
    die_if(strlen(line) == (sizeof line), "Error: line too long.\n"); /* TODO could maybe save some time here. */
    char *word;
    /* parse rule using a handrolled state machine */
    rule_t r = { { 0, }, { 0, } };


@@ 87,11 88,11 @@ void read_input(rule_t *rules_contains, rule_t *rules_contained) {
      switch (state) {
        case 0: /* fall through */
        case 8:
          mod = bisect(modifiers, sizeof modifiers / sizeof *modifiers, word);
          mod = bisect(modifiers, LENGTH(modifiers), word);
          ++state;
          break;
        case 1:
          base = bisect(base_colors, sizeof base_colors / sizeof *base_colors, word);
          base = bisect(base_colors, LENGTH(base_colors), word);
          rule_id = get_id(mod, base);
          ++state;
          break;


@@ 99,7 100,7 @@ void read_input(rule_t *rules_contains, rule_t *rules_contained) {
          {
            int n = atoi(word);
            if (n > 0) {
              /* TODO: maybe check that n <= UINT8_MAX; */
              die_if(n > UINT8_MAX, "i");
              num = (uint8_t) n;
              state = 8;
            }


@@ 112,12 113,12 @@ void read_input(rule_t *rules_contains, rule_t *rules_contained) {
          die("Error: unexpected word in input: %s\n", word);
          break;
        case 9:
          base = bisect(base_colors, sizeof base_colors / sizeof *base_colors, word);
          base = bisect(base_colors, LENGTH(base_colors), word);
          /* got number and color ID of the inner bag, now store it */
          {
            size_t i = 0;
            for (; i < sizeof r.out_numbers / sizeof *r.out_numbers && r.out_numbers[i] != 0; ++i);
            die_unless(i < sizeof r.out_numbers / sizeof *r.out_numbers, "Error: too many for one bag");
            for (; i < LENGTH(r.out_numbers) && r.out_numbers[i] != 0; ++i);
            die_unless(i < LENGTH(r.out_numbers), "Error: too many for one bag");
            r.out_numbers[i] = num;
            r.out_nodes[i] = get_id(mod, base);
          }


@@ 142,15 143,15 @@ void read_input(rule_t *rules_contains, rule_t *rules_contained) {
    /* add rules to the first graph ("contains") */
    memcpy(rules_contains + rule_id, &r, sizeof r);
    /* and the second ("contained") */
    for (size_t i = 0; i < sizeof r.out_nodes / sizeof *r.out_nodes; ++i) {
    for (size_t i = 0; i < LENGTH(r.out_nodes); ++i) {
      if (r.out_numbers[i] == 0) {
        break;
      }
      uint16_t id = r.out_nodes[i];
      size_t j = 0;
      /* find a place to store the reverse connection */
      for (j = 0; j < (sizeof r.out_nodes / sizeof *r.out_nodes) && rules_contained[id].out_numbers[j] != 0; ++j);
      die_unless(j < sizeof r.out_nodes / sizeof *r.out_nodes, "Error: too many reverse connections.\n");
      for (j = 0; j < LENGTH(r.out_nodes) && rules_contained[id].out_numbers[j] != 0; ++j);
      die_unless(j < LENGTH(r.out_nodes), "Error: too many reverse connections.\n");
      rules_contained[id].out_numbers[j] = 1; /* or any nonzero number */
      rules_contained[id].out_nodes[j] = rule_id;
    }


@@ 166,8 167,8 @@ size_t part1(rule_t *rules, uint16_t id) {
  size_t sum = 0;
  while (to_visit_len > 0) {
    uint16_t id = to_visit[--to_visit_len];
    for (size_t i = 0; i < (sizeof rules[id].out_nodes / sizeof *rules[id].out_nodes) && rules[id].out_numbers[i] != 0; ++i) {
      die_unless(to_visit_len < sizeof to_visit / sizeof *to_visit - 1, "Error: ran out of space.\n");
    for (size_t i = 0; i < LENGTH(rules[id].out_nodes) && rules[id].out_numbers[i] != 0; ++i) {
      die_unless(to_visit_len < LENGTH(to_visit) - 1, "Error: ran out of space.\n");
      size_t new_id = rules[id].out_nodes[i];
      if (!visited[new_id]) {
        visited[new_id] = true;


@@ 182,7 183,7 @@ size_t part1(rule_t *rules, uint16_t id) {

size_t part2(const rule_t *rules, uint16_t id) {
  size_t sum = 1;
  for (size_t i = 0; i < (sizeof rules[id].out_nodes / sizeof *rules[id].out_nodes) && rules[id].out_nodes[i] != 0; ++i) {
  for (size_t i = 0; i < LENGTH(rules[id].out_nodes) && rules[id].out_nodes[i] != 0; ++i) {
    sum += rules[id].out_numbers[i] * part2(rules, rules[id].out_nodes[i]);
  }
  return sum;


@@ 192,7 193,7 @@ int main(void) {
  rule_t rules_contains[1<<11] = { 0, };
  rule_t rules_contained[1<<11] = { 0, };
  read_input(rules_contains, rules_contained);
  const uint16_t shiny_gold_id = get_id(bisect(modifiers, sizeof modifiers / sizeof *modifiers, "shiny"), bisect(base_colors, sizeof base_colors / sizeof *base_colors, "gold"));
  const uint16_t shiny_gold_id = get_id(bisect(modifiers, LENGTH(modifiers), "shiny"), bisect(base_colors, LENGTH(base_colors), "gold"));
  printf("%zu\n", part1(rules_contained, shiny_gold_id));
  printf("%zu\n", part2(rules_contains, shiny_gold_id) - 1);
  return 0;

M src/10.c => src/10.c +5 -3
@@ 4,6 4,8 @@
#include <stdbool.h>
#include <stdint.h>

#define LENGTH(a) (sizeof a / sizeof *a)

int main(void) {
  bool adapters[200] = { 0, };
  adapters[0] = true;


@@ 11,7 13,7 @@ int main(void) {
  size_t max_rating = 0;
  size_t rating;
  while ((ret = scanf("%zu\n", &rating)) > 0) {
    if (rating > sizeof adapters / sizeof *adapters) {
    if (rating >= LENGTH(adapters)) {
      fprintf(stderr, "Error: Too many adapters.\n");
      return 1;
    }


@@ 25,7 27,7 @@ int main(void) {
    return 1;
  }

  long long combinations[2 + sizeof adapters / sizeof *adapters] = { 0, };
  long long combinations[2 + LENGTH(adapters)] = { 0, };
  combinations[max_rating] = 1;
  unsigned deltas[4] = { 0, };
  size_t delta = 0;


@@ 35,7 37,7 @@ int main(void) {
      combinations[i] += combinations[i+1];
      combinations[i] += combinations[i+2];
      combinations[i] += combinations[i+3];
      if (delta > sizeof deltas / sizeof *deltas) {
      if (delta > LENGTH(deltas)) {
        fprintf(stderr, "Error: gap in ratings larger than 3.\n");
        return 1;
      }

M src/11.c => src/11.c +5 -3
@@ 5,6 5,8 @@

#define MAX_DATASIZE 10000

#define LENGTH(a) (sizeof a / sizeof *a)

/* tile_t was originally an enum, but this is a few ms faster: */
#define tile_t char
#define FLOOR 0


@@ 37,7 39,7 @@ size_t run(const grid_t *g, const size_t *neighbour_map, size_t max_neigh) {
    for (size_t i = 0; i < size; ++i) {
      occupied_neighbours[i] =
          (copy.data[neighbour_map[i*8+0]] >> 1) /* FLOOR>>1 == 0 */
        + (copy.data[neighbour_map[i*8+1]] >> 1) /* EMPTY>>1 == 1 */
        + (copy.data[neighbour_map[i*8+1]] >> 1) /* EMPTY>>1 == 0 */
        + (copy.data[neighbour_map[i*8+2]] >> 1) /* OCC>>1 == 1 */
        + (copy.data[neighbour_map[i*8+3]] >> 1)
        + (copy.data[neighbour_map[i*8+4]] >> 1)


@@ 67,7 69,7 @@ int main(void) {
    size_t ix = 0;
    size_t iy = 0;
    int c;
    while ((c = getc(stdin)) != EOF && i < sizeof grid.data / sizeof *grid.data) {
    while ((c = getc(stdin)) != EOF && i < LENGTH(grid.data)) {
      if (c == '\n') {
        ++iy;
        if (ix > grid.sx) {


@@ 85,7 87,7 @@ int main(void) {
      fprintf(stderr, "Read error: %s\n", strerror(errno));
      return 1;
    }
    else if (grid.sx * grid.sy > (sizeof grid.data / sizeof *grid.data) - 1) {
    else if (grid.sx * grid.sy > LENGTH(grid.data) - 1) {
      fprintf(stderr, "Input too large.\n");
      return 1;
    }

M src/13.c => src/13.c +14 -14
@@ 7,21 7,20 @@
#define abs(a) ((a<0)? -a : a)

long long mulmod(unsigned long long a, unsigned long long b, unsigned long long m) {
    /* Returns mod(a*b, c) while avoiding overflow for a*b */
    if (a < (1ULL<<32) && b < (1ULL<<32)) { /* long long is at least 64 bits wide */
        return (a * b) % m;
    }
    unsigned long long ret = 0;
    a = a % m;
    b = b % m;
    while (b) {
        if (b & 1) {
            ret = (ret + a) % m;
        }
        a = (a << 1) % m;
        b >>= 1;
  /* Returns mod(a*b, c) while avoiding overflow for a*b */
  if (a < (1ULL<<32) && b < (1ULL<<32)) { /* long long is at least 64 bits wide */
    return (a * b) % m;
  }
  unsigned long long ret = 0;
  a = a % m;
  b = b % m;
  for (; b; b >>= 1) {
    if (b & 1) {
      ret = (ret + a) % m;
    }
    return ret;
    a = (a << 1) % m;
  }
  return ret;
}

unsigned long long mod(long long a, long long b) {


@@ 82,6 81,7 @@ int main(void) {
        return 1;
      }
      period = t * (period / g);
      /* ((-k * t * m - i) % period) without overflow */
      part2 = mod(mulmod((unsigned long long) t, mulmod(mod(-k, period), mod(m, period), period), period) - i, period);

      t = 0;

A src/15.c => src/15.c +84 -0
@@ 0,0 1,84 @@
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
#include <string.h>

#define N1 2020
#define N2 30000000

#if defined(__TINYC__) && defined(__x86_64__)
#define USE_ASM
#endif

#ifdef USE_ASM
#define STR(x) STR_(x)
#define STR_(x) #x
#endif

int main(void) {
  int_least32_t *spoken = calloc(N2, sizeof *spoken);
  if (spoken == NULL) {
    fprintf(stderr, "Allocation error.\n");
    return 1;
  }
  for (size_t i = 0; i < N2; ++i) {
    spoken[i] = INT_LEAST32_MAX;
  }
  int_fast32_t i = 1;
  {
    size_t n;
    while (scanf("%zu%*c", &n) > 0) {
      spoken[n * (n < N2)] = i++;
    }
    if (ferror(stdin) || !feof(stdin)) {
      fprintf(stderr, "Input error.\n");
      return 1;
    }
  }
  int_least32_t n = 0;
  for (; i < N1; ++i) {
    int_least32_t t = spoken[n];
    spoken[n] = (int_least32_t) i;
    n = i - t;
    n = (n >= 0)? n : 0;
  }
  printf("%lu\n", (unsigned long) n);
#ifdef USE_ASM
    __asm__ (
      /* start: save frame pointer & null ecx */
      "mov %%rbp, %%r8\n"
      "xor %%ecx, %%ecx\n"
      "loop:\n"
      /* t = spoken[n]; */
      "mov %%eax, %%rbp\n"
      "lea (%2, %%rbp, 4), %%rax\n"
      "mov (%%rax), %%edx\n"
      /* spoken[n] = i; */
      "mov %%ebx, (%%rax)\n"
      /* n = max(i - t, 0); (branchless) */
      "mov %%ebx, %%eax\n"
      "sub %%edx, %%eax\n"
      "cmovs %%ecx, %0\n"
      /* loop */
      "inc %%rbx\n"
      "cmp $"STR(N2)", %%rbx\n"
      "jne loop\n"
      /* end: restore frame pointer */
      "mov %%r8, %%rbp\n"
    : "+a"(n)
    , "+b"(i)
    : "r"(spoken)
    : "cc", "memory", "ecx", "edx", "r8"
    );
#else
  for (; i < N2; ++i) {
    int_least32_t t = spoken[n];
    spoken[n] = (int_least32_t) i;
    n = i - t;
    n = (n >= 0)? n : 0;
  }
#endif
  printf("%lu\n", (unsigned long) n);
  free(spoken);
  return 0;
}

A src/16.c => src/16.c +144 -0
@@ 0,0 1,144 @@
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <errno.h>

typedef struct {
  bool departure;
  unsigned min1;
  unsigned max1;
  unsigned min2;
  unsigned max2;
  bool may_fit_field[25];
} rule_t;

bool is_between(unsigned min, unsigned i, unsigned max) {
  return (min <= i) && (i <= max);
}

bool rule_applies_to_field(rule_t *r, unsigned field) {
  return is_between(r->min1, field, r->max1) || is_between(r->min2, field, r->max2);
}

bool any_rule_applies(rule_t *r, size_t n, unsigned f) {
  for (size_t i = 0; i < n; ++i) {
    if (rule_applies_to_field(r + i, f)) {
      return true;
    }
  }
  return false;
}

int main(void) {
  rule_t rules[25] = { 0, };
  unsigned my_ticket[25] = { 0, };

  /* read rules */
  char buf[100] = { 0, };
  size_t n_rules = 0;
  for (; fgets(buf, sizeof buf, stdin) != 0 && buf[0] && buf[0] != '\n'; ++n_rules) {
    if (n_rules >= sizeof rules / sizeof *rules) {
      fprintf(stderr, "Error: Too many rules.\n");
      return 1;
    }
    rule_t *r = rules + n_rules;
    const char *departure = "departure";
    if (strncmp(buf, departure, (sizeof departure) - 1) == 0) {
      r->departure = true;
    }
    else {
      r->departure = false;
    }
    char *b = buf;
    for (; *b && *b != ':'; ++b);

  if (sscanf(b, ": %u-%u or %u-%u\n", &r->min1, &r->max1, &r->min2, &r->max2) != 4) {
      fprintf(stderr, "Error parsing rule:\n%s", buf);
      return 1;
    }
    memset(r->may_fit_field, 1, sizeof r->may_fit_field);
  }

  /* read my ticket */
  (void) fgets(buf, sizeof buf, stdin); /* "your ticket:\n" */
  for (size_t i_f = 0; i_f < n_rules; ++i_f) {
    (void) scanf("%u", my_ticket + i_f); /* error? meh. */
    (void) getchar(); /* ',' or line feed */
  }

  /* read other tickets, validate them, check which rules may correspond to which fields */
  (void) getchar(); /* line feed */
  (void) fgets(buf, sizeof buf, stdin); /* "nearby tickets:\n" */

  int sum_of_invalid_fields = 0;
  unsigned fields[25] = { 0, };
  size_t i_f = 0;
  while (scanf("%u", fields + i_f) > 0) {
    ++i_f;
    if (getchar() != ',') {
      /* part 1 filter */
      bool is_valid = true;
      for (size_t i_f = 0; i_f < n_rules; ++i_f) {
        if (!any_rule_applies(rules, n_rules, fields[i_f])) {
          is_valid = false;
          sum_of_invalid_fields += fields[i_f];
        }
      }
      /* part 2 filter */
      if (is_valid) {
        for (size_t i_f = 0; i_f < n_rules; ++i_f) {
          unsigned f = fields[i_f];
          for (size_t i_r = 0; i_r < n_rules; ++i_r) {
            rule_t *r = rules + i_r;
            if (!rule_applies_to_field(r, f)) {
              r->may_fit_field[i_f] = false;
            }
          }
        }
      }
      i_f = 0;
    }
    if (i_f > n_rules) {
      fprintf(stderr, "Too many fields.\n");
      return 1;
    }
  }
  if (ferror(stdin)) {
    fprintf(stderr, "Input error: %s\n", strerror(errno));
    return 1;
  }

  printf("%lld\n", (long long) sum_of_invalid_fields);

  /* part 2 solution */
  unsigned assigned_fields[25] = { 0, }; /* given a rule index, get the assigned field */
  for (size_t k = 0; k < n_rules; ++k) {
    /* find a rule for which only one field fits */
    for (size_t i_r = 0; i_r < n_rules; ++i_r) {
      unsigned number_of_possible_fields = 0;
      size_t field = 0;
      for (size_t i_f = 0; i_f < n_rules && number_of_possible_fields < 2; ++i_f) {
        if (rules[i_r].may_fit_field[i_f]) {
          ++number_of_possible_fields;
          field = i_f;
        }
      }
      if (number_of_possible_fields == 1) {
        assigned_fields[i_r] = field;
        for (size_t i_r = 0; i_r < n_rules; ++i_r) {
          rules[i_r].may_fit_field[field] = false;
        }
        break;
      }
    }
  }
  unsigned long long prod = 1;
  for (size_t i = 0; i < n_rules; ++i) {
    if (rules[i].departure) {
      prod *= (unsigned long long) my_ticket[assigned_fields[i]];
    }
  }
  printf("%llu\n", prod);

  return 0;
}

A src/17.c => src/17.c +193 -0
@@ 0,0 1,193 @@
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <errno.h>
#include <assert.h>

/* input is 8x8; we need 6 cells to grow into and one buffer row/column in each direction */
#define INPUT 8
#define STEPS 6
#define S1 (INPUT + 2*STEPS+2)
#define S2 S1
#define S3 (2*STEPS+3)
#define S4 S3

#define index3(s1, s2, s3)     (              (s3) + S3 * ((s2) + S2 * (s1))  )
#define index4(s1, s2, s3, s4) ( (s4) + S4 * ((s3) + S3 * ((s2) + S2 * (s1))) )

/* This only works for statically allocated arrays! */
#define LENGTH(arr) ((sizeof arr) / (sizeof *arr))

int main(void) {
  bool cells3[S1*S2*S3] = { 0, };
  int neighbours3[S1*S2*S3] = { 0, };

  bool cells4[S1*S2*S3*S4] = { 0, };
  int neighbours4[S1*S2*S3*S4] = { 0, };

  for (size_t s2 = 0; s2 < S2; ++s2) {
    for (size_t s1 = 0; s1 < S1; ++s1) {
      int c = getchar();
      if (c == '\n' || c == EOF || s1 >= INPUT || s2 >= INPUT) {
        s1 = 0;
        break;
      }
      bool x = (c == '#');
      size_t d1 = STEPS+1;
      size_t d2 = STEPS+1;
      size_t m3 = S3 / 2;
      size_t m4 = S3 / 2;
      cells3[index3(s1+d1, s2+d2, m3)] = x;
      cells4[index4(s1+d1, s2+d2, m3, m4)] = x;
    }
  }
  if (ferror(stdin)) {
    fprintf(stderr, "Input error: %s.\n", strerror(errno));
    return 1;
  }

  for (size_t i = 0; i < STEPS; ++i) {
    /* update neighbour counts */
    for (size_t s1 = STEPS - i; s1 < S1 - STEPS + i; ++s1) {
    for (size_t s2 = STEPS - i; s2 < S2 - STEPS + i; ++s2) {
    for (size_t s3 = STEPS - i; s3 < S3 - STEPS + i; ++s3) {
      /* 3d  */
      neighbours3[index3(s1, s2, s3)] = \
        cells3[index3(s1    , s2    , s3 + 1)] + \
        cells3[index3(s1    , s2    , s3 - 1)] + \
        cells3[index3(s1    , s2 + 1, s3    )] + \
        cells3[index3(s1    , s2 + 1, s3 + 1)] + \
        cells3[index3(s1    , s2 + 1, s3 - 1)] + \
        cells3[index3(s1    , s2 - 1, s3    )] + \
        cells3[index3(s1    , s2 - 1, s3 + 1)] + \
        cells3[index3(s1    , s2 - 1, s3 - 1)] + \
        cells3[index3(s1 + 1, s2    , s3    )] + \
        cells3[index3(s1 + 1, s2    , s3 + 1)] + \
        cells3[index3(s1 + 1, s2    , s3 - 1)] + \
        cells3[index3(s1 + 1, s2 + 1, s3    )] + \
        cells3[index3(s1 + 1, s2 + 1, s3 + 1)] + \
        cells3[index3(s1 + 1, s2 + 1, s3 - 1)] + \
        cells3[index3(s1 + 1, s2 - 1, s3    )] + \
        cells3[index3(s1 + 1, s2 - 1, s3 + 1)] + \
        cells3[index3(s1 + 1, s2 - 1, s3 - 1)] + \
        cells3[index3(s1 - 1, s2    , s3    )] + \
        cells3[index3(s1 - 1, s2    , s3 + 1)] + \
        cells3[index3(s1 - 1, s2    , s3 - 1)] + \
        cells3[index3(s1 - 1, s2 + 1, s3    )] + \
        cells3[index3(s1 - 1, s2 + 1, s3 + 1)] + \
        cells3[index3(s1 - 1, s2 + 1, s3 - 1)] + \
        cells3[index3(s1 - 1, s2 - 1, s3    )] + \
        cells3[index3(s1 - 1, s2 - 1, s3 + 1)] + \
        cells3[index3(s1 - 1, s2 - 1, s3 - 1)];
      /* 4d */
    for (size_t s4 = STEPS - i; s4 < S4 - STEPS + i; ++s4) {
      neighbours4[index4(s1, s2, s3, s4)] =
        cells4[index4(s1    , s2    , s3    , s4 + 1)] + \
        cells4[index4(s1    , s2    , s3    , s4 - 1)] + \
        cells4[index4(s1    , s2    , s3 + 1, s4    )] + \
        cells4[index4(s1    , s2    , s3 + 1, s4 + 1)] + \
        cells4[index4(s1    , s2    , s3 + 1, s4 - 1)] + \
        cells4[index4(s1    , s2    , s3 - 1, s4    )] + \
        cells4[index4(s1    , s2    , s3 - 1, s4 + 1)] + \
        cells4[index4(s1    , s2    , s3 - 1, s4 - 1)] + \
        cells4[index4(s1    , s2 + 1, s3    , s4    )] + \
        cells4[index4(s1    , s2 + 1, s3    , s4 + 1)] + \
        cells4[index4(s1    , s2 + 1, s3    , s4 - 1)] + \
        cells4[index4(s1    , s2 + 1, s3 + 1, s4    )] + \
        cells4[index4(s1    , s2 + 1, s3 + 1, s4 + 1)] + \
        cells4[index4(s1    , s2 + 1, s3 + 1, s4 - 1)] + \
        cells4[index4(s1    , s2 + 1, s3 - 1, s4    )] + \
        cells4[index4(s1    , s2 + 1, s3 - 1, s4 + 1)] + \
        cells4[index4(s1    , s2 + 1, s3 - 1, s4 - 1)] + \
        cells4[index4(s1    , s2 - 1, s3    , s4    )] + \
        cells4[index4(s1    , s2 - 1, s3    , s4 + 1)] + \
        cells4[index4(s1    , s2 - 1, s3    , s4 - 1)] + \
        cells4[index4(s1    , s2 - 1, s3 + 1, s4    )] + \
        cells4[index4(s1    , s2 - 1, s3 + 1, s4 + 1)] + \
        cells4[index4(s1    , s2 - 1, s3 + 1, s4 - 1)] + \
        cells4[index4(s1    , s2 - 1, s3 - 1, s4    )] + \
        cells4[index4(s1    , s2 - 1, s3 - 1, s4 + 1)] + \
        cells4[index4(s1    , s2 - 1, s3 - 1, s4 - 1)] + \
        cells4[index4(s1 + 1, s2    , s3    , s4    )] + \
        cells4[index4(s1 + 1, s2    , s3    , s4 + 1)] + \
        cells4[index4(s1 + 1, s2    , s3    , s4 - 1)] + \
        cells4[index4(s1 + 1, s2    , s3 + 1, s4    )] + \
        cells4[index4(s1 + 1, s2    , s3 + 1, s4 + 1)] + \
        cells4[index4(s1 + 1, s2    , s3 + 1, s4 - 1)] + \
        cells4[index4(s1 + 1, s2    , s3 - 1, s4    )] + \
        cells4[index4(s1 + 1, s2    , s3 - 1, s4 + 1)] + \
        cells4[index4(s1 + 1, s2    , s3 - 1, s4 - 1)] + \
        cells4[index4(s1 + 1, s2 + 1, s3    , s4    )] + \
        cells4[index4(s1 + 1, s2 + 1, s3    , s4 + 1)] + \
        cells4[index4(s1 + 1, s2 + 1, s3    , s4 - 1)] + \
        cells4[index4(s1 + 1, s2 + 1, s3 + 1, s4    )] + \
        cells4[index4(s1 + 1, s2 + 1, s3 + 1, s4 + 1)] + \
        cells4[index4(s1 + 1, s2 + 1, s3 + 1, s4 - 1)] + \
        cells4[index4(s1 + 1, s2 + 1, s3 - 1, s4    )] + \
        cells4[index4(s1 + 1, s2 + 1, s3 - 1, s4 + 1)] + \
        cells4[index4(s1 + 1, s2 + 1, s3 - 1, s4 - 1)] + \
        cells4[index4(s1 + 1, s2 - 1, s3    , s4    )] + \
        cells4[index4(s1 + 1, s2 - 1, s3    , s4 + 1)] + \
        cells4[index4(s1 + 1, s2 - 1, s3    , s4 - 1)] + \
        cells4[index4(s1 + 1, s2 - 1, s3 + 1, s4    )] + \
        cells4[index4(s1 + 1, s2 - 1, s3 + 1, s4 + 1)] + \
        cells4[index4(s1 + 1, s2 - 1, s3 + 1, s4 - 1)] + \
        cells4[index4(s1 + 1, s2 - 1, s3 - 1, s4    )] + \
        cells4[index4(s1 + 1, s2 - 1, s3 - 1, s4 + 1)] + \
        cells4[index4(s1 + 1, s2 - 1, s3 - 1, s4 - 1)] + \
        cells4[index4(s1 - 1, s2    , s3    , s4    )] + \
        cells4[index4(s1 - 1, s2    , s3    , s4 + 1)] + \
        cells4[index4(s1 - 1, s2    , s3    , s4 - 1)] + \
        cells4[index4(s1 - 1, s2    , s3 + 1, s4    )] + \
        cells4[index4(s1 - 1, s2    , s3 + 1, s4 + 1)] + \
        cells4[index4(s1 - 1, s2    , s3 + 1, s4 - 1)] + \
        cells4[index4(s1 - 1, s2    , s3 - 1, s4    )] + \
        cells4[index4(s1 - 1, s2    , s3 - 1, s4 + 1)] + \
        cells4[index4(s1 - 1, s2    , s3 - 1, s4 - 1)] + \
        cells4[index4(s1 - 1, s2 + 1, s3    , s4    )] + \
        cells4[index4(s1 - 1, s2 + 1, s3    , s4 + 1)] + \
        cells4[index4(s1 - 1, s2 + 1, s3    , s4 - 1)] + \
        cells4[index4(s1 - 1, s2 + 1, s3 + 1, s4    )] + \
        cells4[index4(s1 - 1, s2 + 1, s3 + 1, s4 + 1)] + \
        cells4[index4(s1 - 1, s2 + 1, s3 + 1, s4 - 1)] + \
        cells4[index4(s1 - 1, s2 + 1, s3 - 1, s4    )] + \
        cells4[index4(s1 - 1, s2 + 1, s3 - 1, s4 + 1)] + \
        cells4[index4(s1 - 1, s2 + 1, s3 - 1, s4 - 1)] + \
        cells4[index4(s1 - 1, s2 - 1, s3    , s4    )] + \
        cells4[index4(s1 - 1, s2 - 1, s3    , s4 + 1)] + \
        cells4[index4(s1 - 1, s2 - 1, s3    , s4 - 1)] + \
        cells4[index4(s1 - 1, s2 - 1, s3 + 1, s4    )] + \
        cells4[index4(s1 - 1, s2 - 1, s3 + 1, s4 + 1)] + \
        cells4[index4(s1 - 1, s2 - 1, s3 + 1, s4 - 1)] + \
        cells4[index4(s1 - 1, s2 - 1, s3 - 1, s4    )] + \
        cells4[index4(s1 - 1, s2 - 1, s3 - 1, s4 + 1)] + \
        cells4[index4(s1 - 1, s2 - 1, s3 - 1, s4 - 1)];
    }
    }}}
    /* update cells for 3d cells */
    for (size_t j = 0; j < LENGTH(cells3); ++j) {
      cells3[j] &= (neighbours3[j] == 2);
      cells3[j] |= (neighbours3[j] == 3);
    }
    /* update cells for 4d cells */
    for (size_t j = 0; j < LENGTH(cells4); ++j) {
      cells4[j] &= (neighbours4[j] == 2);
      cells4[j] |= (neighbours4[j] == 3);
    }
  }

  /* print number of set cells */
  size_t n = 0;
  for (size_t i = 0; i < LENGTH(cells3); ++i) {
    n += cells3[i];
  }
  printf("%zu\n", n);

  n = 0;
  for (size_t i = 0; i < LENGTH(cells4); ++i) {
    n += cells4[i];
  }
  printf("%zu\n", n);

  return 0;
}

A src/18.c => src/18.c +133 -0
@@ 0,0 1,133 @@
#include <stdio.h>
#include <stdbool.h>
#include <ctype.h>

typedef enum {
  NUM,
  PLUS,
  TIMES,
  PARO,
  PARC,
  END,
} token_type_t;

token_type_t next_token(const char *b, const char **next, unsigned long long *n) {
  token_type_t ret = END;
  for (; isspace(*b); ++b);
  if (*b == '\0') {
    return END;
  }
  if (*b == '+') {
    ret = PLUS;
    ++b;
  }
  else if (*b == '*') {
    ret = TIMES;
    ++b;
  }
  else if (*b == '(') {
    ret = PARO;
    ++b;
  }
  else if (*b == ')') {
    ret = PARC;
    ++b;
  }
  else if (isdigit(*b)) {
    unsigned long long a = 0;
    for (; isdigit(*b); ++b) {
      a = 10 * a + (unsigned long long) (*b - '0');
    }
    *n = a;
    ret = NUM;
  }
  else {
    /* error, but we don't care because it never happens . */
  }
  *next = b;
  return ret;
}

typedef struct {
  token_type_t data[20];
  size_t members;
} op_stack_t;

typedef struct {
  unsigned long long data[20];
  size_t members;
} v_stack_t;

#define push(stack, val) do { \
    if (stack.members < sizeof stack.data / sizeof *stack.data) { \
      stack.data[stack.members++] = val; \
    } \
  } while (0)

#define pop(stack) ((stack.members > 0) ? stack.data[--stack.members] : 0)

#define peek(stack) ((stack.members > 0) ? stack.data[stack.members-1] : 0)

unsigned long long eval(const char *s, bool with_precedence) {
  op_stack_t ops = { 0, };
  v_stack_t vals = { 0, };

  unsigned long long n;
  token_type_t t;
  while ((t = next_token(s, &s, &n)) != END) {
    switch (t) {
      case END:
        break;
      case NUM:
        push(vals, n);
        break;
      case PLUS: /* fall through */
      case TIMES:
        while (ops.members > 0 && peek(ops) != PARO) {
          if (with_precedence && t == PLUS && peek(ops) == TIMES) {
            break;
          }
          unsigned long long a = pop(vals);
          unsigned long long b = pop(vals);
          push(vals, (pop(ops) == PLUS) ? (a + b) : (a * b));
        }
        push(ops, t);
        break;
      case PARO:
        push(ops, PARO);
        break;
      case PARC:
        while (1) {
          t = pop(ops);
          if (ops.members == 0 || t == PARO) {
            break;
          }
          unsigned long long a = pop(vals);
          unsigned long long b = pop(vals);
          push(vals, (t == PLUS) ? (a + b) : (a * b));
        }
        break;
    }
  }
  while (ops.members > 0) {
    t = pop(ops);
    unsigned long long a = pop(vals);
    unsigned long long b = pop(vals);
    push(vals, (t == PLUS) ? (a + b) : (a * b));
  }
  return pop(vals);
}

int main(void) {
  char buf[200] = { 0, };
  unsigned long long s1 = 0;
  unsigned long long s2 = 0;
  while (fgets(buf, sizeof buf, stdin) != NULL) {
    s1 += eval(buf, false);
    s2 += eval(buf, true);
  }
  printf("%llu\n", s1);
  printf("%llu\n", s2);

  return 0;
}

A src/19.c => src/19.c +204 -0
@@ 0,0 1,204 @@
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define LENGTH(x) (sizeof(x) / sizeof(*x))

typedef enum {
  NONTERMINAL,
  TERMINAL,
} symbol_type_t;

typedef struct {
  symbol_type_t t;
  union {
    size_t id;
    char terminal;
  } symbol;
} symbol_t;

typedef struct {
  symbol_t symbols[3];
  size_t n_symb;
} sequence_t;

typedef struct {
  sequence_t alternatives[4];
  size_t n_alt;
} alternatives_t;

typedef struct {
  unsigned char s; /* eight bits ought to be enough for anybody */
  size_t len;
} generated_string_t;

typedef struct {
  generated_string_t strings[128];
  size_t n_strings;
} generated_string_set_t;

generated_string_t str_concat(generated_string_t s1, const generated_string_t s2) {
  generated_string_t r;
  r.s = s1.s | (s2.s >> s1.len);
  r.len = s1.len + s2.len;
  return r;
}

void set_union(generated_string_set_t *set1, const generated_string_set_t *set2) {
  for (size_t i = 0; i < set2->n_strings; ++i) {
    generated_string_t s2 = set2->strings[i];
    bool found_it = false;
    for (size_t j = 0; j < set1->n_strings && !found_it; ++j) {
      generated_string_t s1 = set1->strings[j];
      found_it = (s1.len == s2.len && s1.s == s2.s);
    }
    if ((!found_it) && set1->n_strings < LENGTH(set1->strings)) {
      set1->strings[set1->n_strings++] = s2;
    }
  }
}

generated_string_set_t generate(const alternatives_t *rules, size_t id) {
  const alternatives_t *r = rules + id;
  generated_string_set_t ret;
  ret.n_strings = 0;
  if (r->n_alt == 1 && r->alternatives[0].n_symb == 1 && r->alternatives[0].symbols[0].t == TERMINAL) {
    ret.n_strings = 1;
    ret.strings[0].len = 1;
    ret.strings[0].s = (r->alternatives[0].symbols[0].symbol.terminal == 'b') << 7;
  }
  else {
    /* union of generated strings for each alternative */
    for (size_t i = 0; i < r->n_alt; ++i) {
      generated_string_set_t prefixes;
      prefixes.n_strings = 1;
      prefixes.strings[0].len = 0;
      prefixes.strings[0].s = 0;
      for (size_t j = 0; j < r->alternatives[i].n_symb; ++j) {
        /* every combination of generated strings for each symbol in the sequence */
        generated_string_set_t suffixes = generate(rules, r->alternatives[i].symbols[j].symbol.id);
        generated_string_set_t tmp = { .n_strings = 0, };
        for (size_t k = 0; k < prefixes.n_strings; ++k) {
          for (size_t l = 0; l < suffixes.n_strings; ++l) {
            if (tmp.n_strings < LENGTH(tmp.strings)) {
              tmp.strings[tmp.n_strings++] = str_concat(prefixes.strings[k], suffixes.strings[l]);
            }
            else {
              fprintf(stderr, "ERROR: too many strings.\n");
              exit(EXIT_FAILURE);
            }
          }
        }
        prefixes = tmp;
      }
      set_union(&ret, &prefixes);
    }
  }

  return ret;
}

typedef struct {
  unsigned char buf[20];
  size_t len;
} input_string_t;

input_string_t next_message() {
  input_string_t ret;
  memset(&ret, 0, sizeof ret);
  char buf[100] = { 0, };
  if (fgets(buf, sizeof buf, stdin) != NULL) {
    /* convert line to a big endian int */
    char *b = buf;
    size_t i = 0;
    for (; *b && *b != '\n'; ++b, ++i) {
      ret.buf[i >> 3] |= (*b == 'b') << (7 - (i&7));
    }
    ret.len = i >> 3;
  }
  return ret;
}

int main(void) {
  alternatives_t rules[150] = { 0, };
  size_t n_rules = 0;

  char buf[40] = { 0, };
  /* Read rules */
  while (fgets(buf, LENGTH(buf), stdin) != NULL && *buf != '\n') {
    alternatives_t rule;
    memset(&rule, 0, sizeof rule);
    char *b = buf;
    int consumed;
    /* read rule id  */
    size_t id;
    int ret = sscanf(buf, "%zu: %n", &id, &consumed);
    if (ret > 0) {
      b += consumed;
    }
    if (id >= LENGTH(rules)) {
      fprintf(stderr, "Error: rule id #%zu too big.\n", id);
      return EXIT_FAILURE;
    }
    n_rules = (id + 1> n_rules)? (id + 1) : n_rules;
    /* see if we got a terminal */
    char c;
    if (sscanf(b, "\"%c\"\n%n", &c, &consumed) > 0) {
      rule.n_alt = 1;
      rule.alternatives[0].n_symb = 1;
      rule.alternatives[0].symbols[0].t = TERMINAL;
      rule.alternatives[0].symbols[0].symbol.terminal = c;
    }
    else {
      /* parse alternatives (max consecutive nonterminals is 3) */
      for (rule.n_alt = 0; rule.n_alt < LENGTH(rule.alternatives); ++rule.n_alt) {
        sequence_t *s = rule.alternatives + rule.n_alt;
        ret = sscanf(b, "%zu%n %zu%n %zu%n", &s->symbols[0].symbol.id, &consumed, &s->symbols[1].symbol.id, &consumed, &s->symbols[2].symbol.id, &consumed);
        if (ret <= 0) {
          break;
        }
        s->n_symb = ret;
        b += consumed;
        consumed = 0;
        ret = sscanf(b, " | %n", &consumed);
        b += consumed;
      }
      if (*b != '\n') {
        fprintf(stderr, "Error: not end of line: %s.\n", b);
        exit(EXIT_FAILURE);
      }
    }
    rules[id] = rule;
  }

  /* preprocessing: find all strings generated by rule 42. */
  generated_string_set_t set = generate(rules, 42);
  bool generated_by_rule_42[256] = { 0, };
  for (size_t i = 0; i < set.n_strings; ++i) {
    generated_by_rule_42[set.strings[i].s] = true;
  }

  /* read and match inputs */
  size_t match1 = 0;
  size_t match2 = 0;

  while (true) {
    input_string_t s = next_message();
    if (s.len == 0) {
      break;
    }
    size_t m42 = 0;
    size_t m31 = 0;
    size_t i = 0;
    for (; i < s.len &&  generated_by_rule_42[s.buf[i]]; ++i, ++m42);
    for (; i < s.len && !generated_by_rule_42[s.buf[i]]; ++i, ++m31);
    match1 += (i == s.len &&  m42 == 2  &&  m31 == 1);
    match2 += (i == s.len && (m42 >= 2) && (m31 >= 1) && (m31 < m42));
  }

  printf("%zu\n", match1);
  printf("%zu\n", match2);

  return EXIT_SUCCESS;
}

A src/20.c => src/20.c +373 -0
@@ 0,0 1,373 @@
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <errno.h>

#define LENGTH(arr) (sizeof (arr) / sizeof (*arr))

typedef enum {
  O_ROT0, /* do nothing */
  O_ROT1, /* rotate clockwise by a quarter turn */
  O_ROT2, /* rotate clocwkise by a half turn */
  O_ROT3,
  O_ROT0_FLIPV, /* flip vertically */
  O_ROT1_FLIPV, /* rotate clockwise by a quarter turn, then flip */
  O_ROT2_FLIPV,
  O_ROT3_FLIPV,
} orientation_t;

typedef struct {
  unsigned n;
  unsigned edges[8];
  /* edges[0] is the top edge (left to right)
   * edges[1] is the left edge (down to up)
   * edges[2] is the bottom edge (right to left)
   * edges[3] is the right edge (up to down)
   * edges[4] is the top edge (right to left)
   * edges[5] is the left edge (up to down)
   * edges[6] is the bottom edge (left to right)
   * edges[7] is the right edge (down to up)
   */
  orientation_t orientation;
  /* the orientation only affects "data", not "edges"! */
  bool data[8*8];
} tile_t;

#define flatten(i, j, N) ((i) + (N) * (j))

unsigned reverse_bits(unsigned n) {
  unsigned m = 0;
  for (size_t i = 0; i < 10; ++i) {
    m = (m << 1) | (n & 1);
    n >>= 1;
  }
  return m;
}

unsigned count_bits(unsigned n) {
  unsigned count = 0;
  for (; n; count += (n & 1), n >>= 1);
  return count;
}

void rotate_edges_counterclockwise(unsigned edges[8]) {
  unsigned tmp;
  tmp = edges[3];
  edges[3] = edges[2];
  edges[2] = edges[1];
  edges[1] = edges[0];
  edges[0] = tmp;
  edges[4] = reverse_bits(edges[0]);
  edges[5] = reverse_bits(edges[1]);
  edges[6] = reverse_bits(edges[2]);
  edges[7] = reverse_bits(edges[3]);
}

void flip_edges_vertically(unsigned edges[8]) {
  edges[0] = edges[4];
  edges[1] = edges[7];
  edges[2] = edges[6];
  edges[3] = edges[5];
  edges[4] = reverse_bits(edges[0]);
  edges[5] = reverse_bits(edges[1]);
  edges[6] = reverse_bits(edges[2]);
  edges[7] = reverse_bits(edges[3]);
}

void reorient_edges(unsigned edges[8], orientation_t o) {
  switch (o) {
    case O_ROT3: rotate_edges_counterclockwise(edges); /* fall through */
    case O_ROT2: rotate_edges_counterclockwise(edges); /* fall through */
    case O_ROT1: rotate_edges_counterclockwise(edges); /* fall through */
    case O_ROT0: break;
    case O_ROT3_FLIPV: rotate_edges_counterclockwise(edges); /* fall through */
    case O_ROT2_FLIPV: rotate_edges_counterclockwise(edges); /* fall through */
    case O_ROT1_FLIPV: rotate_edges_counterclockwise(edges); /* fall through */
    case O_ROT0_FLIPV: flip_edges_vertically(edges);
  }
}

bool find_matching_edge(const tile_t *tiles, const bool *used, size_t n_tiles, unsigned edge, size_t *which_tile, int *which_edge) {
  for (size_t i = 0; i < n_tiles; ++i) {
    const tile_t *t = tiles + i;
    if (used[i]) {
      continue;
    }
    for (int j = 0; j < 8; ++j) {
      if (t->edges[j] == edge) {
        *which_tile = i;
        *which_edge = j;
        return true;
      }
    }
  }
  return false;
}

bool matching_edge_exists(const tile_t *tiles, const bool *used, size_t n_tiles, unsigned edge) {
  size_t i;
  int e;
  return find_matching_edge(tiles, used, n_tiles, edge, &i, &e);
}

void rotate_data_counterclockwise(bool *data, size_t sx, size_t sy) {
  bool copy[sx * sy];
  for (size_t iy = 0; iy < sy; ++iy) {
    for (size_t ix = 0; ix < sx; ++ix) {
      copy[flatten(iy, sx -1 - ix, sy)] = data[flatten(ix, iy, sx)];
    }
  }
  for (size_t i = 0; i < sx * sy; ++i) {
    data[i] = copy[i];
  }
}

void flip_data_vertically(bool *data, size_t sx, size_t sy) {
  bool copy[sx * sy];
  for (size_t iy = 0; iy < sy; ++iy) {
    for (size_t ix = 0; ix < sx; ++ix) {
      copy[flatten(ix, iy, sx)] = data[flatten(sx - 1 - ix, iy, sx)];
    }
  }
  for (size_t i = 0; i < sx * sy; ++i) {
    data[i] = copy[i];
  }
}

void reorient_data(bool *data, size_t sx, size_t sy, orientation_t o) {
  switch (o) {
    case O_ROT3_FLIPV: rotate_data_counterclockwise(data, sx, sy); // fall through
    case O_ROT2_FLIPV: rotate_data_counterclockwise(data, sx, sy); // fall through
    case O_ROT1_FLIPV: rotate_data_counterclockwise(data, sx, sy); // fall through
    case O_ROT0_FLIPV: flip_data_vertically(data, sx, sy); break;
    case O_ROT3: rotate_data_counterclockwise(data, sx, sy); // fall through
    case O_ROT2: rotate_data_counterclockwise(data, sx, sy); // fall through
    case O_ROT1: rotate_data_counterclockwise(data, sx, sy); // fall through
    case O_ROT0: break;
  }
}

int find_and_remove_monsters(bool *data, size_t sdx, size_t sdy, const bool *monster, size_t smx, size_t smy) {
  int n = 0;
  for (size_t ix = 0; ix + smx <= sdx; ++ix) {
    for (size_t iy = 0; iy + smy <= sdy; ++iy) {
      size_t overlap = 0;
      for (size_t dx = 0; dx < smx; ++dx) {
        for (size_t dy = 0; dy < smy; ++dy) {
          overlap += data[flatten(ix+dx, iy+dy, sdx)] & monster[flatten(dx, dy, smx)];
        }
      }
      if (overlap == 15) {
        /* the monster has 15 set tiles; got a match for all of them. */
        ++n;
        for (size_t dx = 0; dx < smx; ++dx) {
          for (size_t dy = 0; dy < smy; ++dy) {
            data[flatten(ix+dx, iy+dy, sdx)] &= !monster[flatten(dx, dy, smx)];
          }
        }
      }
    }
  }
  return n;
}

int main(void) {
  tile_t tiles[12*12];
  size_t n_tiles = 0;

  /* read tiles */
  while (n_tiles < LENGTH(tiles) && scanf("Tile %u:\n", &tiles[n_tiles].n) == 1) {
    bool data_with_edges[10*10] = { 0 };
    for (size_t j = 0; j < 10; ++j) {
      for (size_t i = 0; i < 10; ++i) {
        data_with_edges[flatten(i, j, 10)] = getchar() == '#';
      }
      (void) getchar();
    }
    (void) getchar();
    for (size_t j = 0; j < 8; ++j) {
      for (size_t i = 0; i < 8; ++i) {
        tiles[n_tiles].data[flatten(i, j, 8)] = data_with_edges[flatten(i+1, j+1, 10)];
      }
    }
    for (size_t i = 0; i < 8; ++i) {
      tiles[n_tiles].edges[i] = 0;
    }
    for (size_t i = 0; i < 10; ++i) {
      tiles[n_tiles].edges[0] = (tiles[n_tiles].edges[0] << 1) | data_with_edges[flatten(  i,   0, 10)];
      tiles[n_tiles].edges[1] = (tiles[n_tiles].edges[1] << 1) | data_with_edges[flatten(  0, 9-i, 10)];
      tiles[n_tiles].edges[2] = (tiles[n_tiles].edges[2] << 1) | data_with_edges[flatten(9-i,   9, 10)];
      tiles[n_tiles].edges[3] = (tiles[n_tiles].edges[3] << 1) | data_with_edges[flatten(  9,   i, 10)];
    }
    for (size_t i = 0; i < 4; ++i) {
      tiles[n_tiles].edges[i+4] = reverse_bits(tiles[n_tiles].edges[i]);
    }
    tiles[n_tiles].orientation = O_ROT0;
    ++n_tiles;
  }
  if (ferror(stdin) || !feof(stdin)) {
    fprintf(stderr, "Input error: %s\n", strerror(errno));
    return 1;
  }

  /* find a corner tile and place it at the top left, oriented such that its edges point down and right */
  bool used[LENGTH(tiles)] = { 0, };
  tile_t *tile_grid[LENGTH(tiles)] = { 0, };

  for (size_t i = 0; i < n_tiles; ++i) {
    used[i] = true;
    int m = 0;
    for (size_t e = 0; e < 4; ++e) {
      m |= matching_edge_exists(tiles, used, n_tiles, tiles[i].edges[e]) << e; // does the e'th edge (clockwise from the top) have a match?
    }
    if (count_bits(m) == 2) {
      tile_t *t = tiles + i;
      tile_grid[0] = t;
      switch(m) {
        case (1 | 2): // top and left have a match
          t->orientation = O_ROT2; break;
        case (1 | 8): // top and right have a match
          t->orientation = O_ROT3; break;
        case (2 | 4): // left and bottom have a match
          t->orientation = O_ROT1; break;
        case (4 | 8): // bottom and right have a match
          t->orientation = O_ROT0; break;
        default:
          fprintf(stderr, "huh?\n");
          return 1;
      }
      reorient_edges(t->edges, t->orientation);
      break;
    }
    used[i] = false;
  }

  if (!tile_grid[0]) {
    fprintf(stderr, "No edge tile found.\n");
    return 1;
  }

  /* fill the top row */
  size_t sx = 12;
  for (size_t ix = 1; ix < sx; ++ix) {
    unsigned target_edge = tile_grid[ix-1]->edges[3];
    int e = -1;
    size_t i = 0;
    if (find_matching_edge(tiles, used, n_tiles, target_edge, &i, &e)) {
      used[i] = true;
      tile_t *t = tiles + i;
      tile_grid[flatten(ix, 0, 12)] = t;
      switch (e) {
        /* NOTE: the orientations here run counter to the one of the tile on the left.
         * If we find a perfect match for edge 1 (left - bottom up) here, then we actually have to flip the tile horizontally!
         */
        case 0: t->orientation = O_ROT3_FLIPV; break;
        case 1: t->orientation = O_ROT2_FLIPV; break;
        case 2: t->orientation = O_ROT1_FLIPV; break;
        case 3: t->orientation = O_ROT0_FLIPV; break;
        case 4: t->orientation = O_ROT1; break;
        case 5: t->orientation = O_ROT0; break;
        case 6: t->orientation = O_ROT3; break;
        case 7: t->orientation = O_ROT2; break;
        default:
          fprintf(stderr, "huh?\n");
          return 1;
      }
      reorient_edges(t->edges, t->orientation);
    }
    else {
      sx = ix;
    }
  }

  /* fill the rows below */
  size_t sy = 12;
  for (size_t iy = 1; iy < sy; ++iy) {
    bool any_match = false;
    for (size_t ix = 0; ix < sx; ++ix) {
      unsigned target_edge = tile_grid[flatten(ix, iy-1, 12)]->edges[2];
      int e = -1;
      size_t i = 0;
      if (find_matching_edge(tiles, used, n_tiles, target_edge, &i, &e)) {
        any_match = true;
        used[i] = true;
        tile_t *t = tiles + i;
        tile_grid[flatten(ix, iy, 12)] = t;
        switch (e) {
        /* NOTE: the orientations here run counter to the one of the tile on the left.
         * If we find a perfect match for edge 0 (top - left right) here, then we actually have to flip the tile vertically!
         */
          case 0: t->orientation = O_ROT0_FLIPV; break;
          case 1: t->orientation = O_ROT3_FLIPV; break;
          case 2: t->orientation = O_ROT2_FLIPV; break;
          case 3: t->orientation = O_ROT1_FLIPV; break;
          case 4: t->orientation = O_ROT0; break;
          case 5: t->orientation = O_ROT3; break;
          case 6: t->orientation = O_ROT2; break;
          case 7: t->orientation = O_ROT1; break;
          default:
            fprintf(stderr, "huh?\n");
            return 1;
        }
        reorient_edges(t->edges, t->orientation);
      }
      else {
        break;
      }
    }
    if (!any_match) {
      sy = iy;
      break;
    }
  }

  /* part1: product of tile numbers for the edges */
  printf("%llu\n",
    ((unsigned long long) tile_grid[flatten(0,       0, 12)]->n)
  * ((unsigned long long) tile_grid[flatten(sx-1,    0, 12)]->n)
  * ((unsigned long long) tile_grid[flatten(0,    sy-1, 12)]->n)
  * ((unsigned long long) tile_grid[flatten(sx-1, sy-1, 12)]->n));

  /* re-join image data */
  bool image_data[8*12*8*12] = { 0, };
  for (size_t iy = 0; iy < sy; ++iy) {
    for (size_t ix = 0; ix < sx; ++ix) {
      reorient_data(tile_grid[flatten(ix, iy, 12)]->data, 8, 8, tile_grid[flatten(ix, iy, 12)]->orientation);
      tile_grid[flatten(ix, iy, 12)]->orientation = O_ROT0;
      for (size_t jy = 0; jy < 8; ++jy) {
        for (size_t jx = 0; jx < 8; ++jx) {
          image_data[flatten(ix*8+jx, iy*8+jy, 8*12)] = tile_grid[flatten(ix, iy, 12)]->data[flatten(jx, jy, 8)];
        }
      }
    }
  }

  /* look for sea monster */
  bool monster[3*20] = {
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0,
    1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1,
    0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0,
  };
  size_t smx = 20;
  size_t smy = 3;

  for (int i = 0; i < 8; ++i) {
    if (find_and_remove_monsters(image_data, 8*12, 8*12, monster, smx, smy)) {
      break;
    }
    rotate_data_counterclockwise(monster, smx, smy);
    { size_t tmp = smx; smx = smy; smy = tmp; }
    if (i == 4) {
      flip_data_vertically(monster, smx, smy);
    }
  }

  size_t sum = 0;
  for (size_t i = 0; i < LENGTH(image_data); ++i) {
    sum += image_data[i];
  }
  printf("%zu\n", sum);

  return 0;
}

A src/21.c => src/21.c +202 -0
@@ 0,0 1,202 @@
#include <stdio.h>
#include <string.h>
#include <stdbool.h>

#define LENGTH(arr) (sizeof (arr) / sizeof *(arr))

#define MAX_NAME_LENGTH 15
#define MAX_NAME_LENGTH_S "14"
#define MAX_INGREDIENTS 250
#define MAX_ALLERGENS 10

typedef struct {
  bool set[MAX_INGREDIENTS];
} int_set_t;

typedef struct {
  bool set[MAX_ALLERGENS];
} small_int_set_t;

typedef struct {
  char buf[MAX_NAME_LENGTH];
} name_t;

typedef struct {
  size_t allergen;
  size_t ingredient;
} match_t;

size_t findindex(const name_t *t, const name_t *table, size_t n) {
  for (size_t i = 0; i < n; ++i) {
    if (strcmp(table[i].buf, t->buf) == 0) {
      return i;
    }
  }
  return n;
}

void set_intersect(int_set_t *set1, const int_set_t *set2) {
  for (size_t i = 0; i < MAX_INGREDIENTS; ++i) {
    set1->set[i] &= set2->set[i];
  }
}

void set_union(int_set_t *set1, const int_set_t *set2) {
  for (size_t i = 0; i < MAX_INGREDIENTS; ++i) {
    set1->set[i] |= set2->set[i];
  }
}

int main(void) {
  int_set_t food_ingredients[40];
  small_int_set_t food_allergens[40];
  size_t n_foods = 0;

  name_t all_allergens[MAX_ALLERGENS];
  size_t n_allergens = 0;

  name_t all_ingredients[MAX_INGREDIENTS];
  size_t n_ingredients = 0;

  /* read input */
  char buf[1000];
  while (fgets(buf, sizeof buf, stdin) != NULL) {
    if (n_foods >= LENGTH(food_ingredients)) {
      fprintf(stderr, "Error: Too many foods.\n");
      return 1;
    }
    memset(food_ingredients + n_foods, 0, sizeof food_ingredients[n_foods]);
    memset(food_allergens + n_foods, 0, sizeof food_allergens[n_foods]);
    ++n_foods;
    if ((!buf[0]) || buf[0] == '\n') {
      break;
    }
    /* read ingredients */
    char *b = buf;
    name_t name;
    int consumed = 0;
    while (sscanf(b, "%"MAX_NAME_LENGTH_S"s %n", name.buf, &consumed) > 0 && name.buf[0]) {
      b += consumed;
      size_t i = findindex(&name, all_ingredients, n_ingredients);
      if (name.buf[0] == '(') {
        break; /* must be "contains" */
      }
      if (i >= n_ingredients) {
        /* if we have not seen this ingredient before, remember its name */
        if (n_ingredients < MAX_INGREDIENTS) {
          all_ingredients[n_ingredients++] = name;
        }
        else {
          fprintf(stderr, "Error: Too many ingredients.\n");
          return 1;
        }
      }
      food_ingredients[n_foods-1].set[i] = true;
    }
    /* read allergens */
    while (sscanf(b, "%"MAX_NAME_LENGTH_S"s %n", name.buf, &consumed) > 0 && name.buf[0]) {
      b += consumed;
      size_t fi = strlen(name.buf) - 1;
      if (fi == 0) {
        break;
      }
      if (name.buf[fi] == ')' || name.buf[fi] == ',') {
        name.buf[fi] = '\0';
      }
      size_t i = findindex(&name, all_allergens, n_allergens);
      if (i >= n_allergens) {
        /* if we have not seen this ingredient before, remember its name */
        if (n_allergens < MAX_ALLERGENS) {
          all_allergens[n_allergens++] = name;
        }
        else {
          fprintf(stderr, "Error: Too many allergens.\n");
          return 1;
        }
      }
      food_allergens[n_foods-1].set[i] = true;
    }
  }

  /* for each allergen, see which ingredients it may be contained in (assuming that there is exactly one); also mark ingredients which cannot correspond to any allergen */
  int_set_t potential_ingredients[MAX_ALLERGENS];
  memset(&potential_ingredients, 0, sizeof potential_ingredients);
  int_set_t unsafe;
  memset(&unsafe, 0, sizeof unsafe);
  for (size_t i_all = 0; i_all < n_allergens; ++i_all) {
    for (size_t i_ingr = 0; i_ingr < n_ingredients; ++i_ingr) {
      potential_ingredients[i_all].set[i_ingr] = true;
    }
    for (size_t i_food = 0; i_food < n_foods; ++i_food) {
      if (food_allergens[i_food].set[i_all]) {
        set_intersect(potential_ingredients + i_all, food_ingredients + i_food);
      }
    }
    set_union(&unsafe, potential_ingredients + i_all);
  }

  /* part1: count occurrences of "definitely" safe foods (... safe as per the description) */
  size_t safe_count = 0;
  for (size_t i = 0; i < n_ingredients; ++i) {
    if (!unsafe.set[i]) {
      for (size_t j = 0; j < n_foods; ++j) {
        safe_count += food_ingredients[j].set[i];
      }
    }
  }
  printf("%zu\n", safe_count);

  /* part 2: repeatedly match ingredients to allergens for those with just one possibility */
  match_t matches[MAX_ALLERGENS];
  size_t n_matched = 0;
  bool already_matched[MAX_ALLERGENS] = { 0, };
  bool found_unassigned = false;
  do {
    found_unassigned = false;
    for (size_t i_allergen = 0; i_allergen < n_allergens; ++i_allergen) {
      if (already_matched[i_allergen]) {
        continue;
      }
      found_unassigned = true;
      /* is there exactly one possible ingredient for the current allergen? */
      size_t i_ingredient = 0;
      size_t n_possibilities = 0;
      for (size_t i = 0; i < n_ingredients; ++i) {
        if (potential_ingredients[i_allergen].set[i]) {
          i_ingredient = i;
          ++n_possibilities;
        }
      }
      if (n_possibilities == 1) {
        /* assign it, then remove the ingredient from other potential matches */
        matches[n_matched].allergen = i_allergen;
        matches[n_matched].ingredient = i_ingredient;
        already_matched[i_allergen] = true;
        for (size_t j = 0; j < n_allergens; ++j) {
          potential_ingredients[j].set[i_ingredient] = false;
        }
        ++n_matched;
        break;
      }
    }
  } while (found_unassigned);

  /* sort the matches in-place by allergen name. Selection sort works fine because there are only 8 allergens */
  for (size_t i = 0; i < n_allergens; ++i) {
    for (size_t j = i+1; j < n_allergens; ++j) {
      if (strcmp(all_allergens[matches[i].allergen].buf, all_allergens[matches[j].allergen].buf) > 0) {
        match_t m = matches[i];
        matches[i] = matches[j];
        matches[j] = m;
      }
    }
  }

  /* output matched ingredient names */
  for (size_t i = 0; i < n_allergens; ++i) {
    size_t i_ingredient = matches[i].ingredient;
    printf("%s%c", all_ingredients[i_ingredient].buf, (i + 1 < n_allergens)? ',' : '\n');
  }

  return 0;
}

A src/22.c => src/22.c +211 -0
@@ 0,0 1,211 @@
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>
#include <errno.h>
#include <string.h>

#define MAX_DECK_SIZE 50
#define MAX_BIN_SIZE 5
#define N_BINS (1<<12) /* NEEDS TO BE A POWER OF TWO */

typedef struct {
  uint8_t size;
  uint8_t data[MAX_DECK_SIZE];
} deck_t;

typedef struct {
  size_t size;
  deck_t data1[MAX_BIN_SIZE];
  deck_t data2[MAX_BIN_SIZE];
} bin_t;

typedef struct {
  bin_t *bins[N_BINS];
} hashset_t;

void *ensure_allocated(void *p, size_t size) {
  if (p != NULL) {
    return p;
  }
  void *ptr = malloc(size);
  if (ptr == NULL) {
    fprintf(stderr, "Allocation error: %s\n", strerror(errno));
    exit(1);
  }
  memset(ptr, 0, size);
  return ptr;
}

bool deck_eq(const deck_t *d1, const deck_t *d2) {
  if (d1->size != d2->size) {
    return false;
  }
  for (size_t i = 0; i < d1->size; ++i) {
    if (d1->data[i] != d2->data[i]) {
      return false;
    }
  }
  return true;
}

uint32_t hs_hash(const deck_t *deck1, const deck_t *deck2) {
  /* specialized djb2 from http://www.cse.yorku.ca/~oz/hash.html */
  uint32_t h = 5381;
  h = ((h << 5) + h) + (uint32_t) deck1->size;
  h = ((h << 5) + h) + (uint32_t) deck2->size;
  for (size_t i = 0; i < (size_t) deck1->size; ++i) {
    h = ((h << 5) + h) + deck1->data[i];
    h = ((h << 5) + h) + deck2->data[i];
  }
  return h;
}

bool insert_unless_present(hashset_t *hs, const deck_t *deck1, const deck_t *deck2) {
  size_t i_bin = hs_hash(deck1, deck2) & (N_BINS-1);
  hs->bins[i_bin] = ensure_allocated(hs->bins[i_bin], sizeof *hs->bins[i_bin]);
  for (size_t i = 0; i < hs->bins[i_bin]->size; ++i) {
    if (deck_eq(deck1, hs->bins[i_bin]->data1 + i) && deck_eq(deck2, hs->bins[i_bin]->data2 + i)) {
      return false;
    }
  }
  if (hs->bins[i_bin]->size >= MAX_BIN_SIZE) {
    fprintf(stderr, "Error: Bin overflow.\n");
    exit(EXIT_FAILURE);
  }
  hs->bins[i_bin]->data1[hs->bins[i_bin]->size] = *deck1;
  hs->bins[i_bin]->data2[hs->bins[i_bin]->size] = *deck2;
  ++hs->bins[i_bin]->size;
  return true;
}

void hs_free(hashset_t *hs) {
  for (size_t i = 0; i < N_BINS; ++i) {
    free(hs->bins[i]);
  }
  free(hs);
}

unsigned long score(const deck_t *deck) {
  size_t s = 0;
  for (size_t i = 0; i < deck->size; ++i) {
    s += deck->data[i] * (deck->size - i);
  }
  return s;
}

unsigned char pop_front(deck_t *d) {
  unsigned char n = d->data[0];
  for (size_t i = 1; i < d->size; ++i) {
    d->data[i-1] = d->data[i];
  }
  --d->size;
  return n;
}

void push_back(deck_t *d, unsigned char a, unsigned char b) {
  d->data[d->size++] = a;
  d->data[d->size++] = b;
}

deck_t take(const deck_t *d, unsigned char n) {
  deck_t ret = { .size = n };
  for (size_t i = 0; i < n; ++i) {
    ret.data[i] = d->data[i];
  }
  return ret;
}

unsigned char max_of_first(const deck_t *deck, unsigned char n) {
  unsigned char max = 0;
  for (size_t i = 0; i < n; ++i) {
    max = (deck->data[i] > max)? deck->data[i] : max;
  }
  return max;
}

int run(deck_t *deck1, deck_t *deck2, bool recur) {
  hashset_t *seen = ensure_allocated(NULL, sizeof *seen);
  while (deck1->size > 0 && deck2->size > 0) {
    if (!insert_unless_present(seen, deck1, deck2)) {
      hs_free(seen);
      return 1;
    }
    unsigned char c1 = pop_front(deck1);
    unsigned char c2 = pop_front(deck2);
    if (recur && c1 <= deck1->size && c2 <= deck2->size) {
      int winner = 0;
      if (max_of_first(deck1, c1) > max_of_first(deck2, c2)) {
        winner = 1;
      }
      else {
        deck_t d1 = take(deck1, c1);
        deck_t d2 = take(deck2, c2);
        winner = run(&d1, &d2, recur);
      }
      if (winner == 1) {
        push_back(deck1, c1, c2);
      }
      else {
        push_back(deck2, c2, c1);
      }
    }
    else if (c1 > c2) {
      push_back(deck1, c1, c2);
    }
    else {
      push_back(deck2, c2, c1);
    }
  }
  hs_free(seen);
  if (deck1->size > 0) {
    return 1;
  }
  else {
    return 2;
  }
}

unsigned long part1(deck_t deck1, deck_t deck2) {
  if (run(&deck1, &deck2, false) == 1) {
    return score(&deck1);
  }
  else {
    return score(&deck2);
  }
}

unsigned long part2(deck_t deck1, deck_t deck2) {
  if (run(&deck1, &deck2, true) == 1) {
    return score(&deck1);
  }
  else {
    return score(&deck2);
  }
}

int main(void) {
  deck_t d1 = { .size = 0 };
  deck_t d2 = { .size = 0 };

  {
    size_t n = 0;
    (void) scanf("%*s %*s\n");
    while (d1.size < MAX_DECK_SIZE && scanf("%zu\n", &n) == 1) {
      d1.data[d1.size++] = (unsigned char) n;
    }
    (void) scanf("%*s %*s\n");
    while (d2.size < MAX_DECK_SIZE && scanf("%zu\n", &n) == 1) {
      d2.data[d2.size++] = (unsigned char) n;
    }
    if (ferror(stdin) || !feof(stdin)) {
      fprintf(stderr, "Input error: %s\n", strerror(errno));
      exit(EXIT_FAILURE);
    }
  }

  printf("%lu\n", part1(d1, d2));
  printf("%lu\n", part2(d1, d2));

  return 0;
}

A src/23.c => src/23.c +98 -0
@@ 0,0 1,98 @@
#include <stdio.h>
#include <ctype.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>

void prep(uint_least32_t **next, const uint_least32_t *numbers, size_t n_numbers, size_t pad) {
  *next = calloc((pad > n_numbers)? pad : n_numbers, sizeof **next);
  if (*next == NULL) {
    fprintf(stderr, "Allocation Error: %s\n", strerror(errno));
    exit(EXIT_FAILURE);
  }
  for (size_t i = 0; i < n_numbers; ++i) {
    (*next)[numbers[i] - 1] = numbers[(i + 1) % n_numbers] - 1;
  }
  if (pad > n_numbers) {
    (*next)[numbers[n_numbers - 1] - 1] = n_numbers;
    for (size_t i = n_numbers; i < pad - 1; ++i) {
      (*next)[i] = i + 1;
    }
    (*next)[pad - 1] = numbers[0] - 1;
  }
}

void run(uint_least32_t *next, size_t next_len, size_t current_cup, size_t runs) {
  for (size_t i = 0; i < runs; ++i) {
    /* pick up cards */
    uint_least32_t p1 = next[current_cup];
    uint_least32_t p2 = next[p1];
    uint_least32_t p3 = next[p2];
    next[current_cup] = next[p3];
    /* find target cup */
    size_t target = current_cup;
    do {
      target = (target > 0) ? target - 1 : next_len - 1;
    } while ((target == p1) || (target == p2) || (target == p3));
    /* insert cups */
    next[p3] = next[target];
    next[target] = p1;
    current_cup = next[current_cup];
  }
}

void get_first(const uint_least32_t *next, uint_least32_t *ret, size_t n) {
  size_t cur = 0;
  for (size_t i = 0; i < n; ++i) {
    cur = (size_t) next[cur];
    ret[i] = (uint_least32_t) cur + 1;
  }
}

void part1(const uint_least32_t *numbers, size_t n_numbers) {
  uint_least32_t *next;
  prep(&next, numbers, n_numbers, 0);
  run(next, n_numbers, numbers[0]-1, 100);
  uint_least32_t x[8];
  get_first(next, x, sizeof x / sizeof *x);
  for (size_t i = 0; i < sizeof x / sizeof *x; ++i) {
    putchar(x[i] + '0');
  }
  putchar('\n');
  free(next);
}

void part2(const uint_least32_t *numbers, size_t n_numbers) {
  uint_least32_t *next;
  size_t pad = 1000000;
  prep(&next, numbers, n_numbers, pad);
  run(next, pad, numbers[0]-1, 10000000);
  uint_least32_t x[2];
  get_first(next, x, sizeof x / sizeof *x);
  unsigned long long res = 1;
  for (size_t i = 0; i < sizeof x / sizeof *x; ++i) {
    res *= (unsigned long long) x[i];
  }
  printf("%llu\n", res);
  free(next);
}

int main(void) {
  uint_least32_t numbers[20] = { 0, };
  size_t n_numbers = 0;
  int c;
  while ((c = getchar()) != EOF) {
    if (isdigit(c) && n_numbers < sizeof numbers / sizeof *numbers) {
      numbers[n_numbers++] = (int_least32_t) (c - '0');
    }
  }
  if (ferror(stdin) || !feof(stdin)) {
    fprintf(stderr, "Input error: %s.\n", strerror(errno));
    return 1;
  }

  part1(numbers, n_numbers);
  part2(numbers, n_numbers);
  return 0;
}

A src/24.c => src/24.c +117 -0
@@ 0,0 1,117 @@
#include <stdio.h>
#include <string.h>
#include <errno.h>
#include <stdbool.h>

#define N 301
#define CENTER (N/2)

#define ITERATIONS 100

#define flatten(i, j) ((i) * N + (j))
#define safe_get(g, i, j) ((i < N && j < N)? g[flatten(i, j)] : 0)
#define safe_set(g, v, i, j) do { \
    if (i < N && j < N) { \
      g[flatten(i, j)] = v; \
    } \
  } while (0)

#define min(a, b) ((a < b)? a : b)
#define max(a, b) ((a < b)? b : a)

int main(void) {
  bool isblack[N*N] = { 0, };

  /* part 1: read */
  size_t a = CENTER; // steps east
  size_t b = CENTER; // steps north east
  while (1) {
    int c = getchar();
    if (c == '\n') {
      safe_set(isblack, !safe_get(isblack, a, b), a, b);
      a = CENTER;
      b = CENTER;
    }
    else if (c == EOF) {
      if (ferror(stdin)) {
        fprintf(stderr, "Input error: %s.\n", strerror(errno));
        return 1;
      }
      break;
    }
    if (c == 'e') {
      a += 1;
    }
    else if (c == 'w') {
      a -= 1;
    }
    else if (c == 'n') {
      b += 1;
      if (getchar() == 'w') {
        a -= 1;
      }
    }
    else if (c == 's') {
      b -= 1;
      if (getchar() == 'e') {
        a += 1;
      }
    }
  }

  /* part1: count */
  size_t cmin = N;
  size_t cmax = 0;
  size_t count = 0;
  for (size_t a = 0; a < N; ++a) {
    for (size_t b = 0; b < N; ++b) {
      if (isblack[flatten(a, b)]) {
        count += 1;
        cmin = min(cmin, a);
        cmin = min(cmin, b);
        cmax = max(cmax, a);
        cmax = max(cmax, b);
      }
    }
  }
  printf("%zu\n", count);

  /* make sure we have enough space to expand */
  --cmin;
  ++cmax;
  if (2 * ((cmax - cmin) + ITERATIONS) + 1 >= N) {
    fprintf(stderr, "Grid too small.\n");
    return 1;
  }

  /* part2: update */
  bool next[N*N] = { 0, };
  for (size_t i = 0; i < 100; ++i) {
    --cmin;
    ++cmax;
    for (size_t a = cmin; a < cmax; ++a) {
      for (size_t b = cmin; b < cmax; ++b) {
        int neighbours = \
            isblack[flatten(a+1, b  )] \
          + isblack[flatten(a,   b+1)] \
          + isblack[flatten(a-1, b+1)] \
          + isblack[flatten(a-1, b  )] \
          + isblack[flatten(a,   b-1)] \
          + isblack[flatten(a+1, b-1)];
        bool black = isblack[flatten(a, b)];
        next[flatten(a, b)] = (neighbours == 2) || (black && neighbours == 1);
      }
    }
    for (size_t i = flatten(cmin, cmin); i < flatten(cmax, cmax); ++i) {
      isblack[i] = next[i];
    }
  }

  count = 0;
  for (size_t i = flatten(cmin, cmin); i < flatten(cmax, cmax); ++i) {
    count += isblack[i];
  }
  printf("%zu\n", count);

  return 0;
}

A src/25.c => src/25.c +62 -0
@@ 0,0 1,62 @@
#include <stdio.h>
#include <string.h>
#include <errno.h>
#include <limits.h>

#define abs(a) ((a<0)? -a : a)

unsigned long long isqrtceil(unsigned long long n) {
  /* note: this is not very efficient in general; here, it works fine. */
  size_t highest_bit = 0;
  for (; (n >> highest_bit) && highest_bit < CHAR_BIT * sizeof n; ++highest_bit);
  unsigned long long x = 1ULL << (highest_bit >> 2);
  for (; x * x < n; ++x);
  return x;
}

unsigned long long powermod(unsigned long long a, unsigned long long b, unsigned long long p) {
  unsigned long long x = 1;
  for (; b; b >>= 1) {
    if (b & 1) {
      x = (a * x) % p;
    }
    a = (a * a) % p;
  }
  return x;
}

unsigned long long dlog(unsigned long long base, unsigned long long x, unsigned long long p) {
  base %= p;
  x %= p;
  unsigned long long m = isqrtceil(p);
  unsigned long long table[m];
  for (size_t i = 0; i < (size_t) m; ++i) {
    table[i] = powermod(base, i, p);
  }
  unsigned long long b_m_inv = powermod(base, p - m - 1, p);
  for (size_t i = 0; i < (size_t) m; ++i) {
    for (size_t j = 0; j < (size_t) m; ++j) {
      if (x == table[j]) {
        return (unsigned long long) i * m + (unsigned long long) j;
      }
    }
    x = (x * b_m_inv) % p;
  }
  return 0;
}

int main(void) {
  const unsigned long long p = 20201227; // this is prime.
  unsigned long long a, b;
  if (scanf("%llu\n%llu\n", &a, &b) != 2) {
    fprintf(stderr, "Input error: %s\n", strerror(errno));
    return 1;
  }
  if (a < 2 || b < 2) {
    fprintf(stderr, "haha, funny.\n");
    return 1;
  }
  printf("%llu\n", powermod(b, dlog(7, a, p), p));

  return 0;
}

A testinputs/15 => testinputs/15 +1 -0
@@ 0,0 1,1 @@
0,3,6

A testinputs/16 => testinputs/16 +12 -0
@@ 0,0 1,12 @@
departure date: 2-2 or 4-19
departure time: 2-5 or 8-19
seat: 2-13 or 16-19

your ticket:
11,12,13

nearby tickets:
20,1,5
3,9,18
15,2,5
5,14,9

A testinputs/17 => testinputs/17 +3 -0
@@ 0,0 1,3 @@
.#.
..#
###

A testinputs/18 => testinputs/18 +1 -0
@@ 0,0 1,1 @@
((2 + 4 * 9) * (6 + 9 * 8 + 6) + 6) + 2 + 4 * 2

A testinputs/19 => testinputs/19 +64 -0
@@ 0,0 1,64 @@
0: 8 11
8: 42
11: 42 31
1: "a"
2: "b"
3: 1 | 2
4: 3 3 3
5: 4 4 3
6: 1
7: 1
9: 1
10: 1
12: 1
13: 1
14: 1
15: 1
16: 1
17: 1
18: 1
19: 1
20: 1
21: 1
22: 1
23: 1
24: 1
25: 1
26: 1
27: 1
28: 1
29: 1
30: 1
31: 5 2
32: 1
33: 1
34: 1
35: 1
36: 1
37: 1
38: 1
39: 1
40: 1
41: 1
42: 5 1
43: 1
44: 1
45: 1

bbbaaabababaabaaabaaaababbbbbabb
aaabbbbabbaabaaaaaabbabbaabbbaba
ababbaaabbaabbbabbaaaaaababbbbab
aababbbabbbabaaabbbbbbab
aaababbaaaababbaaaabbaab
abbbabbabbbaaaaaaabbbbbbaaabbaba
baaaaabaabbabaaaaaaabbaabbbbbbbabababbbaababbababbbabbaaaabbbbbb
bbbabbbaabbabbaababaabbb
aaabaabaabaaaaaabababbba
aabbbabaabababbaaaababaaaaabbbbaabbbbbbabbbaaababaababbababbbaab
abbabaaaaaaaababbbabbbba
aabbbaaabbabbbaaaabbabab
bbbaabaababbbaaabababababbabaababaabaaaaababbaaabababbaaabaabbbb
aaaabbaabbabbbabbaaaaaba
aaababbaabaabbaaabaaaaabbbaabbaabbbbaababaaaabaabbbaabaaaabaababbbaaaabbaaaaaaab
aaaabbaabaabaaaababbbbab
babaaaaababbabaaaaabbbaa

A testinputs/20 => testinputs/20 +107 -0
@@ 0,0 1,107 @@
Tile 2311:
..##.#..#.
##..#.....
#...##..#.
####.#...#
##.##.###.
##...#.###
.#.#.#..##
..#....#..
###...#.#.
..###..###

Tile 1951:
#.##...##.
#.####...#
.....#..##
#...######
.##.#....#
.###.#####
###.##.##.
.###....#.
..#.#..#.#
#...##.#..

Tile 1171:
####...##.
#..##.#..#
##.#..#.#.
.###.####.
..###.####
.##....##.
.#...####.
#.##.####.
####..#...
.....##...

Tile 1427:
###.##.#..
.#..#.##..
.#.##.#..#
#.#.#.##.#
....#...##
...##..##.
...#.#####
.#.####.#.
..#..###.#
..##.#..#.

Tile 1489:
##.#.#....
..##...#..
.##..##...
..#...#...
#####...#.
#..#.#.#.#
...#.#.#..
##.#...##.
..##.##.##
###.##.#..

Tile 2473:
#....####.
#..#.##...
#.##..#...
######.#.#
.#...#.#.#
.#########
.###.#..#.
########.#
##...##.#.
..###.#.#.

Tile 2971:
..#.#....#
#...###...
#.#.###...
##.##..#..
.#####..##
.#..####.#
#..#.#..#.
..####.###
..#.#.###.
...#.#.#.#

Tile 2729:
...#.#.#.#
####.#....
..#.#.....
....#..#.#
.##..##.#.
.#.####...
####.#.#..
##.####...
##..#.##..
#.##...##.

Tile 3079:
#.#.#####.
.#..######
..#.......
######....
####.#..#.
.#...#.##.
#.#####.##
..#.###...
..#.......
..#.###...

A testinputs/21 => testinputs/21 +4 -0
@@ 0,0 1,4 @@
mxmxvkd kfcds sqjhc nhms (contains dairy, fish)
trh fvjkl sbzzf mxmxvkd (contains dairy)
sqjhc fvjkl (contains soy)
sqjhc mxmxvkd sbzzf (contains fish)

A testinputs/22 => testinputs/22 +13 -0
@@ 0,0 1,13 @@
Player 1:
9
2
6
3
1

Player 2:
5
8
4
7
10

A testinputs/23 => testinputs/23 +1 -0
@@ 0,0 1,1 @@
389125467

A testinputs/24 => testinputs/24 +20 -0
@@ 0,0 1,20 @@
sesenwnenenewseeswwswswwnenewsewsw
neeenesenwnwwswnenewnwwsewnenwseswesw
seswneswswsenwwnwse
nwnwneseeswswnenewneswwnewseswneseene
swweswneswnenwsewnwneneseenw
eesenwseswswnenwswnwnwsewwnwsene
sewnenenenesenwsewnenwwwse
wenwwweseeeweswwwnwwe
wsweesenenewnwwnwsenewsenwwsesesenwne
neeswseenwwswnwswswnw
nenwswwsewswnenenewsenwsenwnesesenew
enewnwewneswsewnwswenweswnenwsenwsw
sweneswneswneneenwnewenewwneswswnese
swwesenesewenwneswnwwneseswwne
enesenwswwswneneswsenwnewswseenwsese
wnwnesenesenenwwnenwsewesewsesesew
nenewswnwewswnenesenwnesewesw
eneswnwswnwsenenwnwnwwseeswneewsenese
neswnwewnwnwseenwseesewsenwsweewe
wseweeenwnesenwwwswnew

A testinputs/25 => testinputs/25 +2 -0
@@ 0,0 1,2 @@
5764801
17807724

A testoutputs/15 => testoutputs/15 +2 -0
@@ 0,0 1,2 @@
436
175594

A testoutputs/16 => testoutputs/16 +2 -0
@@ 0,0 1,2 @@
21
132

A testoutputs/17 => testoutputs/17 +2 -0
@@ 0,0 1,2 @@
112
848

A testoutputs/18 => testoutputs/18 +2 -0
@@ 0,0 1,2 @@
13632
23340

A testoutputs/19 => testoutputs/19 +2 -0
@@ 0,0 1,2 @@
5
10

A testoutputs/20 => testoutputs/20 +2 -0
@@ 0,0 1,2 @@
20899048083289
273

A testoutputs/21 => testoutputs/21 +2 -0
@@ 0,0 1,2 @@
5
mxmxvkd,sqjhc,fvjkl

A testoutputs/22 => testoutputs/22 +2 -0
@@ 0,0 1,2 @@
306
291

A testoutputs/23 => testoutputs/23 +2 -0
@@ 0,0 1,2 @@
67384529
149245887792

A testoutputs/24 => testoutputs/24 +2 -0
@@ 0,0 1,2 @@
10
2208

A testoutputs/25 => testoutputs/25 +1 -0
@@ 0,0 1,1 @@
14897079

M time.c => time.c +9 -2
@@ 97,8 97,15 @@ bool run_day(unsigned day, double *time_ns) {
  /* Open input */
  int inp_fd = open(inp_fn, O_RDONLY);
  if (inp_fd < 0) {
    fprintf(stderr, "Day %02u ERROR: Could not open input file: %s\n", day, strerror(errno));
    abort();
    if (errno == ENOENT) {
      free(exe_fn);
      free(inp_fn);
      return false;
    }
    else {
      fprintf(stderr, "Day %02u ERROR: Could not open input file: %s\n", day, strerror(errno));
      abort();
    }
  }
  /* Open /dev/null */
  int devnull_fd = open("/dev/null", O_WRONLY);