part1 (4245B)
1--- Day 23: Amphipod --- 2 3A group of amphipods notice your fancy submarine and flag you down. "With such an impressive shell," 4one amphipod says, "surely you can help us with a question that has stumped our best scientists." 5 6They go on to explain that a group of timid, stubborn amphipods live in a nearby burrow. Four types 7of amphipods live there: [1m[97mAmber[0m (A), [1m[97mBronze[0m (B), [1m[97mCopper[0m (C), and [1m[97mDesert[0m (D). They live in a burrow 8that consists of a [1m[97mhallway[0m and four [1m[97mside rooms[0m. The side rooms are initially full of amphipods, and 9the hallway is initially empty. 10 11They give you a [1m[97mdiagram of the situation[0m (your puzzle input), including locations of each amphipod 12(A, B, C, or D, each of which is occupying an otherwise open space), walls (#), and open space (.). 13 14For example: 15 16############# 17#...........# 18###B#C#B#D### 19 #A#D#C#A# 20 ######### 21 22The amphipods would like a method to organize every amphipod into side rooms so that each side room 23contains one type of amphipod and the types are sorted A-D going left to right, like this: 24 25############# 26#...........# 27###A#B#C#D### 28 #A#B#C#D# 29 ######### 30 31Amphipods can move up, down, left, or right so long as they are moving into an unoccupied open 32space. Each type of amphipod requires a different amount of [1m[97menergy[0m to move one step: Amber amphipods 33require 1 energy per step, Bronze amphipods require 10 energy, Copper amphipods require 100, and 34Desert ones require 1000. The amphipods would like you to find a way to organize the amphipods that 35requires the [1m[97mleast total energy[0m. 36 37However, because they are timid and stubborn, the amphipods have some extra rules: 38 39 40 - Amphipods will never [1m[97mstop on the space immediately outside any room[0m. They can move into that 41space so long as they immediately continue moving. (Specifically, this refers to the four open 42spaces in the hallway that are directly above an amphipod starting position.) 43 44 - Amphipods will never [1m[97mmove from the hallway into a room[0m unless that room is their destination room 45[1m[97mand[0m that room contains no amphipods which do not also have that room as their own destination. If an 46amphipod's starting room is not its destination room, it can stay in that room until it leaves the 47room. (For example, an Amber amphipod will not move from the hallway into the right three rooms, and 48will only move into the leftmost room if that room is empty or if it only contains other Amber 49amphipods.) 50 51 - Once an amphipod stops moving in the hallway, [1m[97mit will stay in that spot until it can move into a 52room[0m. (That is, once any amphipod starts moving, any other amphipods currently in the hallway are 53locked in place and will not move again until they can move fully into a room.) 54 55 56In the above example, the amphipods can be organized using a minimum of [1m[97m12521[0m energy. One way to do 57this is shown below. 58 59Starting configuration: 60 61############# 62#...........# 63###B#C#B#D### 64 #A#D#C#A# 65 ######### 66 67One Bronze amphipod moves into the hallway, taking 4 steps and using 40 energy: 68 69############# 70#...B.......# 71###B#C#.#D### 72 #A#D#C#A# 73 ######### 74 75The only Copper amphipod not in its side room moves there, taking 4 steps and using 400 energy: 76 77############# 78#...B.......# 79###B#.#C#D### 80 #A#D#C#A# 81 ######### 82 83A Desert amphipod moves out of the way, taking 3 steps and using 3000 energy, and then the Bronze 84amphipod takes its place, taking 3 steps and using 30 energy: 85 86############# 87#.....D.....# 88###B#.#C#D### 89 #A#B#C#A# 90 ######### 91 92The leftmost Bronze amphipod moves to its room using 40 energy: 93 94############# 95#.....D.....# 96###.#B#C#D### 97 #A#B#C#A# 98 ######### 99 100Both amphipods in the rightmost room move into the hallway, using 2003 energy in total: 101 102############# 103#.....D.D.A.# 104###.#B#C#.### 105 #A#B#C#.# 106 ######### 107 108Both Desert amphipods move into the rightmost room using 7000 energy: 109 110############# 111#.........A.# 112###.#B#C#D### 113 #A#B#C#D# 114 ######### 115 116Finally, the last Amber amphipod moves into its room, using 8 energy: 117 118############# 119#...........# 120###A#B#C#D### 121 #A#B#C#D# 122 ######### 123 124[1m[97mWhat is the least energy required to organize the amphipods?[0m 125 126