I live in a small city of about 90k and I love it. We have the important amnesties, eg shopping and a hospital, but in a few minutes you’re out in the open fields. Meanwhile buses to nearby large city depart every 6 to 30 min from my street.
Guy:innen
“I want to thank every Amazon employee and every Amazon customer, 'cause you guys paid for all this. So seriously, for every Amazon customer out there, and every Amazon employee, thank you from the bottom of my heart, very much. It’s very appreciated.”
~ Jeff Bezos, July 2021, as he departs for space tourism
Two of my favourite tools!
Part 1 was fun, essentially a matter of mapping a grid and implementing a function to scan above and below bricks.
Was worried part 2 would either make the grid approach impossible (large numbers) or have combinatory complexity that would necessitate some super efficient dependency table that I don’t know about. Luckily that wasn’t the case! Phew.
Fun and interesting puzzle! In part 1 I fumbled a bit trying to implement even/odd outside/inside tracking before realizing that wouldn’t work for this shape and just did the flood fill.
For part 2 I correctly guessed that like the intersecting cuboids (2021 day 22) it would be about finding a better representation for the grid or avoiding representing it entirely. Long story shorter:
/*
* Conceptually: the raw map, which is too large to fit directly in
* memory for part 2, is made much smaller by collapsing (and counting)
* identical rows and columns. Another way to look it at is that a grid
* is fitted to make 'opaque' cells.
* | |#|##|#
* For example: -+---+-+--+-
* #|###|#| |#
* #### ### 1 -+---+-+--+-
* ##### # ### # 1 #| | | |#
* # # becomes # # 2 or: #| | | |#
* # # ##### 1 -+---+-+--+-
* ######## 13121 #|###|#|##|#
*
* To avoid a lot of complex work, instead of actually collapsing and
* splitting rows and columns, we first generate the wall rectangles and
* collect the unique X and Y coordinates. Those are locations of our
* virtual grid lines.
*/
Despite being quite happy with this solution, I couldn’t help but notice the brevity and simplicity of the other solutions here. Gonna have a look what’s happening there and see if I can try that approach too.
(Got bitten by a nasty overflow btw, the list of unique X coordinates was overwriting the list of unique Y coordinates. Oh well, such is the life of a C programmer.)
Very not pretty and not efficient. Using what I think is dynamic programming - essentially I just propagate cost total through a (x, y, heading, steps in heading) state space, so every cell in that N-dimensional array holds the minimum total cost known to get to that state which is updated iteratively from the neighbours until it settles down.
Debugging was annoying because terminals aren’t great at showing 4D grids. My mistakes were in the initial situation and missing the “4 steps to come to a stop at the end” aspect in part 2.
Just tracing the ray. When it splits, recurse one way and continue the other. Didn’t bother with a direction lookup table this time, just a few ifs. The ray ends when it goes out of bounds or a ray in that direction has been previously traced on a given cell (this is tracked with a separate table).
It would’ve been straightforward if I hadn’t gotten the ‘previously visited’ check wrong 😞. I was checking against the direction coming in of the tile but marking the direction going out.
Ray function:
static void
ray(int x, int y, int dir)
{
int c;
while (x>=0 && y>=0 && x<w && y<h) {
if (beams[y][x] & (1 << dir))
break;
beams[y][x] |= 1 << dir;
c = map[y][x];
if (dir==NN && c=='/') dir = EE; else
if (dir==EE && c=='/') dir = NN; else
if (dir==SS && c=='/') dir = WW; else
if (dir==WW && c=='/') dir = SS; else
if (dir==NN && c=='\\') dir = WW; else
if (dir==EE && c=='\\') dir = SS; else
if (dir==SS && c=='\\') dir = EE; else
if (dir==WW && c=='\\') dir = NN; else
if (dir==NN && c=='-') { ray(x,y,WW); dir = EE; } else
if (dir==SS && c=='-') { ray(x,y,WW); dir = EE; } else
if (dir==EE && c=='|') { ray(x,y,NN); dir = SS; } else
if (dir==WW && c=='|') { ray(x,y,NN); dir = SS; }
x += dir==EE ? 1 : dir==WW ? -1 : 0;
y += dir==SS ? 1 : dir==NN ? -1 : 0;
}
}
Yes, it’s a hash table. Did I pick a language with built in hash tables? Of course I didn’t. Could I have used one of the many libraries implementing one? Sure. But the real question is, can we make do with stuffing things into a few static arrays at nearly zero memory and runtime cost? Yes!
In the spirit of Fred Brooks, it’ll suffice here to show my data structures:
struct slot { char label[8]; int lens; };
struct box { struct slot slots[8]; int nslots; };
static struct box boxes[256];
That array initialisation is pure poetry! 😄
Chose not to do transposing/flipping or fancy indexing so it’s rather verbose, but it’s also clear and (I think) fast. I also tried to limit the number of search steps by keeping two cursors in the current row/col, rather than shooting a ray every time.
Part 2 immediately reminded me of that Tetris puzzle from day 22 last year so I knew how to find and apply the solution. State hashes are stored in an array and (inefficiently) scanned until a loop is found.
One direction of the shift function:
/*
* Walk two cursors i and j through each column x. The i cursor
* looks for the first . where an O can go. The j cursor looks
* ahead for O's. When j finds a # we start again beyond it.
*/
for (x=0; xVery pretty again!
Implementing part 1 with a bunch of for loops made me wonder about elegant NumPy solutions but then part 2 came along and it was a perfect fit! Just change a flag to a counter and remove the if-match-early-exit.
https://github.com/sjmulder/aoc/blob/master/2023/c/day13.c
int main()
{
static char g[32][32];
int p1=0,p2=0, w,h, x,y,i, nmis;
while (!feof(stdin)) {
for (h=0; ; h++) {
assert(h < (int)LEN(*g));
if (!fgets(g[h], LEN(*g), stdin)) break;
if (!g[h][0] || g[h][0]=='\n') break;
}
assert(h>0); w = strlen(g[0])-1;
assert(w>0);
for (x=1; xThat was something! I quickly settled on the main approach for part 1 but it took some unit testing to get it all right. Then part 2 had me stumped for a bit. It was clear some kind of pruning was necessary, possibly with memoization.
Hashmaps are possible but annoying with C so I was happy to realise that, for my implementation, (num chars, num runs) is a suitable key within the context of a single recursive search. That space is small enough to index with an array 😁
Yes, thank you!
Brute forced it, runs in 60 ms or so. Only shortcut is quitting the loop when the distance drops below the record. I didn’t bother with the closed form solution here because a) it ran so fast and b) I was concerned about floats, rounding and off-by-one errors. Will probably implement it later!
Edit: implemented the closed form solution. Feels dirty copying a formula without really understanding it…
My first approach to part 2 was to take the list of ranges, map it to a new list of (possibly split up) ranges, etc, but I realized that would take more memory and bookkeeping than I’d like. Scrapped it and rewrote it with recursion. Much cleaner and the benchmarks are still looking good! (But for how much longer?)
$ bmake bench
day01 0:00.00 1380 Kb 0+78 faults
day02 0:00.00 1660 Kb 0+82 faults
day03 0:00.00 1540 Kb 0+107 faults
day04 0:00.00 1536 Kb 0+80 faults
day05 0:00.00 1668 Kb 0+83 faults
https://github.com/sjmulder/aoc/blob/master/2023/c/day05.c
Edit: I see some people went for looping from 0 to try possible answers. Clever and short but I wanted to go for a more efficient approach.
That’s unfortunate, although it looks good on my instance (SDF). Anything I could do?
Language: C
Another day of parsing, another day of strsep() to the rescue. Today was one of those satisfying days where the puzzle text is complicated but the solution is simple once well understood.
int main()
{
char line[128], *rest, *tok;
int nextra[200]={0}, nums[10], nnums;
int p1=0,p2=0, id,val,nmatch, i;
for (id=0; (rest = fgets(line, sizeof(line), stdin)); id++) {
nnums = nmatch = 0;
while ((tok = strsep(&rest, " ")) && !strchr(tok, ':'))
;
while ((tok = strsep(&rest, " ")) && !strchr(tok, '|'))
if ((val = atoi(tok)))
nums[nnums++] = val;
while ((tok = strsep(&rest, " ")))
if ((val = atoi(tok)))
for (i=0; i
That’s a planning problem imo, from small towns to metropolises groceries, health clinic, some entertainment can be in walking distance.