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

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

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

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

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

Uiua

Run it here!

How to read this

Uiua has a very helpful (still experimental) astar function built in which returns all valid paths that match your criteria, 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 heuristic cost to destination (here set to constant 1), return confirmation if we've reached a suitable target node (here testing if it's = 9).

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⊙◌ astarNs 1 (=9⊡:Data))⊚=0Data
&p Count!(◴≡◇⊣)
&p Count!∘

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

Julia

Quite happy that today went a lot smoother than yesterday even though I am 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")

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)))
  I = tuple([[x[0] for x in I], [x[1] for x in I]])

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

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

def construct_trees(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_trees(grid)
  trails = trace_back(trees, grid)
  ntrails = len(set(trails))
  ntargets = sum([len(set([tuple(x.coord) for x in levels[-2]])) for levels in trees])

  return ntargets, 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);
    }
}

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

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

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]