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)

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

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

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

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

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

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

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

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

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

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]

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

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