Radioisotope Thermoelectric Generators

Advent of Code 2016 Day 11

Starting the year at Day 11? Why?

• Day 25 requires having completed Day 12 and Day 23
• Day 23 and Day 12 require having completed Day 11
• So...I'm starting at Day 11, and will attempt to solve all four days: 11, 12, 23, 25

Part 1

1. Not feeling great about this one
2. Documenting the rules
3. Simultaneous: understanding and confusion
4. Brief algorithm: regular expression to extract each floor's items
5. Moving experiments
6. My first successful completion of moves!
7. Shortest path: forever unknown?

Not feeling great about this one

• I have re-read the instructions several times
• minimum required steps is synonymous with shortest path: so this is another of my most dreaded pathfinding puzzles
• I don't feel equipped with the hard skills to solve it algorithmically
• Therefore, it seems like I'll need to attempt solving it similarly to how I attempted solving 2021 Day 23: Amphipod - with pen and paper
• I may attempt to build a simulator...as a way to feel like I've accomplished something, and because it may be fun to use

Documenting the rules

From the instructions

Chips can only be powered by their corresponding RTG. An RTG powering a microchip is still dangerous to other microchips.

• Where the element is A: AM only pairs with AG

If a chip is ever left in the same area as another RTG, and it's not connected to its own RTG, the chip will be fried. Keep chips connected to their corresponding RTG when they're in the same room, and away from other RTGs otherwise.

• If AM is on the same floor as BG, AG must be on the same floor, otherwise it is an invalid move

The elevator can carry at most yourself and two RTGs or microchips in any combination. The elevator will only function if it contains at least one RTG or microchip.

If the floor I'm on has AM, AG, BM, BG, I could take any of the following combinations:

• At least one of them
• At most two of them

From the example walkthrough

• Bring microchip A to a floor containing only its generator: valid, because it gets power
• Bring a pair of microchips to a floor containing a generator of another type: valid, because the microchip is getting power, and the lone generator does no harm
• Leave generators of different types on a floor void of microchips: valid, because they do no harm
• Bring two different microchips to another floor void of generators: valid, because microchips don't affect each other, and the floor contains no generators (let alone generators that are unpaired)
• Bring microchips/generators to a floor with all matching generators/microchips: valid, because everything is getting power

Simultaneous: understanding and confusion

• I feel like I understand the rules
• But I know my puzzle input features several pair of microchips and generators
• Which makes the puzzle far more elaborate
• And likely to require dozens - perhaps hundreds - more steps

The only way from here is simulating the elevator!

Brief algorithm: regular expression to extract each floor's items

My puzzle input's first line is:

The first floor contains a polonium generator, a thulium generator, a thulium-compatible microchip, a promethium generator, a ruthenium generator, a ruthenium-compatible microchip, a cobalt generator, and a cobalt-compatible microchip.

From that, I need to programmatically discern that the first floor contains these items:

polonium generator
thulium generator
thulium-compatible microchip
promethium generator
ruthenium generator
ruthenium-compatible microchip
cobalt generator
cobalt-compatible microchip

The hook I notice is:

• Each item is preceded with a
• Microchips have a -compatible suffix after the element name

Therefore, this regular expression:

/a (\w+)-?/g

• a to hone in on each item
• (\w+) to capture each element name
• -? to identify microchips separately from generators

That regular expression will generate these matches:

a polonium
a thulium
a thulium-
a promethium
a ruthenium
a ruthenium-
a cobalt
a cobalt-

From that, I can leverage the last character in the string to identify the item type, and the first characters to identify the element.

What I seek is a nested array like this for my puzzle input:

[
  ['PO-G', 'TH-M', 'TH-G', 'PR-G', 
   'RU-G', 'RU-M', 'CO-G', 'CO-M'],
  ['PO-M', 'PR-M'],
  [],
  []
]

Moving experiments

Moving two pair

Moving two pair in fewer steps

Failures

My first successful completion of moves!

Each of my failed attempts revealed some intriguing patterns:

• A microchip can only enter a floor: if accompanied by its generator, if the floor contains only other microchip-generator pair, if the floor contains only other generators
• Since the fourth floor accumulates pairs, and moving from that floor back down requires at least one item on the elevator, it seems that the item on the elevator must be the only unpaired generator after moving a paired microchip-generator to the fourth floor
• Generators must be the item most commonly used to transport microchips
• Since the first floor is where nearly everything starts and the fourth floor is where everything ends, I'll need to carefully use the two middle floors to transport one pair and one generator at a time
• There must be a repeatable series of moves that starts and ends with any number of paired microchip-generators and an unpaired generator on the fourth floor
• Then, the last move uses the unpaired generator to fetch the remaining microchip

I did it!

• I moved everything from the first to the fourth floor!
• I examined each move, and they all seem valid!

I counted the moves, submitted the answer, and...

...it is not the correct answer.

Therefore:

• There is either a shorter path
• Or my set of moves is invalid and not the shortest path

Bummer.

Shortest path: forever unknown?

• I tried all sorts of shortcuts based on my working solution
• I re-read the instructions and studied the walkthrough several times

There's one rule that mystifies me:

The elevator always stops on each floor to recharge, and this takes long enough that the items within it and the items on that floor can irradiate each other. (You can prevent this if a Microchip and its Generator end up on the same floor in this way, as they can be connected while the elevator is recharging.)

I don't know what scenario this is calling out.

Unless it is the one depicted in the walkthrough of two microchips joining their generators on another floor?

In which case, I guess I fully understand the rules.

Regardless, I'm stumped.

And this puzzle is starting to frustrate me more than it delightfully challenges me.

Celebrating my accomplishments

• I discovered - by way of animation - one valid path to move all items to the fourth floor!
• I made a ton of GIFs that capture my real-time exploration of the puzzle
• I wrote a regular expression that could have been the start of a simulator

It's not fun starting a year having collected zero stars on the first day, especially when I started with a relatively early day.

But, here I am, bested by another oddly-titled pathfinding puzzle that required me to attempt manually solving it.

To anyone reading this:

• If you can tell me what I'm missing, please leave a comment!