Advent of Code Week 3 - you're lost in a maze of twisty mazes, all alike
Advent of Code Week 3 - you're lost in a maze of twisty mazes, all alike
Problem difficulty so far (up to day 16)
- Day 15 - Warehouse Woes: 30m00s
- Day 12 - Garden Groups: 17m42s
- Day 14 - Restroom Redoubt: 15m48s
- Day 09 - Disk Fragmenter: 14m05s
- Day 16 - Reindeer Maze: 13m47s
- Day 13 - Claw Contraption: 11m04s
- Day 06 - Guard Gallivant: 08m53s
- Day 08 - Resonant Collinearity: 07m12s
- Day 11 - Plutonian Pebbles: 06m24s
- Day 04 - Ceres Search: 05m41s
- Day 02 - Red Nosed Reports: 04m42s
- Day 10 - Hoof It: 04m14s
- Day 07 - Bridge Repair: 03m47s
- Day 05 - Print Queue: 03m43s
- Day 03 - Mull It Over: 03m22s
- Day 01 - Historian Hysteria: 02m31s
You're viewing a single thread.
20: currently a WIP but:
meme
Wait, so it’s all grids? 🧑🏿🚀🔫🧑🏿🚀
Skipping this for now, there are only so many grid maps I can take.
Understandable, have a nice day
ok disco
It took me too long to read the prompt and see that without the shortcuts, it's a single path. I wasted too much time on search algorithms.
P1: Here's what I did: Walk the path. Every time you hit a new grid, check if the two shortcuts you can take will save you 100 ps.
To calculate the shortcut saving:
If you index every grid position on the main path from 0, then it takes X ps to reach position X, The time it takes to travel from start to X, then a shortcut to Y, then from Y to the end, is X + 1 + (main path length - Y). The time saved is then just Y - X - 1, modulo maybe like 5 fence post errors.
P2. The prompt wasn't really clear about whether or not cheating meant you can only travel through one set of walls before your cheat ends, or if it meant you could just move through walls for 20ps to wherever you could reach. Turns out, it's the latter.
The above formula is then a special case of Y - X - manhattan distance(X, Y).