Advent of code 2022 epic häx

README.md

Advent of code 2022 epic häx

Zouppen is not trying to solve 'em all but just show some epic overoptimized stuff.

day06.c

// Streaming and O(n) algorithm for finding the preamble positions in
// https://adventofcode.com/2022/day/6

#include <stdio.h>
#include <stdint.h>
#include <strings.h>
#include <stdbool.h>

int main(int argc, char **argv)
{
	// How long the preamble is
	int const preamble_len = 4;

	// Using a rolling histogram for preamble_len items.
	uint8_t histogram[256];

	// Histogram is initially all zeros.
	bzero(histogram, sizeof(histogram)*sizeof(*histogram));

	// In addition, we are using a ring buffer for the incoming
	// bytes so we can work without memory-mapping the input. Ring
	// buffer doesn't need emptying since we prepopulate it in the
	// finst step.
	char ringbuf[preamble_len];

	// Pointer in the ring buffer starts from the last item
	char *ring_p = ringbuf + preamble_len - 1;

	// To avoid ever iterating the histogram, we use a counter
	// holding number of histogram fields holding value which is
	// larger than 1.
	int duplicates = 0;

	// Prefill is the stage where items are inserted to the ring
	// buffer but none are yet popped out yet.
	int prefill = preamble_len-1;

	// This value is for humans only. Add desired offset here if
	// you want to count differently..
	int pos = 0;

	// Looping through the input
	while (true) {
		// Get the next item, if any. Stop also on newline.
		int c = getchar();
		if (c == EOF || c == '\n') {
			printf("No preamble found, read %d bytes.\n", pos);
			return 1;
		}
		pos++;

		// Insert the item to the ring buffer, overwriting the
		// oldest item.
		*ring_p = c;

		// Insert to the histogram. If histogram value after
		// insertion goes above 1, there is one duplicate
		// more.
		uint8_t after_insert = ++histogram[c];
		if (after_insert == 2) {
			duplicates++;
		}

		// Advance ring pointer, rolling it over if necessary.
		if (ringbuf == ring_p--) {
			ring_p += preamble_len;
		}

		if (prefill) {
			// Skip rest of the loop until we have
			// prefilled the ring buffer and histogram.
			prefill--;
			continue;
		}

		// Check if we have any counts larger than 1
		if (!duplicates) {
			break;
		}

		// Now we remove the oldest item from the
		// histogram. If the count goes below 2, there is one
		// duplicate less.
		uint8_t after_remove = --histogram[(int)*ring_p];
		if (after_remove == 1) {
			duplicates--;
		}
	}

	// We found it! Since the preamble is in the ring buffer and
	// the ring buffer is running from right to left, we need to
	// reconstruct the string in a delicate fashion. If we want
	// only the position, we can just drop the pointer magic.
	printf("Preamble found at %d: ", pos);
	for (int i=0; i<preamble_len; i++) {
		char *p = ring_p - i;
		if (p < ringbuf) {
			p += preamble_len;
		}
		putchar(*p);
	}
	putchar('\n');

	return 0;
}