this post was submitted on 16 Dec 2024
12 points (100.0% liked)

NotAwfulTech

385 readers
4 users here now

a community for posting cool tech news you don’t want to sneer at

non-awfulness of tech is not required or else we wouldn’t have any posts

founded 1 year ago
MODERATORS
 

Problem difficulty so far (up to day 16)

  1. Day 15 - Warehouse Woes: 30m00s
  2. Day 12 - Garden Groups: 17m42s
  3. Day 14 - Restroom Redoubt: 15m48s
  4. Day 09 - Disk Fragmenter: 14m05s
  5. Day 16 - Reindeer Maze: 13m47s
  6. Day 13 - Claw Contraption: 11m04s
  7. Day 06 - Guard Gallivant: 08m53s
  8. Day 08 - Resonant Collinearity: 07m12s
  9. Day 11 - Plutonian Pebbles: 06m24s
  10. Day 04 - Ceres Search: 05m41s
  11. Day 02 - Red Nosed Reports: 04m42s
  12. Day 10 - Hoof It: 04m14s
  13. Day 07 - Bridge Repair: 03m47s
  14. Day 05 - Print Queue: 03m43s
  15. Day 03 - Mull It Over: 03m22s
  16. Day 01 - Historian Hysteria: 02m31s
you are viewing a single comment's thread
view the rest of the comments
[–] [email protected] 4 points 1 week ago (2 children)

16!

p1I 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.

p2If 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

[–] [email protected] 3 points 1 week ago

Fun fact, dijk means dike (the land/water barrier) in Dutch.

[–] [email protected] 3 points 1 week ago

16 commentaryDFS (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.