- 4 Posts
- 82 Comments
Joined 3 years ago
Cake day: June 12th, 2023
You are not logged in. If you use a Fediverse account that is able to follow users, you can follow this user.
1·5 months agoHow would you then distinguish between the situations in these two examples?
...#x -> .###x .#xxx ..... -> .###. .#x#.
My initial attempt on even-odd got me in trouble with the outline, as given, being 1 unit wide, not zero-width. I had to compute normals to find out outline around the tiles. You write “on the line -> outside” but don’t many legal rectangle candidates sit on the edge?
C
Well this one got me stumped for a bit but after a few false starts, lots of debugging and some cleanup I’d say I have a pretty good solution now! The points being tiles rather than zero-width corners was the tricky bit here.
Basic working: it walks through the points, keeping track of normal vectors (the “outside” direction). With those, it generates the zero-width outline around the points, and from there on it’s pretty much old fashioned line intersection checks.
The initial nasty solve took 1.2 seconds on my Raspberry Pi 400, but some optimization (like sorting the edges list) brought that down to 0.08s on the Pi, and 0.02s on my 10-year old PC, and I’m quite happy with the code now.
Code
#include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <inttypes.h> #include <assert.h> #define MIN(a,b) ((a)<(b)?(a):(b)) #define MAX(a,b) ((a)>(b)?(a):(b)) #define LEN(a) (sizeof(a)/sizeof(*(a))) #define MAXP 512 /* * There are two main problems with part 2: * 1. Deciding what is inside and what is outside of the polyline * 2. The points being _tiles_, not zero-width coordinates * * This solution walks the outline and calculates "normals" for each * point, which are angles pointing _out_ of the shape. Those are used * to derrive the outside boundary of the shape, the lines that go * around, not through, the corner tiles. Witth that we can do * more-or-less normal intersection checks. * * Angles are stored as 1/8ths of a circle. */ struct point { int x,y; }; struct edge { int off, lo,hi; }; static struct point pts[MAXP]; static struct edge hedges[MAXP/2]; static struct edge vedges[MAXP/2]; static int norms[MAXP]; static int np, nhe, nve; static int wrapa(int a) { return (a+8)%8; } static int cmp_edges(const void *a, const void *b) { return ((const struct edge *)a)->off - ((const struct edge *)b)->off; } static int line_dir(struct point a, struct point b) { return 4*(a.x>b.x || a.y<b.y) + 2*(a.x!=b.x); } static void calculate_normals(void) { int i, dir1,dir2, angle; int normal; /* relative to the current line */ dir1 = line_dir(pts[np-1], pts[0]); normal = wrapa(dir1 - 2); /* start left, assuming CCW order */ for (i=0; i<np; i++) { dir2 = line_dir(pts[i], pts[i==np-1 ? 0 : i+1]); angle = dir2 == dir1-2 || dir2 == dir1+6 ? -2 : 2; /* the point's normal is diagonal, halfway turned */ norms[i] = wrapa(normal + angle/2); dir1 = dir2; normal = wrapa(normal + angle); } } static void generate_edges(void) { struct point a,b; int i,j; for (i=0; i<np; i++) { a = pts[i]; b = pts[(j = i==np-1 ? 0 : i+1)]; /* shift the line to be _around_ point */ a.x += norms[i]<4; a.y += norms[i]>2 && norms[i]<6; b.x += norms[j]<4; b.y += norms[j]>2 && norms[j]<6; if (a.x == b.x) { assert(nve < (int)LEN(vedges)); vedges[nve].off = a.x; vedges[nve].lo = MIN(a.y, b.y); vedges[nve].hi = MAX(a.y, b.y); nve++; } else if (a.y == b.y) { assert(nhe < (int)LEN(hedges)); hedges[nhe].off = a.y; hedges[nhe].lo = MIN(a.x, b.x); hedges[nhe].hi = MAX(a.x, b.x); nhe++; } else assert(!"diagonal line"); } qsort(hedges, nhe, sizeof(*hedges), cmp_edges); qsort(vedges, nve, sizeof(*vedges), cmp_edges); } static bool rect_inside(struct point a, struct point b) { struct edge *e; int x0,y0,x1,y1; /* * Line intersection of the four rectangle edges against all * the polyline edges, with a caveat: the outline is 1 unit * thick, not zero-width! This is why some of the comparisons * are or-equals. */ x0 = MIN(a.x, b.x); y0 = MIN(a.y, b.y); x1 = MAX(a.x, b.x); y1 = MAX(a.y, b.y); for (e = vedges; e < vedges+nve; e++) { if (e->off <= x0) continue; if (e->off > x1) break; if (y0 >= e->lo && y0 < e->hi) return false; if (y1 >= e->lo && y1 < e->hi) return false; } for (e = hedges; e < hedges+nhe; e++) { if (e->off <= y0) continue; if (e->off > y1) break; if (x0 >= e->lo && x0 < e->hi) return false; if (x1 >= e->lo && x1 < e->hi) return false; } return true; } int main() { int64_t p1=0,p2=0, area, i,j; for (; scanf(" %d,%d", &pts[np].x, &pts[np].y)==2; np++) assert(np+1 < MAXP); assert(np >= 4); calculate_normals(); generate_edges(); for (i=0; i<np-1; i++) for (j=i+1; j<np; j++) { area = (int64_t)(abs(pts[i].x - pts[j].x) + 1) * (int64_t)(abs(pts[i].y - pts[j].y) + 1); if (area > p1) p1 = area; if (area > p2 && rect_inside(pts[i], pts[j])) p2 = area; } printf("09: %"PRIi64" %"PRIi64"\n", p1, p2); }
1·7 months agoI started the Witcher 3 and immediately the world feels like a checklist and for some reason I can’t take Gerald seriously. He looks comical, like a teen’s drawing, and the movement feels completely ungrounded.
- Circut Superstars. I’ll never become good at this but close to finishing it on Amateur
- Diablo 4. I dislike the MMOification and despite Blizzard, but got it with the Xbox so might as we’ll play it. The campaign and monster bashing are fine
- Sound Shapes. Sweet game, taking it one album at a time
- Trials Rising. Cleaning up the Hard tracks and that ain’t no lie
- Dirt 2.0 demo. I’m OK at CMR 2 and 05 but I have no idea how to control my car in this one. It’ll come with time
Don’t tell them about baby powder!
C
Merry Christmas everyone!
Code
#include "common.h" int main(int argc, char **argv) { static char buf[7]; static short h[500][5]; /* heights */ static short iskey[500]; int p1=0, nh=0, i,j,k; if (argc > 1) DISCARD(freopen(argv[1], "r", stdin)); for (nh=0; !feof(stdin) && !ferror(stdin); nh++) { assert(nh < (int)LEN(h)); for (i=0; i<7; i++) { fgets(buf, 7, stdin); if (i==0) iskey[nh] = buf[0] == '#'; for (j=0; j<5; j++) h[nh][j] += buf[j] == '#'; } /* skip empty line */ fgets(buf, 7, stdin); } for (i=0; i<nh; i++) for (j=0; j<nh; j++) if (iskey[i] && !iskey[j]) { for (k=0; k<5 && h[i][k] + h[j][k] <= 7; k++) ; p1 += k == 5; } printf("25: %d\n", p1); return 0; }https://codeberg.org/sjmulder/aoc/src/branch/master/2024/c/day25.c
Made the 1 second challenge with most of it to spare! 😎
$ time bmake bench day01 0:00.00 1912 Kb 0+88 faults day02 0:00.00 1992 Kb 0+91 faults day03 0:00.00 1920 Kb 0+93 faults day04 0:00.00 1912 Kb 0+90 faults day05 0:00.00 2156 Kb 0+91 faults day06 0:00.03 1972 Kb 0+100 faults day07 0:00.06 1892 Kb 0+89 faults day08 0:00.00 1772 Kb 0+87 faults day09 0:00.02 2024 Kb 0+137 faults day10 0:00.00 1876 Kb 0+87 faults day11 0:00.00 6924 Kb 0+3412 faults day12 0:00.00 1952 Kb 0+103 faults day13 0:00.00 1908 Kb 0+88 faults day14 0:00.05 1944 Kb 0+92 faults day15 0:00.00 2040 Kb 0+89 faults day16 0:00.03 2020 Kb 0+250 faults day17 0:00.00 1896 Kb 0+88 faults day18 0:00.00 1952 Kb 0+107 faults day19 0:00.01 1904 Kb 0+91 faults day20 0:00.01 2672 Kb 0+325 faults day21 0:00.00 1804 Kb 0+86 faults day22 0:00.03 2528 Kb 0+371 faults day23 0:00.02 2064 Kb 0+152 faults day24 0:00.00 1844 Kb 0+89 faults day25 0:00.00 1788 Kb 0+89 faults real 0m0,359s
Oh my Kernigan, that was stressful. Really worried about not finishing there.
Considered several approaches, the coolest of which would have been to test individual bits, propagate ‘suspicion’, etc, but it seemed too tricky.
Eventually I needed to go do something other than worry about not finishing so I started writing a validator for the adder structure. Just a couple of rules later I had found 4 faults already and managed to write automated fixups for them!
This means my solver is quite specific to my input but it can potentially be made more complete and I didn’t ‘cheat’ by hardcoding manual graph analysis.
Code
#include "common.h" /* * The approach behind part 2 was to essentially write a bunch of * validation rules for the structure of the adder, and then writing * fixups for problems it would find. That means it's likely quite * tailored to my input, but at least it's not hardcoding manual graph * analysis. */ enum { W_NULL, W_OFF, W_ON }; struct wire; struct wire { struct wire *in[2]; char name[4]; char op; /* [A]ND, [O]R, [X]OR */ int8_t val; /* W_NULL, W_OFF, W_ON */ }; static struct wire wires[320]; static struct wire *zs[46], *swapped[8]; static int nw, nsw; static struct wire * get_wire(const char *name) { int i; for (i=0; i<nw; i++) if (!strcmp(name, wires[i].name)) return &wires[i]; assert(nw < (int)LEN(wires)); assert(strlen(name) < LEN(wires[i].name)); snprintf(wires[nw].name, sizeof(wires[nw].name), "%s", name); return &wires[nw++]; } static int cmp_wires(const void *a, const void *b) { struct wire * const *wa = a; struct wire * const *wb = b; return strcmp((*wa)->name, (*wb)->name); } static int eval(struct wire *wire) { int in1,in2; if (wire->val) return wire->val == W_ON; assert(wire->in[0]); assert(wire->in[1]); in1 = eval(wire->in[0]); in2 = eval(wire->in[1]); wire->val = W_OFF + ( wire->op=='A' ? in1 && in2 : wire->op=='O' ? in1 || in2 : wire->op=='X' ? in1 != in2 : (assert(!"bad op"), -1)); return wire->val == W_ON; } static void swap(struct wire *a, struct wire *b) { struct wire tmp; //printf("swapping %s and %s\n", a->name, b->name); tmp = *a; a->op = b->op; a->in[0] = b->in[0]; a->in[1] = b->in[1]; b->op = tmp.op; b->in[0] = tmp.in[0]; b->in[1] = tmp.in[1]; assert(nsw+2 <= (int)LEN(swapped)); swapped[nsw++] = a; swapped[nsw++] = b; } static struct wire * find_z_xor(int bit) { struct wire *xy_xor; int i; for (i=0; i<nw; i++) { /* must be a XOR */ if (wires[i].op != 'X') continue; /* with an input XOR */ xy_xor = wires[i].in[0]->op == 'X' ? wires[i].in[0] : wires[i].in[1]->op == 'X' ? wires[i].in[1] : NULL; if (!xy_xor) continue; /* connected to the X and Y */ if (xy_xor->in[0]->name[0] != 'x' && xy_xor->in[0]->name[0] != 'y') continue; /* with the same bit number */ if (atoi(xy_xor->in[0]->name+1) != bit) continue; return &wires[i]; } return NULL; } static struct wire * find_xy_and(int bit) { int i; for (i=0; i<nw; i++) { /* must be AND */ if (wires[i].op != 'A') continue; /* must have XY inputs */ if ((wires[i].in[0]->name[0] != 'x' || wires[i].in[1]->name[0] != 'y') && (wires[i].in[0]->name[0] != 'y' || wires[i].in[1]->name[0] != 'x')) continue; /* with the right bit number */ if (atoi(wires[i].in[0]->name+1) != bit || atoi(wires[i].in[0]->name+1) != bit) continue; return &wires[i]; } return NULL; } static void fsck_carry_or(struct wire *or, int bit) { struct wire *wire; int i; /* both inputs must be AND; no fixup if neither */ assert( or->in[0]->op == 'A' || or->in[1]->op == 'A'); for (i=0; i<2; i++) { if (or->in[i]->op == 'A') continue; //printf("carry OR parent %s not AND\n", or->in[i]->name); /* only have fixup for the XY AND */ assert( or->in[!i]->in[0]->name[0] != 'x' && or->in[!i]->in[0]->name[0] != 'y'); wire = find_xy_and(bit); assert(wire); swap(or->in[i], wire); } } static void fsck_z(struct wire *z) { struct wire *wire, *carry_or; int bit; assert(z->name[0] == 'z'); bit = atoi(z->name+1); /* first bit is very different */ if (!bit) return; /* for the final bit, Z is the carry OR */ if (!zs[bit+1]) { /* no fixup if it isn't */ assert(z->op == 'O'); fsck_carry_or(z, bit-1); return; } /* must be a XOR */ if (z->op != 'X') { //printf("Z %s isn't XOR\n", z->name); wire = find_z_xor(bit); assert(wire); swap(z, wire); } /* bit 2 and up must have a carry OR */ if (bit > 1) { carry_or = z->in[0]->op == 'O' ? z->in[0] : z->in[1]->op == 'O' ? z->in[1] : NULL; assert(carry_or); fsck_carry_or(carry_or, bit-1); } } int main(int argc, char **argv) { struct wire *wire; char buf[64], *rest, *lf, *name1,*name2, *opstr; uint64_t p1=0; int bit, i; if (argc > 1) DISCARD(freopen(argv[1], "r", stdin)); while ((rest = fgets(buf, sizeof(buf), stdin))) { if (!strchr(buf, ':')) break; wire = get_wire(strsep(&rest, ":")); wire->val = W_OFF + atoi(rest); } while ((rest = fgets(buf, sizeof(buf), stdin))) { if ((lf = strchr(buf, '\n'))) *lf = '\0'; name1 = strsep(&rest, " "); opstr = strsep(&rest, " "); name2 = strsep(&rest, " "); strsep(&rest, " "); wire = get_wire(rest); wire->in[0] = get_wire(name1); wire->in[1] = get_wire(name2); wire->op = opstr[0]; } for (i=0; i<nw; i++) if (wires[i].name[0] == 'z') { bit = atoi(&wires[i].name[1]); assert(bit >= 0); assert(bit < (int)LEN(zs)); zs[bit] = &wires[i]; } for (i=0; i < (int)LEN(zs); i++) if (zs[i]) p1 |= (uint64_t)eval(zs[i]) << i; for (i=0; i < (int)LEN(zs); i++) if (zs[i]) fsck_z(zs[i]); qsort(swapped, nsw, sizeof(*swapped), cmp_wires); printf("24: %"PRIu64, p1); for (i=0; i<nsw; i++) printf(i ? ",%s" : " %s", swapped[i]->name); putchar('\n'); return 0; }https://codeberg.org/sjmulder/aoc/src/branch/master/2024/c/day24.c
Btw, spending some time on getting Graphviz output right did make studying the structure much easier!
C
Really proud of this one! Started with with an O(n^atoms in the universe) scan which took 44s even after adding a dedup check.
But iterating on a trick to encode the deltas for the dedup check, using it to build a mapping table here, a lookup there etc brought it down to a very fast, fairly low memory, linear complexity solution!
Code
#include "common.h" #define STEPS 2000 #define NCODES (19*19*19*19) int main(int argc, char **argv) { static int8_t prices[STEPS]; static int8_t by_deltas[NCODES]; static int sums[NCODES]; uint64_t p1=0, secret; int p2=0, i; if (argc > 1) DISCARD(freopen(argv[1], "r", stdin)); while (scanf(" %"SCNu64, &secret) == 1) { memset(by_deltas, 0, sizeof(by_deltas)); for (i=0; i<STEPS; i++) { secret = (secret ^ secret << 6) & 0xFFFFFF; secret = (secret ^ secret >> 5); secret = (secret ^ secret << 11) & 0xFFFFFF; prices[i] = secret % 10; } /* * Build a deltas->price map for the buyer. Deltas are * encoded as an integer for easy indexing. Iterating * backwards ensures the stored price is the _earliest_ * occurence of that sequence. */ for (i=STEPS-1; i>=4; i--) by_deltas[ (prices[i-3] - prices[i-4] +9) *19*19*19 + (prices[i-2] - prices[i-3] +9) *19*19 + (prices[i-1] - prices[i-2] +9) *19 + (prices[i] - prices[i-1] +9) ] = prices[i]; for (i=0; i<NCODES; i++) sums[i] += by_deltas[i]; p1 += secret; } for (i=0; i<NCODES; i++) p2 = MAX(p2, sums[i]); printf("22: %"PRIu64" %d\n", p1, p2); return 0; }day22 0m00.04s realhttps://codeberg.org/sjmulder/aoc/src/branch/master/2024/c/day22.c
C
Graph problems are not my cake but this one I could work out: recursively iterate unique combination of adjacent nodes. Performance benefits from using a basic, int-indexed adjacency matrix.
Fast enough on my 2015 PC:
day23 0:00.05 1644 Kb 0+143 faultsCode
#include "common.h" #define VZ 520 /* max no. vertices */ #define SZ 32 /* max set size */ static char names[VZ][3]; static char adj[VZ][VZ]; static int nvert; static int to_id(const char *name) { int i; for (i=0; i<nvert; i++) if (!strcmp(name, names[i])) return i; assert(nvert < VZ); assert(strlen(name) < LEN(*names)); snprintf(names[nvert++], sizeof(*names), "%s", name); return i; } static int cmp_id(const void *a, const void *b) { return strcmp(names[*(int*)a], names[*(int*)b]); } /* * Construct all unique combinations of nodes, with every extension, * confirm they're all connected. Essentally this but recursive: * * for (a=0; a<nvert; a++) * for (b=a+1; b<nvert; b++) * for (c=b+1; c<nvert; c++) * ... * * Note the inner loops continue forward from the point of the outside * loop, avoiding duplicate combinations. * * 'set' and 'best' are arrays of size SZ, length 'sz' and 'bz'. 'set' * is the current working state; 'best' is a copy of the longest known * set. */ static int max_set(int *set, int sz, int *best, int bz) { int bz1, v,i; assert(sz < SZ); /* for each potential candidate */ for (v = sz ? set[sz-1]+1 : 0; v < nvert; v++) { /* adjacent to all in current set? */ for (i=0; i<sz && adj[set[i]][v]; i++) ; if (i != sz) continue; /* recur and update 'best size' if needed */ set[sz] = v; if (bz < (bz1 = max_set(set, sz+1, best, bz))) bz = bz1; } /* store longest known set in 'best' */ if (sz > bz) memcpy(best, set, (bz = sz) * sizeof(*best)); return bz; } int main(int argc, char **argv) { static int set[SZ], best[SZ]; char buf[8]; int p1=0, a,b,c, i, bz; if (argc > 1) DISCARD(freopen(argv[1], "r", stdin)); while (fgets(buf, sizeof(buf), stdin)) { assert(strlen(buf) >= 5); buf[2] = buf[5] = '\0'; a = to_id(buf); b = to_id(buf+3); adj[a][b] = adj[b][a] = 1; } for (a=0; a<nvert; a++) for (b=a+1; b<nvert; b++) for (c=b+1; c<nvert; c++) p1 += adj[a][b] && adj[a][c] && adj[b][c] && ( names[a][0] == 't' || names[b][0] == 't' || names[c][0] == 't'); printf("23: %d ", p1); bz = max_set(set, 0, best, 0); qsort(best, bz, sizeof(*best), cmp_id); for (i=0; i<bz; i++) printf(i ? ",%s" : "%s", names[best[i]]); putchar('\n'); return 0; }https://codeberg.org/sjmulder/aoc/src/branch/master/2024/c/day23.c
Finally got this one done very late last night!
I kept getting stuck reasoning about the recursion here. For some reason I got myself convinced that after a move, the state of the ‘upper’ dpads could make it more advantageous to pick one followup move over another - i.e. steps aren’t independent.
It took a bunch of manually working through sequences to convince myself that, after every move, every dpad above it would be on A. With that, it’s ‘just’ recursive pathfinding for independent moves.
Since there are relatively few types of moves needed on the dpad, I just sketched them out and wrote the routes in code directly (up to two options per move, e.g. left,up or up,left).
Code
#include "common.h" static int64_t dpmem[26][8][2]; enum {NW,NN,NE,EE,SE,SS,SW,WW}; /* * We can sufficiently describe npad/dpad movements as: "move N x, N y, * then press A N times" (a 'move'). It's never faster to take a detour. * After pressing A on one dpad, dpads on all levels above will also be * on A, so these moves can be considered in isolation. * * This function gives the cost of executing a move with the dpad in * direction 'd' at level 'l', excluding the A presses for actually * tapping the selected directions, but including returning the cursor * back to the A button. * * E.g., moving 2 up and 3 left (NW), the steps could be <AAv<AAA>>^. * Excluding the A presses, that's 6 steps. Pulling out the A presses * lets us drop the dx and dy arguments and simplify the memoization. * They're easily calculated: it's |dx|+|dy|. * * The gaps present a problem: picking the lowest-cost option (e.g. * left-then-up vs. up-then-left) may cause us to cross a gap. The * "mind the gap" argument 'mtg' must be set to 1 if-and-only-if there * is such potential, e.g. a move from < to ^ on the dpad (up,right * crosses the gap) or a move from A to 1 on the npad (left,up crosses * the gap). With the flag set, these orderings will be avoided. */ static int64_t dp(int d, int mtg, int l) { int64_t ret, alt=INT64_MAX; if (l<=0) return 0; assert(l >= 0); assert(l < (int)LEN(dpmem)); assert(mtg==0 || mtg==1); if ((ret = dpmem[l][d][mtg])) return ret; /* routes avoiding gaps where necessary */ ret = d==SE ? 1+dp(SS,0,l-1) + 1+dp(WW,0,l-1) + 2+dp(SE,0,l-1) : d==SW ? 2+dp(SW,0,l-1) + 1+dp(WW,0,l-1) + 3+dp(NE,1,l-1) : d==SS ? 2+dp(SW,0,l-1) + 2+dp(NE,0,l-1) : d==NE ? 1+dp(SS,0,l-1) + 2+dp(NW,0,l-1) + 1+dp(EE,0,l-1) : d==NW ? 1+dp(WW,0,l-1) + 2+dp(SW,1,l-1) + 3+dp(NE,1,l-1) : d==NN ? 1+dp(WW,0,l-1) + 1+dp(EE,0,l-1) : d==EE ? 1+dp(SS,0,l-1) + 1+dp(NN,0,l-1) : d==WW ? 3+dp(SW,1,l-1) + 3+dp(NE,1,l-1) : (assert(!"bad dir"), -1); /* alternatives crossing the gaps */ alt = mtg ? INT64_MAX : d==SE ? 2+dp(SW,0,l-1) + 1+dp(EE,0,l-1) + 1+dp(NN,0,l-1) : d==SW ? 3+dp(SW,1,l-1) + 1+dp(EE,0,l-1) + 2+dp(NE,0,l-1) : d==NE ? 1+dp(WW,0,l-1) + 2+dp(SE,0,l-1) + 1+dp(NN,0,l-1) : d==NW ? 3+dp(SW,1,l-1) + 2+dp(NE,1,l-1) + 1+dp(EE,0,l-1) : INT64_MAX; return dpmem[l][d][mtg] = MIN(ret, alt); } static int64_t npcost(const char *s, int lv) { int64_t cost=0; int x=2,y=3, x1,y1, mtg, dir; for (; *s == 'A' || (*s >= '0' && *s <= '9'); s++) { x1 = *s=='A' ? 2 : *s=='0' ? 1 : 2-(9-*s+'0') % 3; y1 = *s=='A' ? 3 : *s=='0' ? 3 : (9-*s+'0') / 3; /* potentially crossing a gap? */ mtg = (x==0 && y1==3) || (x1==0 && y==3); dir = y1>y ? (x1>x ? SE : x1<x ? SW : SS) : y1<y ? (x1>x ? NE : x1<x ? NW : NN) : (x1>x ? EE : x1<x ? WW : 0); cost += dp(dir, mtg, lv) + abs(x1-x) + abs(y1-y) +1; x = x1; y = y1; } return cost; } int main(int argc, char **argv) { char buf[8]; int digits; int64_t p1=0,p2=0; if (argc > 1) DISCARD(freopen(argv[1], "r", stdin)); while (fgets(buf, sizeof(buf), stdin)) { digits = atoi(buf); p1 += digits * npcost(buf, 2); p2 += digits * npcost(buf, 25); } printf("21: %"PRId64" %"PRId64"\n", p1, p2); return 0; }https://codeberg.org/sjmulder/aoc/src/branch/master/2024/c/day21.c
C
Note to self: reread the puzzle after waking up properly! I initially wrote a great solution for the wrong question (pathfinding with a given number of allowed jumps).
For the actual question, a bit boring but flood fill plus some array iteration saved the day again. Find the cost for every open tile with flood fill, then for each position and offset combination, see if that jump yields a lower cost at the destination.
For arbitrary inputs this would require eliminating the non-optimal paths, but the one path covered all open tiles.
Code
#include "common.h" #define GB 2 /* safety border on X/Y plane */ #define GZ (GB+141+2+GB) static char G[GZ][GZ]; /* grid */ static int C[GZ][GZ]; /* costs */ static int sx,sy, ex,ey; /* start, end pos */ static void flood(int x, int y) { int lo = INT_MAX; if (x<1 || x>=GZ-1 || y<1 || y>=GZ-1 || G[y][x]!='.') return; if (C[y-1][x]) lo = MIN(lo, C[y-1][x]+1); if (C[y+1][x]) lo = MIN(lo, C[y+1][x]+1); if (C[y][x-1]) lo = MIN(lo, C[y][x-1]+1); if (C[y][x+1]) lo = MIN(lo, C[y][x+1]+1); if (lo != INT_MAX && (!C[y][x] || lo < C[y][x])) { C[y][x] = lo; flood(x, y-1); flood(x-1, y); flood(x, y+1); flood(x+1, y); } } static int count_shortcuts(int lim, int min) { int acc=0, x,y, dx,dy; for (y=GB; y<GZ-GB; y++) for (x=GB; x<GZ-GB; x++) for (dy = -lim; dy <= lim; dy++) for (dx = abs(dy)-lim; dx <= lim-abs(dy); dx++) acc += x+dx >= 0 && x+dx < GZ && y+dy >= 0 && y+dy < GZ && C[y][x] && C[y][x]+abs(dx)+abs(dy) <= C[y+dy][x+dx]-min; return acc; } int main(int argc, char **argv) { int x,y; if (argc > 1) DISCARD(freopen(argv[1], "r", stdin)); for (y=2; fgets(G[y]+GB, GZ-GB*2, stdin); y++) assert(y < GZ-3); for (y=GB; y<GZ-GB; y++) for (x=GB; x<GZ-GB; x++) if (G[y][x] == 'S') { G[y][x]='.'; sx=x; sy=y; } else if (G[y][x] == 'E') { G[y][x]='.'; ex=x; ey=y; } C[sy][sx] = 1; flood(sx, sy-1); flood(sx-1, sy); flood(sx, sy+1); flood(sx+1, sy); printf("20: %d %d\n", count_shortcuts(2, 100), count_shortcuts(20, 100)); return 0; }https://codeberg.org/sjmulder/aoc/src/branch/master/2024/c/day20.c
Certainly more generic and less prone to user error too. Indeed dealing with hash maps or any advanced data structure is a pain with C, this is where generics or templates really shine, especially if you have control over lifetime aspects as you do with C++ or Rust (e.g. moves, lvalue references, constness, etc).
I think I saw the same! At first I thought it requires pathfinding to see what nodes are connected to the wall, but then someone pointed at disjoint sets and just a glance at Wikipedia made it click right away. What an ingeniously simple but useful data structure! Maybe I’ll reimplement my solution with that - mostly as an exercise for disjoint sets and finding a convenient representation for that in C.
That does mean that if two or more strings end with the same substring, you’d recalculate those substrings?
I hadn’t really considered that, but yes. I’m inclined to think that replacing hash table lookups with plain array indexing (which this allows) outweighs that downside but I’m not sure. Indeed 120ms is pretty damn fast!
Lovely! This is nicer than my memoized recursion. DP remains hard to wrap my head around even though I often apply it by accident.
until I tried matching from right to left instead :3
My intuition nudged me there but I couldn’t reason how that would change things. You still have to test the remaining string, and its remaining string, backtrack, etc right?
I don’t know much about Rust but I assume the
HashMap<String, i64>requires hashing on insertion and lookup, right? I realized that, for every design, all the strings you’ll see are substrings of that design from different starting positions, so I made my lookup tableint pos -> int count. The table is reset after every design.
Luckily the .exe’s MZ header is pretty small. But in this case it was necessary: when DOS loads a .com binary, it can’t know how much memory it will need, so DOS just gives it all free memory. But then the program can’t launch another, because all memory is in use. So that’s why I had to add the MZ header which allows specifying the memory needs.