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.
16!
p1
I used A*, though mathematically I would have been fine with Dijkstra's. Also, here's how I remember how to spell Dijkstra: ijk is in alphabetical order.
p2
If you've implemented path/back tracking on a search algo before, this wasn't too bad, though instead of tracking best parent you need to track equivalently best parents. Woke AOC trying to normalise families with more than two parents, SMH
16 commentary
DFS (it's all dfs all the time now, this is my life now, thanks AOC) pruned by unless-I-ever-passed-through-here-with-a-smaller-score-before worked well enough for Pt1. In Pt2 in order to get all the paths I only had to loosen the filter by a) not pruning for equal scores and b) only prune if the direction also matched.
Pt2 was easier for me because while at first it took me a bit to land on lifting stuff from Djikstra's algo to solve the challenge maze before the sun turns supernova, as I tend to store the paths for debugging anyway it was trivial to group them by score and count by distinct tiles.
Fun fact, dijk means dike (the land/water barrier) in Dutch.