this post was submitted on 23 Dec 2024
7 points (100.0% liked)

NotAwfulTech

385 readers
1 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
[email protected]
7
Advent of Code 2024 - the home stretch - it's been an aMAZEing year (awful.systems)
submitted 3 days ago* (last edited 3 days ago) by [email protected] to c/[email protected]
12 comments fedilink hide all child comments
 

current difficulties

  1. Day 21 - Keypad Conundrum: 01h01m23s
  2. Day 17 - Chronospatial Computer: 44m39s
  3. Day 15 - Warehouse Woes: 30m00s
  4. Day 12 - Garden Groups: 17m42s
  5. Day 20 - Race Condition: 15m58s
  6. Day 14 - Restroom Redoubt: 15m48s
  7. Day 09 - Disk Fragmenter: 14m05s
  8. Day 16 - Reindeer Maze: 13m47s
  9. Day 22 - Monkey Market: 12m15s
  10. Day 13 - Claw Contraption: 11m04s
  11. Day 06 - Guard Gallivant: 08m53s
  12. Day 08 - Resonant Collinearity: 07m12s
  13. Day 11 - Plutonian Pebbles: 06m24s
  14. Day 18 - RAM Run: 05m55s
  15. Day 04 - Ceres Search: 05m41s
  16. Day 23 - LAN Party: 05m07s
  17. Day 02 - Red Nosed Reports: 04m42s
  18. Day 10 - Hoof It: 04m14s
  19. Day 07 - Bridge Repair: 03m47s
  20. Day 05 - Print Queue: 03m43s
  21. Day 03 - Mull It Over: 03m22s
  22. Day 19 - Linen Layout: 03m16s
  23. Day 01 - Historian Hysteria: 02m31s
you are viewing a single comment's thread
view the rest of the comments
[–] [email protected] 2 points 2 days ago* (last edited 2 days ago)

21!

Finally managed to beat this one into submission.

P1I created this disgusting mess of a recursive search that happened to work. This problem was really hard to think about due to the levels of indirection. It was also hard because of a bug I introduced into my code that would have been easy to debug with more print statements, but hubris.

P2Recursive solution from P1 was too slow, once I was at 7 robots it was taking minutes to run the code. It didn't take long to realise that you don't really care about where the robots other than the keypad robot and the one controlling the keypad robot are since the boundary of each state needs all the previous robots to be on the A button. So with memoisation, you can calculate all the shortest paths for a given robot to each of the directional inputs in constant time, so O(kn) all up where n is the number of robots (25) and k is the complexity of searching for a path over 5 or 11 nodes.

What helped was looking at the penultimate robot's button choices when moving the keypad robot. After the first one or two levels, the transitions settle into the table in the appendix. I will not explain the code.

appendix

  (P(0, 1), P(0, 1)): [],
  (P(0, 1), P(0, 2)): [btn.r],
  (P(0, 1), P(1, 0)): [btn.d, btn.l],
  (P(0, 1), P(1, 1)): [btn.d],
  (P(0, 1), P(1, 2)): [btn.d, btn.r],
  (P(0, 2), P(0, 1)): [btn.l],
  (P(0, 2), P(0, 2)): [],
  (P(0, 2), P(1, 0)): [btn.d, btn.l, btn.l],
  (P(0, 2), P(1, 1)): [btn.l, btn.d],
  (P(0, 2), P(1, 2)): [btn.d],
  (P(1, 0), P(0, 1)): [btn.r, btn.u],
  (P(1, 0), P(0, 2)): [btn.r, btn.r, btn.u],
  (P(1, 0), P(1, 0)): [],
  (P(1, 0), P(1, 1)): [btn.r],
  (P(1, 0), P(1, 2)): [btn.r, btn.r],
  (P(1, 1), P(0, 1)): [btn.u],
  (P(1, 1), P(0, 2)): [btn.u, btn.r],
  (P(1, 1), P(1, 0)): [btn.l],
  (P(1, 1), P(1, 1)): [],
  (P(1, 1), P(1, 2)): [btn.r],
  (P(1, 2), P(0, 1)): [btn.l, btn.u],
  (P(1, 2), P(0, 2)): [btn.u],
  (P(1, 2), P(1, 0)): [btn.l, btn.l],
  (P(1, 2), P(1, 1)): [btn.l],
  (P(1, 2), P(1, 2)): [],