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

part2.c (2161B)

      1#include "allocator.h"
      2#include "aoc.h"
      3#include "dvec_s.h"
      4#include "util.h"
      5
      6#include <assert.h>
      7#include <stddef.h>
      8#include <stdlib.h>
      9
     10size_t
     11imul(size_t a, size_t b, size_t n)
     12{
     13	size_t i, out;
     14
     15	out = 0;
     16	for (i = 0; i < sizeof(size_t) * 8; i++, b <<= 1) {
     17		out = (2 * out) % n;
     18		if (b & (1ULL << 63))
     19			out = (out + a) % n;
     20	}
     21
     22	return out;
     23}
     24
     25size_t
     26ipow(size_t a, size_t b, size_t n)
     27{
     28	size_t i, out;
     29
     30	out = 1;
     31	for (i = 0; i < sizeof(size_t) * 8; i++, b <<= 1) {
     32		out = imul(out, out, n);
     33		if (b & (1ULL << 63))
     34			out = imul(out, a, n);
     35	}
     36
     37	return out;
     38}
     39
     40size_t
     41modinv(size_t a, size_t n)
     42{
     43	return ipow(a, n - 2, n);
     44}
     45
     46void
     47part2(void)
     48{
     49	char line[256];
     50	const char *lpos, *lend;
     51	size_t answer;
     52	size_t count;
     53	size_t times;
     54	size_t target;
     55	ssize_t sval;
     56	size_t mul, off;
     57	size_t _mul, _off;
     58	size_t val;
     59
     60	times = 101741582076661;
     61	count = 119315717514047;
     62	target = 2020;
     63
     64	/* reduce operations to a single multiplication and
     65	 * addition under modulus 'count' */
     66	mul = 1;
     67	off = 0;
     68	lpos = aoc.input;
     69	lend = lpos + aoc.input_size;
     70	while (readtok(line, sizeof(line), '\n', &lpos, lend)) {
     71		if (sscanf(line, "deal with increment %lu", &val) == 1) {
     72			/* multiplication : pos = val * pos */
     73			_mul = val;
     74			_off = 0;
     75		} else if (sscanf(line, "cut %li", &sval) == 1) {
     76			/* addition : pos = pos + val */
     77			_mul = 1;
     78			_off = ((size_t) ((ssize_t) count - sval)) % count;
     79		} else if (!strcmp(line, "deal into new stack")) {
     80			/* invert : pos = - pos + n - 1 */
     81			_mul = count - 1;
     82			_off = count - 1;
     83		} else if (strspn(line, " \n\r\t\v") == strlen(line)) {
     84			continue;
     85		} else {
     86			assert(false);
     87		}
     88		mul = imul(mul, _mul, count);
     89		off = (imul(off, _mul, count) + _off) % count;
     90	}
     91
     92	/* apply multiplication and addition 'times' times.. */
     93	val = (ipow(mul, times, count) + count - 1) % count;
     94	val = imul(val, modinv(mul + count - 1, count), count);
     95	off = imul(off, val, count); /* b' = b * ((a^n - 1) / (a - 1)) */
     96	mul = ipow(mul, times, count); /* a' = a^n */
     97
     98	answer = imul((target + count - off) % count, modinv(mul, count), count);
     99	aoc.answer = aprintf("%lu", answer);
    100	aoc.solution = "73394009116480";
    101}