Avatar for fasterthanlime fasterthanlime
Dec 16, 2020 clock icon 6 min #rust · #advent-of-code

Day 5 (Advent of Code 2020)

From the series Advent of Code 2020

1

2

3

4

5

6

7

8

9

10

11

12

13

14

👋 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...

Cool bear

Let me guess: more parsing?

Amos

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.

Cool bear

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

Amos

Watch me!

$ cargo add peg
      Adding peg v0.6.3 to dependencies
Cool bear

Wait, hold on! Binary space partitioning... are we going to start with a 0..128 range and divide it by two each time?

Amos

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
Cool bear

bitvec, really?

Amos

Why not? I don't like to do bit-shifting. It's confusing.

Cool bear

So... you don't know how to do it?

Amos

I do! But even experts often get it wrong.

Cool bear

Experts? Or you?

Amos

...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
    }
}
Cool bear

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
Amos

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)
    }
}
Cool bear

But... that does multiply by 8.

Amos

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)
Cool bear

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-

Cool bear

Amos, wait.

Amos

Yeeees?

Cool bear

Couldn't we simplify our whole thing?

Amos

How do you mean?

Cool bear

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.

Amos

Go on...

Cool bear

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

Amos

That could work...

Cool bear

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)
Amos

Impressive.

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

Cool bear

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!

Amos

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

Cool bear

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!

You're reading the Advent of Code 2020 series.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

Comment on /r/fasterthanlime

(JavaScript is required to see this. Or maybe my stuff broke)

Here's another article just for you:

Cracking Electron apps open

Jul 03, 2023
clock icon 14 min #electron · #rust · #asar

I use the draw.io desktop app to make diagrams for my website. I run it on an actual desktop, like Windows or macOS, but the asset pipeline that converts .drawio files, to .pdf, to .svg, and then to .svg again (but smaller) runs on Linux.

So I have a Rust program somewhere that opens headless chromium, and loads just the HTML/JS/CSS part of draw.io I need to render my diagrams, and then use Chromium's "print to PDF" functionality to save a PDF.

Read more
About Legal Notice Privacy Policy Terms and Conditions