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