Edd Mann Developer

Advent of Code 2016 - Day 4 - Security Through Obscurity

On the fourth day of Advent of Code 2016 we are asked to validate and decrypt a listing of room names.

Part 1

The input consists of a listing of encrypted room names, each with a sector id and accompanying checksum. For part one we are required to filter down to only the valid rooms (based on their checkum) and return the sum of these sector ids. A room is real (not a decoy) if the checksum is the five most common letters in the encrypted name, in order, with ties broken by alphabetization.

We will begin by parsing each room entry into a tuple, consisting of the room name (without any -), sector id (as an integer) and checksum.

def parse_rooms(input):
    return [(name.replace('-', ''), int(id), checksum)
            for (name, id, checksum) in re.findall(r'([a-z\-]+)(\d+)\[([a-z]+)\]', input)]

With the rooms now parsed, we can continue on to validating if a subject room is real or a decoy.

def is_real_room(name, checksum):
    generated = ''.join(c for c, _ in sorted(
        Counter(name).most_common(), key=lambda o: (-o[1], o[0])))
    return generated.startswith(checksum)

The function above uses the Counter collection provided within Python to tally up the letter occurrences present in the room name. From here we then sort the listing, initially based on occurrence -o[1], and then ties based on alphabetization o[0]. As we have generated the checksum for the entire room name we only wish to assert that this value starts with the provided checksum.

Finally, we can combine these two functions together to filter-map the listing down to the valid room sector ids. The sum of these sector ids can then be returned to result in the desired answer 🌟.

def part1(input):
    return sum(id for (name, id, checksum) in parse_rooms(input)
               if is_real_room(name, checksum))

Part 2

For part two, we are required to now deduce the sector id for the decoded room name which contains northpole. The encrypted room names have been constructed using a Caesar cipher - based on cycling each letter forward through the alphabet a number of times equal to the room’s sector id. This can be achieved using Python’s string character translation support like so.

def decode(name, id):
    az = string.ascii_lowercase
    shift = id % len(az)
    return name.translate(str.maketrans(az, az[shift:] + az[:shift]))

Alternatively, we could also achieve the same result by calculating the resulting ASCII character number per letter, like so.

def decode(name, id):
    return ''.join(chr(((ord(c) - ord('a')) + id) % 26 + ord('a')) for c in name)

Using this new function we can now iterate through the rooms, decoding each name as we go, until we finally land on the one that includes northpole. From here, we can return this rooms sector id and answer the second part of today’s problem 🌟.

def part2(input):
    return next(id for (name, id, _) in parse_rooms(input)
                if 'northpole' in decode(name, id))