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

You are viewing a single thread.
View all comments
2 points
*

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
permalink
report
reply
3 points

Hey - I’ve a question about this. Why is it correct? (Or is it?)

If you have two maps for positions in the maze that give (distance to end) and (distance from start), then you can select for points p1, p2 such that

d(p1, p2) + distance-to-end(p1) + distance-to-start(p2) <= best - 100

however, your version seems to assume that distance-to-end(p) = best - distance-to-start(p) - surely this isn’t always the case?

permalink
report
parent
reply
4 points

There is exactly one path without cheating, so yes, the distance to one end is always the total distance minus the distance to the other end.

permalink
report
parent
reply
2 points

Gotcha, thanks. I just re-read the problem statement and looked at the input and my input has the strongest possible version of that constraint: the path is unbranching and has start and end at the extremes. Thank-you!

permalink
report
parent
reply
3 points

(I ask because everyone’s solution seems to make the same assumption - that is, that you’re finding a shortcut onto the same path, as opposed to onto a different path.)

permalink
report
parent
reply
1 point

Some others have answered already, but yes, there was a well-hidden line in the problem description about the map having only a single path from start to end…

permalink
report
parent
reply

Advent Of Code

!advent_of_code@programming.dev

Create post

An unofficial home for the advent of code community on programming.dev!

Advent of Code is an annual Advent calendar of small programming puzzles for a variety of skill sets and skill levels that can be solved in any programming language you like.

AoC 2024

Solution Threads

M T W T F S S
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25

Rules/Guidelines

  • Follow the programming.dev instance rules
  • Keep all content related to advent of code in some way
  • If what youre posting relates to a day, put in brackets the year and then day number in front of the post title (e.g. [2024 Day 10])
  • When an event is running, keep solutions in the solution megathread to avoid the community getting spammed with posts

Relevant Communities

Relevant Links

Credits

Icon base by Lorc under CC BY 3.0 with modifications to add a gradient

console.log('Hello World')

Community stats

  • 483

    Monthly active users

  • 110

    Posts

  • 1.1K

    Comments