Advent of Code 2022 - Day 20

Day 20: Grove Positioning System

Useful Links

‹›

Concepts and Packages Demonstrated

regex deque enumerate comprehensions

Problem Intro
Part 1
Part 2
Results

Problem Intro

This one was quite tricky, but not nearly as hard as yesterday. And it ultimately ends up being very little code.

We need to find the grove, and we have the coordinates. But they’re in some sort of encrypted format:

The encrypted coordinates are a list of numbers. We need to decrypt them using a process called mixing:

Process each number in its original order in the list.
Move that number forwards or backwards a number of places; the number of places to move is given by the number’s value.
The list is circular, so a number that is moved can wrap around either end.

Part 1

What is the sum of the three numbers that form the grove coordinates?

We’re told that the grove coordinates can be found by looking at the 1000th, 2000th, and 3000th numbers after the value 0, wrapping around the list as necessary.

The real challenge here is that we need to move the numbers in the order in which they were originally listed, but any given number’s position will continue to change as we go.

My strategy is:

Read our input list into a deque, since a deque provides a circular list implementation with the ability to rotate a value any arbitrary number of places.
As we read the numbers, enumerate them, so that we always know the original number position. Thus, our deque is composed of tuples of (original index, value).
Now, perform n iterations, where n is the length of the input list:
- Rotate our numbers so that the next pair is at the left end.
- Pop this pair and retrieve the value, i.e. the number of places we need to move this pair by.
- Now rotate the deque by this amount. The result is that the number after the insertion point will now be at the front.
- Finally, add our popped pair back at the right hand end. Thus, it is logically inserted before the pair now at position 0.
- When each iteration has completed, the number at the end will always be the number that moved.

Here’s my mix() function:

def mix(enumerated: deque):
    """ Perform the mix algorithm on our enumerated deque of numbers """
    # Move each number once, using original indexes
    # We can't iterate over actual values from enumerated, since we'll be modifying it as we go
    for original_index in range(len(enumerated)): 
        while enumerated[0][0] != original_index: # bring our required element to the left end
            enumerated.rotate(-1) 
    
        current_pair = enumerated.popleft() 
        shift = current_pair[1] % len(enumerated)  # retrieve the value to move by; allow for wrapping over
        enumerated.rotate(-shift) # rotate everything by n positions
        enumerated.append(current_pair) # and now reinsert our pair at the end
        
        # print(enumerated)  # for debugging
        
    return enumerated

Although we could rotate each number by the actual value of that number, this is very inefficient. That’s because if the value of the number is larger than the length of our deque, most of those rotations will be redundant. We only want to rotate by our number, modulo the length of the deque.

And here’s how we read in the data and mix it:

def main():
    with open(INPUT_FILE, mode="rt") as f:
        data = list(map(int, f.read().splitlines()))
    
    # Part 1
    enumerated = deque(list(enumerate(data.copy())))  # deque of tuples of (original index, value)    
    enumerated = mix(enumerated)

If we enable the print() statement with the sample data, we get output that looks like this:

deque([(2, -3), (3, 3), (4, -2), (5, 0), (6, 4), (1, 2), (0, 1)])
deque([(3, 3), (4, -2), (5, 0), (6, 4), (0, 1), (2, -3), (1, 2)])
deque([(5, 0), (6, 4), (0, 1), (1, 2), (3, 3), (4, -2), (2, -3)])
deque([(6, 4), (0, 1), (1, 2), (4, -2), (2, -3), (5, 0), (3, 3)])
deque([(0, 1), (1, 2), (2, -3), (5, 0), (3, 3), (6, 4), (4, -2)])
deque([(3, 3), (6, 4), (4, -2), (0, 1), (1, 2), (2, -3), (5, 0)])
deque([(5, 0), (3, 3), (4, -2), (0, 1), (1, 2), (2, -3), (6, 4)])

See how the pair that last moved is always at the end?

Now we’re ready to find the grove coordinates. We know we need to find the 1000th, 2000th and 3000th numbers that are after 0. So I’ve implemented this function which retrieves the value of any number in the deque which is n items after the position of the number 0:

def value_at_n(values: list, n: int):
    """ Determine the value at position n in our list.
    If index is beyond the end, then wrap the values as many times as required. """
    digit_posn = (values.index(0)+n) % len(values)
    return values[digit_posn]

Then all we need to do is call this function with 1000, 2000 and 3000:

    coord_sum = 0
    for n in (1000, 2000, 3000):
        coord_sum += value_at_n([val[1] for val in enumerated], n)
    print(f"Part 2: {coord_sum}")

Part 2

Oh, decryption just got a bit more complicated:

Multiply each number in the original list by the decryption key value.
Then mix the list 10 times.

Then, as before:

What is the sum of the three numbers that form the grove coordinates?

Part 2 results in much larger starting numbers, and many more mix iterations. If we had been rotating by the value of the number, this would be a problem for us. We would find Part 2 takes too long. Fortunately, we’re already only rotating by the modulo, so the larger number values makes little difference to us.

For Part 2, I only need to add this:

    # Part 2
    new_data = [val*DECRYPTION_KEY for val in data]
    enumerated = deque(list(enumerate(new_data)))  # new deque    
    for _ in range(10): # run the mix 10 times, but always with same enumeration (starting order)
        enumerated = mix(enumerated) 
        
    coord_sum = 0
    for n in (1000, 2000, 3000):
        coord_sum += value_at_n([val[1] for val in enumerated], n)
    print(f"Part 2: {coord_sum}")

It uses a list comprehension to multiply each initial input value by the decryption key. We then build a new deque from this new list of numbers. And then we simply mix the deque 10 times, as required.

Results

The final code looks like this:

from collections import deque
from pathlib import Path
import time

SCRIPT_DIR = Path(__file__).parent
INPUT_FILE = Path(SCRIPT_DIR, "input/sample_input.txt")
# INPUT_FILE = Path(SCRIPT_DIR, "input/input.txt")

DECRYPTION_KEY = 811589153

def main():
    with open(INPUT_FILE, mode="rt") as f:
        data = list(map(int, f.read().splitlines()))
    
    # Part 1
    enumerated = deque(list(enumerate(data.copy())))  # deque of tuples of (original index, value)    
    enumerated = mix(enumerated)
    
    coord_sum = 0
    for n in (1000, 2000, 3000):
        # Turn our enumerated list into a list
        coord_sum += value_at_n([val[1] for val in enumerated], n)
    print(f"Part 1: {coord_sum}")
    
    # Part 2
    new_data = [val*DECRYPTION_KEY for val in data]
    enumerated = deque(list(enumerate(new_data)))  # new deque    
    for _ in range(10): # run the mix 10 times, but always with same enumeration (starting order)
        enumerated = mix(enumerated) 
        
    coord_sum = 0
    for n in (1000, 2000, 3000):
        coord_sum += value_at_n([val[1] for val in enumerated], n)
    print(f"Part 2: {coord_sum}")

def mix(enumerated: deque):
    """ Perform the mix algorithm on our enumerated deque of numbers """
    # Move each number once, using original indexes
    # We can't iterate over actual values from enumerated, since we'll be modifying it as we go
    for original_index in range(len(enumerated)): 
        while enumerated[0][0] != original_index: # bring our required element to the left end
            enumerated.rotate(-1) 
    
        current_pair = enumerated.popleft() 
        shift = current_pair[1] % len(enumerated)  # retrieve the value to move by; allow for wrapping over
        enumerated.rotate(-shift) # rotate everything by n positions
        enumerated.append(current_pair) # and now reinsert our pair at the end
        
        # print(enumerated)
        
    return enumerated
    
def value_at_n(values: list, n: int):
    """ Determine the value at position n in our list.
    If index is beyond the end, then wrap the values as many times as required. """
    digit_posn = (values.index(0)+n) % len(values)
    return values[digit_posn]

if __name__ == "__main__":
    t1 = time.perf_counter()
    main()
    t2 = time.perf_counter()
    print(f"Execution time: {t2 - t1:0.4f} seconds")

And the output looks like this:

Part 1: 5904
Part 2: 8332585833851
Execution time: 7.8667 seconds

Not too bad.

‹›

Learning Python with Advent of Code Walkthroughs