Advent of Code 2016 - Day 4

Day 4: Security Through Obscurity

Useful Links

‹›

• 2016 Main Page
• My solution code

Concepts and Packages Demonstrated

Regular Expressions (Regex)DataclassesCollections.Counterstring moduleord() and chr()Modulo Operator

Problem Intro

In this Advent of Code puzzle, we encounter a list of rooms, each with an encrypted name, a sector ID, and a checksum. Our task is to identify “real” rooms by validating their checksums and then perform a decryption process on the names of these real rooms.

A room is considered “real” if its checksum matches the five most common letters in its encrypted name. In case of ties in frequency, letters are sorted alphabetically.

Here’s an example of the input data format:

aaaaa-bbb-z-y-x-123[abxyz]
a-b-c-d-e-f-g-h-987[abcde]
not-a-real-room-404[oarel]
totally-real-room-200[decoy]

Part 1: Sum of Sector IDs of Real Rooms

The first part of the puzzle requires us to calculate the sum of the sector IDs of all the “real” rooms.

Solution Approach

1. Parsing Input: We use regular expressions to parse each line of the input, extracting the encrypted name, sector ID, and checksum.
2. Checksum Validation: For each room, we determine if it’s “real” by comparing its checksum with the five most frequent characters in its encrypted name.
   • We count the occurrences of each lowercase letter in the encrypted name (excluding dashes).
   • We then use collections.Counter to efficiently find the five most common characters.
   • If there are ties in frequency, Counter naturally handles this by sorting alphabetically, which aligns with the puzzle’s rules.
   • Finally, we compare the generated top five characters with the provided checksum.

Code Snippet (Parsing and Validation)

import re
from dataclasses import dataclass
from collections import Counter
import string

@dataclass
class Room:
    enc_name: str
    sector_id: int
    checksum: str

def is_valid_room(room: Room) -> bool:
    char_counts = {char:room.enc_name.count(char) for char in string.ascii_lowercase}
    top_five_counts = Counter(char_counts).most_common(5)
    top_five_chars = "".join([item[0] for item in top_five_counts])
    return top_five_chars == room.checksum

def main():
    # ... (file reading and setup) ...
    pattern = re.compile(r"(\D+)-(\d+)\[([a-z]{5})\]")
    rooms: list[Room] = []

    for line in data:
        match = pattern.match(line)
        if match:
            enc_name, sector_id, checksum = match.groups()
            room = Room(enc_name, int(sector_id), checksum)
            if is_valid_room(room):
                rooms.append(room)

    sector_id_sum = sum(room.sector_id for room in rooms)
    # ... (logging) ...

In the is_valid_room function:

• We create a dictionary char_counts to store the frequency of each lowercase letter in the enc_name.
• collections.Counter is then used to get the most_common(5) characters. This handles both frequency and alphabetical tie-breaking.
• The characters are joined to form a string top_five_chars which is then compared with the room.checksum.

Part 2: Decrypting Room Names

For the second part, we need to decrypt the names of the real rooms to find a specific room: “northpole object storage”.

Solution Approach

The decryption process involves two steps:

1. Replace Dashes: All hyphens (-) in the encrypted name are replaced with spaces.
2. Shift Characters: Each letter in the modified name is shifted forward by a number of positions equal to the room’s sector ID. The shifting wraps around the alphabet (e.g., ‘z’ shifted by 1 becomes ‘a’).

Code Snippet (Decryption)

import string

def decrypt_room(room: Room) -> str:
    enc_str = room.enc_name.replace("-", " ")
    decrypted_str = []
    for char in enc_str:
        if char in string.ascii_lowercase:
            ascii_code = ord(char)
            ascii_code += (room.sector_id % 26) # Shift by sector_id, modulo 26 for wrap-around

            if (ascii_code > ord('z')): # If we exceed 'z', wrap back to 'a'
                ascii_code -= 26
                
            decrypted_str.append(chr(ascii_code))
        else:
            decrypted_str.append(char) # Keep spaces as they are
    
    return "".join(decrypted_str)

def main():
    # ... (Part 1 code) ...
    for room in rooms:
        decrypted_room = decrypt_room(room)
        if decrypted_room == "northpole object storage":
            # ... (logging) ...
            break

In the decrypt_room function:

• We iterate through each character of the (dash-replaced) encrypted name.
• If the character is a lowercase letter, we convert it to its ASCII value using ord().
• We then add the sector_id (modulo 26 to handle shifts larger than the alphabet size) to the ASCII value.
• If the new ASCII value exceeds that of ‘z’, we subtract 26 to wrap it back to the beginning of the alphabet.
• Finally, we convert the ASCII value back to a character using chr() and append it to our decrypted_str.

Conclusion

This puzzle effectively combines string manipulation, regular expressions, and character encoding/decoding. The use of collections.Counter simplifies the checksum validation, while basic ASCII arithmetic handles the character shifting for decryption. The solution is efficient and directly addresses both parts of the problem.

‹›