Day 5
We’re finally in!!! Now to just lie down and sleep off the rest of the flight. Jk, it’s AoC so we have more problems to solve. Turns out our little code from before is too efficient, and we have to solve our own problems.
You board your plane only to discover a new problem: you dropped your boarding pass! You aren’t sure which seat is yours, and all of the flight attendants are busy with the flood of people that suddenly made it through passport control.
Instead of zones or groups, this airline uses binary space partitioning to seat people. A seat might be specified like FBFBBFFRLR, where
F
means “front”,B
means “back”,L
means “left”, andR
means “right”. The first 7 characters will either beF
orB
; 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.
Yeah, that was a long read. But a simpler way to analyze this would be to take a hint from the title of the problem - binary boarding. Instead of dealing with the top half and back half, we just need to understand that the sequence of 7 F
/B
characters and 3 L
/R
characters are simply binary representation of a number from 0-127 and 0-7! And as it turns out, computers are reaaally good at reading binary. (Thanks computers!)
So, what are binary numbers? A binary number is made up of only 0s and 1s. Counting using binary numbers is similar to decimal (that we’re so familiar with), but instead of using base 10 we’re in base 2! We add 1 to the right most digit, and everytime we “go over” 1, we add 1 to the next binary place (similar to adding to the next deimal place every time we “go over” 10 in demical base). Using such a system, we can represent decimal numbers in their binary forms.
Decimal | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Binary | 0 | 1 | 10 | 11 | 100 | 101 | 110 | 111 | 1000 | 1001 | 1010 | 1011 | 1100 | 1101 | 1110 | 1111 |
For example, we can parse an input of FBFBFBFRRR
into 0101010111
. We split these up into the row number (first 7 digits, 0101010
) and column number(last 3 digits, 111
). In binary representation, this is a row 42
and column 7
.
Now that we have our strategy planned out, let’s head straight into it! First, we read in our input and parse the strings into their binary representation:
import pandas as pd
seats_bin = []
# import data
with open("input.txt", 'r') as file:
for line in file:
line=line.split('\n')[0]
# recognize that the format of the string is binary in the format: row = [:7], col = [7:]
current_seat = ""
for i in line:
current_seat+={'F': '0','B': '1', 'L': '0', 'R': '1'}.get(i)
seats_bin.append(current_seat)
Part 1
Alrighty - we just pop in our code for converting from binary to decimal, and then apply the given formula to get our seat ID.
seats_id = []
for i in seats_bin:
# converting from binary to row and column no.
row = int(i[:7],2)
col = int(i[7:],2)
# seat ID: multiply the row by 8, then add the column
seats_id.append(row*8+col)
print('Ans:', max(seats_id))
Ans: 953
Ans: 975
Part 2
Ding! The “fasten seat belt” signs have turned on. Time to find your seat.
Since we have the whole list of seat IDs, we simply need to find the seat number that is missing (and isn’t the first OR the last seat!).
# sort all seats in numerical order
seats_id.sort()
for i, seat_id in enumerate(seats_id):
# explicitly skip first seat
if seat_id + 1 != seats_id[i + 1]:
# my seat is the empty seat behind someone elses'!
print('Ans:', seat_id + 1)
break
Ans: 615
Ans: 615
Thoughts after day 5: DID YOU SAY BINARY?
Day 6
As your flight approaches the regional airport where you’ll switch to a much larger plane, customs declaration forms are distributed to the passengers. However, the person sitting next to you seems to be experiencing a language barrier and asks if you can help.
Ah yes some good ol custom declaration forms. Ngl, this is my favorite part of international flights! Filling in the forms is like a little puzzle where you figure out the translations from a foreign language into English (or be like me and scratch your head, asking your neighbour for some help COUGHS) and it’s like your first little glimpse of a foreign country! (Yeah can you tell that I want to travel soon? I do want to travel soon)
The form asks a series of 26 yes-or-no questions marked a through z. All you need to do is identify the questions for which anyone in your group answers “yes”. For each of the people in their group, you write down the questions for which they answer “yes”, one per line. Each group’s answers are separated by a blank line, and within each group, each person’s answers are on a single line.
Alllrightyyy! That’s not too bad in terms of parsing. First, let’s read in our input according to groups:
import pandas as pd
import re
groups = []
# import data
with open("input.txt", 'r') as file:
curGroup = ""
for line in file:
if line == "\n" or line == " ":
groups.append(curGroup)
curGroup = ""
else:
# add current person's answer to group!
curGroup+=line
Part 1
This can be done simply enough with sets - one of the 4 built in data types in Python. This creates a collection that is unordered and unindxed, which is great for us in this application since we can simply count the number of unique elements in each group!
count_p1 = 0
# add number of unique answers to current count
for i in groups:
count_p1 += len(set(i.replace('\n','')))
print('Ans:', count_p1)
Ans: 6310
Ans: 6310
Part 2
As you finish the last group’s customs declaration, you notice that you misread one word in the instructions.
Ooookay so this one is a little more tricky. But, we can still use sets to help us with a little bit more tweaking. First, we count the number of group members and the number of unique questions, and simply check if the number of answers matches the number of group members for each question. And voila - we’re rolling!
count_p2 = 0
for i in groups:
# count group members and number of unique questions
group_mem = i.count('\n')
qns = set(i.replace('\n',''))
# check if number of answers matches number of group members
for char in qns:
if i.count(char) == group_mem:
count_p2+=1
print('Ans:', count_p2)
Ans: 3193
Ans: 3193
Thoughts after day 6: mhmm fun with sets!