Amphipod
Tags: adventofcode, programming, algorithms, computerscience
Published: 2022-01-06 14:43:00

## [Advent of Code 2021 Day 23](https://adventofcode.com/2021/day/23)

### Solve for X where X equals...
- An integer that is greater than and as close as possible to the minimum unobstructed score after solving the puzzle

### That's our output. What's our input?
- A multi-line string
- Consisting of 6 possible characters `#.ABCD`

### What does our input represent?
- A hallway and four rooms
- The stage for playing a game akin to [Towers of Hanoi](https://www.mathsisfun.com/games/towerofhanoi.html)

### How do we win this game?
- Move the letters `A,B,C,D` such that each of the four rooms - from left to right - contains only one type of letter organized alphabetically
- Achieve the smallest possible score (see scoring in the next section). Strategically speaking: move D's as few times as possible, and move A's more often than any other character.

### How do we play this game?
- Abide by all three movement constraints: 1) Any letter can move at most twice - either directly from its starting location into its destination room, or with a stop in the hallway in between; 2) Letters cannot stop on spaces directly north of each room; 3) Letters cannot enter any room other than their destination room, and can only enter that room when empty or when the other letters in that room are each of the correct type
- Keep track of a running score that accounts for each letter type's move cost: `A costs 1 to move`, `B costs 10 to move`, `C costs 100 to move`, `D costs `1000 to move`

### Why there are no algorithms in this article
- It took me several hours in a day just to solve Part 1 with pen and paper
- It took me even more hours in a day to solve Part 2 using a Design tool on my computer where I re-created the game board and moved text layers around to simulate playing
- When scouring GitHub and Reddit for coded solutions, they were each far too complex for me to understand, let alone attempt to re-create
- Given how difficult it was to solve these puzzles by hand, I recognize how unprepared I am to attempt to codify even an inefficient, brute-force algorithm that discovers the same minimum solution

### Part 1
- What follows are my hand-drawn notes from solving Part 1 with the input generated for me

Visualization created using [Amphipod.net](https://amphipod.net/)
![Animation of solution to part 1](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/96dibnqimqi9pmah3oo0.gif)

#### My process: hand-drawn
First successful attempt: 20926 energy, too high
![Hand-drawn steps to solve - first attempt](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/oll6f2k0bfwq5z0gmg8z.jpg)

Second successful attempt: 18210 energy, too high
![Hand-drawn steps to solve - second attempt](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/enb0i21kmjp8u8aeek5l.jpg)

At this point, I needed to move pieces around for real
![Cut-out pieces to attempt puzzle for real](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/gbjgnyn7p0tg13j2c3ht.jpg)

Third successful attempt: 18206 energy, too high
![Hand-drawn steps to solve - third attempt](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/i6bp8nnev4ipoft80ten.jpg)

Fourth successful attempt: 18186 energy, too high
![Hand-drawn steps to solve - fourth attempt](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/u86z0uqivisu4pz823o7.jpg)

Fifth successful attempt: 18170 energy, correct!
![Hand-drawn steps to solve - fifth attempt](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/apa0xvms1k8t0htc5tb7.jpg)

The full collection of artifacts that led to my discovery of the correct answer
![All notes and board pieces that led to correct solution](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/0vurj6ftfv37btsbg9ce.jpg)

### Part 2
- I must have tried hundreds of times
- I kept trying to solve it by starting with the two C's in the second room
- It wasn't until late in the day that I started by emptying the 2 B's and 2 A's in room three
- To all fellow beginner puzzlers, know that what you don't see below are all the Quicktime recordings (and the thousands of Undo commands) representing my failed attempts to solve Part 2

Visualization created using [Amphipod.net](https://amphipod.net/)
![Animation of solution to part 2](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/xts7fgz7hugyj8nba4l0.gif)

#### My process: Moving text layers in Sketch
- It was going to be too much work to move pieces of paper around
- Instead, I recreated the game board using a design tool called Sketch
- This way, I could freely attempt to play the game, and press 'Undo' as many times as needed to 'reset' the game board
- Also, I could record my attempts at any time using Quicktime. If it didn't teach me anything, I could just throw the video away and reset the game board in seconds, not minutes.

![ASCII art serving as digital game board](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/wjke48hqg8ib7quojw2r.jpg)

### Save for later
- Study Dijkstra's algorithm, as that was the 'shortest path' algorithm most-often referenced by other solvers