Haskell

I should probably do something about the n² loop in findCheats, but it’s fast enough for now. Besides, my brain has melted. Somewhat better (0.575s). Can’t shake the feeling that I’m missing an obvious closed-form solution, though.

import Control.Monad
import Data.List
import Data.Map (Map)
import Data.Map qualified as Map
import Data.Maybe
import Data.Set qualified as Set

type Pos = (Int, Int)

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

solveMaze :: Map Pos Char -> Maybe [Pos]
solveMaze maze = listToMaybe $ go [] start
  where
    walls = Map.keysSet $ Map.filter (== '#') maze
    Just [start, end] = traverse (\c -> fst <$> find ((== c) . snd) (Map.assocs maze)) ['S', 'E']
    go h p@(i, j)
      | p == end = return [end]
      | otherwise = do
          p' <- [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]
          guard $ p' `notElem` h
          guard $ p' `Set.notMember` walls
          (p :) <$> go [p] p'

dist (i1, j1) (i2, j2) = abs (i2 - i1) + abs (j2 - j1)

findCheats :: [Pos] -> Int -> Int -> [((Pos, Pos), Int)]
findCheats path minScore maxLen = do
  (t2, end) <- zip [0 ..] path
  (t1, start) <- zip [0 .. t2 - minScore] path
  let len = dist start end
      score = t2 - t1 - len
  guard $ len <= maxLen
  guard $ score >= minScore
  return ((start, end), score)

main = do
  Just path <- solveMaze . readInput <$> readFile "input20"
  mapM_ (print . length . findCheats path 100) [2, 20]

Rust

I was stuck for a while, even after getting a few hints, until I read the problem more closely and realized: there is only one non-cheating path, and every free space is on it. This means that the target of any shortcut is guaranteed to be on the shortest path to the end.

This made things relatively simple. I used Dijkstra to calculate the distance from the start to each space. I then looked at every pair of points: if they are a valid distance away from each other, check how much time I would save jumping from one to the next. If that amount of time is in the range we want, then this is a valid cheat.

https://gitlab.com/bricka/advent-of-code-2024-rust/-/blob/main/src/days/day20.rs?ref_type=heads

// Critical point to note: EVERY free space is on the shortest path.

use itertools::Itertools;

use crate::search::dijkstra;
use crate::solver::DaySolver;
use crate::grid::{Coordinate, Grid};

type MyGrid = Grid<MazeElement>;

enum MazeElement {
    Wall,
    Free,
    Start,
    End,
}

impl MazeElement {
    fn is_free(&self) -> bool {
        !matches!(self, MazeElement::Wall)
    }
}

fn parse_input(input: String) -> (MyGrid, Coordinate) {
    let grid: MyGrid = input.lines()
        .map(|line| line.chars().map(|c| match c {
            '#' => MazeElement::Wall,
            '.' => MazeElement::Free,
            'S' => MazeElement::Start,
            'E' => MazeElement::End,
            _ => panic!("Invalid maze element: {}", c)
        })
             .collect())
        .collect::<Vec<Vec<MazeElement>>>()
        .into();

    let start_pos = grid.iter().find(|(_, me)| matches!(me, MazeElement::Start)).unwrap().0;

    (grid, start_pos)
}

fn solve<R>(grid: &MyGrid, start_pos: Coordinate, min_save_time: usize, in_range: R) -> usize
where R: Fn(Coordinate, Coordinate) -> bool {
    let (cost_to, _) = dijkstra(
        start_pos,
        |&c| grid.orthogonal_neighbors_iter(c)
            .filter(|&n| grid[n].is_free())
            .map(|n| (n, 1))
            .collect()
    );

    cost_to.keys()
        .cartesian_product(cost_to.keys())
        .map(|(&c1, &c2)| (c1, c2))
        // We don't compare with ourself
        .filter(|&(c1, c2)| c1 != c2)
        // The two points need to be within range
        .filter(|&(c1, c2)| in_range(c1, c2))
        // We need to save at least `min_save_time`
        .filter(|(c1, c2)| {
            // Because we are working with `usize`, the subtraction
            // could underflow. So we need to use `checked_sub`
            // instead, and check that a) no underflow happened, and
            // b) that the time saved is at least the minimum.
            cost_to.get(c2).copied()
                .and_then(|n| n.checked_sub(*cost_to.get(c1).unwrap()))
                .and_then(|n| n.checked_sub(c1.distance_to(c2)))
                .map(|n| n >= min_save_time)
                .unwrap_or(false)
        })
        .count()
}

pub struct Day20Solver;

impl DaySolver for Day20Solver {
    fn part1(&self, input: String) -> String {
        let (grid, start_pos) = parse_input(input);
        solve(
            &grid,
            start_pos,
            100,
            |c1, c2| c1.distance_to(&c2) == 2,
        ).to_string()
    }

    fn part2(&self, input: String) -> String {
        let (grid, start_pos) = parse_input(input);
        solve(
            &grid,
            start_pos,
            100,
            |c1, c2| c1.distance_to(&c2) <= 20,
        ).to_string()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_part1() {
        let input = include_str!("../../inputs/test/20");
        let (grid, start_pos) = parse_input(input.to_string());
        let actual = solve(&grid, start_pos, 1, |c1, c2| c1.distance_to(&c2) == 2);
        assert_eq!(44, actual);
    }

    #[test]
    fn test_part2() {
        let input = include_str!("../../inputs/test/20");
        let (grid, start_pos) = parse_input(input.to_string());
        let actual = solve(&grid, start_pos, 50, |c1, c2| c1.distance_to(&c2) <= 20);
        assert_eq!(285, actual);
    }
}

Haskell

First parse and floodfill from start, each position then holds the distance from the start

For part 1, I check all neighbor tiles of neighbor tiles that are walls and calculate the distance that would’ve been in-between.

In part 2 I check all tiles within a manhattan distance <= 20 and calculate the distance in-between on the path. Then filter out all cheats <100 and count

Takes 1.4s sadly, I believe there is still potential for optimization.

Edit: coding style

import Control.Arrow

import qualified Data.List as List
import qualified Data.Set as Set
import qualified Data.Map as Map
import qualified Data.Maybe as Maybe

parse s = Map.fromList [ ((y, x), c) | (l, y) <- zip ls [0..], (c, x) <- zip l [0..]]
        where
        ls = lines s

floodFill m = floodFill' m startPosition (Map.singleton startPosition 0)
        where
                startPosition = Map.assocs
                        >>> filter ((== 'S') . snd)
                        >>> head
                        >>> fst
                        $ m

neighbors (p1, p2) = [(p1-1, p2), (p1, p2-1), (p1, p2+1), (p1+1, p2)]

floodFill' m p f
        | m Map.! p == 'E' = f
        | otherwise = floodFill' m n f'
        where
                seconds = f Map.! p
                ns = neighbors p
                n = List.filter ((m Map.!) >>> (`Set.member` (Set.fromList ".E")))
                        >>> List.filter ((f Map.!?) >>> Maybe.isNothing)
                        >>> head
                        $ ns
                f' = Map.insert n (succ seconds) f

taxiCabDistance (a1, a2) (b1, b2) = abs (a1 - b1) + abs (a2 - b2)

calculateCheatAdvantage f (p1, p2) = c2 - c1 - taxiCabDistance p1 p2
        where
                c1 = f Map.! p1
                c2 = f Map.! p2

cheatDeltas :: Int -> Int -> [(Int, Int)]
cheatDeltas l h = [(y, x) | x <- [-h..h], y <- [-h..h], let d = abs x + abs y, d <= h, d >= l]

(a1, a2) .+. (b1, b2) = (a1 + b1, a2 + b2)

solve l h (f, ps) = Set.toList
        >>> List.map ( repeat
                >>> zip (cheatDeltas l h)
                >>> List.map (snd &&& uncurry (.+.))
                >>> List.filter (snd >>> (`Set.member` ps))
                >>> List.map (calculateCheatAdvantage f)
                >>> List.filter (>= 100)
                >>> List.length
                )
        >>> List.sum
        $ ps
part1 = solve 2 2
part2 = solve 1 20

main = getContents
        >>= print
        . (part1 &&& part2)
        . (id &&& Map.keysSet)
        . floodFill
        . parse

Haskell

import Control.Arrow
import Data.Array.Unboxed
import Data.Functor
import Data.List
import Data.Map qualified as M
import Data.Set qualified as S

type Pos = (Int, Int)
type Board = Array Pos Char
type Path = M.Map Pos Int

parse board = listArray ((1, 1), (length l, length $ head l)) (concat l)
  where
    l = lines board

moves :: Pos -> [Pos]
moves p = [first succ p, first pred p, second succ p, second pred p]

getOrigin :: Board -> Maybe Pos
getOrigin = fmap fst . find ((== 'S') . snd) . assocs

getPath :: Board -> Pos -> [Pos]
getPath board p
    | not $ inRange (bounds board) p = []
    | board ! p == 'E' = [p]
    | board ! p == '#' = []
    | otherwise = p : (moves p >>= getPath (board // [(p, '#')]))

taxiCab (xa, ya) (xb, yb) = abs (xa - xb) + abs (ya - yb)

solve dist board = do
    path <- M.fromList . flip zip [1 ..] <$> (getOrigin board <&> getPath board)
    let positions = M.keys path
        jumps = [ (path M.! a) - (path M.! b) - d | a <- positions, b <- positions, d <- [taxiCab a b], d <= dist]
    return $ length $ filter (>=100) jumps

main = getContents >>= print . (solve 2 &&& solve 20) . parse

Dart

Simple path-finding + brute force. O(n*sqrt-n) I think but only takes ~200 milliseconds so that’ll do for today. Time to walk the dog!

After being so pleased to have written my own path-finding algorithm the other day, I discovered that my regular more library already includes one. D’oh.

(edit: shaved some milliseconds off)

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

List<Point<num>> d4 = [Point(1, 0), Point(-1, 0), Point(0, 1), Point(0, -1)];

List<Point<num>> findPath(List<String> lines) {
  var maze = {
    for (var r in lines.indexed())
      for (var c in r.value.split('').indexed().where((e) => e.value != '#'))
        Point<num>(c.index, r.index): c.value
  }.withDefault('#');
  var path = AStarSearchIterable<Point>(
      startVertices: [maze.entries.firstWhere((e) => e.value == 'S').key],
      successorsOf: (p) => d4.map((e) => (e + p)).where((n) => maze[n] != '#'),
      costEstimate: (p) => 1,
      targetPredicate: (p) => maze[p] == 'E').first.vertices;
  return path;
}

num dist(Point p1, Point p2) => (p1.x - p2.x).abs() + (p1.y - p2.y).abs();

solve(List<String> lines, int cheat, int target) {
  List<Point<num>> path = findPath(lines);
  var cheats = 0;
  for (int s = 0; s < path.length - cheat; s++) {
    for (int e = s + cheat; e < path.length; e++) {
      var d = dist(path[e], path[s]);
      var diff = e - s - d;
      if (d <= cheat && diff >= target) cheats += 1;
    }
  }
  return cheats;
}