Day 16: Reindeer Maze
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
Yay more grids! Seemed like prime Dijkstra or A* material but I went with an iterative approach instead!
I keep an array cost[y][x][dir], which is seeded at 1 for the starting location and direction. Then I keep going over the array, seeing if any valid move (step or turn) would yield to a lower best-known-cost for this state. It ends when a pass does not yield changes.
This leaves us with the best-known-costs for every reachable state in the array, including the end cell (bit we have to take the min() of the four directions).
Part 2 was interesting: I just happend to have written a dead end pruning function for part 1 and part 2 is, really, dead-end pruning for the cost map: remove any suboptimal step, keep doing so, and you end up with only the optimal steps. ‘Suboptimal’ here is a move that yields a higher total cost than the best-known-cost for that state.
It’s fast enough too on my 2015 i5:
day16 0:00.05 1656 Kb 0+242 faults
Code
#include "common.h"
#define GZ 145
enum {NN, EE, SS, WW};
static const int dx[]={0,1,0,-1}, dy[]={-1,0,1,0};
static char g[GZ][GZ]; /* with 1 tile border */
static int cost[GZ][GZ][4]; /* per direction, starts at 1, 0=no info */
static int traversible(char c) { return c=='.' || c=='S' || c=='E'; }
static int
minat(int x, int y)
{
int acc=0, d;
for (d=0; d<4; d++)
if (cost[y][x][d] && (!acc || cost[y][x][d] < acc))
acc = cost[y][x][d];
return acc;
}
static int
count_exits(int x, int y)
{
int acc=0, i;
assert(x>0); assert(x<GZ-1);
assert(y>0); assert(y<GZ-1);
for (i=0; i<4; i++)
acc += traversible(g[y+dy[i]][x+dx[i]]);
return acc;
}
/* remove all dead ends */
static void
prune_dead(void)
{
int dirty=1, x,y;
while (dirty) {
dirty = 0;
for (y=1; y<GZ-1; y++)
for (x=1; x<GZ-1; x++)
if (g[y][x]=='.' && count_exits(x,y) < 2)
{ dirty = 1; g[y][x] = '#'; }
}
}
/* remove all dead ends from cost[], leaves only optimal paths */
static void
prune_subopt(void)
{
int dirty=1, x,y,d;
while (dirty) {
dirty = 0;
for (y=1; y<GZ-1; y++)
for (x=1; x<GZ-1; x++)
for (d=0; d<4; d++) {
if (!cost[y][x][d])
continue;
if (g[y][x]=='E') {
if (cost[y][x][d] != minat(x,y))
{ dirty = 1; cost[y][x][d] = 0; }
continue;
}
if (cost[y][x][d]+1 > cost[y+dy[d]][x+dx[d]][d] &&
cost[y][x][d]+1000 > cost[y][x][(d+1)%4] &&
cost[y][x][d]+1000 > cost[y][x][(d+3)%4])
{ dirty = 1; cost[y][x][d] = 0; }
}
}
}
static void
propagate_costs(void)
{
int dirty=1, cost1, x,y,d;
while (dirty) {
dirty = 0;
for (y=1; y<GZ-1; y++)
for (x=1; x<GZ-1; x++)
for (d=0; d<4; d++) {
if (!traversible(g[y][x]))
continue;
/* from back */
if ((cost1 = cost[y-dy[d]][x-dx[d]][d]) &&
(cost1+1 < cost[y][x][d] || !cost[y][x][d]))
{ dirty = 1; cost[y][x][d] = cost1+1; }
/* from right */
if ((cost1 = cost[y][x][(d+1)%4]) &&
(cost1+1000 < cost[y][x][d] || !cost[y][x][d]))
{ dirty = 1; cost[y][x][d] = cost1+1000; }
/* from left */
if ((cost1 = cost[y][x][(d+3)%4]) &&
(cost1+1000 < cost[y][x][d] || !cost[y][x][d]))
{ dirty = 1; cost[y][x][d] = cost1+1000; }
}
}
}
int
main(int argc, char **argv)
{
int p1=0,p2=0, sx=0,sy=0, ex=0,ey=0, x,y;
char *p;
if (argc > 1)
DISCARD(freopen(argv[1], "r", stdin));
for (y=1; fgets(g[y]+1, GZ-1, stdin); y++) {
if ((p = strchr(g[y]+1, 'S'))) { sy=y; sx=p-g[y]; }
if ((p = strchr(g[y]+1, 'E'))) { ey=y; ex=p-g[y]; }
assert(y+1 < GZ-1);
}
cost[sy][sx][EE] = 1;
prune_dead();
propagate_costs();
prune_subopt();
p1 = minat(ex, ey) -1; /* costs[] values start at 1! */
for (y=1; y<GZ-1; y++)
for (x=1; x<GZ-1; x++)
p2 += minat(x,y) > 0;
printf("16: %d %d\n", p1, p2);
return 0;
}
