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
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
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?
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.
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!
(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.)
