Day 20: Race Condition
Megathread guidelines
- Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
- You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL
FAQ
- What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
- Where do I participate?: https://adventofcode.com/
- Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465
3 points
*
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
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);
}
}
2 points
*
Haskell
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
1 point
3 points
*
Haskell
I should probably do something about the n2 loop in Somewhat better (0.575s). Can’t shake the feeling that I’m missing an obvious closed-form solution, though.findCheats, but it’s fast enough for now. Besides, my brain has melted.
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]
1 point
2 points
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.
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
2 points
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
#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);
}
