Advent of Code 2022 - Day 6

Day 6: Tuning Trouble

Useful Links

‹›

• 2022 Main Page
• My solution code

Concepts and Packages Demonstrated

CounterEnumerate

Page Navigation

• Problem Intro
• Part 1
• Part 2
• Results

Problem Intro

Today’s problem is pretty simple. The logic is easy to understand, and it doesn’t need much code at all. This one took me under 5 minutes, which was nice!

So… We’re given a stream of text, and we’re asked to identify when the first sequence of unique characters appears.

The input data looks like a longer version of this…

nznrnfrfntjfmvfwmzdfjlvtqnbhcprsg

Part 1

A start-of-packet marker has been identified when the last four characters read are all different.

How many characters need to be processed before the first start-of-packet marker is detected?

My strategy here is very simple…

• Let distinct_chars_required = 4
• Read in the data as a string.
• Process the data stream one character at a time and track the slice of the last distinct_chars_required
• Perform a count of all chars in distinct_chars_required. If they are all 1, then all the characters are different.

And that’s it!

Here’s where all the good stuff happens:

def process_stream(data: str, distinct_char_sz: int) -> tuple:
    """ Process a str of data. 
    Report char position when the last distinct_char_sz chars are all different.

    Returns: tuple: (distinct_chars, position) """
    last_sz_chars = ""
    current_posn = 0
    
    stream = data[0:distinct_char_sz]
    for i, char in enumerate(data[distinct_char_sz:]):
        current_posn = i + distinct_char_sz
        last_sz_chars = data[current_posn-distinct_char_sz:current_posn]
        char_counts = Counter(last_sz_chars) # count chars in last four chars
        if all(count == 1 for count in char_counts.values()):
            break

        stream += char
    
    return (last_sz_chars, current_posn)

How does it work?

• First, we seed our stream with the first four characters from the input data.
• Then we enumerate over each character in the remaining data.
  • We store the last_sz_chars read, i.e. the last four characters.
  • We use the Python Counter class to create a dictionary that counts each character in our last_sz_chars string.
  • If the counts of every character in this string are all 1, then they are all unique characters. And we’re done!

An alternative approach would be to convert the last_sz_chars string to a set and count the size of the set. If the set is the same length as the string, then all the characters must be unique. This would be easier to write, but I wanted to demonstrate the cool Counter class!

Part 2

A start-of-message marker has been identified when the last 14 characters read are all different.

How many characters need to be processed before the first start-of-message marker is detected?

The solution here is identical to Part 1, except we now use a distinct_char_sz of 14, rather than 4.

Results

The final code looks like this:

from pathlib import Path
import time
from collections import Counter

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

MARKER_SZ = 4
START_MSG_SZ = 14

def main():
    with open(INPUT_FILE, mode="rt") as f:
        data = f.read()
        
    distinct_chars, current_posn = process_stream(data, MARKER_SZ)
    print(f"Part 1: {distinct_chars} at {current_posn}")
    
    distinct_chars, current_posn = process_stream(data, START_MSG_SZ)
    print(f"Part 2: {distinct_chars} at {current_posn}")    

def process_stream(data: str, distinct_char_sz: int) -> tuple:
    """ Process a str of data. 
    Report char position when the last distinct_char_sz chars are all different.

    Returns: tuple: (distinct_chars, position) """
    last_sz_chars = ""
    current_posn = 0
    
    stream = data[0:distinct_char_sz]
    for i, char in enumerate(data[distinct_char_sz:]):
        current_posn = i + distinct_char_sz
        last_sz_chars = data[current_posn-distinct_char_sz:current_posn]
        char_counts = Counter(last_sz_chars) # count chars in last four chars
        if all(count == 1 for count in char_counts.values()):
            break

        stream += char
    
    return (last_sz_chars, current_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: lhtw at 1909
Part 2: hndbzfswtmvcpr at 3380
Execution time: 0.0101 seconds

‹›