AoC Day4 – Security Through Obscurity

Advent Of Code

This is the puzzle for Day 4 of Advent Of Code 2016.  All of my code for this day can be found in my Day 4 Repository

Finally, you come across an information kiosk with a list of rooms. Of course, the list is encrypted and full of decoy data, but the instructions to decode the list are barely hidden nearby. Better remove the decoy data first.

Each room consists of an encrypted name (lowercase letters separated by dashes) followed by a dash, a sector ID, and a checksum in square brackets.

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.

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

My input for the puzzle was 991 lines long and included this excerpt:

bnqqnrhud-okzrshb-fqzrr-cdrhfm-105[rhqbd]
yhtwhnpun-tpspahyf-nyhkl-jovjvshal-zlycpjlz-487[hlpyj]
iutyaskx-mxgjk-hatte-lotgtiotm-176[shzku]
gntmfefwitzx-kqtbjw-xfqjx-645[nmfsa]
jvsvymbs-jhukf-jbzavtly-zlycpjl-695[frnkz]
dlhwvupglk-zjhclunly-obua-jvuahputlua-825[ulahj]
wyvqljapsl-jhukf-jvhapun-ylzlhyjo-487[jlhya]
ghkmaihex-hucxvm-lmhktzx-267[hmxka]
irgyyolokj-vrgyzoi-mxgyy-xkikobotm-670[ryfvl]
kwzzwaqdm-zijjqb-amzdqkma-564[qzdtv]
rflsjynh-idj-xytwflj-541[jflyd]

First I needed to split the input lines into their respective parts – Room name, sectorID, and checksum.  I created a method that would take in a line and return these parts:

def GetParts(line):
    parts = line.strip().split("-")
    nonName = parts[len(parts)-1]
    sectorID = nonName[:nonName.find("[")]
    name = line[:line.find(sectorID)].replace("-", " ")
    checksum = nonName[-6:-1]
    return name, checksum, int(sectorID)

Next I needed a method to evaluate a room with it’s checksum to tell if the room is valid.  In order to do this, I needed to convert the name to a set of characters with counts for each, sort them alphabetically to break ties, then sort them by decreasing count.  If the letters in this order match the checksum, it is a valid room:

def IsValidRoom(names, checksum):
    allNames = names.replace(" ", "")
    count = lambda s : list([char, s.count(char)] for char in set(s))
    counts = count(allNames)
    counts.sort(key = lambda x: x[0])
    counts.sort(key = lambda x: x[1], reverse=True)
    value = counts[0][0] + counts[1][0] + counts[2][0] + counts[3][0] + counts[4][0]
    return value == checksum

Now I can iterate through the lines and add the sectorID from valid lines to a running total:

SectorSum = 0

with open("Input") as inputFile:
    lines = inputFile.readlines()
 
for line in lines:
    names, checksum, sectorID = GetParts(line)
    if IsValidRoom(names, checksum):
        SectorSum += sectorID
 
print "Sum of valid SectorIDs:", SectorSum

Part 2 tells us how to translate the coded room names, and gives us a specific room to target:

With all the decoy data out of the way, it’s time to decrypt this list and get moving.

The room names are encrypted by a state-of-the-art shift cipher, which is nearly unbreakable without the right software. However, the information kiosk designers at Easter Bunny HQ were not expecting to deal with a master cryptographer like yourself.

To decrypt a room name, rotate each letter forward through the alphabet a number of times equal to the room’s sector ID. A becomes B, B becomes C, Z becomes A, and so on. Dashes become spaces.

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

I needed a method to shift the characters of a string of text a specific distance.  Importing the “string” library gives us an easy way to do this:

def Shift(text, distance):
    alphabet = string.ascii_lowercase
    shifted_alphabet = alphabet[distance:] + alphabet[:distance]
    table = string.maketrans(alphabet, shifted_alphabet)
    return text.translate(table)

Then I changed the main function so that in addition to summing up the valid sectorIDs, it checks for the room with all of our stuff:

for line in lines:
    names, checksum, sectorID = GetParts(line)
    if IsValidRoom(names, checksum):
        SectorSum += sectorID
        shiftedRoomName = Shift(names, sectorID % 26).strip()
        print "SectorID:", sectorID, "Room Name:", shiftedRoomName
        if (shiftedRoomName == "northpole object storage"):
            targetSectorID = sectorID
 
print "\nSectorID of NorthPole Object Storage:", targetSectorID
print "Sum of valid SectorIDs:", SectorSum

Finally allowing us to find the right room.