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

::: spoiler The Code

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

I should probably do something about the n^2^ 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]

Haskell

::: spoiler solution

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

:::

C

Note to self: reread the puzzle after waking up properly! I initially wrote a great solution for the wrong question (pathfinding with a given number of allowed jumps).

For the actual question, a bit boring but flood fill plus some array iteration saved the day again. Find the cost for every open tile with flood fill, then for each position and offset combination, see if that jump yields a lower cost at the destination.

For arbitrary inputs this would require eliminating the non-optimal paths, but the one path covered all open tiles.

::: spoiler Code

#include "common.h"

#define GB 2	/* safety border on X/Y plane */
#define GZ (GB+141+2+GB)

static char G[GZ][GZ];		/* grid */
static int  C[GZ][GZ];		/* costs */
static int sx,sy, ex,ey;	/* start, end pos */

static void
flood(int x, int y)
{
	int lo = INT_MAX;

	if (x<1 || x>=GZ-1 ||
	    y<1 || y>=GZ-1 || G[y][x]!='.')
		return;

	if (C[y-1][x]) lo = MIN(lo, C[y-1][x]+1);
	if (C[y+1][x]) lo = MIN(lo, C[y+1][x]+1);
	if (C[y][x-1]) lo = MIN(lo, C[y][x-1]+1);
	if (C[y][x+1]) lo = MIN(lo, C[y][x+1]+1);

	if (lo != INT_MAX && (!C[y][x] || lo < C[y][x])) {
		C[y][x] = lo;

		flood(x, y-1); flood(x-1, y);
		flood(x, y+1); flood(x+1, y);
	}
}

static int
count_shortcuts(int lim, int min)
{
	int acc=0, x,y, dx,dy;

	for (y=GB; y<GZ-GB; y++)
	for (x=GB; x<GZ-GB; x++)
	for (dy = -lim; dy <= lim; dy++)
	for (dx = abs(dy)-lim; dx <= lim-abs(dy); dx++)
		acc += x+dx >= 0 && x+dx < GZ &&
		       y+dy >= 0 && y+dy < GZ && C[y][x] &&
		       C[y][x]+abs(dx)+abs(dy) <= C[y+dy][x+dx]-min;

	return acc;
}

int
main(int argc, char **argv)
{
	int x,y;

	if (argc > 1)
		DISCARD(freopen(argv[1], "r", stdin));
	for (y=2; fgets(G[y]+GB, GZ-GB*2, stdin); y++)
		assert(y < GZ-3);

	for (y=GB; y<GZ-GB; y++)
	for (x=GB; x<GZ-GB; x++)
		if (G[y][x] == 'S') { G[y][x]='.'; sx=x; sy=y; } else
		if (G[y][x] == 'E') { G[y][x]='.'; ex=x; ey=y; }

	C[sy][sx] = 1;

	flood(sx, sy-1); flood(sx-1, sy);
	flood(sx, sy+1); flood(sx+1, sy);

	printf("20: %d %d\n",
	    count_shortcuts(2, 100),
	    count_shortcuts(20, 100));

	return 0;
}

:::

https://codeberg.org/sjmulder/aoc/src/branch/master/2024/c/day20.c

Rust

The important part here is to build two maps first that hold for every point on the path the distance to the start and the distance to the end respectively. Then calculating the path length for a cheat vector is a simple lookup. For part 2 I first generated all vectors with manhattan distance <= 20, or more specifically, exactly half of those vectors to avoid checking the same vector in both directions.

Part 2 takes 15ms. The code looks a bit unwieldy at parts and uses the pyramid of doom paradigm but works pretty well.

::: spoiler Solution

use euclid::{default::*, vec2};

const DIRS: [Vector2D<i32>; 4] = [vec2(1, 0), vec2(0, 1), vec2(-1, 0), vec2(0, -1)];
const MIN_SAVE: u32 = 100;
const MAX_DIST: i32 = 20;

fn parse(input: &str) -> (Vec<Vec<bool>>, Point2D<i32>, Point2D<i32>) {
    let mut start = None;
    let mut end = None;
    let mut field = Vec::new();
    for (y, line) in input.lines().enumerate() {
        let mut row = Vec::new();
        for (x, b) in line.bytes().enumerate() {
            row.push(b == b'#');
            if b == b'S' {
                start = Some(Point2D::new(x, y).to_i32());
            } else if b == b'E' {
                end = Some(Point2D::new(x, y).to_i32());
            }
        }
        field.push(row);
    }
    (field, start.unwrap(), end.unwrap())
}

fn distances(
    field: &[Vec<bool>],
    start: Point2D<i32>,
    end: Point2D<i32>,
) -> (Vec<Vec<u32>>, Vec<Vec<u32>>) {
    let width = field[0].len();
    let height = field.len();
    let mut dist_to_start = vec![vec![u32::MAX; width]; height];
    let bounds = Rect::new(Point2D::origin(), Size2D::new(width, height)).to_i32();

    let mut cur = start;
    let mut dist = 0;
    dist_to_start[cur.y as usize][cur.x as usize] = dist;
    while cur != end {
        for dir in DIRS {
            let next = cur + dir;
            if bounds.contains(next)
                && !field[next.y as usize][next.x as usize]
                && dist_to_start[next.y as usize][next.x as usize] == u32::MAX
            {
                cur = next;
                break;
            }
        }
        dist += 1;
        dist_to_start[cur.y as usize][cur.x as usize] = dist;
    }
    let total_dist = dist_to_start[end.y as usize][end.x as usize];
    let dist_to_end = dist_to_start
        .iter()
        .map(|row| {
            row.iter()
                .map(|&d| {
                    if d == u32::MAX {
                        u32::MAX
                    } else {
                        total_dist - d
                    }
                })
                .collect()
        })
        .collect();
    (dist_to_start, dist_to_end)
}

fn cheats(
    field: &[Vec<bool>],
    dist_to_start: &[Vec<u32>],
    dist_to_end: &[Vec<u32>],
    total_dist: u32,
) -> u32 {
    let width = field[0].len();
    let height = field.len();
    let bounds = Rect::new(Point2D::origin(), Size2D::new(width, height)).to_i32();
    let mut count = 0;
    for (y, row) in field.iter().enumerate() {
        for (x, _w) in row.iter().enumerate().filter(|&(_i, w)| *w) {
            let pos = Point2D::new(x, y).to_i32();
            for (d0, &dir0) in DIRS.iter().enumerate().skip(1) {
                for &dir1 in DIRS.iter().take(d0) {
                    let p0 = pos + dir0;
                    let p1 = pos + dir1;
                    if bounds.contains(p0) && bounds.contains(p1) {
                        let p0 = p0.to_usize();
                        let p1 = p1.to_usize();
                        if !field[p0.y][p0.x] && !field[p1.y][p1.x] {
                            let dist = dist_to_start[p0.y][p0.x].min(dist_to_start[p1.y][p1.x])
                                + dist_to_end[p1.y][p1.x].min(dist_to_end[p0.y][p0.x])
                                + 2; // Add 2 for cutting across the wall
                            if total_dist - dist >= MIN_SAVE {
                                count += 1;
                            }
                        }
                    }
                }
            }
        }
    }
    count
}

fn part1(input: String) {
    let (field, start, end) = parse(&input);
    let (dist_to_start, dist_to_end) = distances(&field, start, end);
    let total_dist = dist_to_start[end.y as usize][end.x as usize];
    println!(
        "{}",
        cheats(&field, &dist_to_start, &dist_to_end, total_dist)
    );
}

// Half of all vectors with manhattan distance <= MAX_DIST.
// Only vectors with positive x or going straight down are considered to avoid using the same
// vector twice in both directions.
fn cheat_vectors() -> Vec<Vector2D<i32>> {
    let mut vectors = Vec::new();
    for y in -MAX_DIST..=MAX_DIST {
        let start = if y > 0 { 0 } else { 1 };
        for x in start..=(MAX_DIST - y.abs()) {
            assert!(x + y <= MAX_DIST);
            vectors.push(vec2(x, y));
        }
    }
    vectors
}

fn cheats20(
    field: &[Vec<bool>],
    dist_to_start: &[Vec<u32>],
    dist_to_end: &[Vec<u32>],
    total_dist: u32,
) -> u32 {
    let vectors = cheat_vectors();
    let width = field[0].len();
    let height = field.len();
    let bounds = Rect::new(Point2D::origin(), Size2D::new(width, height)).to_i32();
    let mut count = 0;
    for (y, row) in field.iter().enumerate() {
        for (x, _w) in row.iter().enumerate().filter(|&(_i, w)| !*w) {
            let p0 = Point2D::new(x, y);
            for &v in &vectors {
                let pi1 = p0.to_i32() + v;
                if bounds.contains(pi1) {
                    let p1 = pi1.to_usize();
                    if !field[p1.y][p1.x] {
                        let dist = dist_to_start[p0.y][p0.x].min(dist_to_start[p1.y][p1.x])
                            + dist_to_end[p1.y][p1.x].min(dist_to_end[p0.y][p0.x])
                            + v.x.unsigned_abs()  // Manhattan distance of vector
                            + v.y.unsigned_abs();
                        if total_dist - dist >= MIN_SAVE {
                            count += 1;
                        }
                    }
                }
            }
        }
    }
    count
}

fn part2(input: String) {
    let (field, start, end) = parse(&input);
    let (dist_to_start, dist_to_end) = distances(&field, start, end);
    let total_dist = dist_to_start[end.y as usize][end.x as usize];
    println!(
        "{}",
        cheats20(&field, &dist_to_start, &dist_to_end, total_dist)
    );
}

util::aoc_main!();

:::

Also on github

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

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

C++ / Boost

Ah, cunning - my favourite one so far this year, I think. Nothing too special compared to the other solutions - floods the map using Dijkstra, then checks "every pair" for how much of a time saver it is. 0.3s on my laptop; it iterates through every pair twice since it does part 1 and part 2 separately, which could easily be improved upon.

::: spoiler spoiler

#include <boost/log/trivial.hpp>
#include <boost/unordered/unordered_flat_map.hpp>
#include <boost/unordered/unordered_flat_set.hpp>
#include <cstddef>
#include <fstream>
#include <limits>
#include <queue>
#include <stdexcept>

namespace {

using Loc = std::pair<int, int>;
using Dir = std::pair<int, int>;
template <class T>
using Score = std::pair<size_t, T>;
template <class T>
using MinHeap = std::priority_queue<Score<T>, std::vector<Score<T>>, std::greater<Score<T>>>;
using Map = boost::unordered_flat_set<Loc>;

auto operator+(const Loc &l, const Dir &d) {
  return Loc{l.first + d.first, l.second + d.second};
}

auto manhattan(const Loc &a, const Loc &b) {
  return std::abs(a.first - b.first) + std::abs(a.second - b.second);
}

auto dirs = std::vector<Dir>{
    {0,  -1},
    {0,  1 },
    {-1, 0 },
    {1,  0 }
};

struct Maze {
  Map map;
  Loc start;
  Loc end;
};

auto parse() {
  auto rval = Maze{};
  auto line = std::string{};
  auto ih = std::ifstream{"input/20"};
  auto row = 0;
  while (std::getline(ih, line)) {
    for (auto col = 0; col < int(line.size()); ++col) {
      auto t = line.at(col);
      switch (t) {
      case 'S':
        rval.start = Loc{col, row};
        rval.map.insert(Loc{col, row});
        break;
      case 'E':
        rval.end = Loc{col, row};
        rval.map.insert(Loc{col, row});
        break;
      case '.':
        rval.map.insert(Loc{col, row});
        break;
      case '#':
        break;
      default:
        throw std::runtime_error{"oops"};
      }
    }
    ++row;
  }
  return rval;
}

auto dijkstra(const Maze &m) {
  auto unvisited = MinHeap<Loc>{};
  auto visited = boost::unordered_flat_map<Loc, size_t>{};

  for (const auto &e : m.map)
    visited[e] = std::numeric_limits<size_t>::max();

  visited[m.start] = 0;
  unvisited.push({0, {m.start}});

  while (!unvisited.empty()) {
    auto next = unvisited.top();
    unvisited.pop();

    if (visited.at(next.second) < next.first)
      continue;

    for (const auto &dir : dirs) {
      auto prospective = Loc{next.second + dir};
      if (!visited.contains(prospective))
        continue;
      auto pscore = next.first + 1;
      if (visited.at(prospective) > pscore) {
        visited[prospective] = pscore;
        unvisited.push({pscore, prospective});
      }
    }
  }

  return visited;
}

using Walk = decltype(dijkstra(Maze{}));

constexpr auto GOOD_CHEAT = 100;

auto evaluate_cheats(const Walk &walk, int skip) {
  auto rval = size_t{};
  for (auto &start : walk) {
    for (auto &end : walk) {
      auto distance = manhattan(start.first, end.first);
      if (distance <= skip && end.second > start.second) {
        auto improvement = int(end.second) - int(start.second) - distance;
        if (improvement >= GOOD_CHEAT)
          ++rval;
      }
    }
  }
  return rval;
}

} // namespace

auto main() -> int {
  auto p = parse();
  auto walk = dijkstra(p);
  BOOST_LOG_TRIVIAL(info) << "01: " << evaluate_cheats(walk, 2);
  BOOST_LOG_TRIVIAL(info) << "02: " << evaluate_cheats(walk, 20);
}

:::