Advent of Code - 2021

This is a solution to Day 23 of Advent of Code 2021.

Day 23 - Amphipod

A group of amphipods notice your fancy submarine and flag you down. "With such an impressive shell," one amphipod says, "surely you can help us with a question that has stumped our best scientists."

They go on to explain that a group of timid, stubborn amphipods live in a nearby burrow. Four types of amphipods live there: Amber (A), Bronze (B), Copper (C), and Desert (D). They live in a burrow that consists of a hallway and four side rooms. The side rooms are initially full of amphipods, and the hallway is initially empty.

They give you a diagram of the situation (your puzzle input), including locations of each amphipod (A, B, C, or D, each of which is occupying an otherwise open space), walls (#), and open space (.).

For example:
#############
#...........#
###B#C#B#D###
  #A#D#C#A#
  #########
The amphipods would like a method to organize every amphipod into side rooms so that each side room contains one type of amphipod and the types are sorted A-D going left to right, like this:
#############
#...........#
###A#B#C#D###
  #A#B#C#D#
  #########
Amphipods can move up, down, left, or right so long as they are moving into an unoccupied open space. Each type of amphipod requires a different amount of energy to move one step: Amber amphipods require 1 energy per step, Bronze amphipods require 10 energy, Copper amphipods require 100, and Desert ones require 1000. The amphipods would like you to find a way to organize the amphipods that requires the least total energy.

However, because they are timid and stubborn, the amphipods have some extra rules:

Amphipods will never stop on the space immediately outside any room. They can move into that space so long as they immediately continue moving. (Specifically, this refers to the four open spaces in the hallway that are directly above an amphipod starting position.)

Amphipods will never move from the hallway into a room unless that room is their destination room and that room contains no amphipods which do not also have that room as their own destination. If an amphipod's starting room is not its destination room, it can stay in that room until it leaves the room. (For example, an Amber amphipod will not move from the hallway into the right three rooms, and will only move into the leftmost room if that room is empty or if it only contains other Amber amphipods.)

Once an amphipod stops moving in the hallway, it will stay in that spot until it can move into a room. (That is, once any amphipod starts moving, any other amphipods currently in the hallway are locked in place and will not move again until they can move fully into a room.)

In the above example, the amphipods can be organized using a minimum of 12521 energy. One way to do this is shown below.

Starting configuration:
#############
#...........#
###B#C#B#D###
  #A#D#C#A#
  #########
One Bronze amphipod moves into the hallway, taking 4 steps and using 40 energy:
#############
#...B.......#
###B#C#.#D###
  #A#D#C#A#
  #########
The only Copper amphipod not in its side room moves there, taking 4 steps and using 400 energy:
#############
#...B.......#
###B#.#C#D###
  #A#D#C#A#
  #########
A Desert amphipod moves out of the way, taking 3 steps and using 3000 energy, and then the Bronze amphipod takes its place, taking 3 steps and using 30 energy:
#############
#.....D.....#
###B#.#C#D###
  #A#B#C#A#
  #########
The leftmost Bronze amphipod moves to its room using 40 energy:
#############
#.....D.....#
###.#B#C#D###
  #A#B#C#A#
  #########
Both amphipods in the rightmost room move into the hallway, using 2003 energy in total:
#############
#.....D.D.A.#
###.#B#C#.###
  #A#B#C#.#
  #########
Both Desert amphipods move into the rightmost room using 7000 energy:
#############
#.........A.#
###.#B#C#D###
  #A#B#C#D#
  #########
Finally, the last Amber amphipod moves into its room, using 8 energy:
#############
#...........#
###A#B#C#D###
  #A#B#C#D#
  #########
What is the least energy required to organize the amphipods?

Become the computer

This time, I'm not gonna use Python. No-code is a hot topic again this year and while it means something completely different than this, I'm gonna expand the Advent of Code's lore with a piece of headcanon and say that my solution, using pen, paper and dice is the no-code of this world.

Dice on a paper with hand-drawn squares that represent a corridor and rooms

Here's what it looks like. I drew the squares available, filled them with dice to their initial position and started moving them around, making notes and adding costs.

I also calculated the optimal cost of each letter, optimal here meaning a cost that it would take to move both of its pieces from their starting position to their goal positions. This gave me a benchmark of how much I was behind and especially when I had hit it for the more expensive ones so I could stop trying to optimize those.

As the costs grow in magnitude (1, 10, 100, 1000), it was relatively easy to see what needed to be optimized: first try to make D movements as close to optimal as possible, then C moves and so on.

Part 1

Attempt 1

Start:

#############
#...........#
###D#D#B#A###
  #B#C#A#C#
  #########

Step 1: +9 = 9

#############
#A..........#
###D#D#B#.###
  #B#C#A#C#
  #########

Step 2: +300 = 309

#############
#A........C.#
###D#D#B#.###
  #B#C#A#.#
  #########

Step 3: +7000 = 7309 (this is an optimal move: from start position to finish)

#############
#A........C.#
###D#.#B#.###
  #B#C#A#D#
  #########

Step 4: +8000 = 15309 (optimal move)

#############
#A........C.#
###.#.#B#D###
  #B#C#A#D#
  #########

Step 5: +20 = 15329

#############
#A......B.C.#
###.#.#.#D###
  #B#C#A#D#
  #########

Step 6: +7 = 15336

#############
#AA.....B.C.#
###.#.#.#D###
  #B#C#.#D#
  #########

Step 7: +600 = 15936e (optimal)

#############
#AA.....B.C.#
###.#.#.#D###
  #B#.#C#D#
  #########

Step 7: +60 = 15996 (optimal)

#############
#AA.....B.C.#
###.#.#.#D###
  #.#B#C#D#
  #########

Step 8: +40 = 16036

#############
#AA.......C.#
###.#B#.#D###
  #.#B#C#D#
  #########

Step 9: +400 = 16436

#############
#AA.........#
###.#B#C#D###
  #.#B#C#D#
  #########

Step 10: +3 = 16439

#############
#A..........#
###.#B#C#D###
  #A#B#C#D#
  #########

Step 11: +3 = 16442

#############
#...........#
###A#B#C#D###
  #A#B#C#D#
  #########

Total cost: 16442

Attempt 2

Start:

#############
#...........#
###D#D#B#A###
  #B#C#A#C#
  #########

Step 2: +8 = 8

#############
#.A.........#
###D#D#B#.###
  #B#C#A#C#
  #########

Step 3: +300 = 308

#############
#.A.......C.#
###D#D#B#.###
  #B#C#A#.#
  #########

Step 4: +7000 = 7308 (optimal)

#############
#.A.......C.#
###D#.#B#.###
  #B#C#A#D#
  #########

Step 5: +8000 = 15 308 (optimal)

#############
#.A.......C.#
###.#.#B#D###
  #B#C#A#D#
  #########

Step 6: +40 = 15 348

#############
#.A.B.....C.#
###.#.#.#D###
  #B#C#A#D#
  #########

Step 7: +3 = 15 351

#############
#.A.B...A.C.#
###.#.#.#D###
  #B#C#.#D#
  #########

Step 8: +600 = 15 951 (optimal)

#############
#.A.B...A.C.#
###.#.#.#D###
  #B#.#C#D#
  #########

Step 9: +30 = 15 981

#############
#.A.....A.C.#
###.#.#.#D###
  #B#B#C#D#
  #########

Step 10: +50 = 16 031 (optimal)

#############
#.A.....A.C.#
###.#B#.#D###
  #.#B#C#D#
  #########

Step 11: +3 = 16 034

#############
#.......A.C.#
###.#B#.#D###
  #A#B#C#D#
  #########

Step 12: +6 = 16 044

#############
#.........C.#
###A#B#.#D###
  #A#B#C#D#
  #########

Step 13: +400 = 16 444

#############
#...........#
###A#B#C#D###
  #A#B#C#D#
  #########

Total cost: 16444 (this was worse than previous)

Attempt 3

Start:

#############
#...........#
###D#D#B#A###
  #B#C#A#C#
  #########

Step 1: +9 = 9

#############
#A..........#
###D#D#B#.###
  #B#C#A#C#
  #########

Step 2: +60 = 69

#############
#AB.........#
###D#D#.#.###
  #B#C#A#C#
  #########

Step 3: +5 = 74

#############
#AB.......A.#
###D#D#.#.###
  #B#C#.#C#
  #########

Step 4: +600 = 674

#############
#AB.......A.#
###D#D#.#.###
  #B#C#C#.#
  #########

Step 5: +7000 + 8000 = 15 674 (combined two optimal D moves to one)

#############
#AB.......A.#
###.#.#.#D###
  #B#C#C#D#
  #########

Step 6: +500 (optimal) = 16 174

#############
#AB.......A.#
###.#.#C#D###
  #B#.#C#D#
  #########

Step 7: +60+40 = 16 274 (combined two B moves, one optimal)

#############
#A........A.#
###.#B#C#D###
  #.#B#C#D#
  #########

Step 8: +4+8 = 16 286 (combined two A moves)

#############
#...........#
###A#B#C#D###
  #A#B#C#D#
  #########

Total cost: 16286

Attempt 4

Start:

#############
#...........#
###D#D#B#A###
  #B#C#A#C#
  #########

Step 1: +8 = 8

#############
#.A.........#
###D#D#B#.###
  #B#C#A#C#
  #########

Step 2: +40 = 48

#############
#.A.B.......#
###D#D#.#.###
  #B#C#A#C#
  #########

Step 3: +5 = 53

#############
#.A.B.....A.#
###D#D#.#.###
  #B#C#.#C#
  #########

Step 4: +600 = 653

#############
#.A.B.....A.#
###D#D#.#.###
  #B#C#C#.#
  #########

Step 5: +7000 = 7 653

#############
#.A.B.....A.#
###D#.#.#.###
  #B#C#C#D#
  #########

Step 6: +500 = 8 153

#############
#.A.B.....A.#
###D#.#C#.###
  #B#.#C#D#
  #########

Step 7: +30 = 8 183

#############
#.A.......A.#
###D#.#C#.###
  #B#B#C#D#
  #########

Step 8: +8000 = 16 183

#############
#.A.......A.#
###.#.#C#D###
  #B#B#C#D#
  #########

Step 9: +50 = 16 233

#############
#.A.......A.#
###.#B#C#D###
  #.#B#C#D#
  #########

Step 10: +3 = 16 236

#############
#.........A.#
###.#B#C#D###
  #A#B#C#D#
  #########

Step 11: +8 = 16 244

#############
#...........#
###A#B#C#D###
  #A#B#C#D#
  #########

Total cost: 16 244

Part 2

Add
  #D#C#B#A#
  #D#B#A#C#
between the two rows of amphies.

This time my first attempt was already very good. The optimal (unattainable) cost for this setup is 42420 and I got to 43 406 on my first go.

Attempt 1

Start:

#############
#...........#
###D#D#B#A###
  #D#C#B#A#
  #D#B#A#C#
  #B#C#A#C#
  #########

Step 1: +9+9 = 18 (two A moves)

#############
#AA.........#
###D#D#B#.###
  #D#C#B#.#
  #D#B#A#C#
  #B#C#A#C#
  #########

Step 2: +500+500 = 1018 (two C moves)

#############
#AA.......CC#
###D#D#B#.###
  #D#C#B#.#
  #D#B#A#.#
  #B#C#A#.#
  #########

Step 3: 9000+10000+10000+10000 = 40 018 (four optimal D moves, feels good man)

#############
#AA.......CC#
###.#.#B#D###
  #.#C#B#D#
  #.#B#A#D#
  #B#C#A#D#
  #########

Step 4: +500 = 40 518

#############
#AA.....C.CC#
###.#.#B#D###
  #.#.#B#D#
  #.#B#A#D#
  #B#C#A#D#
  #########

Step 5: +70 = 40 088

#############
#AA...B.C.CC#
###.#.#B#D###
  #.#.#B#D#
  #.#B#A#D#
  #.#C#A#D#
  #########

Step 6: +5+5 = 40 098 (two A moves)

#############
#.....B.C.CC#
###.#.#B#D###
  #.#.#B#D#
  #A#B#A#D#
  #A#C#A#D#
  #########

Step 7: +70+700 = 40 868 (B and C move)

#############
#BC...B.C.CC#
###.#.#B#D###
  #.#.#B#D#
  #A#.#A#D#
  #A#.#A#D#
  #########

Step 8: +50 = 40 918

#############
#BC.....C.CC#
###.#.#B#D###
  #.#.#B#D#
  #A#.#A#D#
  #A#B#A#D#
  #########

Step 9: +60+60 = 41 038 (two B moves)

#############
#BC.....C.CC#
###.#.#.#D###
  #.#B#.#D#
  #A#B#A#D#
  #A#B#A#D#
  #########

Step 10: +9+9 = 41 056 (two A moves)

#############
#BC.....C.CC#
###A#.#.#D###
  #A#B#.#D#
  #A#B#.#D#
  #A#B#.#D#
  #########

Step 11: +500+600+600+600 = 43 356 (four C moves, jackpot!)

#############
#B..........#
###A#.#C#D###
  #A#B#C#D#
  #A#B#C#D#
  #A#B#C#D#
  #########

Step 12: +50 = 43 406

#############
#...........#
###A#B#C#D###
  #A#B#C#D#
  #A#B#C#D#
  #A#B#C#D#
  #########

Total cost: 43 406

Attempt 2

Start:

#############
#...........#
###D#D#B#A###
  #D#C#B#A#
  #D#B#A#C#
  #B#C#A#C#
  #########

Step 1: +9+9 = 18 (two A moves)

#############
#AA.........#
###D#D#B#.###
  #D#C#B#.#
  #D#B#A#C#
  #B#C#A#C#
  #########

Step 2: +500+500 = 1018 (two C moves)

#############
#AA.......CC#
###D#D#B#.###
  #D#C#B#.#
  #D#B#A#.#
  #B#C#A#.#
  #########

Step 3: +9000+10000+10000+10000 = 40 018 (four optimal D moves)

#############
#AA.......CC#
###.#.#B#D###
  #.#C#B#D#
  #.#B#A#D#
  #B#C#A#D#
  #########

Step 4: +90 = 40 108

#############
#AA.....B.CC#
###.#.#B#D###
  #.#C#B#D#
  #.#B#A#D#
  #.#C#A#D#
  #########

Step 5: +5+5 = 40 118 (two A moves)

#############
#.......B.CC#
###.#.#B#D###
  #.#C#B#D#
  #A#B#A#D#
  #A#C#A#D#
  #########

Step 6: +70+70 = 40 258 (two B moves)

#############
#BB.....B.CC#
###.#.#.#D###
  #.#C#.#D#
  #A#B#A#D#
  #A#C#A#D#
  #########

Step 7: +9+9 = 40 276 (two optimal A moves)

#############
#BB.....B.CC#
###A#.#.#D###
  #A#C#.#D#
  #A#B#.#D#
  #A#C#.#D#
  #########

Step 8: +800 = 41 076 (optimal C move)

#############
#BB.....B.CC#
###A#.#.#D###
  #A#.#.#D#
  #A#B#.#D#
  #A#C#C#D#
  #########

Step 9: +40 = 41 116

#############
#BB.B...B.CC#
###A#.#.#D###
  #A#.#.#D#
  #A#.#.#D#
  #A#C#C#D#
  #########

Step 10: +900 = 42 016 (optimal C move)

#############
#BB.B...B.CC#
###A#.#.#D###
  #A#.#.#D#
  #A#.#C#D#
  #A#.#C#D#
  #########

Step 11: +50+60+50+50 = 42 226 (four B moves)

#############
#.........CC#
###A#B#.#D###
  #A#B#.#D#
  #A#B#C#D#
  #A#B#C#D#
  #########

Step 12: +500+500 = 43 226

#############
#...........#
###A#B#C#D###
  #A#B#C#D#
  #A#B#C#D#
  #A#B#C#D#
  #########

Total cost: 43226