Advent of Code 2020 Day 5 – Our Solutions

Airports can be hectic, especially around Christmas. Nobody wants to get stuck and miss their flight, even if it is completely hypothetical. Advent of Code’s day 5 question deals with a chaotic situation of boarding passes and locating your seat on a plane; seems a distant memory now with all that’s going on in the world...

Your given input is a set of boarding passes which will allow you to determine Seat IDs. The first 7 characters help determine the row, and the last 3 determine the column. The example given is ‘“FBFBBFFRLR” where F means "front", B means "back", L means "left", and R means "right". Each letter tells you which half of a region the given seat is in’ You can see the full details of this problem and the others on the Advent of Code website.

Jonners

Day 5 Part 1: What is the highest seat ID on a boarding pass?

⌈/{2⊥('B'=7↑⍵),'R'=¯3↑⍵}¨d5

The key to this problem was realising the boarding passes were just binary numbers in disguise! By encoding the 'B's as 1s and 'F's as 0s for the first section, and then the 'R's and 1s and 'L's as 0s for the second, we get the seat number in binary. Then it is simply a case of finding the maximum of the lot; 885 in my case.

Day 5 Part 2: What is the ID of your seat?

{⌈/⍵~⍨⍳⌈/⍵}{2⊥('B'=7↑⍵),'R'=¯3↑⍵}¨d5

Since we know the seat number must be in the same range as the other seats (i.e. starting at 35 and ending at 885) I simply removed the list of known seat numbers from the list of integers between the minimum and maximum, to get the answer 623.

James (me!)

Here is my solution for Part 1 in APL:

r←q5_1 input;seatIDs

 ⍝ Original solution:
 ⍝ I split the input string into rows and columns
 ⍝ converting strings into binary
 ⍝ and using the formula of cols(base-2) + rows(base-2) × 8

 seatIDs←{
     cols rows←¯3(↑{⍺ ⍵}↓)⍵
     rn cn←'BR'{2⊥⍺=⍵}¨rows cols
     cn+rn×8
 }¨input

 r←⌈⌿seatIDs

 ⍝ ---------
 ⍝ Due to the formula of Seat ID, multiplying row by 8
 ⍝ is the same as multiplying by 2*3 (where * is exponent in APL).
 ⍝ As the columns are always three in length,
 ⍝ the shift in bits is the same as just applying the formula directly.
 ⍝ Essentially I can convert the input string to binary as a whole
 ⍝ and yield the same result as using the formula. Shocked I didn't see
 ⍝ this the first time round... *facepalm*

 seatIDs←{
     2⊥⍵∊'BR'
 }¨input

 r←⌈⌿seatIDs

 ⍝ ---------
 ⍝ Optimised and golfed for fun...
 r←⌈⌿2⊥⍉'BR'∊⍨↑input

And here is my solution for Part 2 in APL:

r←q5_2 input;seatIDs;allSeats;min;max

 ⍝ Using part of my phase 1 solution to generate
 ⍝ all seat IDs, I generate the set of integers in the
 ⍝ range from [min, max] inclusive. By removing the seatIDs
 ⍝ from this set, the one number left will be my seat.

 seatIDs←2⊥⍉'BR'∊⍨↑input
 min max←(⌊/{⍺ ⍵}⌈/)seatIDs
 allSeats←min+0,⍳max-min
 r←allSeats~seatIDs

And here is my solution, this time in Python.

# read input file (\inputs\5.txt) and format text to numbers if necessary
from utils.read_input import read_input

def bin_to_dec(input_list):
    # convert list of integers from base-2 to base-10

    # Convert each item in the list to text, and join them into one string
    # ... converting back to an integer in base 2.
    return int("".join(str(i) for i in input_list), 2)

def get_ids(data):
    # convert ticket number to seat id

    # For each ticket
    # ... Compare each character to 'B' and 'R'.
    # ... if each char is either of those set bit, otherwise don't.
    # Convert from binary list- i.e. [0, 1, 1]- to binary singleton- i.e. 011
    # ... and covert to decimal.
    ids = [bin_to_dec([int(char in ['B', 'R']) for char in ticket])
           for ticket in data]
    return ids

def q5_1(data):
    # get the set of seat IDs and return the largest
    ids = get_ids(data)
    return max(ids)

def q5_2(data):
    # get the set of seat IDs
    ids = get_ids(data)

    # iterate over the set of integers from [min, max] inclusive
    # ... and when you come across a number in that set which isn't
    # ... in the seat IDs, that must be your seat.
    for i in range(min(ids), 1+max(ids)):
        if not i in ids:
            return i

if __name__ == "__main__":

    data = read_input(5)
    print(q5_1(data))
    print(q5_2(data))