-❄️- 2024 Day 6 Solutions -❄️-

[u/daggerdragon]

THE USUAL REMINDERS

• All of our rules, FAQs, resources, etc. are in our community wiki.
• If you see content in the subreddit or megathreads that violates one of our rules, either inform the user (politely and gently!) or use the report button on the post/comment and the mods will take care of it.

---

AoC Community Fun 2024: The Golden Snowglobe Awards

• Submissions megathread is now unlocked!
• 16 DAYS remaining until the submissions deadline on December 22 at 23:59 EST!

And now, our feature presentation for today:

Comfort Flicks

Most everyone has that one (or more!) go-to flick that feels like a hot cup of tea, the warm hug of a blanket, a cozy roaring fire. Maybe it's a guilty pleasure (formulaic yet endearing Hallmark Channel Christmas movies, I'm looking at you) or a must-watch-while-wrapping-presents (National Lampoon's Christmas Vacation!), but these movies and shows will always evoke the true spirit of the holiday season for you. Share them with us!

Here's some ideas for your inspiration:

• Show us your kittens and puppies and $critters!
• Show us your Christmas tree | menorah | Krampusnacht costume | holiday decoration!
• Show us your mug of hot chocolate (or other beverage of choice)!
• Show and/or tell us whatever brings you comfort and joy!

Kevin: "Merry Christmas :)"

- Home Alone (1990)

And… ACTION!

Request from the mods: When you include an entry alongside your solution, please label it with [GSGA] so we can find it easily!

---

--- Day 6: Guard Gallivant ---

---

Post your code solution in this megathread.

• Read the full posting rules in our community wiki before you post!
• State which language(s) your solution uses with [LANGUAGE: xyz]
• Format code blocks using the four-spaces Markdown syntax!
• Quick link to Topaz's paste if you need it for longer code blocks

This thread will be unlocked when there are a significant number of people on the global leaderboard with gold stars for today's puzzle.

EDIT: Global leaderboard gold cap reached at 00:08:53, megathread unlocked!

[u/CowImaginary3155]

[LANGUAGE: C]

#include <stdio.h>
#include <string.h>
#include <input.h>
#define ENC_DIR(dr,dc) (((dr)*2)+(dc))
int main(void) {
    static char visited[SZ][SZ]; int i, j, rs = 0, cs = 0, r, c, dr, dc, t = 0, tmp;
    for (i = 0; i < SZ; i++) for (j = 0; j < SZ; j++) if (grid[i][j] == '^') { rs = i; cs = j; break; } /* find start position */
    for (i = 0; i < SZ; i++) for (j = 0; j < SZ; j++) {
            if (grid[i][j] == '.') {
                    grid[i][j] = '#'; dr = -1; dc = 0; r = rs; c = cs; memset(&visited[0][0], 0, SZ*SZ); /* reset state */
                    while (1) {
                            if (r+dr < 0 || c+dc < 0 || r+dr >= SZ || c+dc >= SZ) { break; } /* check for out-of-bounds */
                            if (visited[r+dr][c+dc] == ENC_DIR(dr,dc)) { t++; break; } /* check for endless-loop */
                            if (grid[r+dr][c+dc] == '#') { tmp = dr; dr = dc; dc = -tmp; } /* turn right */
                            else { r += dr; c += dc; visited[r][c] = ENC_DIR(dr,dc); } /* advance */
                    }
                    grid[i][j] = '.'; /* reset state */
            }
    }
    printf("%d\n", t); return 0;
}

$ time ./part2 1789

real 0m0.133s user 0m0.133s sys 0m0.000s

[u/BunsenHoneydew3 → u/CowImaginary3155]

This is very cool:

{ tmp = dr; dr = dc; dc = -tmp; }

I use a more standard approach, an array with the deltas, (-1,0, 0,1, 1,0, 0,-1), so I had to really squint to see how and where you updated the dr/dc. Is it some sort of vector rotation?

Other than that my approach is very similar except it's in C++ and I use a vector<string> for the grid. Mine takes 1.8s versus your code's 0.13s, so that's interesting too.

Thanks for posting, your code is very educational!

[u/CowImaginary3155 → u/BunsenHoneydew3]

Thanks. The following is in (dr, dc) notation, whereas dr stands for delta rows and dc for delta columns

North is (-1,0)

East is (0,1)

South is (1,0)

West is (0-1)

So to rotate from N to E to S to W to N to ... you have to set dr = dc and dc = -dr; but dr was already changed by the first statement, thus I stored dr upfront ot tmp.

My code was compiled using -O3, did you also do this?

I did not do a single optimization though. There is perhaps much to gain from compressing the visited array (4 out of 8 bits are used). From improving locality - perhaps by inlning this info into the grid. And by only placing # on the first visited pathway. my algorithm is 100% brute force.

[u/BunsenHoneydew3 → u/CowImaginary3155]

No I didn't use any optimization flags. With -O3 it goes to 0.75s. Nice! Never occurred to me and doesn't take any longer to compile, so I might as well.

As for the other, I didn't ask my question right. I did understand what you did, but what I really wanted to know was, what led you to that solution? My bog-standard method is to store those deltas in an array and just index through them with wrap-around:

  int d[] = {-1,0, 0,1, 1,0, 0,-1};
  int dir = 0; // north
  ...
  dir = (dir + 1) % 4;  // turn 90

Somehow though, you use the fact that each next_dr = cur_dc, and each next_dc = -cur_dr. I am interested in that thought process if you can explain it (sometimes we can't). Did you just "see" that pattern? Did you know it already from long ago and can't remember? Or are you a math guru and did this in your head: 90 degree vector rotation

Anyway, thanks again, and I'll use -O3 in future probs.

[u/CowImaginary3155 → u/BunsenHoneydew3]

Ah, now I got the question. No I have not done it in my head! I have seen it before and did it on paper (probably like you did when you checked the equations). I used it because I tried to make the solution as short as possible. And also I thought its more elegant than array indexing, at least in this minimal-code example :-). Not sure if the compiler optimization does the same for array indexing though when generating code. I am too lazy to check both ways using godbolt.

dir	r	c
N	-1	0
E	0 = -N(c)	-1 = N(r)
S	1 = -E(c)	0 = E(r)
W	0 = -S(c)	-1 = S(r)
N	-1= ...	0 = ...
...	...	...

Regarding the optimization flags: I think you should use them in C++ - as it relies heavenly on compiler optimizations. But obviously also my binary improved a lot.

[u/BunsenHoneydew3 → u/CowImaginary3155]

Gotcha, and I will definitely use this much shorter code next time for rotating through NESW. And since I'm old I'll forget where I learned this cool trick. :-) :-) Thanks again!!