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

  • @[email protected]
    4•7 months ago

    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;
}

    https://github.com/sjmulder/aoc/blob/master/2024/c/day10.c