Day 14: Restroom Redoubt
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
C
Solved part 1 without a grid, looked at part 2, almost spit out my coffee. Didn’t see that coming!
I used my visualisation mini-library to generate video with ffmpeg, stepped through it a bit, then thought better of it - this is a programming puzzle after all!
So I wrote a heuristic to find frames low on entropy (specifically: having many robots in the same line of column), where each record-breaking frame number was printed. That pointed right at the correct frame!
It was pretty slow though (.2 secs or such) because it required marking spots on a grid. I noticed the Christmas tree was neatly tucked into a corner, concluded that wasn’t an accident, and rewrote the heuristic to check for a high concentration in a single quadrant. Reverted this because the tree-in-quadrant assumption proved incorrect for other inputs. Would’ve been cool though!
Code
#include "common.h"
#define SAMPLE 0
#define GW (SAMPLE ? 11 : 101)
#define GH (SAMPLE ? 7 : 103)
#define NR 501
int
main(int argc, char **argv)
{
static char g[GH][GW];
static int px[NR],py[NR], vx[NR],vy[NR];
int p1=0, n=0, sec, i, x,y, q[4]={}, run;
if (argc > 1)
DISCARD(freopen(argv[1], "r", stdin));
for (; scanf(" p=%d,%d v=%d,%d", px+n,py+n, vx+n,vy+n)==4; n++)
assert(n+1 < NR);
for (sec=1; !SAMPLE || sec <= 100; sec++) {
memset(g, 0, sizeof(g));
memset(q, 0, sizeof(q));
for (i=0; i<n; i++) {
px[i] = (px[i] + vx[i] + GW) % GW;
py[i] = (py[i] + vy[i] + GH) % GH;
g[py[i]][px[i]] = 1;
if (sec == 100) {
if (px[i] < GW/2) {
if (py[i] < GH/2) q[0]++; else
if (py[i] > GH/2) q[1]++;
} else if (px[i] > GW/2) {
if (py[i] < GH/2) q[2]++; else
if (py[i] > GH/2) q[3]++;
}
}
}
if (sec == 100)
p1 = q[0]*q[1]*q[2]*q[3];
for (y=0; y<GH; y++)
for (x=0, run=0; x<GW; x++)
if (!g[y][x])
run = 0;
else if (++run >= 10)
goto found_p2;
}
found_p2:
printf("14: %d %d\n", p1, sec);
return 0;
}
