Christmas Advent of Code 2022 - Day 9

Advent is a Christmas season of preparation for the celebration of the birth and the second coming of Jesus Christ. It begins on the fourth Sunday before Christmas, and ends on the Christmas Eve. An Advent calendar is used to count the days of Advent from the first Sunday to Christmas Eve.

There are many Advent calendar products for customers to buy. They usually contains 24 or 25 (usually starts on December 1st for the purpose of convenience) hidden items that one can open one per day. Advent of Code is such an Advent calendar of programming puzzles made by Eric Wastl which one can solve one task per day for fun! It accompanies us to go through the darkest days of the year.

Today is the 9th day of December and the Advent code puzzle for today is quite interesting, so I post my solution here to share! For the other days, my solution was/will be updated on my Github. The puzzles are solved in Python and written in notebook for presentation reason.

Day 9 Part 1

The original description of the code puzzle is here. I formulated the task as following:

There is a bridge which one can simulate its stability by measuring the movements of the rope (where H is the Head of the rope, T is the Tail). Given a set of movements of H (in the data file). It looks like for example (where R, U, L, D means moving right, up, left, down, the number means steps. So R 4 means H moves 4 steps to the right):

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

There is also a rule for how T moves with H:

  • If the head is ever two steps directly up, down, left, or right from the tail, the tail must also move one step in that direction so it remains close enough:

      .....    .....    .....
  .TH.. -> .T.H. -> ..TH.
  .....    .....    .....

  • Otherwise, if the head and tail aren’t touching and aren’t in the same row or column, the tail always moves one step diagonally to keep up:

      .....    .....    .....
  .....    ..H..    ..H..
  ..H.. -> ..... -> ..T..
  .T...    .T...    .....
  .....    .....    .....

By following the movements of H according to the data file, and executing and movements of T following the above rules, one can simulate how the rope moves. Specifically, one wants to count up all of the positions the tail visited at least once (including the start position s). For example, if the initial state is 

......
......
......
......
H.....  (H covers T, s)

The above example of movements of H, the positions that T has visited is:

..##..
...##.
.####.
....#.
s###..

which gives a total number of positions of 13.

Calculate how many positions does the tail of the rope visit at least once according to the given data file.

After formulating the task, we know that the head/H follows exactly the movements from the data file, while the tail/T follows the above rule based on H’s position. Then we can create two functions, one for moving H, one for moving T. Note that the tail follows the head every move, so the functions should move ONE step a time.

I first read the data file which contains the instructions about how the head/H should move:

1
data_moves = pd.read_table('data/input9.txt', sep=" ", header=None).to_numpy()

Then I wrote the methods to move the head/H (moveH) based on the current position of H and the instruction, and to move the tail/T (moveT) by following the rule given above, based on the current position of T and the current position of H.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
def _checkEdges(pos_to):
    global nrow, ncol
    if pos_to[0] < 0 or pos_to[0] > nrow - 1 or pos_to[1] < 0 or pos_to[1] > ncol - 1:
        print('Map too small!',pos_to)
    return pos_to
    
def _markPosT(pos_T):
    global state
    state[pos_T[0],pos_T[1]] = 1
    
def _isTouching(pos_H, pos_T):
    return pos_T == pos_H or (abs(pos_T[0]-pos_H[0]) <= 1 and abs(pos_T[1]-pos_H[1]) <= 1)
    
def moveH(pos_from, direction):
    if direction in ['L','R']:
        pos_to = [pos_from[0], pos_from[1]-1 if direction == 'L' else pos_from[1]+1]
    else: # ['U','D']
        pos_to = [pos_from[0]-1 if direction == 'U' else pos_from[0]+1, pos_from[1]]
    pos_to = _checkEdges(pos_to)
    return pos_to
    
def moveT(pos_from, pos_H, if_track=True):
    if _isTouching(pos_from, pos_H):
        pos_to = pos_from
    else:
        if pos_H[1] != pos_from[1] and pos_H[0] != pos_from[0]: # move diagonally
            pos_to = [pos_from[0], pos_from[1]+1] if pos_H[1] > pos_from[1] else [pos_from[0], pos_from[1]-1]
            pos_to = [pos_to[0]+1, pos_to[1]] if pos_H[0] > pos_to[0] else [pos_to[0]-1, pos_to[1]]
            pos_to = _checkEdges(pos_to)
            if if_track: _markPosT(pos_to)
        elif pos_H[1] != pos_from[1]: # move directly up/down
            pos_to = [pos_from[0], pos_from[1]+1] if pos_H[1] > pos_from[1] else [pos_from[0], pos_from[1]-1]
            pos_to = _checkEdges(pos_to)
            if if_track: _markPosT(pos_to)
        else: # move directly left/right
            pos_to = [pos_from[0]+1, pos_from[1]] if pos_H[0] > pos_from[0] else [pos_from[0]-1, pos_from[1]]
            pos_to = _checkEdges(pos_to)
            if if_track: _markPosT(pos_to)
    return pos_to

Then I set up the environment, where the map size is set up to a large enough size:

1
2
3
4
5
6
7
nrow = 600
ncol = 600
pos_s = [nrow//2,ncol//2] # start position
pos_H = pos_s
pos_T = pos_s
state = np.zeros((nrow, ncol), dtype=int)
state[pos_T[0],pos_T[1]] = 1 # T has visited

Then we can try to test it on the given smaller test example (saved in my Github data/input9_test1.txt) first, since it is easier to debug if anything goes wrong. One can also print the state map (can set to a smaller size if the data is fewer) to debug visually. After finishing debugging, we can now run the code on the full data file (data/input9.txt)!

1
2
3
4
5
6
7
for move_H in data_moves:
    for i in range(move_H[1]):
        pos_H = moveH(pos_H, move_H[0])
        pos_T = moveT(pos_T, pos_H)
print('Current position of H', pos_H)
print('Current position of T', pos_T)
print('All positions of T has visited', sum(sum(state)))

Now we successfully simulated the movements of the rope with a head knot and a tail knot, and tracked how the tail knot moved after all the movements.

Day 9 Part 2

The second part of the task comes with an extension of part one. In part one, there are only two knots: head/H and tail/T. In part two, rather than two knots (H and T), one now must simulate a rope consisting of 10 knots. One knot is still the head of the rope and moves according to the series of motions (the data file). Each knot further down the rope follows the knot in front of it using the same rules as before. And now, only the positions visited by the last knot (9) need to be tracked.

For a second example:

R 5
U 8
L 8
D 3
R 17
D 10
L 25
U 20

The state after the movements now become:

..........................
..........................
..........................
..........................
..........................
..........................
..........................
..........................
..........................
#.........................
#.............###.........
#............#...#........
.#..........#.....#.......
..#..........#.....#......
...#........#.......#.....
....#......s.........#....
.....#..............#.....
......#............#......
.......#..........#.......
........#........#........
.........########.........

For the second example, the tail (9) visits 36 positions (including s) at least once.

So for this part, the head/H doesn’t change, which means that we can still use the moveH function for it. For the tails (9 tails instead of 1 now), each one follows the previous one (new head) based on the same rule of moving tail in part one, which means we can reuse the same moveT function for all the tails by updating the corresponding head. And now only the real tail (the last knot) needs to be tracked.

Then we setup the environment for this one. (Before trying the full data file, one can still try the code first on the given example (data/input9_test2.txt) and make sure the code works for that.)

1
2
3
4
5
6
7
8
9
nrow = 600
ncol = 600
pos_s = [nrow//2,ncol//2] # start position
pos_H = pos_s
pos_Ts=[]
for i in range(9):
    pos_Ts.append(pos_s)
state = np.zeros((nrow, ncol), dtype=int)
state[pos_Ts[0][0],pos_Ts[0][1]] = 1 # any T has visited

Then execute the moves and mark all the places the last knot has visited!

1
2
3
4
5
6
7
8
9
10
for move_H in data_moves:
    for i in range(move_H[1]):
        pos_H = moveH(pos_H, move_H[0])
        for i in range(9):
            pos_from = pos_H if i == 0 else pos_Ts[i-1]
            iftrack = i == 8
            pos_Ts[i] = moveT(pos_Ts[i], pos_from, iftrack)
print('Current position of H', pos_H)
print('Current position of T', pos_Ts)
print('All positions of T has visited', sum(sum(state)))

That is it for Day nine! Isn’t it interesting?