Advent of Code: 2020 Day 05 solutions

SPOILER ALERT This is a post with my solutions and learnings from the puzzle. Don’t continue reading if you haven’t tried the puzzle on your own yet.

If you want to do the puzzle, visit adventofcode.com/2020/day/5.

My programming language of choice is python and all examples below are in python.

Key learnings

• Binary numbers

This puzzle makes play with binaries. Though not explicitly, but knowing of binaries will help out with this puzzle.

Puzzle

The puzzle today is about transforming seats to seat-ids using binary space partitioning. The seats consist of 10 letters. The first 7 can be F or B and the last 3 can be R or L. The letters stand for front, back, left, right.

The first 7 characters will either be F or B; these specify exactly one of the 128 rows on the plane (numbered 0 through 127). Each letter tells you which half of a region the given seat is in. Start with the whole list of rows; the first letter indicates whether the seat is in the front (0 through 63) or the back (64 through 127). The next letter indicates which half of that region the seat is in, and so on until you’re left with exactly one row.

The last three characters will be either L or R; these specify exactly one of the 8 columns of seats on the plane (numbered 0 through 7). The same process as above proceeds again, this time with only three steps. L means to keep the lower half, while R means to keep the upper half.

Every seat also has a unique seat ID: multiply the row by 8, then add the column.

Example input for some seats:

FBFBBFFRLR
BFBBBFBRLL
FBFBBFBLLL
BBBFFFBRRR
FBFFFBFRRL
BFFFFFFRLR

Part 1

The puzzle is to find the highest seat ID. To do this we need to transform the seat-names to IDs and find the one with maximum value.

The puzzle differentiates the first seven and last three letters. The value of the row should be multiplied with 8 and then the column value is added. That is just a trick to make the puzzle seem more difficult.

Multiplying the row value with 8 is the same as shifting it with 3 bits because of 2^3 = 8. Adding the column value then is just concatenating the two binary strings.

We can treat the seat-name as a binary where B and R are 1 and the other 0.

def calc_id(seat):
    transformation = { 'F': '0', 'B': '1', 'L': '0', 'R': '1'}
    binary = "".join([transformation[x] for x in seat])
    return int(binary,2)

def part1(data):
    ids = [calc_id(x) for x in data]
    return max(ids)
print "Part 1 solution: %d " % part1(data)

Part 2

The second is to find which pair of IDs are 2 steps apart. We can reuse our calc_id function above.

def part2(data):
    ids = [calc_id(x) for x in data]

    for i in range(max(ids)):
        low = i - 1
        high = i + 1
        if  low in ids and high in ids and i not in ids:
            return i
print "Part 2 solution: %d " % part2(data)

Alternative solutions

The transformation above could be solved with using an if statement in the list comprehension

binary = "".join(['1' if x in ['B','R'] else '0' for x in seat])

Or using the string-replacement.

binary = seat.replace('B', '1').replace('R', '1').replace('F', '0').replace('L', '0')

Using a translation table in python:

def calc_id(seat):
  translate_table = str.maketrans(dict(B="1", F="0", R="1", L="0"))
  return int(seat.translate(translate_table), 2)

Another alternative is to use binary calculations to transform the seat-names to IDs. Here is an example:

def part1(data):
    ids = []
    for line in data:
        current = 0
        row = 64
        for letter in line[:7]:
            if letter == 'B':
                current += row
            row = row >> 1 # Shift right 1 bit (same as dividing by 2)

        current = current << 3 # Shift left 3 bits (same as multiplying with 8)

        row = 4
        for c in line[7:]:
            if c == 'R':
                current += row
            row = row >> 1 # Shift right 1 bit (same as dividing by 2)
        ids.append(current)

    return max(ids)

My initial train of thought of part 1 was to find the maximum value by sorting the strings and manually calculate the binary number. As B is before F in the alphabet you could do sort the lines to get max row-value without even transforming to binary. Though R is after L and the column value will get reversed sorted. I forgot the reversed sorting on the column values, therefore failed and changed tactics. Guessing that was the purpose of AoC to differentiate column and row values.

This would be a full solution for part 1:

sorted_data = sorted([
  line.replace('R','B').replace('L','F')
  for line
  in data
])
print sorted_data[0]
# Step 2: Manually transform string to binary-string and then to 
#         decimal with help of a online-calculator.

A last alternative: An unreadable oneliner for part 1:

def part1(data):
  return max([
    int("".join([{ 'F': '0', 'B': '1', 'L': '0', 'R': '1'}[letter] or letter in x]), 2) 
    for x in data])

Python tips

Transform dictionaries

Dictionaries is a nice way to transform values during AoC puzzles. As I did in the part 1 above:

transformation = { 
  'F': '0', 
  'B': '1', 
  'L': '0', 
  'R': '1'
}

transformation['F'] # Returns '0'
transformation['B'] # Returns '1'
transformation['L'] # Returns '0'
transformation['R'] # Returns '1'

“".join(list)

To concatinate an array of strings it’s easiest to use the join-function. The join-function is called on a string that will work as a delimiter. A empty string would then join the array-strings without delimiter.

",".join['comma','seperated','string'] 
# => "comma,seperated,string"
"".join['no','seperation','at','all'] 
# => "noseperationatall"

int(‘10101010’, 2)

Using int() we can convert strings to numbers. If we want to convert a binary string we have to set the base to 2.

# Converting string using base 2
int('10111', 2) # outputs: 23

# Hexademical example:
int('FF', 16) # outputs: 255

max(arr)

In our solution we got a array of numbers. Finding the maximum value can be tempting to use an for-loop and a maximum_value variable. The max() function in python can take in an array as argument and does it for us.

max([6,2,3,8,3,9]) # outputs: 9

Thanks for reading!

I hope these solutions were helpful for you. Just ask if anything was hard to grasp.

Complete code can be found at: github.com/cNille/AdventOfCode/blob/master/2020/05.py