Day 5 (Advent of Code 2020)

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

Time for another day of Advent of Code 2020.

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

Let me guess: more parsing?


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:


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?


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!(, $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|, ); 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.


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)


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 was made possible thanks to my patrons: Alexander Payne, Fredrik Østrem, David Barsky, Yufan Lou, Stephen Molyneaux, Barret Rennie, Thomas Corbin, MW, Jacob Cheriathundam, Michael Watzko, Embark Studios, Eugene Bulkin, Marcus Griep, Petar Radosevic, Tool Army, Tully, Santiago Lema, Spencer Gilbert, Jörn Huxhorn, Garrett Ward, DEX, Christian Oudard, Ronen Cohen, Thor Kamphefner, Kamran Khan, Cole Kurkowski, Arjen Laarhoven, Vicente Bosch, Chirag Jain, Ville Mattila, Marie Janssen, Vladyslav Batyrenko, Cameron Clausen, spike grobstein, Jon Gjengset, Paul Marques Mota, Jakub Fijałkowski, Mitchell Hamilton, Brad Luyster, Max von Forell, Jake S, Dimitri Merejkowsky, Chris Biscardi, René Ribaud, Alex Doroshenko, Vincent, Steven McGuire, Chad Birch, Chris Emery, Bob Ippolito, John Van Enk, metabaron, Isak Sunde Singh, Philipp Gniewosz, Mads Johansen, lukvol, Ives van Hoorne, Jan De Landtsheer, Daniel Strittmatter, Evgeniy Dubovskoy, Alex Rudy, Shane Lillie, Romet Tagobert, Douglas Creager, Corey Alexander, Molly Howell, knutwalker, Zachary Dremann, Sebastian Ziebell, Julien Roncaglia, Amber Kowalski, T, queenfartbutt, Paul Kline, Kristoffer Ström, Astrid Bek, Yoh Deadfall, Justin Ossevoort, Tomáš Duda, Jeremy Banks, Rasmus Larsen, Torben Clasen, C J Silverio, Walther, Pete Bevin, Shane Sveller, Clara Schultz, jer, Wonwoo Choi, Hawken Rives, João Veiga, Richard Pringle, Adam Perry, Benjamin Röjder Delnavaz, Matt Jadczak, Jonathan Knapp, Maximilian, Seth Stadick, brianloveswords, Sean Bryant, Ember, Sebastian Zimmer, Makoto Nakashima, Geoff Cant, Geoffroy Couprie, Michael Alyn Miller, o0Ignition0o, Zaki, Raphael Gaschignard, Romain Ruetschi, Ignacio Vergara, Pascal, Jane Lusby, Nicolas Goy, Ted Mielczarek, Aurora.

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

Read the next part

If you liked this article, please support my work on Patreon!

Become a Patron

Looking for the homepage?
Another article: Rust modules vs files