Day 10: Hoof It
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
You are viewing a single thread.
View all comments 4 points
C
Tried a dynamic programming kind of thing first but recursion suited the problem much better.
Part 2 seemed incompatible with my visited list representation. Then at the office I suddenly realised I just had to skip a single if(). Funny how that works when you let things brew in the back of your mind.
Code
#include "common.h"
#define GZ 43
/*
* To avoid having to clear the 'seen' array after every search we mark
* and check it with a per-search marker value ('id').
*/
static char g[GZ][GZ];
static int seen[GZ][GZ];
static int
score(int id, int x, int y, int p2)
{
if (x<0 || x>=GZ ||
y<0 || y>=GZ || (!p2 && seen[y][x] == id))
return 0;
seen[y][x] = id;
if (g[y][x] == '9')
return 1;
return
(g[y-1][x] == g[y][x]+1 ? score(id, x, y-1, p2) : 0) +
(g[y+1][x] == g[y][x]+1 ? score(id, x, y+1, p2) : 0) +
(g[y][x-1] == g[y][x]+1 ? score(id, x-1, y, p2) : 0) +
(g[y][x+1] == g[y][x]+1 ? score(id, x+1, y, p2) : 0);
}
int
main(int argc, char **argv)
{
int p1=0,p2=0, id=1, x,y;
if (argc > 1)
DISCARD(freopen(argv[1], "r", stdin));
for (y=0; y<GZ && fgets(g[y], GZ, stdin); y++)
;
for (y=0; y<GZ; y++)
for (x=0; x<GZ; x++)
if (g[y][x] == '0') {
p1 += score(id++, x, y, 0);
p2 += score(id++, x, y, 1);
}
printf("10: %d %d\n", p1, p2);
return 0;
}
3 points
2 points
