NotAwfulTech

386 readers

8 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

self@awful.systems

Advent of Code 2024 - the home stretch - it's been an aMAZEing year (awful.systems)

submitted 1 day ago* (last edited 1 day ago) by gerikson@awful.systems to c/notawfultech@awful.systems

10 comments fedilink hide all child comments

current difficulties

Day 21 - Keypad Conundrum: 01h01m23s
Day 17 - Chronospatial Computer: 44m39s
Day 15 - Warehouse Woes: 30m00s
Day 12 - Garden Groups: 17m42s
Day 20 - Race Condition: 15m58s
Day 14 - Restroom Redoubt: 15m48s
Day 09 - Disk Fragmenter: 14m05s
Day 16 - Reindeer Maze: 13m47s
Day 22 - Monkey Market: 12m15s
Day 13 - Claw Contraption: 11m04s
Day 06 - Guard Gallivant: 08m53s
Day 08 - Resonant Collinearity: 07m12s
Day 11 - Plutonian Pebbles: 06m24s
Day 18 - RAM Run: 05m55s
Day 04 - Ceres Search: 05m41s
Day 23 - LAN Party: 05m07s
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 19 - Linen Layout: 03m16s
Day 01 - Historian Hysteria: 02m31s

you are viewing a single comment's thread
view the rest of the comments

[–] swlabr@awful.systems 2 points 22 hours ago* (last edited 22 hours ago)

21!

Finally managed to beat this one into submission.

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

Recursive 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)): [],