« posts | «« home

Day 6: Tuning Trouble

View puzzle page »

Skip to the code?

If you’d like to read my solution first, the code is available on GitHub.

Puzzle 1

Day 6’s puzzle input is a 4096-char string meant to represent a datastream. Within the stream is a marker indicating the start-of-packet which consists of 4 different characters. Prior to this marker, all possible sequences of 4 characters will include repetition of one or more characters. The task is to discover the index of the last character of the marker.

For example, in mjqjpqmgbljsphdztnvjfqwrcgsmlb the first four different characters in sequence are jqpm starting at index 4. The last character in the marker is m which is index 7 - this is the location which matters.

Solution

My approach to this puzzle is to have a buffer of 4 characters that takes care of cleaning itself out. That way I can check the buffer for duplicates, if there are any, shove the next character in (pushing out the furthest left character), and check again.

Python’s deque works great for this with its maxlen argument.

from collections import deque

char_buffer = deque(maxlen=4)

We can iterate over the content of the string and also grab our index using enumerate. We’ll also get the first three characters into the buffer with a conditional and continue.

with open("day6_input.txt", encoding="utf-8") as f:
    line = f.readline()
    for i, c in enumerate(line):
        if len(char_buffer) <= 3:
            char_buffer.append(c)
            continue

If the deque has 3 characters or less, we can’t check yet if we have our 4-character sequence so we’ll just fill the buffer and jump to the next iteration.

From the 4th iteration, we want to add the new character and then check if there are any duplicates in the deque.

char_buffer.append(c)
duplicates = [char_buffer.count(x) for x in char_buffer]

I’m using a list comprehension here to generate a list which contains a count of each character in the deque. So a deque like deque(['q', 'q', 'b', 'q']) would produce the list [3, 3, 1, 3] while deque(['q', 'b', 'q', 'g']) would produce [2, 1, 2, 1]. We’re looking for a list where the count of each item is 1 so there are no duplicates. We can find this by just summing the list (looking for a sum of 4).

if sum(duplicates) == 4:
    print(i+1)
    break

Once we’ve found the sequence with no duplicates, we just need to know the index of the rightmost character which we have in i (plus one to account for zero-index). The result is our answer to puzzle 1.

Puzzle 2

The second part of the puzzle asks to find a start of message marker which follows the same rules but expects to see 14 distinct characters, rather than 4. We already have all the parts for this, we just need to adjust the deque length, the minimum buffer fill, and the sum check.

...
char_buffer = deque(maxlen=14)
...
if len(char_buffer) <= 13:
...
if sum(duplicates) == 14:
...

The new result is the answer to puzzle 2.

Source Code

View the code on GitHub.

Would you like to read something else by me?

« «

» »

« posts | «« home