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

We’re back in the Easter Bunny’s headquarters, and this time we need to disable a system that can remotely wipe our prototype computer. To do this, we need to find the sector ID of the room where North Pole objects are stored.

We’re given a list of encrypted room names. Each room has a name, a sector ID, and a checksum. For example:

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]

A room is “real” if the checksum is the five most common letters in the encrypted name, in order, with ties broken by alphabetization.

Part 1

What is the sum of the sector IDs of the real rooms?

Strategy

My approach is to:

1. Parse each line to extract the encrypted name, sector ID, and checksum. I’ll use a regular expression for this.
2. For each room, I’ll count the occurrences of each character in the encrypted name.
3. I’ll then use collections.Counter to find the five most common characters.
4. I’ll compare this generated checksum with the one from the input to see if the room is “real”.
5. Finally, I’ll sum the sector IDs of all the real rooms.

Parsing the Input

I’ll use a regular expression to parse each line. The pattern (\D+)-(\d+)\[([a-z]{5})\] will capture the encrypted name, sector ID, and checksum.

To keep the data organized, I’ll use a dataclass to represent a room:

from dataclasses import dataclass

@dataclass
class Room:
    """ Dataclass for a room """
    enc_name: str
    sector_id: int
    checksum: str

A Note on Dataclasses

I’m using a dataclass here to store the information for each room. A dataclass is a great choice for a few reasons:

• Conciseness: It automatically generates special methods like __init__(), __repr__(), and __eq__() for you. This means you can create a simple data container class with minimal boilerplate code.
• Readability: By using a dataclass, the code becomes more self-documenting. It’s immediately clear that a Room object is a simple data structure with three fields: enc_name, sector_id, and checksum.

In short, a dataclass is a clean and modern way to create classes that are primarily used for storing data.

Validating the Room

Here’s the function to determine if a room is valid:

from collections import Counter
import string

def is_valid_room(room: Room) -> bool:
    """ Room is valid if descending counts of most frequent chars in room.enc_name
    matches the chars in the checksum.  Where char counts are tied, sort by alphabetic order.
    """
    # create dict of char:count(char) for each char in 'abcde...'
    char_counts = {char:room.enc_name.count(char) for char in string.ascii_lowercase}

    # Create a multiset from the dict, which stores item, count
    # Then use most_common(5) to retrieve the 5 most common items in the multiset
    top_five_counts = Counter(char_counts).most_common(5)
    
    # create a str from the most common chars and compare it to the checksum
    top_five_chars = "".join([item[0] for item in top_five_counts])
    if top_five_chars == room.checksum:
        return True
    
    return False

collections.Counter is a fantastic tool for this job. It’s a subclass of dict that’s designed for counting hashable objects. When we call most_common(5), it returns a list of the five most common elements and their counts, from the most common to the least. If two elements have the same count, they are ordered alphabetically, which is exactly what the puzzle requires.

A Note on join()

In the is_valid_room function, I use "".join([item[0] for item in top_five_counts]) to create the checksum string. The join() method is a string method that concatenates the elements of an iterable (like a list) into a single string. The string on which the method is called is used as a separator between the elements.

In this case, I’m calling join() on an empty string "". This means that the elements of the list will be joined together with no separator. The list itself is created using a list comprehension [item[0] for item in top_five_counts], which extracts the character (the first element, item[0]) from each tuple in the top_five_counts list.

So, if top_five_counts was [('a', 5), ('b', 4), ('c', 3), ('d', 2), ('e', 1)], the list comprehension would create ['a', 'b', 'c', 'd', 'e'], and "".join(...) would then create the string "abcde".

Part 2

What is the sector ID of the room where North Pole objects are stored?

Now we need to decrypt the names of the real rooms. The decryption algorithm is a Caesar cipher (or shift cipher):

1. Replace all dashes in the encrypted name with spaces.
2. Shift each letter forward by a number of places equal to the sector ID. The alphabet wraps around, so ‘z’ shifted by one becomes ‘a’.

Decrypting the Room Name

Here’s the decryption function:

def decrypt_room(room: Room) -> str:
    """ Decrypt room names.
    Replace "-" with " ".
    Then, shift all a-z chars by the sector ID
    """
    enc_str = room.enc_name.replace("-", " ")
    
    # Now shift each letter by the sector_id value. z wraps back to a.
    decrypted_str = []
    for char in enc_str:
        if char in string.ascii_lowercase:
            # conver to ascii code
            ascii_code = ord(char)
            
            # wrap around
            ascii_code += (room.sector_id % 26)

            # Note: z=122.  If we exceed this, we need to subtract 26.
            if (ascii_code > 122):
                ascii_code -= 26
                
            decrypted_str.append(chr(ascii_code))
        else:
            assert char == " ", "It must be a space"
            decrypted_str.append(char)
    
    return "".join(decrypted_str)

I’m using ord() to get the ASCII value of a character, and chr() to convert it back. The modulo operator (%) is used to handle sector IDs larger than 26. For example, a shift of 27 is the same as a shift of 1.

Here’s a closer look at how ord() and chr() work together for the decryption:

• ord(char): This function takes a character (a string of length one) and returns its corresponding ASCII (or Unicode) code point as an integer. For example, ord('a') returns 97.
• chr(ascii_code): This function is the inverse of ord(). It takes an integer ASCII code and returns the corresponding character. For example, chr(97) returns 'a'.

By converting the character to its integer representation, I can perform mathematical operations on it, like adding the sector ID to shift it. After the shift, I convert the new ASCII code back to a character. This ord() -> integer math -> chr() pattern is a common and effective way to perform character manipulation and ciphers in Python.

Finding the Room

With the decrypt_room function, I can now iterate through the real rooms and decrypt their names until I find “northpole object storage”:

for room in rooms:
    decrypted_room = decrypt_room(room)
    if decrypted_room == "northpole object storage":
        logging.info("Found %s with sector id %d", decrypted_room, room.sector_id)
        break

Results

The final output looks something like this:

Sector ID sum: 159935
Found northpole object storage with sector id 994
Execution time: 0.0136 seconds

‹›