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
- What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
- Where do I participate?: https://adventofcode.com/
- Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465
You are viewing a single thread.
View all comments 1 point
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;
}
