Advent of Code: 2020 Day 05
Tags: adventofcode, python
Published: 2020-12-05 07:39:24

**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](https://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.


```python
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.
```python
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
```python
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.
```python
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:
```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:
```python
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:

```python
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:
```python
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:
```python
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.

```python
",".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`.

```python
# 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.

```python
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](https://github.com/cNille/AdventOfCode/blob/master/2020/05.py)