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?

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:

Then:

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 was made possible thanks to my patrons: Christian Oudard, Ronen Cohen, Matt Welke, Ivan Towlson, Nathan Lincoln, Daniel Wagner-Hall, Felix Weis, Henrik Sylvester Pedersen, Thor Kamphefner, VALENTIN MARIETTE, Kamran Khan, Cole Kurkowski, Arjen Laarhoven, Jeremy Kaplan, Jon Reynolds, Vicente Bosch, Chirag Jain, Ville Mattila, Marie Janssen, Vladyslav Batyrenko, Cameron Clausen, Pierre Guillaume Herveou, Agam Brahma, spike grobstein, Daniel Franklin, Jon Gjengset, Tex, Nick Thomas, Blaž Tomažič, Johan, Paul Marques Mota, Jakub Fijałkowski, Mitchell Hamilton, Ruben Duque, Brad Luyster, Max von Forell, Jake S, Justin, Dimitri Merejkowsky, Chris Biscardi, mrcowsy, René Ribaud, Alex Doroshenko, Julian, Vincent, Steven McGuire, Jack DeNeut, Chad Birch, Martin-Louis Bright, Chris Emery, Bob Ippolito, Jomer, John Van Enk, metabaron, Isak Sunde Singh, DaVince, Philipp Gniewosz, Richard Hill, Simon Rüegg, Roman Levin, V, Max Fermor, Mads Johansen, lukvol, Ives van Hoorne, Greg Stoll, Jan De Landtsheer, Scott Munro, Михаил Захаркин, Daniel Strittmatter, Evgeniy Dubovskoy, Sandro, Alex Rudy, Jake Rodkin, Shane Lillie, Romet Tagobert, Geekingfrog, Douglas Creager, Corey Alexander, Molly Howell, Jeff Crocker, knutwalker, Zachary Dremann, Olivier Peyrusse, Sebastian Ziebell, Julien Roncaglia, eigentourist, Amber Kowalski, Charlton Eivind Rodda, Jan Schiefer, Edil Kratskih, Chris Emerson, Matthew Campbell, Krasimir Slavkov, Juniper Wilde, Paul Kline, Pascal Hartig, Samir Talwar, TD, Kristoffer Ström, Henning Schmick, Ryan Levick, Antoine Boegli, Astrid Bek, Ryan, Yoh Deadfall, Justin Ossevoort, Jeremy, Tomáš Duda, playest, Meghana Gupta, Sebastian Dröge, Adam, Nick Gerace, Jeremy Banks, Rasmus Larsen, exelotl, Ramnivas Laddad, Yury Mikhaylov, Torben Clasen, Sam Rose, Nickolas Fotopoulos, C J Silverio, Walther, Pete Bevin, Shane Sveller, Marcel Jackwerth, Brian Dawn, Clara Schultz, Robert Cobb, jer, Wonwoo Choi, Hawken Rives, João Veiga, Dave Gauer, David Cornu, Richard Pringle, Adam Perry, Yann Schwartz, Jaseem Abid, Zinahe Asnake, Ryan Blecher, Benjamin Röjder Delnavaz, Grégoire Hubert, Matt Jadczak, Nazar Mokrynskyi, Julian Hofer, Mara Bos, Brandon, Jonathan Knapp, Maximilian, Seth Stadick, brianloveswords, Sean Bryant, Ember, Sebastian Zimmer, Makoto Nakashima, Geert Depuydt, Geoff Cant, Geoffroy Couprie, Michael Alyn Miller, Vengarioth, o0Ignition0o, Zaki, Raphael Gaschignard, Romain Ruetschi, Ignacio Vergara, Pascal, Cassie Jones, Pat Monaghan, Jane Lusby, Nicolas Goy, Suhib Sam Kiswani, Henry Goffin, Ted Mielczarek, Random832, Ryszard Sommefeldt, Jesús Higueras, 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