70 %

Toast is in Beta!Learn more →

Chris Biscardi

Advent of Code 2020 in Rust day 5: bitvec

Day 5 was basically binary numbers in disguise.

rust
#[test]
fn test_input_one() {
assert_eq!(process_seat("FBFBBFFRLR"), Seat { row: 44, column: 5 });
}

Turning FBFBBFFRLR into the numbers on the right (44 and 5) is as easy as converting them to 1s and 0s.

FBFBBFF -> 0101100 -> 32 + 8 + 4 -> 44

RLR -> 101 -> 4 + 1 -> 5

The bitvec crate allows us to turn an iterator of boolean values into a vector of bits, then load it as a u8.

bitvec.rs
rust
#[derive(Debug, Eq, PartialEq)]
struct Seat {
row: usize,
column: usize,
}
impl Seat {
fn id(&self) -> usize {
self.row * 8 + self.column
}
}
fn process_seat(input: &str) -> Seat {
let mut groups = input
.chars()
.group_by(|c| *c == 'F' || *c == 'B')
.into_iter()
.map(|(_, s)| {
s.map(|v| match v {
'B' | 'R' => true,
'F' | 'L' => false,
_ => panic!("asfkj"),
})
.collect::<BitVec>()
})
.collect::<Vec<_>>();
groups[0].reverse();
groups[1].reverse();
Seat {
row: groups[0][0..7].load::<u8>().into(),
column: groups[1][0..].load::<u8>().into(),
}
}

We can speed it up a little by dropping the group_by.

two_iterators.rs
rust
fn char_to_bool(c: char) -> bool {
match c {
'B' | 'R' => true,
'F' | 'L' => false,
_ => panic!("asfkj"),
}
}
fn process_seat(input: &str) -> Seat {
let mut a = input.chars().take(7).map(char_to_bool).collect::<BitVec>();
let mut b = input
.chars()
.skip(7)
.take(3)
.map(char_to_bool)
.collect::<BitVec>();
a.reverse();
b.reverse();
Seat {
row: a[0..].load::<u8>().into(),
column: b[0..].load::<u8>().into(),
}
}

Performance

I guess the best way to say this is that there's Work To Do here lol. 800us is about the longest anything has taken for the 2020 year so far. My guess is that if I was manually bit shifting around an array this would be the fastest approach, but I'm mostly fine if I have fairly maintainable code in the microsecond range.

examplelower boundbest guessupper bound
bitvec794.86 us798.13 us801.63 us
two_iterators489.08 us491.20 us493.49 us