Opportunity of code 2020 -- boarding seat problem

Advent of code 2020 – Boarding seat problem

Advent of code 2020 – Binary Boarding

This problem , It's about using 10 Characters of bytes indicate boarding seats , There are 128 That's ok 、8 Column , Such as "FBFBBFFRLR" It means that the position is on the second 44 That's ok 、 The first 5 The place of the column .

• B and F Used to represent the number of rows ;
  F: It means the first half , Such as 0-127, So the first one F Indicates that the position is 0-63 Range ;
  B: Indicates the latter half , Such as 0-63, So the first 2 individual B Indicates that the position is 32-63 Range ;
  …
  To launch , The number of rows is 44

• R and L Used to indicate the number of columns ;
  R: Indicates the latter half ;
  L: It means the first half ;
  …
  To launch , The number of columns is 5

Structure defining position

Because the number of rows and columns does not exceed 255, Then the number of rows and columns can be used 8bit The integer representation of , stay Rust In Chinese, it means u8.

#[derive(Default, Debug, PartialEq)]
struct Seat {
    row: u8,
    col: u8,
}

Resolution location

We know 127 The binary representation of 7 individual 1;

127

0111 1111

Then you can go ahead 7 A character F and B It can be expressed in order 7 individual bit On a 0 perhaps 1, F Express 0, B Express 1;

FBFBBFF
0101100
 representative 44

Again , After use 3 A character R and L It can be expressed in order 3 individual bit On a 0 perhaps 1, L Express 0, R Express 1;

RLR
101
 representative 5

stay Rust Can be used in bitvec Libraries are easy to do bit operation .
You can use the command to import

cargo add bitvec

Define the location resolution method ：

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();
        {
            let row = BitSlice::<Msb0, _>::from_element_mut(&mut res.row);

            for (i, &b) in bytes[0..Self::ROW_BITS].iter().enumerate() {
                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
    }

}

Test location resolution method ：

#[test]
fn test_parse() {
    let input = "FBFBBFFRLR";
    let seat = Seat::parse(input);

    assert_eq!(seat, Seat { row: 44, col: 5 });
}

Get the position number from the position

We define the data deconstruction of location Seat, Location by row and col Express .

The position number can be expressed as ：

id = row * 8 + col

Position number calculation function :

impl Seat {
    const ROW_BITS: usize = 7;
    const COL_BITS: usize = 3;


    fn id(&self) -> u64 {
        //  Instead of multiplying the number of rows by 8
        ((self.row as u64) << Self::COL_BITS) + (self.col as u64)
    }
}

test ：

#[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);
}

problem 1 ： Calculate the maximum position number in the test set

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

}

problem 2 ： Find the missing location number

last_id, That is, discontinuous Id, Such as 7 and 9 There is a gap between 8

find last_id, Then calculate all position numbers , And then sort it , We use all the position numbers Vec Storage , Then to achieve sort() Method , Then Seat Data structure implementation PartialOrd, Ord Trait.

change Seat data structure

#[derive(Clone, Copy,Default, Debug, PartialEq, PartialOrd, Eq, Ord)]
struct Seat {
    row: u8,
    col: u8,
}

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.id() - last_id.id();
            if gap > 1{
                println!("Our seat ID is {}", last_id.id());
                return;
            }
        }
        last_id = Some(id);
    }
}

Reference learning ：https://fasterthanli.me/series/advent-of-code-2020/part-5