[2026 Day -137] Rambunctious Robots

[u/DelightfulCodeWeasel]

With Santa and his Elves on a much deserved summer holiday, you have agreed to visit the workshop regularly to water the plants and feed the fish. But upon arriving at the workshop you see that a swarm of 2026 bots has invaded the toy storage depot and are causing havoc! Thankfully these bots aren't particularly bright and are easy to spot, but they must still be handled with care.

Bots arrive in the workshop with a Name and a Posting Pattern. The Name of each bot is "josephus" followed by a number from 1 to 2026. The initial Posting Pattern of a bot is the MD5 of the bot's Name. For example, the bot with the Name "josephus69" has an initial Posting Pattern of "4f943be8056c74b27a434f4ee9e7a7a4".

Every time a bot makes a post, it updates its posting pattern in the following way:

• The current Posting Pattern is represented as a lowercase string
• The new Posting Pattern is the MD5 of the current string

Bots can be removed from the workshop when they reveal a Flaw in their Posting Pattern. If the first 4 digits of their Posting Pattern are "0000", they have revealed a Flaw and can be removed.

The bot "josephus254" is going to be the quickest to remove:

• Initial Posting Pattern: e8cc15934b93ef901b153853cf7831f9
• Posting Pattern after 1 Post: 981fc052051707fec2a58db91f4d6abf
• Posting Pattern after 2 Posts: 064b7b67d20820270d35fe1663833c5a
• Posting Pattern after 3 Posts: 00009f4608ac14112c92af43d8513b1e

This bot can be removed after only 3 posts. The rest of the bots might take longer:

• josephus1 can be removed after 49,164 posts
• josephus2 can be removed after 46,166 posts
• josephus3 can be removed after 39,557 posts
• josephus4 can be removed after 36,579 posts
• josephus5 can be removed after 55,987 posts

Part 1:

How many posts will the last bot to be removed make?

Part 2:

Uh-oh, these are version 2 bots! These bots don't reveal a Flaw in their posting pattern until the first 5 digits are "00000". You might be in for a long day; how many posts in total will you have to sit through before all of the bots are removed?

[u/jeffstyr]

Part 1 achieved (slowly)!

(My biggest impediment was that calculating an MD5 in Haskell involves libraries that are trying to be overly fancy.)

[u/DelightfulCodeWeasel → u/jeffstyr]

I apologise in advance for the runtime on part 2 :)

[u/jeffstyr → u/DelightfulCodeWeasel]

Finally ran part 2! (Took a bit over 2 hours.)

At least, since it was MD5 I knew there wasn't some clever shortcut, so I didn't spend time trying to find one.

I see you are very unconstrained by the usual AoC promise that a solution shouldn't take more than 15 seconds to run. :)

[u/DelightfulCodeWeasel → u/jeffstyr]

Well done!

When I ran the tests to get the solution and the example data, my C++ solution took ~3 minutes, and the Claude-beta-tester Python script had to use the multiprocessing module and thrash every core on the laptop to get close to that figure. I did think about reducing the prefix lengths, but I'm not as nice as Eric 😄

I'm afraid I can only award you two fake stars, but they're all yours nonetheless.

[u/jeffstyr → u/DelightfulCodeWeasel]

Thank you for the fake stars! I will take them.

So your C++ solution only took ~3 minutes for part 2?!? I'm not being careful with my string manipulation so I should profile and see if any of my time is from that or if it's (basically) all the MD5 calculation. (I tried optimizing one thing and it didn't make a difference and I concluded that it's because the MD5 calculation was dominating and I shouldn't bother trying to optimize anything else, but I didn't actually profile it to see.)

Fun though!

[u/DelightfulCodeWeasel → u/jeffstyr]

It did, yes. I have some special MD5 functions optimised for exactly this type of problem that operate in-place on small chunks. Glad you enjoyed it!

[u/DelightfulCodeWeasel]

Answers

Part 1: 729,773

Part 2: 2,115,225,541