Day 10: Hoof It

Class {
	#name : 'Day10Solver',
	#superclass : 'AoCSolver',
	#instVars : [
		'trailMap',
		'trailHeads'
	],
	#category : 'AoCDay10',
	#package : 'AoCDay10'
}

Day10Solver >> parseRawData [
	| temp |
	temp := rawData lines collect: [ :row | row collect: #digitValue as: Array ].
	trailMap := Array2D
		            rows: temp size
		            columns: (temp at: 1) size
		            tabulate: [ :r :c | (temp at: r) at: c ].
	trailHeads := OrderedCollection new.
	trailMap withIndicesDo: [ :x :r : c | x = 0 ifTrue: [ trailHeads add: r @ c ] ]
]

Day10Solver >> solvePart1 [
	^ (trailHeads collect: [ :trailHead | self numPathsStartingAt: trailHead unique: false ]) sum
]

Day10Solver >> solvePart2 [
	^ (trailHeads collect: [ :trailHead | self numPathsStartingAt: trailHead unique: true ]) sum
]

Day10Solver >> isPointInRange: aPoint [ 
	^ aPoint > (0@0) and: aPoint <= (trailMap numberOfRows @ trailMap numberOfColumns)
]

Day10Solver >> neighborsOf: aPoint [
	| neighbors height |
	height := trailMap atPoint: aPoint.
	neighbors := {
		             (aPoint + (1 @ 0)).
		             (aPoint + (0 @ 1)).
		             (aPoint - (1 @ 0)).
		             (aPoint - (0 @ 1)) }.
	^ neighbors select: [ :p | (self isPointInRange: p) and: [ (trailMap atPoint: p) = (height + 1) ] ]
]

Day10Solver >> numPathsStartingAt: aPoint unique: aBoolean [
	| curr pathCount |
	curr := aBoolean
		        ifTrue: [ OrderedCollection new ]
		        ifFalse: [ Set new ].
	curr add: aPoint.
	pathCount := 0.
	[ curr isEmpty ] whileFalse: [
		curr := curr flatCollect: [ :p |
			        (trailMap atPoint: p) = 9
				        ifTrue: [ pathCount := pathCount + 1. #(  ) ]
				        ifFalse: [ self neighborsOf: p ] ] ].
	^ pathCount
]

with open('input/10.txt', 'r') as f:
    lines = f.read().splitlines()

grid = {}
for y, line in enumerate(lines):
    for x, char in enumerate(line):
        grid[x + y * 1j] = int(char)

trailheads = [key for key, value in grid.items() if value == 0]

def get_score(trailhead, count_distinct_paths=False):
    score = 0
    queue = [trailhead]
    encountered_positions = set()
    while len(queue) > 0:
        position = queue.pop(0)
        if position in encountered_positions:
            continue
        if not count_distinct_paths:
            encountered_positions.add(position)
        elevation = grid[position]
        if elevation == 9:
            score += 1
            continue
        surrounding_positions = [position + direction for direction in [1, -1, 1j, -1j] if position + direction in grid and grid[position + direction] == elevation + 1]
        queue.extend(surrounding_positions)
    return score


print("Part 1:", sum(get_score(trailhead) for trailhead in trailheads))
print("Part 2:", sum(get_score(trailhead, count_distinct_paths=True) for trailhead in trailheads))

/* Advent of Code 2024
 * Day 10: Hoof It
 */

#import "Basic";
#import "File";
#import "Hash";
#import "Hash_Table";
#import "String";

Vector2_Int :: struct {
    x, y: int;
}

Vector2_Int_Set :: Table(
    Vector2_Int,
    void,
    (vector: Vector2_Int) -> u32 {
        return inline sdbm_hash(xx *vector, size_of(Vector2_Int));
    },
    (a: Vector2_Int, b: Vector2_Int) -> bool {
        return a.x == b.x && a.y == b.y;
    }
);

main :: () {
    input, success := read_entire_file("inputs/day_10.txt");
    assert(success);

    map: [..][..] int;
    defer {
        for map {
            array_free(it);
        }

        array_free(map);
    }

    trailheads: [..] Vector2_Int;
    defer array_free(trailheads);

    for line, y: split(input, "\n") {
        if line == "" {
            continue;
        }

        row: [..] int;
        for char, x: line {
            array_add(*row, char - #char "0");

            if char == #char "0" {
                array_add(*trailheads, .{x, y});
            }
        }

        array_add(*map, row);
    }

    width := map[0].count;
    height := map.count;

    score_sum := 0;
    rating_sum := 0;

    for trailheads {
        trails: [..][..] Vector2_Int;
        defer array_free(trails);

        trail: [..] Vector2_Int;
        array_add(*trail, it);
        array_add(*trails, trail);

        reachable_peaks: Vector2_Int_Set;
        defer deinit(*reachable_peaks);

        while trails.count {
            trail := pop(*trails);
            defer array_free(trail);

            tile := trail[trail.count - 1];
            current_height := map[tile.y][tile.x];

            for Vector2_Int.[
                .{tile.x - 1, tile.y},
                .{tile.x + 1, tile.y},
                .{tile.x, tile.y - 1},
                .{tile.x, tile.y + 1}
            ] {
                if
                    it.x >= 0 && it.x < width && it.y >= 0 && it.y < height
                    && map[it.y][it.x] == current_height + 1
                {
                    if map[it.y][it.x] == 9 {
                        if !table_contains(*reachable_peaks, it) {
                            table_add(*reachable_peaks, it, #run {});
                        }

                        rating_sum += 1;
                    } else {
                        new_trail: [..] Vector2_Int;
                        array_copy(*new_trail, trail);
                        array_add(*new_trail, it);
                        array_add(*trails, new_trail);
                    }
                }
            }
        }

        score_sum += reachable_peaks.count;
    }

    print("Part 1: %\nPart 2: %\n", score_sum, rating_sum);
}

I went with another recursive function for this one. Seemed like a good way to stretch myself a bit! Also similar to some previous puzzles this year, I set up a directions array containing basic walk functions for each cardinal direction.

My solution searches the map for possible trailheads (0) and for each one it kicks off a recursive function that does the following:

1. Sets up an array (actually passed to it as an arg because recursive) to track the coords of all end positions that have been identified. Like with my Day 8 solution I'm storing these as strings to speed up uniqueness checks.
2. Loops through the four directions and calls each walk function to get neighbor coords. For each of those, it validates that they are both in bounds and that the corresponding elevation is exactly one higher than that of the current coords.
3. If the neighbor was determined to be valid in step 2, it checks if it's a trail end (9). If so, it pushes the current coordinates to the array of known ends. (In Part 1, a uniqueness check flag is true to ensure the coords are only pushed if they're not already in the array.) If the current position is not a trail end, the function recurses.
4. Finally the length of the known end position array is checked and those are totaled for all of the trailheads.

type InputData = number[][];
type Directions = Array<(row: number, col: number) => [number, number]>;
type RecursiveFunc = (
  coords: [number, number],
  map: InputData,
  knownEnds: string[],
  shouldCountUniqueEndsOnly?: boolean
) => string[];

function formatInput(input: string): InputData {
  return input
    .trim()
    .split('\n')
    .map(line => line.split('').map(char => Number(char)));
}

const directions: Directions = [
  (row, col) => [row - 1, col], // up
  (row, col) => [row, col + 1], // right
  (row, col) => [row + 1, col], // down
  (row, col) => [row, col - 1], // left
];

const recursiveFindTrailEnds: RecursiveFunc = ([row, col], map, knownEnds, shouldCountUniqueEndsOnly = false) => {
  let clonedKnownEnds = [...knownEnds];
  for (const direction of directions) {
    const [nextRow, nextCol] = direction(row, col);
    if (nextRow < map.length && nextRow >= 0 && nextCol < map[0].length && nextCol >= 0) {
      if (map[nextRow][nextCol] === map[row][col] + 1) {
        const coordString = `[${nextRow}, ${nextCol}]`;
        if (map[nextRow][nextCol] === 9 && (!shouldCountUniqueEndsOnly || !clonedKnownEnds.includes(coordString))) {
          clonedKnownEnds.push(coordString);
          continue;
        }
        clonedKnownEnds = [
          ...recursiveFindTrailEnds([nextRow, nextCol], map, clonedKnownEnds, shouldCountUniqueEndsOnly),
        ];
      }
    }
  }
  return clonedKnownEnds;
};

export function run(input: string): string[] {
  const data = formatInput(input);

  const sumTrailheadScores = (map: InputData): number => {
    let total = 0;
    for (let row = 0; row < map.length; row++) {
      for (let col = 0; col < map[0].length; col++) {
        if (map[row][col] === 0) {
          const knownEnds = recursiveFindTrailEnds([row, col], map, [], true);
          total += knownEnds.length;
        }
      }
    }
    return total;
  };

  const sumTrailheadRatings = (map: InputData): number => {
    let total = 0;
    for (let row = 0; row < map.length; row++) {
      for (let col = 0; col < map[0].length; col++) {
        if (map[row][col] === 0) {
          const knownEnds = recursiveFindTrailEnds([row, col], map, []);
          total += knownEnds.length;
        }
      }
    }
    return total;
  };

  return [`${sumTrailheadScores(data)}`, `${sumTrailheadRatings(data)}`];
}

pub fn part1(input: &PuzzleInput) -> String {
    let heads = trail_heads(input);
    let mut scores = Vec::new();

    for head in heads {
        let score = trail_head_score(input, head);
        scores.push(score);
    }

    scores.iter().sum::<usize>().to_string()
}

fn trail_head_score(input: &PuzzleInput, head: Coordinate) -> usize {
    let start = head;
    let mut seen = HashSet::new();

    let mut successors = move |p: &Coordinate| {
        let mut result = Vec::new();

        if input.map.get(*p) == Some(&9) {
            return result;
        }

        for dir in Direction::cardinal() {
            let neighbor = p.neighbor(dir);
            if let Some(n) = input.map.get(neighbor) {
                if *n == input.map.get(*p).unwrap() + 1 {
                    if seen.insert(neighbor) {
                        result.push(neighbor);
                    }
                }
            }
        }

        result
    };

    let mut score = 0;
    let mut bfs = BrFS::new(vec![start]);
    while let Some(next) = bfs.next(&mut successors) {
        if input.map.get(next) == Some(&9) {
            score += 1;
        }
    }

    score
}

pub fn trail_heads(input: &PuzzleInput) -> Vec<Coordinate> {
    input
        .map
        .iter()
        .filter(|(_, &c)| c == 0)
        .map(|(p, _)| p)
        .collect_vec()
}

pub fn part2(input: &PuzzleInput) -> String {
    let heads = trail_heads(input);
    let mut scores = Vec::new();

    for head in heads {
        let score = trail_destination_score(input, head);
        scores.push(score);
    }

    scores.iter().sum::<usize>().to_string()
}

fn destinations(input: &PuzzleInput) -> Vec<Coordinate> {
    input
        .map
        .iter()
        .filter(|(_, &c)| c == 9)
        .map(|(p, _)| p)
        .collect_vec()
}

fn trail_destination_score(input: &PuzzleInput, head: Coordinate) -> usize {
    let destinations = destinations(input);

    let mut successors = move |p: &(Coordinate, Vec<Coordinate>)| {
        let (current, trail) = p;

        let mut result = Vec::new();

        if *current == head {
            return result;
        }

        for dir in Direction::cardinal() {
            let neighbor = current.neighbor(dir);

            if let Some(n) = input.map.get(neighbor) {
                if *n + 1 == *input.map.get(*current).unwrap() {
                    let mut trail = trail.clone();
                    trail.push(neighbor);

                    //if seen.insert((neighbor, trail.clone())) {
                    result.push((neighbor, trail));
                    //}
                }
            }
        }

        result
    };

    let mut score = 0;
    let mut bfs = BrFS::new(destinations.iter().map(|d| (*d, vec![*d])).collect_vec());
    while let Some((next, _d)) = bfs.next(&mut successors) {
        if next == head {
            score += 1;
        }
    }

    score
}

pub struct BrFS<N>
where
    N: Clone,
{
    queue: VecDeque<N>,
}

impl<N> BrFS<N>
where
    N: Clone,
{
    pub fn new<IN>(start: IN) -> Self
    where
        IN: IntoIterator<Item = N>,
    {
        let mut queue = VecDeque::new();

        for s in start.into_iter() {
            queue.push_back(s.clone());
        }

        Self { queue }
    }

    pub fn next<S, IN>(&mut self, mut successors: S) -> Option<N>
    where
        S: FnMut(&N) -> IN,
        IN: IntoIterator<Item = N>,
    {
        if let Some(cur) = self.queue.pop_front() {
            for next in successors(&cur) {
                self.queue.push_back(next.clone());
            }

            return Some(cur);
        }

        None
    }
}

day_10    fastest       │ slowest       │ median        │ mean          │ samples │ iters
├─ part1  259.1 µs      │ 287.9 µs      │ 261.1 µs      │ 264 µs        │ 100     │ 100
╰─ part2  148.3 ms      │ 172.6 ms      │ 151 ms        │ 155.6 ms      │ 100     │ 100

defmodule AdventOfCode.Solution.Year2024.Day10 do
  use AdventOfCode.Solution.SharedParse

  alias AdventOfCode.Grid, as: G

  @impl true
  def parse(input), do: G.from_input(input)

  def part1(grid), do: solve(grid, true)
  def part2(grid), do: solve(grid, false)

  defp solve(grid, uniq?) do
    for {point, ?0} <- grid, reduce: 0 do
      acc -> acc + count_trailheads([point], ?1, grid, uniq?)
    end
  end

  defp count_trailheads(points, ?9, grid, uniq?) do
    length(next(points, ?9, grid, uniq?))
  end

  defp count_trailheads([], target, _, _) when target < ?9, do: 0

  defp count_trailheads(points, target, grid, uniq?) do
    count_trailheads(next(points, target, grid, uniq?), target + 1, grid, uniq?)
  end

  defp next(points, target, grid, uniq?) do
    next_points =
      for point <- points,
          {p, ^target} <- G.adjacent_cells(grid, point, :cardinal) do
        p
      end

    if uniq?, do: Enum.uniq(next_points), else: next_points
  end
end

Name             ips        average  deviation         median         99th %
Parse         4.18 K      239.19 μs    ±10.26%      235.29 μs      318.13 μs
Part 1        1.01 K      991.95 μs     ±6.37%      964.33 μs     1198.67 μs
Part 2        0.84 K     1189.14 μs     ±6.19%     1161.58 μs     1395.33 μs

Comparison: 
Parse         4.18 K
Part 1        1.01 K - 4.15x slower +752.76 μs
Part 2        0.84 K - 4.97x slower +949.95 μs

#! /usr/bin/env racket
#lang racket

(require graph "common.rkt")

(module+ test
  (require rackunit))

(define (map->graph in-map)
  ;; Check if (i1, j1) -> (i2, j2) should be an edge
  ;; Can only be an edge if (map-ref in-map i1 j1) + 1 = (map-ref in-map i2 j2)
  (define (edge? i1 j1 i2 j2)
    (cond
      [(or (out-of-bounds? in-map i1 j1)
           (out-of-bounds? in-map i2 j2)) #f]
      [else (eq? 1 (- (map-ref in-map i2 j2)
                      (map-ref in-map i1 j1)))]))
  ;; Iterate through the entire map and create any edges
  (directed-graph (for*/fold ([edges '()])
                             ([i (length in-map)]
                              [j (length (list-ref in-map i))]
                              [dest (in-list (list (list (sub1 i) j)
                                                   (list (add1 i) j)
                                                   (list i (sub1 j))
                                                   (list i (add1 j))))])
                    (cond
                      [(edge? i j (first dest) (second dest))
                       (let* ([start (list i j)]
                              [new-edge (list start dest)])
                         (cons new-edge edges))]
                      [else edges]))))

;; Get the coordinates of all 0s on the map
(define (trailhead-coords in-map)
  (for*/fold ([trailhead-coords '()])
             ([i (length in-map)]
              [j (length (list-ref in-map i))])
    (cond
      [(zero? (map-ref in-map i j)) (cons (list i j) trailhead-coords)]
      [else trailhead-coords])))
;; Get the coordinates of all 9s on the map
(define (peak-coords in-map)
  (for*/fold ([trailhead-coords '()])
             ([i (length in-map)]
              [j (length (list-ref in-map i))])
    (cond
      [(= 9 (map-ref in-map i j)) (cons (list i j) trailhead-coords)]
      [else trailhead-coords])))

;; Calculate if a path exists for a single trailhead->peak pair
(define (has-path? g trailhead peak)
  (let helper ((v trailhead) (visited '()))
    (cond
      ;; found a path
      [(equal? v peak) 1]
      [else (for/or ([neighbor (in-list (get-neighbors g v))])
              (cond
                ;; Already visited this vertex
                [(member neighbor visited) 0]
                [else (helper neighbor (cons v visited))]))])))

;; Calculate the rating for a single trailhead->peak pair.
;; This is essentially (has-path?) but it doesn't return
;; as soon as it finds a path.
(define (rating g trailhead peak)
  (let helper ((v trailhead) (visited '()))
    (cond
      ;; found a path
      [(equal? v peak) 1]
      [else (for/sum ([neighbor (in-list (get-neighbors g v))])
              (cond
                ;; Already visited this vertex
                [(member neighbor visited) 0]
                [else (helper neighbor (cons v visited))]))])))


(define (day10/run-part01 in-map)
  (let ([map-graph (map->graph in-map)]
        [trailhead-coords (trailhead-coords in-map)]
        [peak-coords (peak-coords in-map)])
    ;; For each trailhead->peak pair, see if there's a path.
    ;; If there is, add 1 to our sum of paths.
    (for*/sum ([trailhead-coord (in-list trailhead-coords)]
               [peak-coord (in-list peak-coords)])
      (cond
        [(fewest-vertices-path map-graph trailhead-coord peak-coord) 1]
        [else 0]))))

(define (day10/run-part01-better in-map)
  (let ([map-graph (map->graph in-map)]
        [trailhead-coords (trailhead-coords in-map)]
        [peak-coords (peak-coords in-map)])
    ;; For each trailhead->peak pair, see if there's a path.
    ;; If there is, add 1 to our sum of paths.
    (for*/sum ([trailhead-coord (in-list trailhead-coords)]
               [peak-coord (in-list peak-coords)])
      (if (has-path? map-graph trailhead-coord peak-coord)
          1
          0))))

(define (day10/run-part02 in-map)
  (let ([map-graph (map->graph in-map)]
        [trailhead-coords (trailhead-coords in-map)]
        [peak-coords (peak-coords in-map)])
    ;; For each trailhead->peak pair, see if there's a path.
    ;; If there is, add 1 to our sum of paths.
    (for*/sum ([trailhead-coord (in-list trailhead-coords)]
               [peak-coord (in-list peak-coords)])
      (rating map-graph trailhead-coord peak-coord))))

(module+ test
  (check-equal? (day10/run-part01 (input->list-numbers (open-input-file "examples/day10_1.in")))   2 "Test part 1: 1")
  (check-equal? (day10/run-part01 (input->list-numbers (open-input-file "examples/day10_2.in")))   4 "Test part 1: 2")
  (check-equal? (day10/run-part01 (input->list-numbers (open-input-file "examples/day10_3.in")))   3 "Test part 1: 3")
  (check-equal? (day10/run-part01 (input->list-numbers (open-input-file "examples/day10_4.in")))  36 "Test part 1: 4")
  (check-equal? (day10/run-part02 (input->list-numbers (open-input-file "examples/day10_5.in")))   3 "Test part 2: 1")
  (check-equal? (day10/run-part02 (input->list-numbers (open-input-file "examples/day10_6.in")))  13 "Test part 2: 2")
  (check-equal? (day10/run-part02 (input->list-numbers (open-input-file "examples/day10_7.in"))) 227 "Test part 2: 3")
  (check-equal? (day10/run-part02 (input->list-numbers (open-input-file "examples/day10_4.in")))  81 "Test part 2: 4"))

;; Run against my input and print the results
(module+ main
  (let* ([in-port (open-input-file "inputs/day10.in")]
         [in-map (input->list-numbers in-port)]
         [part1 (day10/run-part01-better in-map)]
         [part2 (day10/run-part02 in-map)])
    (printf "Part 1: ~a, Part 2: ~a\n" part1 part2)))