SPOILER ALERT
This is a post with my solutions and learning 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 learning
- 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(lines):
ids = [calc_id(line) for line in lines]
return max(ids)
print "Part 1 solution: %d " % part1(lines)
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(lines):
ids = [calc_id(line) for line in lines]
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(lines)
Alternative solutions
The transformation above could be solved with using an if statement in the list comprehension
def calc_id(seat):
binary = "".join(['1' if x in ['B','R'] else '0' for x in seat])
return int(binary,2)
Or using the string-replacement.
def calc_id(seat):
binary = seat.replace('B', '1').replace('R', '1').replace('F', '0').replace('L', '0')
return int(binary,2)
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(lines):
ids = []
for line in lines:
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 lines
])
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(lines):
return max([
int("".join([{ 'F': '0', 'B': '1', 'L': '0', 'R': '1'}[letter] or letter in line]), 2)
for line in lines])
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 concatenate 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
# Hexadecimal 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. Complete code can be found at:
github.com/cNille/AdventOfCode/blob/master/2020/05.py
Top comments (0)