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
    link
    15 hours 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