9 min
Day 5 (Advent of Code 2020)
👋 This page was last updated ~4 years ago. Just so you know.
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!
$ 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!
$ 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:
#[derive(Default, Debug, PartialEq)]
struct Seat {
row: u8,
col: u8,
}
And then, well, then we do bit crims:
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?
#[test]
fn test_parse() {
let input = "FBFBBFFRLR";
let seat = Seat::parse(input);
assert_eq!(seat, Seat { row: 44, col: 5 });
}
$ 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:
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:
#[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!
$ cargo add itertools
Adding itertools v0.9.0 to dependencies
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);
}
$ 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:
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);
}
$ 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.
#[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:
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:
$ cargo run --quiet Our seat ID is 623
We've solved another puzzle 😎
See you next time!
Thanks to my sponsors: Lena Schönburg, L0r3m1p5um, Geoffroy Couprie, Moritz Lammerich, Astrid, Benjamin Röjder Delnavaz, Daniel Wagner-Hall, Boris Dolgov, Ryan, Ross Williams, Mikkel Rasmussen, Luiz Irber, Aleksandre Khokhiashvili, Joshua Roesslein, David White, Antoine Rouaze, Romet Tagobert, Xirvik Servers, David Barsky, Gran PC and 227 more
If you liked what you saw, please support my work!
Donate on GitHub
Donate on Patreon
Here's another article just for you:
23 min
Disclaimer:
At some point in this article, I discuss The Rust Foundation. I have received a $5000 grant from them in 2023 for making educational articles and videos about Rust.
I have NOT signed any non-disclosure, non-disparagement, or any other sort of agreement that would prevent me from saying exactly how I feel about their track record.
Disclaimer: