Andrey Listopadov

Advent of Code: Day 23 - Amphipod

@aoc2021 ~9 minutes read

And they did it again. Today’s task is yet again “try this easy part, that can be solved by brute force. Yes, correct… now suffer from all this extra data you need to process” type of task. Our task is to move every Amphipod into their room:

#############      #############
#...........#      #...........#
###B#C#B#D### -->  ###A#B#C#D###
  #A#D#C#A#          #A#B#C#D#
  #########          #########

Each Amphipod is marked as a letter, and we can only place letters above # symbols. Furthermore, letters can only go into their own room, and only if there are no letters from other rooms. In other words, these cases are invalid:

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

B stands over        B entered a room that still contains D
the room's exit      which don't belong to that room

We have a hallway with two pockets on each side, each of which can contain two letters at most, and we also have three more positions between rooms. Letters can’t go over each other, so we need to avoid deadlocks. The other catch is that each letter has a different move cost. A costs 1 point, B costs 10, C costs 100, and D costs 1000. This means that we should try to never move D more than once, and we can probably do some extra moves of A and B, but not too much.

Overall this looks like a Hanoi Tower type of task, but instead of moving sorted pillars of disks from one pole to another pole, we need to sort discs between poles. In the case of the following example, there aren’t too many ways we can solve it, because of deadlocks and move costs. But I’m not in the coding mood today, so let’s use a neural network instead, and let it solve the task for us without any line of code. By neural network, I mean my own brain ofc.

So I’ve tried it 4 times, and figured that the following sequence of moves leads to the most optimal result:

#############  #############  #############  #############  #############  #############  #############  #############  #############  #############  #############  #############  #############
#...........#  #..........A#  #.........CA#  #.........CA#  #.A.......CA#  #.A.B.....CA#  #.A.B......A#  #.A.B......A#  #.A........A#  #.A........A#  #.A........A#  #..........A#  #...........#
###B#B#D#A###  ###B#B#D#.###  ###B#B#D#.###  ###B#B#.#.###  ###B#B#.#.###  ###B#.#.#.###  ###B#.#.#.###  ###B#.#C#.###  ###B#.#C#.###  ###.#B#C#.###  ###.#B#C#D###  ###.#B#C#D###  ###A#B#C#D###
  #D#C#A#C#      #D#C#A#C#      #D#C#A#.#      #D#C#A#D#      #D#C#.#D#      #D#C#.#D#      #D#C#C#D#      #D#.#C#D#      #D#B#C#D#      #D#B#C#D#      #.#B#C#D#      #A#B#C#D#      #A#B#C#D#
  #########      #########      #########      #########      #########      #########      #########      #########      #########      #########      #########      #########      #########
  0              3              300            5000           7              20             50             50             30             40             9000           3              9

Adding these together we get the correct result 14512. But the second part will not be that easy, because it adds two more rows to the rooms, with the preset pattern:

#############
#...........#
###B#B#D#A###
  #D#C#B#A#  <-- these
  #D#B#A#C#  <-- ones
  #D#C#A#C#
  #########

Now there a lot more moves to consider. Well, given that the first column contains all three D letters, we can safely assume that we will have at very least three moves 11000 worth of points. Two C letters in the last room are likely to be moved after we already fully empty the second room, so that’s another 1400 points. Then we move A letters to the packets, finish C room, and then D room, finishing with A room.

Well, that’s just a guess based on the whole situation, so let’s try this:

#############  #############  #############  #############  #############  #############  #############  #############  #############  #############  #############  #############  #############  #############  #############  #############  #############  #############  #############  #############  #############  #############  #############  #############  #############  #############  #############  #############  #############  #############
#...........#  #..........D#  #B.........D#  #BA........D#  #BA.......AD#  #BA.B.....AD#  #BA.B.....AD#  #BA.B...B.AD#  #BA.B...B.AD#  #BA.....B.AD#  #BA.......AD#  #BA.......AD#  #B....A...AD#  #.....A...AD#  #A........AD#  #AA.......AD#  #AA...A...AD#  #AA...A...AD#  #AA...A...AD#  #AA...A.A..D#  #AA...A.A...#  #AA...A....A#  #AA.......AA#  #AA.......AA#  #AA.......AA#  #AA.......AA#  #A........AA#  #.........AA#  #..........A#  #...........#
###B#B#D#A###  ###B#B#.#A###  ###B#B#.#A###  ###B#B#.#A###  ###B#B#.#A###  ###B#.#.#A###  ###B#.#.#A###  ###B#.#.#A###  ###B#.#.#A###  ###B#.#.#A###  ###B#.#.#A###  ###.#.#.#A###  ###.#.#.#A###  ###.#B#.#A###  ###.#B#.#A###  ###.#B#.#.###  ###.#B#.#.###  ###.#B#.#.###  ###.#B#C#.###  ###.#B#C#.###  ###.#B#C#.###  ###.#B#C#.###  ###.#B#C#.###  ###.#B#C#.###  ###.#B#C#.###  ###.#B#C#D###  ###.#B#C#D###  ###.#B#C#D###  ###.#B#C#D###  ###A#B#C#D###
  #D#C#B#A#      #D#C#B#A#      #D#C#.#A#      #D#C#.#A#      #D#C#.#A#      #D#C#.#A#      #D#.#.#A#      #D#.#.#A#      #D#.#.#A#      #D#.#.#A#      #D#.#.#A#      #D#B#.#A#      #D#B#.#A#      #D#B#.#A#      #D#B#.#A#      #D#B#.#A#      #D#B#.#.#      #D#B#C#.#      #D#B#C#.#      #D#B#C#.#      #D#B#C#.#      #D#B#C#.#      #D#B#C#.#      #.#B#C#.#      #.#B#C#D#      #.#B#C#D#      #.#B#C#D#      #.#B#C#D#      #A#B#C#D#      #A#B#C#D#
  #D#B#A#C#      #D#B#A#C#      #D#B#A#C#      #D#B#.#C#      #D#B#.#C#      #D#B#.#C#      #D#B#.#C#      #D#.#.#C#      #D#.#C#C#      #D#.#C#C#      #D#B#C#C#      #D#B#C#C#      #D#B#C#C#      #D#B#C#C#      #D#B#C#C#      #D#B#C#C#      #D#B#C#C#      #D#B#C#.#      #D#B#C#.#      #D#B#C#.#      #D#B#C#.#      #D#B#C#.#      #D#B#C#.#      #D#B#C#D#      #.#B#C#D#      #.#B#C#D#      #.#B#C#D#      #A#B#C#D#      #A#B#C#D#      #A#B#C#D#
  #D#C#A#C#      #D#C#A#C#      #D#C#A#C#      #D#C#A#C#      #D#C#.#C#      #D#C#.#C#      #D#C#C#C#      #D#C#C#C#      #D#.#C#C#      #D#B#C#C#      #D#B#C#C#      #D#B#C#C#      #D#B#C#C#      #D#B#C#C#      #D#B#C#C#      #D#B#C#C#      #D#B#C#C#      #D#B#C#C#      #D#B#C#.#      #D#B#C#.#      #D#B#C#D#      #D#B#C#D#      #D#B#C#D#      #D#B#C#D#      #D#B#C#D#      #.#B#C#D#      #A#B#C#D#      #A#B#C#D#      #A#B#C#D#      #A#B#C#D#
  #########      #########      #########      #########      #########      #########      #########      #########      #########      #########      #########      #########      #########      #########      #########      #########      #########      #########      #########      #########      #########      #########      #########      #########      #########      #########      #########      #########      #########      #########
  0              5000           80             8              7              20             800            60             900            50             60             50             4              50             5              8              5              700            700            2              6000           3              4              11000          11000          11000          5              5              9              9

This gives us the total of 47544 points:

However, this is not the correct answer. I’ve noticed that instead of moving B to the left pocket, which I’ve assumed would be the most optimal move, I can instead move it to the right pocket. This will add up later, but we can solve this in a bit fewer moves of A letters:

#############  #############  #############  #############  #############  #############  #############  #############  #############  #############  #############  #############  #############  #############  #############  #############  #############  #############  #############  #############  #############  #############  #############  #############  #############  #############  #############
#...........#  #..........D#  #.........BD#  #A........BD#  #AA.......BD#  #AA.....B.BD#  #AA.....B.BD#  #AA.B...B.BD#  #AA.B...B.BD#  #AA.....B.BD#  #AA.....B.BD#  #AA.......BD#  #AA.......AD#  #AA...A...AD#  #AA...A...AD#  #AA...A...AD#  #AA...A.A..D#  #AA...A.A...#  #AA...A....A#  #AA.......AA#  #AA.......AA#  #AA.......AA#  #AA.......AA#  #A........AA#  #.........AA#  #..........A#  #...........#
###B#B#D#A###  ###B#B#.#A###  ###B#B#.#A###  ###B#B#.#A###  ###B#B#.#A###  ###B#.#.#A###  ###B#.#.#A###  ###B#.#.#A###  ###B#.#.#A###  ###B#.#.#A###  ###.#.#.#A###  ###.#.#.#A###  ###.#B#.#.###  ###.#B#.#.###  ###.#B#.#.###  ###.#B#C#.###  ###.#B#C#.###  ###.#B#C#.###  ###.#B#C#.###  ###.#B#C#.###  ###.#B#C#.###  ###.#B#C#.###  ###.#B#C#D###  ###.#B#C#D###  ###.#B#C#D###  ###.#B#C#D###  ###A#B#C#D###
  #D#C#B#A#      #D#C#B#A#      #D#C#.#A#      #D#C#.#A#      #D#C#.#A#      #D#C#.#A#      #D#.#.#A#      #D#.#.#A#      #D#.#.#A#      #D#.#.#A#      #D#.#.#A#      #D#B#.#A#      #D#B#.#A#      #D#B#.#.#      #D#B#C#.#      #D#B#C#.#      #D#B#C#.#      #D#B#C#.#      #D#B#C#.#      #D#B#C#.#      #.#B#C#.#      #.#B#C#D#      #.#B#C#D#      #.#B#C#D#      #.#B#C#D#      #A#B#C#D#      #A#B#C#D#
  #D#B#A#C#      #D#B#A#C#      #D#B#A#C#      #D#B#.#C#      #D#B#.#C#      #D#B#.#C#      #D#B#.#C#      #D#.#.#C#      #D#.#C#C#      #D#.#C#C#      #D#B#C#C#      #D#B#C#C#      #D#B#C#C#      #D#B#C#C#      #D#B#C#.#      #D#B#C#.#      #D#B#C#.#      #D#B#C#.#      #D#B#C#.#      #D#B#C#.#      #D#B#C#D#      #.#B#C#D#      #.#B#C#D#      #.#B#C#D#      #A#B#C#D#      #A#B#C#D#      #A#B#C#D#
  #D#C#A#C#      #D#C#A#C#      #D#C#A#C#      #D#C#A#C#      #D#C#.#C#      #D#C#.#C#      #D#C#C#C#      #D#C#C#C#      #D#.#C#C#      #D#B#C#C#      #D#B#C#C#      #D#B#C#C#      #D#B#C#C#      #D#B#C#C#      #D#B#C#C#      #D#B#C#.#      #D#B#C#.#      #D#B#C#D#      #D#B#C#D#      #D#B#C#D#      #D#B#C#D#      #D#B#C#D#      #.#B#C#D#      #A#B#C#D#      #A#B#C#D#      #A#B#C#D#      #A#B#C#D#
  #########      #########      #########      #########      #########      #########      #########      #########      #########      #########      #########      #########      #########      #########      #########      #########      #########      #########      #########      #########      #########      #########      #########      #########      #########      #########      #########
  0              5000           50             9              9              40             800            40             900            50             60             50             60             5              700            700            2              6000           3              4              11000          11000          11000          5              5              9              9

This gives us 47510 points, which is less than our previous result, but still not correct. The problem is, I don’t know if this answer is too low or too high, as the page stopped giving hints at some point, to avoid bisecting, I guess. So I can’t verify if I’m doing it completely wrong in case this answer is too low, or I’m not doing it optimal enough if it is too high.

However, since I’m not going to write code for this task, I’ve decided to cheat. I went to the leaderboard and found the solution for this task. Funnily enough, I’ve noticed that I’m not the only one who decided to solve this task by hand, and some of these people are as high as 14th rank. Pretty impressive, as this task is not an easy one to do manually, given all possible variants.

But I’m here for the answers, and the code says that the correct answer is… 52358! I’m not going to submit it just because someone else computed it for me, I just wanted to see if I’m not doing it optimally or not. But wait, my solution is much more optimal than that, what the hell? Have I made a wrong move somehow or have I misinterpreted the rules? While doing this I’ve checked that I basically:

  • never step into the tiles that are directly above the room.
  • never went into the other’s letter’s room.
  • never jumped over another letter.

The rule about not standing above the room is a bit vague. It explicitly says that it refers to four open places above each room, so naturally, I think it’s safe to assume that we can never stand on those. But then it also mentions: “this refers to the four open spaces in the hallway that are directly above an amphipod starting position”. So this means that we can stand on this tile when we’re not moving out of the room or what?

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

  forbidden.      allowed???

I guess it’s not allowed, as the rule says that “never stop on the space immediately outside any room”. I’m not sure why they decided to mention the “above an amphipod starting position” part at all. So from now on, I’ll assume that both cases are forbidden. But I never used such moves in my solution, so what exactly have I done wrong?

Turns out, I’ve forgotten about one critical rule. You can’t move in the hallway once you’ve stopped there. From the hallway, you can only move into the room. And In my solution, I’m moving letter A back and forth through the hall to make room for maneuvers. Now, this surely complicates the task. However, it also cuts down a lot of possible moves.

So our strategy should be basically about finding optimal starting moves that occupy hallway ends and provide enough room for other letter moves. I’ve thought that it should not be that bad, but it turns out it was pretty hard. (who would have guessed?) Anyway, after about 18 tries (I’ve lost count) that ended in a deadlock one way or another, I’ve managed to do it like this:

#############  #############  #############  #############  #############  #############  #############  #############  #############  #############  #############  #############  #############  #############  #############  #############  #############  #############  #############  #############  #############  #############  #############  #############  #############  #############
#...........#  #B..........#  #B.........D#  #B........DD#  #BD.......DD#  #BD.......DD#  #BD.C.....DD#  #BD.C.C...DD#  #BD.C.C...DD#  #BD.C.C....D#  #BD.C.C.....#  #BD.C.C....B#  #BD.C.C.A.AB#  #BD.C...A.AB#  #BD.....A.AB#  #BD.......AB#  #BD........B#  #B.........B#  #BB........B#  #BB........B#  #BB.B......B#  #BB.B......B#  #BB........B#  #B.........B#  #..........B#  #...........#
###B#B#D#A###  ###.#B#D#A###  ###.#B#D#A###  ###.#B#D#A###  ###.#B#D#A###  ###.#B#D#.###  ###.#B#D#.###  ###.#B#D#.###  ###.#B#.#.###  ###.#B#.#.###  ###.#B#.#.###  ###.#B#.#.###  ###.#B#.#.###  ###.#B#.#.###  ###.#B#.#.###  ###.#B#.#.###  ###A#B#.#.###  ###A#B#.#D###  ###A#.#.#D###  ###A#.#.#D###  ###A#.#.#D###  ###A#.#C#D###  ###A#.#C#D###  ###A#.#C#D###  ###A#.#C#D###  ###A#B#C#D###
  #D#C#B#A#      #D#C#B#A#      #.#C#B#A#      #.#C#B#A#      #.#C#B#A#      #.#C#B#A#      #.#C#B#.#      #.#C#B#.#      #.#C#B#.#      #.#C#B#.#      #.#C#B#D#      #.#C#.#D#      #.#C#.#D#      #.#C#.#D#      #.#C#.#D#      #A#C#.#D#      #A#C#.#D#      #A#C#.#D#      #A#C#.#D#      #A#.#C#D#      #A#.#C#D#      #A#.#C#D#      #A#.#C#D#      #A#.#C#D#      #A#B#C#D#      #A#B#C#D#
  #D#B#A#C#      #D#B#A#C#      #D#B#A#C#      #.#B#A#C#      #.#B#A#C#      #.#B#A#C#      #A#B#A#.#      #A#B#A#.#      #A#B#A#.#      #A#B#A#D#      #A#B#A#D#      #A#B#A#D#      #A#B#.#D#      #A#B#.#D#      #A#B#C#D#      #A#B#C#D#      #A#B#C#D#      #A#B#C#D#      #A#B#C#D#      #A#B#C#D#      #A#.#C#D#      #A#.#C#D#      #A#.#C#D#      #A#B#C#D#      #A#B#C#D#      #A#B#C#D#
  #D#C#A#C#      #D#C#A#C#      #D#C#A#C#      #D#C#A#C#      #.#C#A#C#      #A#C#A#C#      #A#C#A#C#      #A#C#A#.#      #A#C#A#D#      #A#C#A#D#      #A#C#A#D#      #A#C#A#D#      #A#C#.#D#      #A#C#C#D#      #A#C#C#D#      #A#C#C#D#      #A#C#C#D#      #A#C#C#D#      #A#C#C#D#      #A#C#C#D#      #A#C#C#D#      #A#.#C#D#      #A#B#C#D#      #A#B#C#D#      #A#B#C#D#      #A#B#C#D#
  #########      #########      #########      #########      #########      #########      #########      #########      #########      #########      #########      #########      #########      #########      #########      #########      #########      #########      #########      #########      #########      #########      #########      #########      #########      #########
  0              30             10000          10000          5000           11             800            700            7000           4000           4000           60             5              500            600            7              8              8000           40             600            40             700            50             60             60             70

Which indeed computes to 52358, so the code I’ve tried was correct. I’m not sure if there is actually more than one solution to this problem. With all rules listed in the task, it looks like that there can be only one solution. So the code can probably just recursively try all games and cut branches that end in a deadlock.

Anyway, we got through, and there are only two days left. I’m unsure if I’ll be able to solve the 25th day in time, as I’ll be out of town yet again this weekend. And since I’m leaving tomorrow evening, so tomorrow’s task is under the question as well. We’ll see how it goes.