Advent of Code 2020 Day 5 – Our Solutions

James HeslipAPLLeave a Comment

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))



Roy

I went the long way round with this one with a massive nested if statement. This got me the answer I needed, but on reflection I thought there must be an easier way.

I decided that it might be easier to use the first 8 characters and assign 1 to B and 0 to F and treat it like binary, but the thought was as far as I got. I never bothered to investigate it as I was too far behind on other days requirements.

Roy's solution was a little long to publish on this blog, but can be downloaded.

Roy’s code was too long to include here, but can be downloaded.



Sam G

Day 5 Part 1: I found Day 5 interesting, I immediately noticed the similarity to a search algorithm I had covered in college, the Binary Search algorithm. However, even though I had spotted that similarity, I overlooked the Binary aspect of the question and went about answering it a different way. I had thought about the way the search algorithm works and tried to code something along those lines.

I started by looping through every seat and splitting the rows and columns to be processed separately. For the rows, I generated the numbers 0-127 and looped through the row items removing either the lower or upper half of the remaining numbers, depending on whether or not the item was an ‘F’ or a ‘B’ until I was left with one number. I then repeated the same process with the columns however, filtering the numbers 0-7 using ‘L’ and ‘R’. I then used the resulting numbers to apply the calculation to retrieve the ID number of the seat in question like this: column number + row number * 8.

To get the required answer for Part 1, I simply took the highest value from the list of ID numbers I had generated.


r←P5_Q1 data;seat;rowSplit;colSplit;c;op;rows;cols;ids
ids←''
:For seat :In data
     rowSplit colSplit←{(¯3↓⍵)(¯3↑⍵)}seat
     rows←¯1+⍳128
     :For c :In rowSplit
         op←⍎'↑↓'⊃⍨'FB'⍳c
         rows←(2÷⍨⍴rows)op rows
     :EndFor

     cols←¯1+⍳8
     :For c :In colSplit
         op←⍎'↑↓'⊃⍨'LR'⍳c
         cols←(2÷⍨⍴cols)op cols
     :EndFor

     ids,←cols+rows×8

:EndFor
r←⌈/ids

For Part 2, I copied my Part 1 solution and made some slight amendments to the end, as the initial ID number generation was the same. In hindsight, I could have refactored the ID generation into a sub function as to not repeat myself across both solutions.

As for the amendments made to solve this part, I sorted the list of IDs into ascending order, determined the minimum and maximum IDs in the list. I then generated a list of IDs up to the maximum ID value and then dropped everything before the minimum ID value and checked what ID didn’t exist in the list of previously generated IDs, this left me with ID of my seat.


r←P5_Q2 data;seat;rowSplit;colSplit;c;op;rows;cols;ids;seats;max;min
ids←''
:For seat :In data
     rowSplit colSplit←{(¯3↓⍵)(¯3↑⍵)}seat
     rows←¯1+⍳128
     :For c :In rowSplit
         op←⍎'↑↓'⊃⍨'FB'⍳c
         rows←(2÷⍨⍴rows)op rows
     :EndFor

     cols←¯1+⍳8
     :For c :In colSplit
         op←⍎'↑↓'⊃⍨'LR'⍳c
         cols←(2÷⍨⍴cols)op cols
     :EndFor

     ids,←cols+rows×8

:EndFor
ids←ids[⍋ids]
min←¯1+⊃ids
max←⌈/ids
seats←min↓⍳max
r←seats~ids

After having discussed this problem with the rest of the team, I wish I hadn’t overlooked the binary aspect I picked up on before, as I believe that using binary to denary conversion is a much better solution.



Afterword

Personally, I enjoyed this problem a lot. I feel like APL is a great choice for a problem like this due to:

  • Booleans being treated as integer values.
  • The primitive functions it offers (built-in change of base, etc).
  • Its array-based nature to easily execute functions en-masse.

That said, I felt my Python solution was also fairly terse, and came quite naturally when writing. I think I prefer APL here, but these problems are always a great opportunity the hone my skills in lesser practiced areas.


About the Author

James Heslip

APL Team Leader


James is an APL Programmer with a keen interest in mathematics. His love for computing was almost an accident. From a young age he always enjoyed using them- playing video games and such- but it was never considered that anything more would come from it. James originally had plans to pursue a career in finance. More about James.


More from James



Other Posts