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

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]

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

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

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!∘

Nim

As many others today, I've solved part 2 first and then fixed a 'bug' to solve part 1. =)

type Vec2 = tuple[x,y:int]
const Adjacent = [(x:1,y:0),(-1,0),(0,1),(0,-1)]

proc path(start: Vec2, grid: seq[string]): tuple[ends, trails: int] =
  var queue = @[@[start]]
  var endNodes: HashSet[Vec2]
  while queue.len > 0:
    let path = queue.pop()
    let head = path[^1]
    let c = grid[head.y][head.x]

    if c == '9':
      inc result.trails
      endNodes.incl head
      continue

    for d in Adjacent:
      let nd = (x:head.x + d.x, y:head.y + d.y)
      if nd.x < 0 or nd.y < 0 or nd.x > grid[0].high or nd.y > grid.high:
        continue
      if grid[nd.y][nd.x].ord - c.ord != 1: continue
      queue.add path & nd
  result.ends = endNodes.len

proc solve(input: string): AOCSolution[int, int] =
  let grid = input.splitLines()
  var trailstarts: seq[Vec2]

  for y, line in grid:
    for x, c in line:
      if c == '0':
        trailstarts.add (x,y)

  for start in trailstarts:
    let (ends, trails) = start.path(grid)
    result.part1 += ends
    result.part2 += trails

Codeberg Repo

Rust

This was a nice one. Basically 9 rounds of Breadth-First-Search, which could be neatly expressed using fold. The only difference between part 1 and part 2 turned out to be the datastructure for the search frontier: The HashSet in part 1 unifies paths as they join back to the same node, the Vec in part 2 keeps all paths separate.

use std::collections::HashSet;

fn parse(input: &str) -> Vec<&[u8]> {
    input.lines().map(|l| l.as_bytes()).collect()
}

fn adj(grid: &[&[u8]], (x, y): (usize, usize)) -> Vec<(usize, usize)> {
    let n = grid[y][x];
    let mut adj = Vec::with_capacity(4);
    if x > 0 && grid[y][x - 1] == n + 1 {
        adj.push((x - 1, y))
    }
    if y > 0 && grid[y - 1][x] == n + 1 {
        adj.push((x, y - 1))
    }
    if x + 1 < grid[0].len() && grid[y][x + 1] == n + 1 {
        adj.push((x + 1, y))
    }
    if y + 1 < grid.len() && grid[y + 1][x] == n + 1 {
        adj.push((x, y + 1))
    }
    adj
}

fn solve(input: String, trailhead: fn(&[&[u8]], (usize, usize)) -> u32) -> u32 {
    let grid = parse(&input);
    let mut sum = 0;
    for (y, row) in grid.iter().enumerate() {
        for (x, p) in row.iter().enumerate() {
            if *p == b'0' {
                sum += trailhead(&grid, (x, y));
            }
        }
    }
    sum
}

fn part1(input: String) {
    fn score(grid: &[&[u8]], start: (usize, usize)) -> u32 {
        (1..=9)
            .fold(HashSet::from([start]), |frontier, _| {
                frontier.iter().flat_map(|p| adj(grid, *p)).collect()
            })
            .len() as u32
    }
    println!("{}", solve(input, score))
}

fn part2(input: String) {
    fn rating(grid: &[&[u8]], start: (usize, usize)) -> u32 {
        (1..=9)
            .fold(vec![start], |frontier, _| {
                frontier.iter().flat_map(|p| adj(grid, *p)).collect()
            })
            .len() as u32
    }
    println!("{}", solve(input, rating))
}

util::aoc_main!();

Also on github

Haskell

import Control.Arrow
import Control.Monad.Reader
import Data.Array.Unboxed
import Data.List

type Pos = (Int, Int)
type Board = UArray Pos Char
type Prob = Reader Board

parse :: String -> Board
parse s = listArray ((1, 1), (n, m)) $ concat l
  where
    l = lines s
    n = length l
    m = length $ head l

origins :: Prob [Pos]
origins =
    ask >>= \board ->
        return $ fmap fst . filter ((== '0') . snd) $ assocs board

moves :: Pos -> Prob [Pos]
moves pos =
    ask >>= \board ->
        let curr = board ! pos
         in return . filter ((== succ curr) . (board !)) . filter (inRange (bounds board)) $ fmap (.+. pos) deltas
  where
    deltas = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    (ax, ay) .+. (bx, by) = (ax + bx, ay + by)

solve :: [Pos] -> Prob [Pos]
solve p = do
    board <- ask
    nxt <- concat <$> mapM moves p

    let (nines, rest) = partition ((== '9') . (board !)) nxt

    fmap (++ nines) $ if null rest then return [] else solve rest

scoreTrail = fmap (length . nub) . solve . pure
scoreTrail' = fmap length . solve . pure

part1 = sum . runReader (origins >>= mapM scoreTrail)
part2 = sum . runReader (origins >>= mapM scoreTrail')

main = getContents >>= print . (part1 &&& part2) . parse

Haskell

Cool task, nothing to optimize

import Control.Arrow

import Data.Array.Unboxed (UArray)
import Data.Set (Set)

import qualified Data.Char as Char
import qualified Data.List as List
import qualified Data.Set as Set
import qualified Data.Array.Unboxed as UArray

parse :: String -> UArray (Int, Int) Int
parse s = UArray.listArray ((1, 1), (n, m)) . map Char.digitToInt . filter (/= '\n') $ s
        where
                n = takeWhile (/= '\n') >>> length $ s
                m = filter (== '\n') >>> length >>> pred $ s

reachableNeighbors :: (Int, Int) -> UArray (Int, Int) Int -> [(Int, Int)]
reachableNeighbors p@(py, px) a = List.filter (UArray.inRange (UArray.bounds a))
        >>> List.filter ((a UArray.!) >>> pred >>> (== (a UArray.! p)))
        $ [(py-1, px), (py+1, px), (py, px-1), (py, px+1)]

distinctTrails :: (Int, Int) -> UArray (Int, Int) Int -> Int
distinctTrails p a
        | a UArray.! p == 9 = 1
        | otherwise = flip reachableNeighbors a
                >>> List.map (flip distinctTrails a)
                >>> sum
                $ p

reachableNines :: (Int, Int) -> UArray (Int, Int) Int -> Set (Int, Int)
reachableNines p a
        | a UArray.! p == 9 = Set.singleton p
        | otherwise = flip reachableNeighbors a
                >>> List.map (flip reachableNines a)
                >>> Set.unions
                $ p

findZeros = UArray.assocs
        >>> filter (snd >>> (== 0))
        >>> map fst

part1 a = findZeros
        >>> map (flip reachableNines a)
        >>> map Set.size
        >>> sum
        $ a
part2 a = findZeros
        >>> map (flip distinctTrails a)
        >>> sum
        $ a

main = getContents
        >>= print
        . (part1 &&& part2)
        . parse

Nice to have a really simple one for a change, both my day 1 and 2 solutions worked on their very first attempts.
I rewrote the code to combine the two though, since the implementations were almost identical for both solutions, and also to replace the recursion with a search list instead.

int[] heights = new int[0];
(int, int) size = (0, 0);

public void Input(IEnumerable<string> lines)
{
  size = (lines.First().Length, lines.Count());
  heights = string.Concat(lines).Select(c => int.Parse(c.ToString())).ToArray();
}

int trails = 0, trailheads = 0;
public void PreCalc()
{
  for (int y = 0; y < size.Item2; ++y)
    for (int x = 0; x < size.Item1; ++x)
      if (heights[y * size.Item1 + x] == 0)
      {
        var unique = new HashSet<(int, int)>();
        trails += CountTrails((x, y), unique);
        trailheads += unique.Count;
      }
}

public void Part1()
{
  Console.WriteLine($"Trailheads: {trailheads}");
}
public void Part2()
{
  Console.WriteLine($"Trails: {trails}");
}

int CountTrails((int, int) from, HashSet<(int,int)> unique)
{
  int found = 0;

  List<(int,int)> toSearch = new List<(int, int)>();
  toSearch.Add(from);

  while (toSearch.Any())
  {
    var cur = toSearch.First();
    toSearch.RemoveAt(0);

    int height = heights[cur.Item2 * size.Item1 + cur.Item1];
    for (int y = -1; y <= 1; ++y)
      for (int x = -1; x <= 1; ++x)
      {
        if ((y != 0 && x != 0) || (y == 0 && x == 0))
          continue;

        var newAt = (cur.Item1 + x, cur.Item2 + y);
        if (newAt.Item1 < 0 || newAt.Item1 >= size.Item1 || newAt.Item2 < 0 || newAt.Item2 >= size.Item2)
          continue;

        int newHeight = heights[newAt.Item2 * size.Item1 + newAt.Item1];
        if (newHeight - height != 1)
          continue;

        if (newHeight == 9)
        {
          unique.Add(newAt);
          found++;
          continue;
        }

        toSearch.Add(newAt);
      }
  }

  return found;
}

J

Who needs recursion or search algorithms? Over here in line noise array hell, we have built-in sparse matrices! :)

data_file_name =: '10.data'
grid =: "."0 ,. > cutopen fread data_file_name
data =: , grid
'rsize csize' =: $ grid
inbounds =: monad : '(*/ y >: 0 0) * (*/ y < rsize, csize)'
coords =: ($ grid) & #:
uncoords =: ($ grid) & #.
NB. if n is the linear index of a point, neighbors n lists the linear indices
NB. of its orthogonally adjacent points
neighbors =: monad : 'uncoords (#~ inbounds"1) (coords y) +"1 (4 2 $ 1 0 0 1 _1 0 0 _1)'
uphill1 =: dyad : '1 = (y { data) - (x { data)'
uphill_neighbors =: monad : 'y ,. (#~ (y & uphill1)) neighbors y'
adjacency_of =: monad define
   edges =. ; (< @: uphill_neighbors"0) i.#y
   NB. must explicitly specify fill of integer 0, default is float
   1 edges} 1 $. ((#y), #y); (0 1); 0
)
adjacency =: adjacency_of data
NB. maximum path length is 9 so take 9th power of adjacency matrix
leads_to_matrix =: adjacency (+/ . *)^:8 adjacency
leads_to =: dyad : '({ & leads_to_matrix) @: < x, y'
trailheads =: I. data = 0
summits =: I. data = 9
scores =: trailheads leads_to"0/ summits
result1 =: +/, 0 < scores
result2 =: +/, scores

Julia

Quite happy that today went a lot smoother than yesterday even though I am not really familiar with recursion. Normally I never use recursion but I felt like today could be solved by it (or using trees, but I'm even less familiar with them). Surprisingly my solution actually worked and for part 2 only small modifications were needed to count peaks reached by each trail.

function readInput(inputFile::String)
	f = open(inputFile,"r")
	lines::Vector{String} = readlines(f)
	close(f)
	topoMap = Matrix{Int}(undef,length(lines),length(lines[1]))
	for (i,l) in enumerate(lines)
		topoMap[i,:] = map(x->parse(Int,x),collect(l))
	end
	return topoMap
end

function getTrailheads(topoMap::Matrix{Int})
	trailheads::Vector{Vector{Int}} = []
	for (i,r) in enumerate(eachrow(topoMap))
		for (j,c) in enumerate(r)
			c==0 ? push!(trailheads,[i,j]) : nothing
		end
	end
	return trailheads
end

function getReachablePeaks(topoMap::Matrix{Int},trailheads::Vector{Vector{Int}})
	reachablePeaks = Dict{Int,Vector{Vector{Int}}}()
	function getPossibleMoves(topoMap::Matrix{Int},pos::Vector{Int})
		possibleMoves::Vector{Vector{Int}} = []
		pos[1]-1 in 1:size(topoMap)[1] && topoMap[pos[1]-1,pos[2]]==topoMap[pos[1],pos[2]]+1 ? push!(possibleMoves,[pos[1]-1,pos[2]]) : nothing #up?
		pos[1]+1 in 1:size(topoMap)[1] && topoMap[pos[1]+1,pos[2]]==topoMap[pos[1],pos[2]]+1 ? push!(possibleMoves,[pos[1]+1,pos[2]]) : nothing #down?
		pos[2]-1 in 1:size(topoMap)[2] && topoMap[pos[1],pos[2]-1]==topoMap[pos[1],pos[2]]+1 ? push!(possibleMoves,[pos[1],pos[2]-1]) : nothing #left?
		pos[2]+1 in 1:size(topoMap)[2] && topoMap[pos[1],pos[2]+1]==topoMap[pos[1],pos[2]]+1 ? push!(possibleMoves,[pos[1],pos[2]+1]) : nothing #right?
		return possibleMoves
	end
	function walkPossMoves(topoMap::Matrix{Int},pos::Vector{Int},reachedPeaks::Matrix{Bool},trailId::Int)
		possMoves::Vector{Vector{Int}} = getPossibleMoves(topoMap,pos)
		for m in possMoves
			if topoMap[m[1],m[2]]==9
				reachedPeaks[m[1],m[2]]=1
				trailId += 1
				continue
			end
			reachedPeaks,trailId = walkPossMoves(topoMap,m,reachedPeaks,trailId)
		end
		return reachedPeaks, trailId
	end
	peaksScore::Int = 0; trailsScore::Int = 0
	trailId::Int = 0
	for (i,t) in enumerate(trailheads)
		if !haskey(reachablePeaks,i); reachablePeaks[i]=[]; end
		reachedPeaks::Matrix{Bool} = zeros(size(topoMap))
		trailId = 0
		reachedPeaks,trailId = walkPossMoves(topoMap,t,reachedPeaks,trailId)
		trailPeaksScore = sum(reachedPeaks)
		peaksScore += trailPeaksScore
		trailsScore += trailId
	end
	return peaksScore,trailsScore
end #getReachablePeaks

topoMap::Matrix{Int} = readInput("input/day10Input")
trailheads::Vector{Vector{Int}} = getTrailheads(topoMap)
@info "Part 1"
reachablePeaks = getReachablePeaks(topoMap,trailheads)[1]
println("reachable peaks: ",reachablePeaks)
@info "Part 2"
trailsScore::Int = getReachablePeaks(topoMap,trailheads)[2]
println("trails score: $trailsScore")

Raku

Pretty straight-forward problem today.

sub MAIN($input) {
    my $file = open $input;
    my @map = $file.slurp.trim.lines>>.comb>>.Int;

    my @pos-tracking = [] xx 10;
    for 0..^@map.elems X 0..^@map[0].elems -> ($row, $col) {
        @pos-tracking[@map[$row][$col]].push(($row, $col).List);
    }

    my %on-possible-trail is default([]);
    my %trail-score-part2 is default(0);
    for 0..^@pos-tracking.elems -> $height {
        for @pos-tracking[$height].List -> ($row, $col) {
            if $height == 0 {
                %on-possible-trail{"$row;$col"} = set ("$row;$col",);
                %trail-score-part2{"$row;$col"} = 1;
            } else {
                for ((1,0), (-1, 0), (0, 1), (0, -1)) -> @neighbor-direction {
                    my @neighbor-position = ($row, $col) Z+ @neighbor-direction;
                    next if @neighbor-position.any < 0 or (@neighbor-position Z>= (@map.elems, @map[0].elems)).any;
                    next if @map[@neighbor-position[0]][@neighbor-position[1]] != $height - 1;
                    %on-possible-trail{"$row;$col"} ∪= %on-possible-trail{"{@neighbor-position[0]};{@neighbor-position[1]}"};
                    %trail-score-part2{"$row;$col"} += %trail-score-part2{"{@neighbor-position[0]};{@neighbor-position[1]}"};
                }
            }
        }
    }

    my $part1-solution = @pos-tracking[9].map({%on-possible-trail{"{$_[0]};{$_[1]}"}.elems}).sum;
    say "part 1: $part1-solution";

    my $part2-solution = @pos-tracking[9].map({%trail-score-part2{"{$_[0]};{$_[1]}"}}).sum;
    say "part 2: $part2-solution";
}

C#

using System.Diagnostics;
using Common;

namespace Day10;

static class Program
{
    static void Main()
    {
        var start = Stopwatch.GetTimestamp();

        var sampleInput = Input.ParseInput("sample.txt");
        var programInput = Input.ParseInput("input.txt");

        Console.WriteLine($"Part 1 sample: {Part1(sampleInput)}");
        Console.WriteLine($"Part 1 input: {Part1(programInput)}");

        Console.WriteLine($"Part 2 sample: {Part2(sampleInput)}");
        Console.WriteLine($"Part 2 input: {Part2(programInput)}");

        Console.WriteLine($"That took about {Stopwatch.GetElapsedTime(start)}");
    }

    static object Part1(Input i) => GetTrailheads(i)
        .Sum(th => CountTheNines(th, i, new HashSet<Point>(), false));

    static object Part2(Input i) => GetTrailheads(i)
        .Sum(th => CountTheNines(th, i, new HashSet<Point>(), true));

    static int CountTheNines(Point loc, Input i, ISet<Point> visited, bool allPaths)
    {
        if (!visited.Add(loc)) return 0;
        
        var result =
            (ElevationAt(loc, i) == 9) ? 1 :
            loc.GetCardinalMoves()
                .Where(move => move.IsInBounds(i.Bounds.Row, i.Bounds.Col))
                .Where(move => (ElevationAt(move, i) - ElevationAt(loc, i)) == 1)
                .Where(move => !visited.Contains(move))
                .Sum(move => CountTheNines(move, i, visited, allPaths));
        
        if(allPaths) visited.Remove(loc);
        
        return result;
    }

    static IEnumerable<Point> GetTrailheads(Input i) => Grid.EnumerateAllPoints(i.Bounds)
        .Where(loc => ElevationAt(loc, i) == 0);

    static int ElevationAt(Point p, Input i) => i.Map[p.Row][p.Col];
}

public class Input
{
    public required Point Bounds { get; init; }
    public required int[][] Map { get; init; }
    
    public static Input ParseInput(string file)
    {
        using var reader = new StreamReader(file);
        var map = reader.EnumerateLines()
            .Select(l => l.Select(c => (int)(c - '0')).ToArray())
            .ToArray();
        var bounds = new Point(map.Length, map.Max(l => l.Length));
        return new Input()
        {
            Map = map,
            Bounds = bounds,
        };
    }
}

Uiua

After finally deciding to put aside Day 9 Part 2 for now, this was really easy actually. The longest was figuring out how many extra dimensions I had to give some arrays and where to remove those again (and how). Then part 2 came along and all I had to do was remove a single character (not removing duplicates when landing on the same field by going different ways from the same starting point). Basically, everything in the parentheses of the Trails! macro was my solution for part 1, just that the ^0 was ◴ (deduplicate). Once that was removed, the solution for part 2 was there as well.

Run with example input here

Note: in order to use the code here for the actual input, you have to replace =₈ with =₅₀ because I was too lazy to make it work with variable array sizes this time.

$ 89010123
$ 78121874
$ 87430965
$ 96549874
$ 45678903
$ 32019012
$ 01329801
$ 10456732
.
Adj ← ¤[0_¯1 0_1 ¯1_0 1_0]

Trails! ← (
  ⊚=0.
  ⊙¤
  ≡(□¤)
  1
  ⍥(⊙(≡(□^0/⊂≡(+¤)⊙¤°□)⊙Adj
      ≡(□▽¬≡/++⊃=₋₁=₈.°□))
    +1⟜⊸⍚(▽=⊙(:⟜⊡))
  )9
  ⊙◌◌
  ⧻/◇⊂
)

PartOne ← (
  # &rs ∞ &fo "input-10.txt"
  ⊜∵⋕≠@\n.
  Trails!◴
)

PartTwo ← (
  # &rs ∞ &fo "input-10.txt"
  ⊜∵⋕≠@\n.
  Trails!∘
)

&p "Day 10:"
&pf "Part 1: "
&p PartOne
&pf "Part 2: "
&p PartTwo

TypeScript

Maaaannnn. Today's solution was really something. I actually got so confused initially that I unknowingly wrote the algorithm for part 2 before I even finished part 1! As an upside, however, I did expand my own Advent of Code standard library ;)

import { AdventOfCodeSolutionFunction } from "./solutions";
import { Grid } from "./utils/grids";
import { LinkedPoint } from "./utils/structures/linkedPoint";
import { makeGridFromMultilineString, SumArray } from "./utils/utils";

class TrailPoint extends LinkedPoint<number, TrailPoint> {
    constructor(x: number, y: number, item: number, grid: Grid<TrailPoint>) {
        super(x, y, item, grid);
    }

    lookAroundValid(): Array<TrailPoint> {
        return this.lookAround().filter(v => v.item == this.item + 1);
    }

    findAllValidPeaks(): Array<TrailPoint> {
        if (this.item == 9)
            return [this];

        // filter for distinct references (this theoretically saves time)
        return [...(new Set(this.lookAroundValid().flatMap(v => v.findAllValidPeaks())))];
    }

    findAllValidPeaksWithReps(): Array<TrailPoint> {
        if (this.item == 9)
            return [this];

        // don't filter
        return this.lookAroundValid().flatMap(v => v.findAllValidPeaksWithReps());
    }
}

export const solution_10: AdventOfCodeSolutionFunction = (input) => {
    const map: Grid<TrailPoint> =
        makeGridFromMultilineString(input)
            .map((row) => row.map((item) => item != "." ? Number(item) : -1))
            .map((row, y) => row.map((item, x) => new TrailPoint(x, y, item, undefined!)));

    map.flat().forEach((v) => v.grid = map); // promise is a promise

    const startNodes: Array<TrailPoint> = map.flat().filter(v => v.item == 0);

    const part_1 = SumArray(startNodes.map(v => v.findAllValidPeaks().length));
    const part_2 = SumArray(startNodes.map(v => v.findAllValidPeaksWithReps().length));

    return {
        part_1, // 557
        part_2, // 1062
    }
}

Python

Sets of tuples and iteration for both first and second parts. A list of tuples used as a stack for the conversion of recursion to iteration. Dictionary of legal trail moves for traversal. Type hints for antibugging in VSCode. Couple of seconds runtime for each part.

https://github.com/jdnewmil/aocpy/blob/master/aocpy%2Faoc2024%2Fday10.py

C#

using QuickGraph;
using QuickGraph.Algorithms.Search;
using Point = (int, int);

public class Day10 : Solver
{
  private int[][] data;
  private int width, height;
  private List<int> destinations_counts = [], paths_counts = [];
  private record PointEdge(Point Source, Point Target): IEdge<Point>;

  private DelegateVertexAndEdgeListGraph<Point, PointEdge> MakeGraph() => new(AllPoints(), GetNeighbours);

  private static readonly List<Point> directions = [(1, 0), (-1, 0), (0, 1), (0, -1)];

  private bool GetNeighbours(Point from, out IEnumerable<PointEdge> result) {
    List<PointEdge> neighbours = [];
    int next_value = data[from.Item2][from.Item1] + 1;
    foreach (var (dx, dy) in directions) {
      int x = from.Item1 + dx, y = from.Item2 + dy;
      if (x < 0 || y < 0 || x >= width || y >= height) continue;
      if (data[y][x] != next_value) continue;
      neighbours.Add(new(from, (x, y)));
    }
    result = neighbours;
    return true;
  }

  private IEnumerable<Point> AllPoints() => Enumerable.Range(0, width).SelectMany(x => Enumerable.Range(0, height).Select(y => (x, y)));

  public void Presolve(string input) {
    data = input.Trim().Split("\n").Select(s => s.Select(ch => ch - '0').ToArray()).ToArray();
    width = data[0].Length;
    height = data.Length;
    var graph = MakeGraph();
    for (int i = 0; i < width; i++) {
      for (int j = 0; j < height; j++) {
        if (data[j][i] != 0) continue;
        var search = new BreadthFirstSearchAlgorithm<Point, PointEdge>(graph);
        Point start = (i, j);
        Dictionary<Point, int> paths_into = [];
        paths_into[start] = 1;
        var destinations = 0;
        var paths = 0;
        search.ExamineEdge += edge => {
          paths_into.TryAdd(edge.Target, 0);
          paths_into[edge.Target] += paths_into[edge.Source];
        };
        search.FinishVertex += vertex => {
          if (data[vertex.Item2][vertex.Item1] == 9) {
            paths += paths_into[vertex];
            destinations += 1;
          }
        };
        search.SetRootVertex(start);
        search.Compute();
        destinations_counts.Add(destinations);
        paths_counts.Add(paths);
      }
    }
  }

  public string SolveFirst() => destinations_counts.Sum().ToString();
  public string SolveSecond() => paths_counts.Sum().ToString();
}

Very optimized python script. takes ~1.5 milliseconds for it to do both parts. [ link ]

Dart

I dug out the hill-climbing trail-walking code from 2022 Day 12, put it up on blocks, and stripped all the weirdness out of it.

Ended up with just a simple flood-fill from each trailhead, so it turns out I only actually used the Graph and Node classes which I then also stripped out...

import 'dart:math';
import 'package:collection/collection.dart';
import 'package:more/more.dart';

late Map<Point, int> nodes;
late Map<Point, List> nexts;

/// Parse the lines, build up nodes and nexts, return starts.
List<Point> parse(ls) {
  nodes = {
    for (var y in 0.to(ls.length))
      for (var x in 0.to(ls.first.length)) Point(x, y): int.parse(ls[y][x])
  };
  nexts = Map.fromEntries(nodes.keys.map((n) => MapEntry(
      n,
      [Point(0, 1), Point(0, -1), Point(1, 0), Point(-1, 0)]
          .map((d) => n + d)
          .where((d) => (nodes[d] ?? -1) - nodes[n]! == 1)
          .toList())));
  return nodes.keys.where((e) => nodes[e] == 0).toList();
}

/// Given a starting node, return all valid paths to any '9' on the grid.
Set paths(Point here, [Set sofar = const {}]) {
  if (nodes[here]! == 9) return {sofar};
  return nexts[here]!
      .where((e) => !sofar.contains(e))
      .fold({}, (s, f) => s..addAll(paths(f, sofar.toSet()..add(f))));
}

/// Finds all paths from each start, then apply the fn to each and sum.
count(lines, int Function(Set) fn) => parse(lines).map(paths).map<int>(fn).sum;

part1(lines) => count(lines, (e) => e.map((p) => p.last).toSet().length);
part2(lines) => count(lines, (e) => e.length);

Kotlin

• Clean ❌
• Fast ❌
• Worked first try ✅

fun main() {
    /**
     * The idea is simple: Just simulate the pathing and sum all the end points
     */
    fun part1(input: List<String>): Int {
        val topologicalMap = Day10Map(input)
        val startingPoints = topologicalMap.asIterable().indicesWhere { it == 0 }
        val directions = Orientation.entries.map { it.asVector() }
        return startingPoints.sumOf { startingPoint ->
            var wayPoints = setOf(VecNReal(startingPoint))
            val endPoints = mutableSetOf<VecNReal>()
            while (wayPoints.isNotEmpty()) {
                wayPoints = wayPoints.flatMap { wayPoint ->
                    directions.map { direction ->
                        val checkoutLocation = wayPoint + direction
                        checkoutLocation to runCatching { topologicalMap[checkoutLocation] }.getOrElse { -1 }
                    }.filter { nextLocation ->
                        val endPointHeight = topologicalMap[wayPoint]
                        if (nextLocation.second - 1 == endPointHeight && nextLocation.second == 9) false.also { endPoints.add(nextLocation.first) }
                        else if (nextLocation.second - 1 == endPointHeight) true
                        else false
                    }.map { it.first }
                }.toSet()
            }

            endPoints.count()
        }
    }

    /**
     * A bit more complicated, but not by much.
     * Main difference is, that node accumulates all the possible paths, thus adding all the possibilities of
     * its parent node.
     */
    fun part2(input: List<String>): Int {
        val topologicalMap = Day10Map(input)
        val startingPoints = topologicalMap.asIterable().indicesWhere { it == 0 }
        val directions = Orientation.entries.map { it.asVector() }

        return startingPoints.sumOf { startingPoint ->
            var pathNodes = setOf<Node>(Node(VecNReal(startingPoint), topologicalMap[VecNReal(startingPoint)], 1))
            val endNodes = mutableSetOf<Node>()
            while (pathNodes.isNotEmpty()) {
                pathNodes = pathNodes.flatMap { pathNode ->
                    directions.map { direction ->
                        val nextNodeLocation = pathNode.position + direction
                        val nextNodeHeight = runCatching { topologicalMap[nextNodeLocation] }.getOrElse { -1 }
                        Node(nextNodeLocation, nextNodeHeight, pathNode.weight)
                    }.filter { nextNode ->
                        nextNode.height == pathNode.height + 1
                    }
                }.groupBy { it.position }.map { (position, nodesUnadjusted) ->
                    val adjustedWeight = nodesUnadjusted.sumOf { node -> node.weight }
                    Node(position, nodesUnadjusted.first().height, adjustedWeight)
                }.filter { node ->
                    if (node.height == 9) false.also { endNodes.add(node) } else true
                }.toSet()
            }

            endNodes.sumOf { endNode -> endNode.weight }
        }
    }

    val testInput = readInput("Day10_test")
    check(part1(testInput) == 36)
    check(part2(testInput) == 81)

    val input = readInput("Day10")
    part1(input).println()
    part2(input).println()
}

class Day10Map(input: List<String>): Grid2D<Int>(input.map { row -> row.map { "$it".toInt() } }) {
    init { transpose() }
}

data class Node(val position: VecNReal, val height: Int, val weight: Int = 1)