Day 11: Plutonian Pebbles

Megathread guidelines

  • Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
  • You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL

FAQ

  • sjmulder@lemmy.sdf.org
    1·
    16 days ago

    C

    Started out a bit sad that this problem really seemed to call for hash tables - either for storing counts for an iterative approach, or to memoize a recursive one.

    Worried that the iterative approach would have me doing problematic O(n^2) array scans I went with recursion and a plan to memoize only the first N integers in a flat array, expecting low integers to be much more frequent (and dense) than higher ones.

    After making an embarrassing amount of mistakes it worked out beautifully with N=1m (testing revealed that to be about optimal). Also applied some tail recursion shortcuts where possible.

    day11  0:00.01  6660 Kb  0+1925 faults
    Code 
    #include "common.h"

/* returns 1 and splits x if even-digited, 0 otherwise */
static int
split(uint64_t x, uint64_t *a, uint64_t *b)
{
	uint64_t p;
	int n, i;

	if (!x) return 0;
	for (n=0, p=1; p<=x;  n++, p*=10) ; if (n%2) return 0;
	for (i=0, p=1; i<n/2; i++, p*=10) ;
	*a = x/p;
	*b = x%p; return 1;
}

/*
 * recur() is memoized in mem[]. Testing found the size MEMZ to be optimal:
 * lowering siginificantly reduced hits, but raising tenfold didn't add a
 * single hit.
 */

#define MEMZ (1024*1024)
static uint64_t mem[MEMZ][76];

static uint64_t
recur(uint64_t v, int n)
{
	uint64_t a,b;

	if (n<1 ) return 1;
	if (v==0) return recur(1, n-1);
	if (v<10) return recur(v*2024, n-1);
	if (v<MEMZ && mem[v][n]) return mem[v][n];
	if (!split(v, &a, &b))   return recur(v*2024, n-1);

	return v<MEMZ ? mem[v][n] =
	    recur(a, n-1) + recur(b, n-1) :
	    recur(a, n-1) + recur(b, n-1);
}

int
main(int argc, char **argv)
{
	uint64_t p1=0,p2=0, val;

	if (argc > 1)
		DISCARD(freopen(argv[1], "r", stdin));

	while (scanf(" %"SCNu64, &val) == 1) {
		p1 += recur(val, 25);
		p2 += recur(val, 75);
	}

	printf("10: %"PRId64" %"PRId64"\n", p1, p2);
	return 0;
}

    https://github.com/sjmulder/aoc/blob/master/2024/c/day11.c