aoc-2019-c

Advent of Code 2019 Solutions in C
git clone https://git.sinitax.com/sinitax/aoc-2019-c
Log | Files | Refs | README | sfeed.txt

main.c (3367B)

      1#include "aoc.h"
      2#include "allocator.h"
      3#include "util.h"
      4#include "dvec_s.h"
      5
      6#include <assert.h>
      7#include <string.h>
      8#include <stdio.h>
      9
     10static const int freq[] = { 0, 1, 0, -1 };
     11
     12void
     13parse_input(struct dvec *phases)
     14{
     15	const char *c, *sep;
     16	int *val;
     17
     18	sep = strchr(aoc.input, '\n');
     19	assert(sep != NULL);
     20
     21	for (c = aoc.input; c < sep; c++) {
     22		val = dvec_add_slot(phases);
     23		*val = *c - '0';
     24	}
     25}
     26
     27void
     28fft(struct dvec *phases, size_t rounds)
     29{
     30	struct dvec copy;
     31	size_t r, i, k, l;
     32	ssize_t sum;
     33	int digit;
     34	int *val;
     35
     36	dvec_init(&copy, sizeof(int), 0, &stdlib_strict_heap_allocator);
     37
     38	for (r = 0; r < rounds; r++) {
     39		dvec_copy(&copy, phases);
     40
     41		for (i = 0; i < copy.len; i++) {
     42			sum = 0;
     43			for (k = 0; k < copy.len; k++) {
     44				l = (k + 1) / (i + 1);
     45				digit = *(int *)dvec_at(&copy, k);
     46				sum += freq[l % 4] * digit;
     47			}
     48			sum = ABS(sum) % 10;
     49			val = dvec_at(phases, i);
     50			*val = (int) sum;
     51		}
     52	}
     53
     54	dvec_deinit(&copy);
     55}
     56
     57void
     58fft_dup(struct dvec *phases, size_t offset, size_t rounds, size_t dup)
     59{
     60	size_t r, i, len, lutlen;
     61	int *lut, *lutc, *lutp;
     62	int digit, *slot;
     63
     64	/*   |    a           b    c
     65	 * --+------------------------
     66	 * 1 |  a+b+c        b+c   c
     67	 * 2 | a+2b+3c       b+2c  c
     68	 * n |a+nb+n(n+1)/2c b+nc  c
     69	 *
     70	 * a+sum(1)b+sum(sum(1))c .. not nice
     71	 *
     72	 * sum(1): n
     73	 * sum(sum(1)): n(n+1)/2
     74	 * sum(sum(sum(1))): (K2+K1)/2 = (n^2+n)/2 + (n^3-n)/6
     75	 *
     76	 * .. calculation possible but not practically feasible since we
     77	 * would have to do 10000..th sum() .. will have to use a lookup table
     78	 */
     79
     80	len = phases->len * dup;
     81	assert(offset >= len / 2 && offset < len);
     82
     83	lutlen = len - offset;
     84	lut = malloc(lutlen * sizeof(int) * (rounds + 1));
     85	assert(lut != NULL);
     86
     87	/* top row */
     88	for (i = 0; i < lutlen; i++) {
     89		digit = *(int *)dvec_at(phases, (i + offset) % phases->len);
     90		lut[i] = digit;
     91	}
     92
     93	/* right column */
     94	digit = *(int *)dvec_at(phases, (len - 1) % phases->len);
     95	for (r = 0; r < rounds; r++) {
     96		lut[(r + 1) * lutlen + lutlen - 1] = digit;
     97	}
     98
     99	for (r = 0; r < rounds; r++) {
    100		lutp = &lut[r * lutlen + lutlen - 2];
    101		lutc = &lut[(r + 1) * lutlen + lutlen - 2];
    102		for (i = 1; i < lutlen; i++, lutp--, lutc--)
    103			lutc[0] = (lutp[0] + lutc[1]) % 10;
    104	}
    105
    106	dvec_clear(phases);
    107	for (i = 0; i < 8; i++) {
    108		slot = dvec_add_slot(phases);
    109		*slot = lut[rounds * lutlen + i];
    110	}
    111
    112	free(lut);
    113}
    114
    115void
    116part1(void)
    117{
    118	struct dvec phases;
    119	char *answer;
    120	size_t i;
    121	int digit;
    122
    123	dvec_init(&phases, sizeof(int), 64, &stdlib_strict_heap_allocator);
    124
    125	parse_input(&phases);
    126
    127	fft(&phases, 100);
    128
    129	answer = malloc(9);
    130	for (i = 0; i < 8; i++) {
    131		digit = *(int *)dvec_at(&phases, i);
    132		answer[i] = '0' + (char) digit;
    133	}
    134	answer[i] = 0;
    135
    136	aoc.answer = answer;
    137	aoc.solution = "29956495";
    138
    139	dvec_deinit(&phases);
    140}
    141
    142void
    143part2(void)
    144{
    145	struct dvec phases;
    146	char *answer;
    147	int digit;
    148	size_t offset;
    149	size_t base;
    150	size_t i;
    151
    152	dvec_init(&phases, sizeof(int), 64, &stdlib_strict_heap_allocator);
    153
    154	parse_input(&phases);
    155
    156	base = 1;
    157	offset = 0;
    158	for (i = 0; i < 7; i++) {
    159		digit = *(int *)dvec_at(&phases, 6 - i);
    160		offset += base * (size_t) digit;
    161		base *= 10;
    162	}
    163
    164	fft_dup(&phases, offset, 100, 10000);
    165
    166	answer = malloc(9);
    167	for (i = 0; i < 8; i++) {
    168		digit = *(int *)dvec_at(&phases, i);
    169		answer[i] = '0' + (char) digit;
    170	}
    171	answer[i] = 0;
    172
    173	aoc.answer = answer;
    174	aoc.solution = "73556504";
    175
    176	dvec_deinit(&phases);
    177}