Haskell

A nice easy one today: didn’t even have to hit this with the optimization hammer.

import Data.Char
import Data.List
import Data.Map (Map)
import Data.Map qualified as Map

readInput :: String -> Map (Int, Int) Int
readInput s =
  Map.fromList
    [ ((i, j), digitToInt c)
      | (i, l) <- zip [0 ..] (lines s),
        (j, c) <- zip [0 ..] l
    ]

findTrails :: Map (Int, Int) Int -> [[[(Int, Int)]]]
findTrails input =
  Map.elems . Map.map (filter ((== 10) . length)) $
    Map.restrictKeys accessible starts
  where
    starts = Map.keysSet . Map.filter (== 0) $ input
    accessible = Map.mapWithKey getAccessible input
    getAccessible (i, j) h
      | h == 9 = [[(i, j)]]
      | otherwise =
          [ (i, j) : path
            | (di, dj) <- [(-1, 0), (0, 1), (1, 0), (0, -1)],
              let p = (i + di, j + dj),
              input Map.!? p == Just (succ h),
              path <- accessible Map.! p
          ]

main = do
  trails <- findTrails . readInput <$> readFile "input10"
  mapM_
    (print . sum . (`map` trails))
    [length . nub . map last, length]

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.

#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

Uiua

Run it here!

How to read this

Uiua has a very helpful path function built in which returns all valid paths that match your criteria (using diijkstra/a* depending on whether third function is provided), making a lot of path-finding stuff almost painfully simple, as you just need to provide a starting node and three functions: return next nodes, return confirmation if we’ve reached a suitable target node (here testing if it’s = 9), (optional) return heuristic cost to destination (here set to constant 1), .

Data   ← ⊜≡⋕⊸≠@\n"89010123\n78121874\n87430965\n96549874\n45678903\n32019012\n01329801\n10456732"
N₄     ← ≡+[0_1 1_0 0_¯1 ¯1_0]¤
Ns     ← ▽:⟜(=1-:∩(⬚0⊡:Data))▽⊸≡(/×≥0)N₄. # Valid, in-bounds neighbours.
Count! ← /+≡(⧻^0⊙◌ path(Ns|(=9⊡:Data)|1))⊚=0Data
&p Count!(◴≡◇⊣)
&p Count!∘

Rust

Definitely a nice and easy one, I accidentally solved part 2 first, because I skimmed the challenge and missed the unique part.

#[cfg(test)]
mod tests {

    const DIR_ORDER: [(i8, i8); 4] = [(-1, 0), (0, 1), (1, 0), (0, -1)];

    fn walk_trail(board: &Vec<Vec<i8>>, level: i8, i: i8, j: i8) -> Vec<(i8, i8)> {
        let mut paths = vec![];
        if i < 0 || j < 0 {
            return paths;
        }
        let actual_level = match board.get(i as usize) {
            None => return paths,
            Some(line) => match line.get(j as usize) {
                None => return paths,
                Some(c) => c,
            },
        };
        if *actual_level != level {
            return paths;
        }
        if *actual_level == 9 {
            return vec![(i, j)];
        }

        for dir in DIR_ORDER.iter() {
            paths.extend(walk_trail(board, level + 1, i + dir.0, j + dir.1));
        }
        paths
    }

    fn count_unique(p0: &Vec<(i8, i8)>) -> u32 {
        let mut dedup = vec![];
        for p in p0.iter() {
            if !dedup.contains(p) {
                dedup.push(*p);
            }
        }
        dedup.len() as u32
    }

    #[test]
    fn day10_part1_test() {
        let input = std::fs::read_to_string("src/input/day_10.txt").unwrap();

        let board = input
            .trim()
            .split('\n')
            .map(|line| {
                line.chars()
                    .map(|c| {
                        if c == '.' {
                            -1
                        } else {
                            c.to_digit(10).unwrap() as i8
                        }
                    })
                    .collect::<Vec<i8>>()
            })
            .collect::<Vec<Vec<i8>>>();

        let mut total = 0;

        for (i, row) in board.iter().enumerate() {
            for (j, pos) in row.iter().enumerate() {
                if *pos == 0 {
                    let all_trails = walk_trail(&board, 0, i as i8, j as i8);
                    total += count_unique(&all_trails);
                }
            }
        }

        println!("{}", total);
    }
    #[test]
    fn day10_part2_test() {
        let input = std::fs::read_to_string("src/input/day_10.txt").unwrap();

        let board = input
            .trim()
            .split('\n')
            .map(|line| {
                line.chars()
                    .map(|c| {
                        if c == '.' {
                            -1
                        } else {
                            c.to_digit(10).unwrap() as i8
                        }
                    })
                    .collect::<Vec<i8>>()
            })
            .collect::<Vec<Vec<i8>>>();

        let mut total = 0;

        for (i, row) in board.iter().enumerate() {
            for (j, pos) in row.iter().enumerate() {
                if *pos == 0 {
                    total += walk_trail(&board, 0, i as i8, j as i8).len();
                }
            }
        }

        println!("{}", total);
    }
}

Python

Not surprisingly, trees

import numpy as np
from pathlib import Path

cwd = Path(__file__).parent

cross = np.array([[-1,0],[1,0],[0,-1],[0,1]])

class Node():
  def __init__(self, coord, parent):
    self.coord = coord
    self.parent = parent

  def __repr__(self):
    return f"{self.coord}"

def parse_input(file_path):

  with file_path.open("r") as fp:
    data = list(map(list, fp.read().splitlines()))

  return np.array(data, dtype=int)

def find_neighbours(node_pos, grid):

  I = list(filter(lambda x: all([c>=0 and o-c>0 for c,o in zip(x,grid.shape)]),
                  list(cross + node_pos)))

  candidates = grid[tuple(np.array(I).T)]
  J = np.argwhere(candidates-grid[tuple(node_pos)]==1).flatten()

  return list(np.array(I).T[:, J].T)

def construct_tree_paths(grid):

  roots = list(np.argwhere(grid==0))
  trees = []

  for root in roots:

    levels = [[Node(root, None)]]
    while len(levels[-1])>0 or len(levels)==1:
      levels.append([Node(node, root) for root in levels[-1] for node in
                     find_neighbours(root.coord, grid)])
    trees.append(levels)

  return trees

def trace_back(trees, grid):

  paths = []

  for levels in trees:
    for node in levels[-2]:

      path = ""
      while node is not None:
        coord = ",".join(node.coord.astype(str))
        path += f"{coord} "
        node = node.parent
      paths.append(path)

  return paths

def solve_problem(file_name):

  grid = parse_input(Path(cwd, file_name))
  trees = construct_tree_paths(grid)
  trails = trace_back(trees, grid)
  ntrails = len(set(trails))
  nreached = sum([len(set([tuple(x.coord) for x in levels[-2]])) for levels in trees])

  return nreached, ntrails