Advent of Code 2019 Day 16 Part 2 in under 15 μs

day16p2.cpp

#include <cstdio>
#include <cstdint>
#include <cstdio>
#include <vector>
#include <chrono>

int main(int argc, char **argv) {
	FILE *fp;
	if (argc < 2 || !(fp = fopen(argv[1], "r"))) fp = stdin;

	// Optimized for 650-digit inputs
	constexpr int N = 650;

	auto t0 = std::chrono::steady_clock::now();

	// Read the input, convert to digits
	std::vector<int8_t> V(N);
	fread(&V[0], N, 1, fp);
	for (auto &n : V) n -= '0';

	// Read the offset
	int offset = 0;
	for (int i = 0; i < 7; i++) {
		offset = 10 * offset + V[i];
	}

	// Compute the length of the tail end of the expanded list
	int tail = 10000 * N - offset;

	int part2 = 0;

	for (int d = 0, base = offset % N; d < 8; d++) {
		int sum = 0, tmp, todo, skip;

		constexpr int TWO_CYCLES = 325 * 128 * 2;
		constexpr int FIVE_CYCLES = 26 * 125 * 5;

		// mod 2 (0, 4, ..., 28 mod 128)
		for (int k = 0; k < 32; k += 4) {
			todo = tail - d + k;
			skip = todo / TWO_CYCLES * TWO_CYCLES;
			for (int i = d + k + skip, idx = base + k; i < tail; i += 128, idx += 128) {
				idx -= N & -(idx >= N);
				sum ^= V[idx];
			}
		}
		sum = (sum % 2) * 5;

		// mod 5 (0 mod 125)
		todo = tail - (d + 0);
		skip = todo / FIVE_CYCLES * FIVE_CYCLES;
		tmp = 0;
		for (int i = d + skip, idx = base; i < tail; i += 125, idx += 125) {
			idx -= N & -(idx >= N);
			tmp += V[idx];
		}
		sum += 6 * tmp;

		// mod 5 (25 mod 125)
		todo = tail - (d + 25);
		skip = todo / FIVE_CYCLES * FIVE_CYCLES;
		tmp = 0;
		for (int i = d + 25 + skip, idx = base + 25; i < tail; i += 125, idx += 125) {
			idx -= N & -(idx >= N);
			tmp += V[idx];
		}
		sum += 4 * tmp;

		part2 = 10 * part2 + (sum % 10);

		base++;
		base &= -(base < N);
	}

	auto elapsed = std::chrono::steady_clock::now() - t0;
	auto ns = std::chrono::duration_cast<std::chrono::nanoseconds>(elapsed).count();

	printf("%08d\n", part2);
	fprintf(stderr, "%ld nanoseconds\n", ns);

	return 0;
}