How to solve Advent of Code 2022 - Day 9 with Python

How to solve Advent of Code 2022 - Day 9 with Python

If you missed any previous days, click here for all my content about that: Advent of Code, if you want to know why you should participate and try to code the solution for yourself, click here: Advent Of Code 2022 – 7 Reasons why you should participate. If you're here to see the solution of Day 9, continue reading ;)

GitHub Repository

https://github.com/GalaxyInfernoCodes/Advent_Of_Code_2022

I will upload all of my solutions there - in the form of Python (or Scala alternatives) notebooks. You have to use your own input for the "input.txt" since everyone gets their own and everyone needs to provide a different solution based on their input.

Day 9 Puzzle

On day 9 of Advent of Code, we had to simulate a rope. We are given series of instructions of how to move the head of the rope looking like this:

R 4
U 4
L 3
D 1
R 4
D 1
L 5
R 2

As always, I read in all lines and in this case directly parse each line into a letter ('R') and the number following it. The movements list then contains tuples like ('R', 4) etc.

with open('example.txt', 'r') as f:
    lines = f.readlines()
    movements = [(entry.strip().split(' ')[0], 
                    int(entry.strip().split(' ')[1])
                  ) 
                    for entry in lines]

Part 1

The movements from our input file tell us how to move the front (head) of the rope on a 2 dimensional grid.

I decided to not create a grid and instead I just keep track of the coordinates of head and tail. Because of this I can't run out of grid space and avoid index out of bounds errors:

head = np.array([0,0])
tail = np.array([0,0])

I use numpy arrays so I can easily subtract them from each other. First index is the row number, second is column.

Our task is now to check which coordinates in the grid the tail visits, based on these movement rules:

Movement rules for part 1

Once the head leaves the 8 neighboring squares of the tail, the tail follows like shown above.

To move the tail, I calculated the differences between head and tail. Then I create a dictionary that tells me based on how far away the head is, how far the tail needs to move in each direction, encoding the above picture. This needed change is added to the tail to get the new tail position.

def update_tail(head, tail):
    difference = head - tail
    change_for_tail={
        # head is 2 up 1 right from tail, then tail follows up and right once
        (2, 1):(1, 1),
        # 1 up, 2 right
        (1, 2):(1, 1),
        # 2up
        (2, 0):(1, 0),
        # 2up 1left
        (2, -1):(1, -1),
        # 1up, 2eft
        (1, -2):(1, -1),
        # 2left and so on
        (0, -2):(0, -1),
        (-1, -2):(-1,-1),
        (-2, -1):(-1, -1),
        (-2, 0):(-1, 0),
        (-2, 1):(-1, 1),
        (-1, 2):(-1, 1),
        (0, 2):(0, 1),
        # additional cases for part 2
        (2, 2):(1, 1),
        (-2, -2):(-1, -1),
        (-2, 2):(-1, 1),
        (2, -2):(1, -1)
      }
    new_tail_pos = tail + np.array(change_for_tail.get(tuple(difference), (0,0)))
    return new_tail_pos

The head update is fairly simple in comparison:

def update_head(head, direction):
    if direction == 'R':
        head[1] += 1
    elif direction == 'L':
        head[1] -= 1
    elif direction == 'U':
        head[0] += 1
    elif direction == 'D':
        head[0] -= 1
    return head

Since we only need to check which coordinates were visited at least once, I used a set of tuples to keep track of that, because a set doesn't save duplicates.

For each movement instruction I update the head, then update the tail based on that and add the new tail position.

tail_positions = set([tuple(tail)])
for direction, distance in movements:
    while distance > 0:
        head = update_head(head, direction)
        distance -= 1
        tail = update_tail(head, tail)
        tail_positions.add(tuple(tail))
        #print(f"{head=}, {tail=}")
len(tail_positions)

In the end, we just need the length of the visited tail positions for the solution.

Part 2

To make it a bit more difficult, we now have a rope with 10 parts. A head and 9 parts that each follow the one before it.

The rope is still represented by the coordinates of its parts, it just has 10 parts now saved in rope.

After updating the head, each tail is updated based on the previous one.

rope = [np.array([0,0]) for _ in range(10)]

tail_positions = set([tuple(rope[9])])
for direction, distance in movements:
    while distance > 0:
        rope[0] = update_head(rope[0], direction)
        distance -= 1
        for i in range(1, len(rope)):
            rope[i] = update_tail(rope[i-1], rope[i])
        tail_positions.add(tuple(rope[9]))
len(tail_positions)

Again, we just keep track of the positions of rope part with index 9 (the last one) like in part 1.

The only thing you need to consider here is that the tails have 4 more movement possibilities. Because the tails can move diagonally when being pulled, while the head can only move in left/right/up/down, it is now possible for rope parts beyond the 2nd one to be pulled into those directions too (here the H represents the leading knot in each pair of two):

Additional movements in part 2 in orange

So these are the additional cases in the map that you might have already seen above :)

def update_tail(head, tail):
    difference = head - tail
    change_for_tail={
        # head is 2 up 1 right from tail, then tail follows up and right once
        (2, 1):(1, 1),
        # 1 up, 2 right
        (1, 2):(1, 1),
        # 2up
        (2, 0):(1, 0),
        # 2up 1left
        (2, -1):(1, -1),
        # 1up, 2eft
        (1, -2):(1, -1),
        # 2left and so on
        (0, -2):(0, -1),
        (-1, -2):(-1,-1),
        (-2, -1):(-1, -1),
        (-2, 0):(-1, 0),
        (-2, 1):(-1, 1),
        (-1, 2):(-1, 1),
        (0, 2):(0, 1),
        # additional cases for part 2
        (2, 2):(1, 1),
        (-2, -2):(-1, -1),
        (-2, 2):(-1, 1),
        (2, -2):(1, -1)
      }
    new_tail_pos = tail + np.array(change_for_tail.get(tuple(difference), (0,0)))
    return new_tail_pos

Conclusion

I loved that. This is all I wanted from the grid task yesterday :D

The only thing I'm not too happy with is my unwieldy dictionary. I possibly could have deducted shorter rules but I hope the images made it clear what is happening in this function :)