# Day 5 (Advent of Code 2020)

This article is part of the Advent of Code 2020 series.

### Contents

• Part 2

Time for another day of Advent of Code 2020.

For Day 5, we're going to have to do...

Let me guess: more parsing?

Correct!

So there's an airline that uses binary space partitioning when referring to seats - there's 128 rows and 8 columns. The first 7 characters are either F (Front, for the lower half) and B (back, for the upper half), and the last 3 are L (Left, for the lower half) or R (Right, for the upper half).

They give the following example. For FBFBBFFRLR:

• Start by considering the whole range, rows 0 through 127.
• F means to take the lower half, keeping rows 0 through 63.
• B means to take the upper half, keeping rows 32 through 63.
• F means to take the lower half, keeping rows 32 through 47.
• B means to take the upper half, keeping rows 40 through 47.
• B keeps rows 44 through 47.
• F keeps rows 44 through 45.
• The final F keeps the lower of the two, row 44.

Then:

• Start by considering the whole range, columns 0 through 7.
• R means to take the upper half, keeping columns 4 through 7.
• L means to take the lower half, keeping columns 4 through 5.
• The final R keeps the upper of the two, column 5.

And since the peg crate worked for us so well last time, I want to try a little challenge... to solve almost the whole problem with just a single grammar.

Almost, you can't solve all your problems with parsers.

Watch me!

Shell session
$cargo add peg Adding peg v0.6.3 to dependencies  Wait, hold on! Binary space partitioning... are we going to start with a 0..128 range and divide it by two each time? I've got a different idea... Effectively, what the problem statement is saying is that FBFBBF is simply a bit string! Where F means 0 and B means 1. Which means... wait, I got an even better idea! Shell session $ cargo rm peg
Removing peg from dependencies
$cargo add bitvec Adding bitvec v0.19.4 to dependencies  bitvec, really? Why not? I don't like to do bit-shifting. It's confusing. So... you don't know how to do it? I do! But even experts often get it wrong. Experts? Or you? ...both. So, bitvec is really neat. It lets you treat anything as a vector of... bits! And that's exactly what we want to do here. First, there's fewer than 255 rows and fewer than 255 columns, so we can use an u8 for both: Rust code #[derive(Default, Debug, PartialEq)] struct Seat { row: u8, col: u8, }  And then, well, then we do bit crims: Rust code use bitvec::prelude::*; impl Seat { const ROW_BITS: usize = 7; const COL_BITS: usize = 3; fn parse(input: &str) -> Self { let bytes = input.as_bytes(); let mut res: Seat = Default::default(); { // treat res.row as a collection of bits... let row = BitSlice::<Msb0, _>::from_element_mut(&mut res.row); // for each F or B element... for (i, &b) in bytes[0..Self::ROW_BITS].iter().enumerate() { // set the corresponding bit, in positions 1 through 7 (0-indexed) row.set( (8 - Self::ROW_BITS) + i, match b { b'F' => false, b'B' => true, _ => panic!("unexpected row letter: {}", b as char), }, ); } } { let col = BitSlice::<Msb0, _>::from_element_mut(&mut res.col); for (i, &b) in bytes[Self::ROW_BITS..][..Self::COL_BITS].iter().enumerate() { col.set( (8 - Self::COL_BITS) + i, match b { b'L' => false, b'R' => true, _ => panic!("unexpected col letter: {}", b as char), }, ); } } res } }  Impressive! Does it work? Rust code #[test] fn test_parse() { let input = "FBFBBFFRLR"; let seat = Seat::parse(input); assert_eq!(seat, Seat { row: 44, col: 5 }); }  Shell session $ cargo test --quiet

running 1 test
.
test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out


Looks like it!

Next up, we have to compute the seat ID, based on the row and column. We can make a method for that.

The problem statement says to multiply the row number by 8 but... we see right through their game. We can just do some bit shifting this time:

Rust code
impl Seat {
fn id(&self) -> u64 {
((self.row as u64) << Self::COL_BITS) + (self.col as u64)
}
}


But... that does multiply by 8.

Yes, but conceptually... it's different.

We can add tests from the examples given in the problem statement:

Rust code
#[test]
fn test_seat_id() {
macro_rules! validate {
($input: expr,$row: expr, $col: expr,$id: expr) => {
let seat = Seat::parse($input); assert_eq!( seat, Seat { row:$row,
col: $col } ); assert_eq!(seat.id(),$id);
};
}

validate!("BFFFBBFRRR", 70, 7, 567);
validate!("FFFBBBFRRR", 14, 7, 119);
validate!("BBFFBBFRLL", 102, 4, 820);
}


Time to answer the question: what's the highest seat ID in our puzzle input?

itertools has a max function which works on iterators, which I like!

Shell session
$cargo add itertools Adding itertools v0.9.0 to dependencies  Rust code fn main() { let max_id = itertools::max( include_str!("input.txt") .lines() .map(Seat::parse) .map(|seat| seat.id()), ); println!("The maximum seat ID is {:?}", max_id); }  Shell session $ cargo run --quiet
The maximum seat ID is Some(885)


Nice! That was quick.

### Part 2

Part 2 wants us to find a missing seat from the list! But it's not at the very front and not at the very back of the plane, because those seats don't actually exist. It's somewhere in between.

So what we can do here is-

Amos, wait.

Yeeees?

Couldn't we simplify our whole thing?

How do you mean?

Hear me out: we make our whole Seat type just a u16.

Because when you think about it, that's all it is right? Well, technically it's a u10 - 7 bits for the row, 3 bits for the column.

Go on...

And then we just parse all ten bits in one go - and we have getters for the row and column instead!

That could work...

Or better yet! We don't have getters for row and column, since none of the questions ask for them anyway.

Here, let me show you:

Rust code
use bitvec::prelude::*;

#[derive(Clone, Copy, Default, Debug, PartialEq)]
struct Seat(u16);

impl Seat {
fn parse(input: &str) -> Self {
let mut res: Seat = Default::default();

let bits = BitSlice::<Lsb0, _>::from_element_mut(&mut res.0);
for (i, &b) in input.as_bytes().iter().rev().enumerate() {
bits.set(
i,
match b {
b'F' | b'L' => false,
b'B' | b'R' => true,
_ => panic!("unexpected letter: {}", b as char),
},
)
}

res
}
}

#[test]
fn test_seat_id() {
assert_eq!(Seat::parse("BFFFBBFRRR"), Seat(567));
assert_eq!(Seat::parse("FFFBBBFRRR"), Seat(119));
assert_eq!(Seat::parse("BBFFBBFRLL"), Seat(820));
}

fn main() {
let max_id = itertools::max(
include_str!("input.txt")
.lines()
.map(Seat::parse)
.map(|seat| seat.0),
);
println!("The maximum seat ID is {:?}", max_id);
}

Shell session
$cargo t -q running 1 test . test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out$ cargo r -q
The maximum seat ID is Some(885)


Impressive.

You know, in some cultures, it's considered rude to refactor your colleague's entire work in one go.

What are you talking about? I even reversed the iterator and used Lsb0 (least-significant bit first) order so we don't have to worry about arithmetic!

I'll admit... it's shorter.

Think of all the Twitter mentions I just saved you.

And now, to answer part 2's question. Here's an idea: how about we collect all the IDs, sort them (from smallest to largest), then iterate, keep track of the last one, and whenever the gap is more than 1 - that's it! We've found our seat.

First off, to be able to sort a Vec<Seat>, we need to derive Ord - to indicate that our type (which is just an u16 in a trenchcoat) has total ordering.

Rust code
#[derive(Clone, Copy, Default, Debug, PartialEq, Eq, PartialOrd, Ord)]
struct Seat(u16);


And then, well, we just have to do what we set out to do. For the first iteration, we won't have a "last id", so we'll just use an Option here:

Rust code
fn main() {
let mut ids: Vec<_> = include_str!("input.txt").lines().map(Seat::parse).collect();
ids.sort();

let mut last_id: Option<Seat> = None;
for id in ids {
if let Some(last_id) = last_id {
let gap = id.0 - last_id.0;
if gap > 1 {
println!("Our seat ID is {}", last_id.0 + 1);
return;
}
}
last_id = Some(id);
}
}


And just like that:

Shell session
\$ cargo run --quiet
Our seat ID is 623


We've solved another puzzle 😎

See you next time!

This article is part 5 of the Advent of Code 2020 series.

If you liked what you saw, please support my work!

## Latest video

Getting good at SNES games through DLL injection

Are you ever confronted with a problem and then think to yourself "wait a minute, I know how to code?" — that's exactly what happened there.

You can watch more videos over there

Looking for the homepage?
Another article: The curse of strong typing