Thanks to my sponsors: Yves, SeniorMars, Kristoffer Winther Balling, Daniel Papp, Berkus Decker, Astrid, Guillaume E, Max Bruckner, Philipp Hatt, Mario Fleischhacker, jatescher, Richard Stephens, Henrik Tudborg, Herman J. Radtke III, Tobias Bahls, Max von Forell, Jean Manguy, Tabitha, budrick, Sarah Berrettini and 230 more
Day 11 (Advent of Code 2020)
👋 This page was last updated ~4 years ago. Just so you know.
Another day, another problem.
This time the problem looks suspiciously like Conway's Game of Life, or, I guess, any old Cellular automaton.
We have a map like so:
L.LL.LL.LL
LLLLLLL.LL
L.L.L..L..
LLLL.LL.LL
L.LL.LL.LL
L.LLLLL.LL
..L.L.....
LLLLLLLLLL
L.LLLLLL.L
L.LLLLL.LL
And for each iteration:
L
symbols turn into#
if there's no#
in any of the 8 adjacent cells#
symbols turn intoL
if four or more of the adjacent cells are#
.
symbols do not change
This is a delightful problem. We can even recycle some of the stuff we did in Day 3!
First a 2D vector type:
#[derive(Debug, Clone, Copy, PartialEq)]
struct Vec2 {
x: i64,
y: i64,
}
Then a tile enum:
#[derive(Clone, Copy, PartialEq)]
enum Tile {
Floor,
EmptySeat,
OccupiedSeat,
}
impl Default for Tile {
fn default() -> Self {
Self::Floor
}
}
With a neat Debug
implementation:
use std::fmt;
impl fmt::Debug for Tile {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
let c = match self {
Tile::Floor => '.',
Tile::EmptySeat => 'L',
Tile::OccupiedSeat => '#',
};
write!(f, "{}", c)
}
}
And then, a Map
- this time, let's make it generic. Just for fun!
struct Map<T> {
size: Vec2,
tiles: Vec<T>,
}
We can only implement new
if T
implements Default
:
impl<T> Map<T>
where
T: Default,
{
fn new(size: Vec2) -> Self {
let num_tiles = size.x * size.y;
Self {
size,
tiles: (0..num_tiles)
.into_iter()
.map(|_| Default::default())
.collect(),
}
}
}
Then Map::index
, to map from 2D space to our 1D storage space:
impl<T> Map<T> {
fn index(&self, pos: Vec2) -> Option<usize> {
if (0..self.size.x).contains(&pos.x) && (0..self.size.y).contains(&pos.y) {
Some((pos.x + pos.y * self.size.x) as _)
} else {
None
}
}
}
From there we can easily implement set
:
impl<T> Map<T> {
fn set(&mut self, pos: Vec2, tile: T) {
if let Some(index) = self.index(pos) {
self.tiles[index] = tile;
}
}
}
And for get
, we'll require T
to be copy, so we don't have to deal
with references ever:
impl<T> Map<T>
where
T: Copy,
{
fn get(&self, pos: Vec2) -> Option<T> {
self.index(pos).map(|index| self.tiles[index])
}
}
Next up - we'll have to deal with neighbors, so it would be neat if we could enumerate neighbors of a given cell:
impl<T> Map<T> {
fn neighbor_positions(&self, pos: Vec2) -> impl Iterator<Item = Vec2> {
(-1..=1)
.map(|dx| (-1..=1).map(move |dy| (dx, dy)))
.flatten()
.filter(|&(dx, dy)| !(dx == 0 && dy == 0))
.map(move |(dx, dy)| Vec2 {
x: pos.x + dx,
y: pos.y + dy,
})
}
}
This seems hairy, how about a quick test?
#[test]
fn test_neighbor_positions() {
use std::collections::HashSet;
let map = Map::<()>::new(Vec2 { x: 3, y: 3 });
let positions: HashSet<_> = map
.neighbor_positions(Vec2 { x: 1, y: 1 })
.map(|v| (v.x, v.y))
.collect();
for p in &[
(0, 0),
(0, 1),
(0, 2),
(1, 0),
(2, 0),
(1, 2),
(2, 2),
(2, 1),
] {
assert!(positions.contains(p));
}
}
$ cargo t -q
running 1 test
.
test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out
Alright, carry on.
Then for good measures, we could have a .neighbor_tiles
method that returns
an iterator of Tile
!
impl<T> Map<T>
where
T: Copy,
{
fn neighbor_tiles(&self, pos: Vec2) -> impl Iterator<Item = T> + '_ {
self.neighbor_positions(pos)
.filter_map(move |pos| self.get(pos))
}
}
What's with the + '_
?
Well, that iterator is only valid as long as &self
is borrowed,
because it's reading from it!
Ah And what would the lifetime of impl Iterator<Item = T>
(without
any additional annotations) be?
Just like Box<T>
, it defaults to 'static
, which is only true for owned
types (like our neighbor_positions
iterator, which owns everything it needs
to yield items) or, I guess, truly 'static
references, like a const
,
something that's leaked with Box::leak
or the result of include_str!
.
Okay! Now we can start implementing some of the cellular automaton logic.
Let's do it as a method on Tile
:
impl Tile {
fn next<I>(self, neighbors: I) -> Self
where
I: Iterator<Item = Self>,
{
match self {
Self::Floor => Self::Floor,
Self::EmptySeat => match neighbors
.filter(|t| matches!(t, Self::OccupiedSeat))
.count()
{
// no one around? we can sit here!
0 => Self::OccupiedSeat,
// social distancing please
_ => Self::EmptySeat,
},
Self::OccupiedSeat => {
match neighbors.filter(|t| matches!(t, Self::OccupiedSeat)).count() {
// up to 3 neighbors: still okay for now
0..=3 => Self::OccupiedSeat,
// that's too many folks!
_ => Self::EmptySeat,
}
}
}
}
}
Let's see, what else do we want... ah right, a nice Debug
implementation
for Map
too - but only if T
itself is Debug
. Oh, and Copy
too since
we need get
:
impl<T> fmt::Debug for Map<T>
where
T: fmt::Debug + Copy,
{
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
for y in 0..self.size.y {
for x in 0..self.size.x {
write!(f, "{:?}", self.get(Vec2 { x, y }).unwrap())?;
}
writeln!(f)?;
}
Ok(())
}
}
And then... you know what would be neat? Since the rules are applied to all tiles simultaneously, it would be neat if we could iterate through all tiles.
impl<T> Map<T>
where
T: Copy,
{
fn iter(&self) -> impl Iterator<Item = T> + '_ {
self.tiles.iter().copied()
}
}
But uhhh.. we're going to need to know their positions as well, right?
So we can check their neighbors?
Right! To do this, we can introduce another type: Positioned
:
#[derive(Debug)]
struct Positioned<T>(Vec2, T);
And make our iter
method returns Positioned<T>
as its Item
type:
impl<T> Map<T>
where
T: Copy,
{
// this replaces our previous `iter` method
fn iter(&self) -> impl Iterator<Item = Positioned<T>> + '_ {
(0..self.size.y)
.map(move |y| {
(0..self.size.x).map(move |x| {
let pos = Vec2 { x, y };
Positioned(pos, self.get(pos).unwrap())
})
})
.flatten()
}
}
Let's try it out:
fn main() {
let mut m = Map::new(Vec2 { x: 3, y: 3 });
m.set(Vec2 { x: 1, y: 1 }, Tile::OccupiedSeat);
for tile in m.iter() {
println!("{:?}", tile);
}
}
$ cargo run --quiet
Positioned(Vec2 { x: 0, y: 0 }, .)
Positioned(Vec2 { x: 1, y: 0 }, .)
Positioned(Vec2 { x: 2, y: 0 }, .)
Positioned(Vec2 { x: 0, y: 1 }, .)
Positioned(Vec2 { x: 1, y: 1 }, #)
Positioned(Vec2 { x: 2, y: 1 }, .)
Positioned(Vec2 { x: 0, y: 2 }, .)
Positioned(Vec2 { x: 1, y: 2 }, .)
Positioned(Vec2 { x: 2, y: 2 }, .)
Looking good!
And then, finally, as a treat - we can make it possible to collect
into a Map
.
That's new! How do we do that?
All we have to do is look at the signature of Iterator::collect
:
fn collect<B>(self) -> B
where
B: FromIterator<Self::Item>,
and... we just need to implement FromIterator
!
use std::iter::FromIterator;
impl<A> FromIterator<Positioned<A>> for Map<A> {
fn from_iter<T: IntoIterator<Item = Positioned<A>>>(iter: T) -> Self {
todo!()
}
}
There's just, uh... one problem. Our constructor for Map
takes a size:
fn new(size: Vec2) -> Self
And we're just getting a stream of positioned tiles - we have no idea how
large the resulting map should be! So I guess our problem is not well-suited
to collect
.
Maybe there's another method/trait? One that would let us take an existing Map
?
There is! Look what I found:
fn extend<T>(&mut self, iter: T)
where
T: IntoIterator<Item = A>,
Ah, that looks like it would work.
use std::iter::Extend;
impl<A> Extend<Positioned<A>> for Map<A> {
fn extend<T: IntoIterator<Item = Positioned<A>>>(&mut self, iter: T) {
for Positioned(pos, tile) in iter {
self.set(pos, tile)
}
}
}
How neat!
Okay, I guess now we need to actually parse our map:
impl Map<Tile> {
fn parse(input: &[u8]) -> Self {
let mut columns = 0;
let mut rows = 1;
for &c in input.iter() {
if c == b'\n' {
rows += 1;
columns = 0;
} else {
columns += 1;
}
}
let mut iter = input.iter().copied();
let mut map = Self::new(Vec2 {
x: columns,
y: rows,
});
for row in 0..map.size.y {
for col in 0..map.size.x {
let tile = match iter.next() {
Some(b'.') => Tile::Floor,
Some(b'L') => Tile::EmptySeat,
Some(b'#') => Tile::OccupiedSeat,
c => panic!("Expected '.', 'L' or '#', but got: {:?}", c),
};
map.set(Vec2 { x: col, y: row }, tile);
}
iter.next();
}
map
}
}
Let's do a quick visual check. Our example input is:
L.LL.LL.LL
LLLLLLL.LL
L.L.L..L..
LLLL.LL.LL
L.LL.LL.LL
L.LLLLL.LL
..L.L.....
LLLLLLLLLL
L.LLLLLL.L
L.LLLLL.LL
And our parsed version is:
fn main() {
let m = Map::<Tile>::parse(include_bytes!("input.txt"));
dbg!(&m.size);
println!("{:?}", m);
}
$ cargo run --quiet
[src/main.rs:230] &m.size = Vec2 {
x: 10,
y: 10,
}
L.LL.LL.LL
LLLLLLL.LL
L.L.L..L..
LLLL.LL.LL
L.LL.LL.LL
L.LLLLL.LL
..L.L.....
LLLLLLLLLL
L.LLLLLL.L
L.LLLLL.LL
Looks good!
Now, I guess we'll need a next
method on Map
as well, right? But only
when T = Tile
:
impl Map<Tile> {
fn next(&self) -> Self {
let mut res = Self::new(self.size);
res.extend(
self.iter()
.map(|Positioned(pos, tile)| Positioned(pos, tile.next(self.neighbor_tiles(pos)))),
);
res
}
}
This is really, really neat. All our foundational code paid off!
Let's print a few iterations of our example map:
$ cargo add itertools
Adding itertools v0.9.0 to dependencies
fn main() {
let maps = itertools::iterate(Map::<Tile>::parse(include_bytes!("input.txt")), Map::next);
for map in maps.take(5) {
println!("{:?}", map);
}
}
You really have to turn everything into an Iterator
, don't you?
It's the winter holidays, bear! We can afford it!
$ cargo run --quiet
L.LL.LL.LL
LLLLLLL.LL
L.L.L..L..
LLLL.LL.LL
L.LL.LL.LL
L.LLLLL.LL
..L.L.....
LLLLLLLLLL
L.LLLLLL.L
L.LLLLL.LL
#.##.##.##
#######.##
#.#.#..#..
####.##.##
#.##.##.##
#.#####.##
..#.#.....
##########
#.######.#
#.#####.##
#.LL.L#.##
#LLLLLL.L#
L.L.L..L..
#LLL.LL.L#
#.LL.LL.LL
#.LLLL#.##
..L.L.....
#LLLLLLLL#
#.LLLLLL.L
#.#LLLL.##
#.##.L#.##
#L###LL.L#
L.#.#..#..
#L##.##.L#
#.##.LL.LL
#.###L#.##
..#.#.....
#L######L#
#.LL###L.L
#.#L###.##
#.#L.L#.##
#LLL#LL.L#
L.L.L..#..
#LLL.##.L#
#.LL.LL.LL
#.LL#L#.##
..L.L.....
#L#LLLL#L#
#.LLLLLL.L
#.#L#L#.##
Now to answer the question:
Simulate your seating area by applying the seating rules repeatedly until no seats change state. How many seats end up occupied?
Mhh we're going to have to compare the previous state with the current
state... sounds like a job for tuple_windows
!
Why not! But I don't want to be comparing all tiles one by one...
We could just derive PartialEq
on Map
?
Sounds like a plan!
#[derive(PartialEq)]
struct Map<T> {
size: Vec2,
tiles: Vec<T>,
}
Cool bear's hot tip
Note: Vec2
already derives PartialEq
. As for T
, it might or it might not. Map<T>
will only implement PartialEq
if T
itself implements PartialEq
.
Uhh how do we know that?
Why, we can check the result of the derive macro with cargo-expand!
#[automatically_derived]
#[allow(unused_qualifications)]
impl<T: ::core::cmp::PartialEq> ::core::cmp::PartialEq for Map<T> {
#[inline]
fn eq(&self, other: &Map<T>) -> bool {
match *other {
Map {
size: ref __self_1_0,
tiles: ref __self_1_1,
} => match *self {
Map {
size: ref __self_0_0,
tiles: ref __self_0_1,
} => (*__self_0_0) == (*__self_1_0) && (*__self_0_1) == (*__self_1_1),
},
}
}
#[inline]
fn ne(&self, other: &Map<T>) -> bool {
match *other {
Map {
size: ref __self_1_0,
tiles: ref __self_1_1,
} => match *self {
Map {
size: ref __self_0_0,
tiles: ref __self_0_1,
} => (*__self_0_0) != (*__self_1_0) || (*__self_0_1) != (*__self_1_1),
},
}
}
}
Ah! Looks... generated. Which makes sense. Also it's using core::
types rather than
std::
, which I guess also makes sense.
Moving on - let's implement last
on Map
, which simulates until we reach a
stable state:
impl Map<Tile> {
fn last(self) -> Self {
use itertools::Itertools;
itertools::iterate(self, Map::next)
.tuple_windows()
.find_map(|(prev, next)| if prev == next { Some(next) } else { None });
todo!();
}
}
Uh oh, that doesn't work:
$ cargo check --quiet
error[E0277]: the trait bound `Map<Tile>: Clone` is not satisfied
--> src/main.rs:210:14
|
210 | .tuple_windows()
| ^^^^^^^^^^^^^ the trait `Clone` is not implemented for `Map<Tile>`
error[E0277]: the trait bound `Map<Tile>: Clone` is not satisfied
--> src/main.rs:211:14
|
211 | .find_map(|(prev, next)| if prev == next { Some(next) } else { None });
| ^^^^^^^^ the trait `Clone` is not implemented for `Map<Tile>`
|
= note: required because of the requirements on the impl of `Iterator` for `TupleWindows<Iterate<Map<Tile>, for<'r> fn(&'r Map<Tile>) -> Map<Tile> {Map::<Tile>::next}>, (Map<Tile>, Map<Tile>)>`
error: aborting due to 2 previous errors
Oh! We need to derive Clone
on Map
too. But if we're going to be cloning
our Map
... and we don't want a whole lot of allocations and copying to go
around...
We could just use the im crate?
Let's see how much of a "drop-in replacement" it is:
$ cargo add im
Adding im v15.0.0 to dependencies
use im::Vector;
#[derive(PartialEq)]
struct Map<T> {
size: Vec2,
tiles: Vector<T>,
}
Ah, we got one problem already:
$ cargo check --quiet
error[E0369]: binary operation `==` cannot be applied to type `Vector<T>`
--> src/main.rs:71:5
|
71 | tiles: Vector<T>,
| ^^^^^^^^^^^^^^^^
|
= note: this error originates in a derive macro (in Nightly builds, run with -Z macro-backtrace for more info)
help: consider further restricting this bound
|
68 | #[derive(PartialEq + std::cmp::PartialEq)]
| ^^^^^^^^^^^^^^^^^^^^^
Let's look at whether im::Vector
implements PartialEq
. Turns out, it does...
impl<A: Clone + PartialEq> PartialEq<Vector<A>> for Vector<A>
...but only if A
is Clone
.
Okay, Tile
is definitely Clone
, we can do that:
#[derive(PartialEq)]
struct Map<T>
where
T: Clone,
{
size: Vec2,
tiles: Vector<T>,
}
Now we need to add that bound to our other impl blocks as well - this is left as an exercise to the reader.
Cool bear's hot tip
Wherever we have a bound of T: Copy
, we don't need to add + Clone
, because Copy
implies Clone
:
pub trait Copy: Clone { }
Now we can also derive Clone
for Map
:
#[derive(PartialEq, Clone)]
struct Map<T>
where
T: Clone,
{
size: Vec2,
tiles: Vector<T>,
}
And finish our last
method:
impl Map<Tile> {
fn last(self) -> Self {
use itertools::Itertools;
itertools::iterate(self, Map::next)
.tuple_windows()
.find_map(|(prev, next)| if prev == next { Some(next) } else { None })
.unwrap()
}
}
Let's try it out!
fn main() {
let last = Map::<Tile>::parse(include_bytes!("input.txt")).last();
println!("{:?}", last);
}
$ cargo run --quiet
#.#L.L#.##
#LLL#LL.L#
L.#.L..#..
#L##.##.L#
#.#L.LL.LL
#.#L#L#.##
..L.L.....
#L#L##L#L#
#.LLLLLL.L
#.#L#L#.##
Yay, it terminates! Take that, halting problem.
And, since our answer to the question needs to be in the form of a number, let's count how many seats end up occupied:
fn main() {
let last = Map::<Tile>::parse(include_bytes!("input.txt")).last();
println!("{:?}", last);
println!(
"there are {} occupied seats",
last.iter()
// 👇 this is a Positioned<Tile>
.filter(|p| matches!(p.1, Tile::OccupiedSeat))
.count()
);
}
$ cargo run --quiet
#.#L.L#.##
#LLL#LL.L#
L.#.L..#..
#L##.##.L#
#.#L.LL.LL
#.#L#L#.##
..L.L.....
#L#L##L#L#
#.LLLLLL.L
#.#L#L#.##
there are 37 occupied seats
That's it for the example! Let's try it with my real puzzle input:
$ cargo run --quiet
#L#L#.#LL#L##L#.#LL##L##L#.#L#L#L#.#L#L#L#L#L#L#L#L#.#L#L#L#L#.#L##L#.#L#L#L#.#L#L#L#L#LL#L#L#L#L#
LLLLL.LL.L.LLLL.LLL..LLLLL.LLLLLL#LLLLLLLLLLLLLLLLLL.LLLLLLLLL.LLLLLL.LLLLLLL.LLLLLLL.LLLLLLLLLLLL
#L#L#.L#L#.#L#L#L#L#L#L#L#L#L#L.L..#L#L#L#L#L#L#L#L#L#L#L#L#L#.#L#L#L.L#L#L##L#L#L#L#.#.L#L#L#L#L#
LLLLLLLLLL.LLLL.LLLLLLLLLL.LLLL#L#.LLLLLLLLLLLLLLLLL.LLLLLLLLL.LLLLLL#LLLLLLLLLLLLLLL.LLLLLLLLLLLL
#L#L#L#L#L#L#L#.#L##.#L#L#.#L#LLLL.##.L#L#L#..#L#L#L#L#L#L#.L#.#L#L#L#.#L#L#L#L##L#L#.L#L#L#L#L#L#
LLLLLLLLLL.LLLL.LLLL.LLLLL.LLLL#L#LLLLLLLLLL.LLLLLLLLLLLLLLLLL.LLLLLL.LLLLLL.LLLLLLLLLLLLLLLLLLLLL
#L#L#L.L##.##L#.#L##.#L#L#L##LLLL#.#L#L#L#L#.#L#L#LL.#L##L#.##.#L##.#L#L#L#.#L#LL#L##.##L#L#L#L#LL
.LL..L#.L..L.L...LL..L..L.L...L#..L...LL..LLLL.#.L.#.....L....L.LL...L.LL.LL....#...L..L....L....#
#L#L#.LL##.#L#L#L#L#.#L#L#.#L#LLL#L#L#L#L#LLL#LLL#LLL#L#L#L#L#.#L#L#L.#L#L#L#.#LLL.#L#LLL#L#L#L#LL
#LLLLL#LLL.LL#L.L#LL.LLL.L.LLLL#L#L#L#L#L#L#LLL#LLL#.L.LLLLLLLLLL.LLLLLL#L#L#.#L#LL#L.L#LLLLL.LLL#
LL#LL.#LLL.LLLL.LLL#L#L#L#.#L#LLLLLLLLLLLLLLL#LLL#LL.#L#L#L#L#.#L#L#LLLLLLLLL...LLLLLLLLL#.#L#L#LL
#LLL#L.L#L#L#L#.#L#L.LLLL#L#L.L#L#.#L#L#L#L#..L#LL.#.LLLLLL#L#.#LLLLL#.L#L#L#.#L#LL#L#L#LLL.LLL.L#
L.#...#.....LLL.L..L#...#......L.LLL........L#..L#L..#.#L#....L..#.#.L..L..L.LL..L.......LL..L.#..
#LLL#.#L#L#L#L#L#LLL#L#LLL#L#LL#L#.#L#L#L#L#.LL#LLL#LLLLLLL#L#.#LLL.L#L#L#L#L###L#L#L#L#L#L#L#LLL#
LL#L#LLLL.LLLLL.LL#L.LLL#L.LLLLLLL.LLLLLLLLLL#LLL#LL.#L#L#LLLL.LL#L#L.LL.LLLL.LLLLLLLLLL.LLLLLL#LL
#LLL###L#L.L#L#.#LLL.#LLL.##LL#L#.##L#L#L#L#.#L#LLL#.LLLLLL#L#.#LLLLL.#L#L#.#.#L#L#L#.##L#L#L#L#L#
LL#LL.LLLL#LLLL.LLL#.LL#LL.LLLLL.LLLLLLLLLLL.#LLL#LL.#L#L#LLL#LLL##L#.LLLLLLL..LLLLLL.LLLL.LLLLLLL
#LLL#.#L#L.L#L#.#LLL.#LLL#L#L#.#L#L#L##L#L#L.L##LLL#.LLLL.L#L#.#LLLLLL#L#L#L#.#L#L#L#.#L##L#L#L#L#
..#..L.L........LL.#.#..##L........L....#L..#L#.L#....#.......LL.##L#....L...L.LL........#.L......
#LLL#.#.L#.#L#L#L#L#.LLLLL.#L#L#L#L#.#LLLLLL.LLLLLL#.LLLL#L#L#.#LLLLL.#L#L#L#LLL#L#L#.#.LLL#L#L#.#
LL#L#.LLLL.LLLL..LL#.#L#L#L#LLLLLL.#L#L#L#L#L#L#L#LL.#L#LLLL.LLLL##L#L#L#LLLLL#LLLLLL.LL##LLLLLLLL
.LLLLL##L#.#L##.#LLL..LLL#LLLLLLLL.#LLLLLLLL.LLLLLLL.LLLL#L#L#.#LLL.L.L..L#L#.LL#L#L#L#LLLL#L#L#L#
#L#L#.LLLL.LL#L.LL##.#L#LLL#.#L#L#LLL#L#L#L#.#L#L#L#.#L#L#LLLL.LL##L#.#L#L#LL.#LLL#L#L#LL#LL.#LLLL
.....L#.L.##...#..LL.LL..#...#..L.L#..LL..L.L..........#....#...#.L....L.L.L....#L.........#L..#L.
#L#L#.LLL#.LL#L.L#L#L#L#LLL#LLL#L#.LL#.#L#L#L#L#L#L#.#LLL#LLLL.##L#L#.#L#L#L#.#.#.#L#.#L#LLLL#LLL#
LLLLLL##LL.LLLL.LLLL.LLLL#.#L#L#LLL#LLLLLL.LLLL.LLLL.LL#LLL#.#LLLLLLL.LLL.LLL.LLLLLLL.LLLL##LLL#LL
#L#L#.LLL#.#L#L#L.L#.#L#LL.LLLLLL#.#L#L#L#L#L#L#L#L#.#L.L#LLL..##L#L#.#L#L#L#L#L#L#L#.#L#LLLL#L.L#
LLLLLL##.LLLLLL.L#LL.LLLL#.#L#L#LL.LLLLLL.LL.LLLLLLLLLLLLLL#.#..LLLLLLLLLLLLL.LLLLLLL.LLLL##LLLLLL
#L#L#.LLL#.#LL#.LLL#.#L#LL.LLLLLL#L#L#L#L#L#.#L#L###.#L#L#LLLL.L#L#L#.#L#.#L#L#L#L#L#.#L#LLLL#L#L#
L..L#.#.......L.#L..L.....#..#.#..L.L...L....LLL..........LL#.#L......L.L..L.LL..L....LL..#.......
#L#LL.LLL#.#LL#.LLLLL#L#LL.LLLLLL#.LL#L#L#L#.#L#L#L#.#L#LLLLLLLLL#L#LL#L#L#L#.L#L#L#L#L#LLLLL#L#L#
#LLL#.##.L.LLL..#L#L.LL#L#.#L#L#LL.#LLLLLLLL.LLLLLLL.LLLL#L#L#.#LLLLL.LLLLLLLLLLLLLLL.LLL#L#LLLLL.
LL#LL.LLL#.#LL#.LLLL.#LLLL.LLLLLL#LLL#L#L#L#.#L#L#L#.#L#LLLLL#.LL#L##.#L#L#L#.#L#L#L#.#.LLLLL#L#L#
#LLL#.##LL.LLLL.#L##.LL#L#.#L#L#LL.#LLLLLLLL.LLLLLLLLLLLL#L#LL.#LL.LL.#LLLLLL.#LLLLLLLLLL#L#LLLLLL
LL#LL.LLL#.#.L#.LLLLL#LLLL.LLLLLL#.LL#L#L#L#.#L#L#L#.#L#LLLLL#.LL#L##.#L#L#L#.LLL#L#L.L#LLLLL#L#L#
#LLL#.##L#.#LLL.#L#..LL#L#.#L#L#L..#LLL#LLLL.LLLLLL#.LLLL#L#L#.#LLLLL.L.LLLLL.#LLLLLL#LLL#L#LLLLLL
LL#LLLLLLL.LL##.LLLL#LLLLL.LLLL.L..LL#LLL#L#.#L#L#LL.#L#LLL.LLLLL#L#L##L#L#L#.LLL#L#L.L#LLLLL#L#L#
#LLL#.##L#.#LLL.#L#L.L#L#L#L#L#L##.#L.L#L#LL.L.LLLL#.LLLL#L#L#L#LLL#..LLLLLLL.L#LLLLL#L#L#L#L#LLLL
...L#LLL..L...#..L..L.............L..#...#..#.#.#..LL#.#.....L.L.#.#.#..#.L#.#..L.#..#LL..LL...#L#
#L#LL.L#L#.#LLL.##L#.#L#L#.#L#.#L#.#LLL#LLLL.LL.LL##.LLLL.L#L#L#LLLLL.LLLLLL..LL#LLLL.L#L#L#L#LLLL
LLLL#LLLLL.L.##.LLLLLL.LLL.LLLLLLL.LL#LLL#L#.#L#LLL#L#L#L#LLL..L.#L#L.LL#L.L#.#LLL#L#.LLLLLLLLL#L#
.#LLLL##L#.#LLL.#L##.##L#L.L#.##L#.#LLL#LLLL.LLLL#LL.#L#L#L###L#LLLLL#LLLL#LL.LL#LLLL.##.#L#L#LLLL
LLL##.LLLL.LLL#.LLLL.LLLLL#LL.LLLL.LL#LLL#L#.#L#LLL#.LLLLLLLLL.LL#L#L.L##LLL#L#LLL#L#.LLLLLLLLL#L#
#LLL..#L#L#L#LL.#L##.#L.L#..##L#L#.#LLL#LL.L.LLLL#L#.#L#.#L#L#.#LLL#L#L#.L#L#LLL#L#LL.##L#.#L#LLLL
LL#L#L.LLL.LLL#.LLLL.LL#LL.#LL...LLLL#LLL#L#L#L#LLLLLLLLLLLLLLLLL#LLL.LLLLLLL.#LLLLL#.LLLLLLLLL#L#
#LLL#.#L#L.L#LL.#L##.#L#L#.LL#L#L#.#LLL#LLLL.LLLL#L#.#L#L#L#L#L#LLLL#.#L#L#L#.LL#L#LL.##.#L#.#LLLL
LL#LLLLLLL#LLL#LL.LL.LLLLL.#LLLLLL.LL#LLLLL#L#L#LLLLLLLLLLLLLLLLL##LLLLLLLLLL.#LLLLL#.LLLLLLLLL#L#
#LLLL##L#L..#LL.#L##.#L#L#.#L#L#L#.#L.L#L#L#L.L#L#L#.#L#L#L#L#.#LLLL#L#L#L#L#.LL#L#LL.L#L#L#L#LLLL
.L#..L....#..L#....L.......#........L#......L...L..............L.#...L.L....LL#L.....#......LLL..#
#L#L#.#L#L.L#LL.#L##.#L#L#L#L#L#L#.#LLL#L#L#.#L#L###L#L#L.L#L..#L#L####LLL#L#.LLL#L#L#L#L#L#L#L#LL
LLLLL.#LLL#LLL#.LLLLLLLLLL.LL.LLLL.LL#LLLLLLLLLLLLLL.LLLL#LLL#.LLLLLL.LL#.LLLL#LLLLLL.LLLLLLLLLLL#
#L#L#.LL#L.L#LLL#L#L#L##L#.#L#L#L#.#L.L#L#L#.#L#L#L.L#L#LLL#LL.L#L#L#.#LLL#L#.LL#L#L#.##L##L#.L#L#
LLLLL.#LLL.LLL#.LLLLLLLLLL.#LLLLLL.LLLLLLLLLLLLLLLL#LLLLL#LLLL#LLLLLL.LL#LLLL.#LLLLLL.LLLLLLLLLLLL
#L#L#.LLL##L#LL.#L#L.#L#L#.##L#L#..#L#L#L#L#.#L#L#LLL#L#LLL##L.L#L#L#L#LLL#L#.LL##L#L##L#L#.L#L#L#
...L.L.#.#LL..#......LLL.L..L......L...LLL....L....#..LL.#.L..#..L......#.....#L.L.....L........L.
#L.L#LLL.L.#LLL.L#L#.#L#L#.#L#.#L#.#L#L#L#L#.#L#L#L#.#L#LLL##..L#L#L#.#L#L#L#.LLLL#L#.L.L#L#L#L#L#
LL#LL.##L#.LL#L#LLLLL#LLLL.LLLLLLL.L.LLLLLL..LLLLLLL.LLLL#LLLL.LLLLLL.LL#LLLL.#L#L#LLL##LLLLLLL#LL
#LLL#.LLL..#LLLLL#L#.L.#L#.#L#L#L#.#L#L#L#L#.#L#L#L#L#L#LLLLL#.##L#L#.#LLL#L#LLLLLLLL.LLL#L#L#LLL#
LL#L#.#L#..#L#L#LLLLL#LLLLLLLLLLLL.LLLLLLLLLLLLL.LL..LLLL#L#.L.LLL.LL.LL#LL.LL#L#L##L#L#LLLLLLL#LL
LLLLL.LLLL.LLLLLL#L#.LL#L#.#L#L#L#.#L#L#L#L#.#L#L#L#.#L#LL.LLL#L#L#L#.#LLL#L#.LLLLLLL.L.L#L#L#LLL#
#L#L#L#L#L#L#L#.LLLL.#LLLL.LLLLLLL.LLLLLLLLLLLLLLLLL.#LLLL#L#L.LLLLLLLLL#LLLL.#L#L#L#.L#LLLLLL.#L.
LLLLL.LLLL.LLLL.L#L#.LL#L#L#L#L#L##L#L#L#L#L#L#L#L#L.LLL##LLLL.##L#L#L#LLL#L#.LLLLLLLLL.L#L#L#L.L#
#L##L#.#L#L#L#L#LLL#.#LLLLLLLLLLL..LLLLL#LLL.LLLLL#L#L#LLLL#L#.LLLLL#.LL#L#L#L#L#L#L#.##LLLLLLLLLL
...L...L...L...#L...LL.#.#..##..#....##...#L#L.#........#......#..#....L.L....L...L.L.L.#L#.#..#.#
#L#L#.#.L#.LL#L.L#L#.#LLLLLLLLLLLLL#L.LL#LLL.LLLL.L#.#L.LLL#L#.LLLLL#.#L#L#L#L#L#L#L#.#LLLLLLLLLLL
LLLL#.LLLL.#L#L.L#LLLLL#L#L#L#L#L#LLL#LLL.L#.#L#L#L#L#L#L#L#L##L#L#LL.LLLLLLLLL.LLLLL.LLL#L#L#L#L#
#L#LL.L#L#.LLLL#L#L#.#LLLL.LLLL.LL.#LLL#L#LL.LLLLLLL.LLLLLLLLLLLLLLL#.#L#L#L#.#L#L#LL#L#LLLLLLLLLL
LLLLL#LLLL.#L#L.LLLL.LL#L#.#L#L#L#.LL#LLLLL#.#L#L#L#L#L#L#L#L#.#L#LLLLLLLLLLL.LLLLLLLLLLL#.#L#L#L#
#L#LL.LL#L.LLLL.LL##L#LLLLLLLL.LLL.#LLL#L#LL.LLLLLLL.LLLLLLLLL.LLLL#L#L#L#L#L.L#L####.L#LLLLLLLLLL
LLLL#.#LLL#L#L#.#LLLLLL#L#L#L#L#L#LLL#LLLLL#.###L#L#.#L#L#L#L#.#L#LL.LLLLLLLL#LLLLLLL.LLL#L#L#.#L#
#L#LL.LL#LLLLLLLLL#L#LLLL#LLLLLLLL.#LLLLLLLLLLLLLLLLLL.LLLLLLL.L.LL#L#L#L#L#LLLLLL#L#L#LLLLLLLLLLL
LL#L#.#LLL#L#L#.#L.L.L#LLLL#L#L#L#.LL##L#L##L#L#L#L#L#L#L#L#L#L#L#LLL.LLLLLLL.#L#LLL..#L##L#L#L#L#
#L.L...L#..LL..L..#.L....#...L..L..#L......#L.L.......L..LL........L#.#L#L#.......#.....LL.#L.....
LL#LL.LLLLLL#.#.#LLL.#L#LL.#L#L#L#.LL#L#L#LLLLL#L#L#.#L#L#LLL..LL#LLL.LLLLLL#L#L#L.L#.#L##LLLLL#L#
#L#L#.#L#L#L#.L.LL##.#LLL#.LLLLLLL.#LLLLLLL#.#LLLLLL.LL#LLL#L##LL#L###L#L#L##.#L#L#LL.LLLLL#L#LLLL
LLLLL.LLLL.LLL#L#LLLL.L#LL.L.#L#L#.LL#L#L#LL.LL#L#L#.#LL.#LLLL.LLLLLL.LLLLLLLLLLLL#L#.#L##LLLLL#L#
#L#.#.#L#L#L#L#.#L#L##LLL#L#LLLLLL.#LLLLL.L#.#L#LLLL.LL#LLL#L#.##L#L#.#L#L#L#.#L#LLLL.LLLLL#L#.#LL
..#.#....LL.LL.....L.LL......#.#L..LLL#L#......LL.L.#L.LL#...LLLL......L.L.L...LL..#..#..#...LL..#
#L#L#.#L#L#L#LL.#L#..#LLL#.#LLLLL#.#LLLLLLL#.#L#L#L#..#LLLL###.#LLL#L###.##L#.#L##LLL.LLLLL#L#.#L#
LL#L..LLLL.LLL#.LLLL.LL#LL.LL#L#LLLLL#L#L#LLLLLLLLLL.LLLL#LLLL.LL#LLL.LLLLLLL.LLLLL#L##L##LLLLL#LL
#L#.#.#L##.#LLL.L#L#.#LLL#.#LLLLL#.#LLLLLLL#L#L#L#.#.#L#LLLL#L#LLLLLL.#L#L#L#.#L##LLL.LLLLL#L#L.L#
L.#L..LLLL.L.#L#L#LLLLL#LL.LL#L#LL.LL#L#L#L..LLL.LLL.LLLL#L.LL.L#L#L#.LLLLLLLLLLLLLL#.#L##LLLLLLLL
#L#L#.#LL#.#L.L.LLLL.#LLL#.#LLLLL#LLLLLLLLL#L#L#L#L#.#L#L.L#L#LLLLLL..#L#L#L#.#L#L#LL.LLLLL#L#L#L#
L....L...L..L.#...#....#......#..#L#..#..#L.LL.L.L....L..#.#.LL#.#.L#LL.........L..L#.#L#......L..
#L#L#.##L#.#LLL.#LLL.#L#L#.#LLLLLL.LLLLLL#L#L#L#L#L#.#L#L#.LL#LLLLLLLL#L#L#L#.#L#LLLL.LLLLL#L#L#.#
LL#LL.LLL..LLL#.LLL#.LLLLL.LL#L#L#.#L#L#L#L#L.LLLL.LLLLLL#L#LLLL#L#L#.LLLLLLL.LL#L#L#.#LL#LLLLL.LL
LLLL#.#LL#LL.LL.LLLL.#L#L#.#LLLLLL.L.LLLLLLL.LLLLL#L#LLLLLLLLL#LLLLLLL#L#L#L#L#LLLLLL.LLLLL#L#L#L#
#L#LL.LLL#.#L###L#L#.#L#LL.LL#L#L#.#L#LL#L#.#L#L#L#L.L#L#L#L#L.L#L#L#.#L.L#L#L#L#L#L#.#LL#L#L#L#L#
LLLLL.LLLL.LLLL.LLLL.LLLLL.LLLLLLL.LLLLLLLLLLLLLLLLL.LLLLLLLLL.LLLLLL.LLLLLLL.LLLLLLLLLLLLLLLLLLLL
#L#L#LL#L#L#.#L#L#L#.#L##L#.#L#L#L#L#L##L#L#.#L#L#.#L#L#L#L#L#.#L#L#L##L#L#L#.#L#L#L#.#LL#L#L#L#L#
there are 2289 occupied seats
And just like that, we're allowed to move on to the next part.
Part 2
It's a new part, and the rules, they are a a-changing.
Now we have to look for seats that may not be adjacent, but that are in any of the 8 directions.
So before, we looked at these, and we'd only see two occupied seats:
But now we look further in each direction until we see a seat - and we see eight occupied seats:
Time for a new method! visible_seats
will do exactly that.
impl Map<Tile> {
fn visible_seats(&self, pos: Vec2) -> impl Iterator<Item = Tile> + '_ {
use itertools::Itertools;
(-1..=1)
.map(|dx| (-1..=1).map(move |dy| (dx, dy)))
.flatten()
.filter(|&(dx, dy)| !(dx == 0 && dy == 0))
// for each direction...
.map(move |(dx, dy)| {
// keep moving in set direction
itertools::iterate(pos, move |v| Vec2 {
x: v.x + dx,
y: v.y + dy,
})
// as long as we're on the map
.map(move |pos| self.index(pos))
.while_some()
// and until we reach a seat
.filter_map(move |index| match self.tiles[index] {
Tile::Floor => None,
seat => Some(seat),
})
.take(1)
})
.flatten()
}
}
Okay, that one definitely needs a test.
Agreed.
It's a good time to show off the indoc
crate!
$ cargo add indoc
Adding indoc v1.0.3 to dependencies
#[test]
fn test_visible_seats() {
let map = Map::<Tile>::parse(
indoc::indoc!(
"
.......#.
...#.....
.#.......
.........
..#L....#
....#....
.........
#........
...#.....
"
)
.trim()
.as_bytes(),
);
println!("{:?}", map);
assert_eq!(map.visible_seats(Vec2 { x: 3, y: 4 }).count(), 8);
assert_eq!(map.visible_seats(Vec2 { x: 8, y: 0 }).count(), 2);
}
$ cargo t -q
running 2 tests
..
test result: ok. 2 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out
Seems good!
And a second test for good measure:
#[test]
fn test_visible_seats2() {
let map = Map::<Tile>::parse(
indoc::indoc!(
"
.##.##.
#.#.#.#
##...##
...L...
##...##
#.#.#.#
.##.##.
"
)
.trim()
.as_bytes(),
);
assert_eq!(map.visible_seats(Vec2 { x: 3, y: 3 }).count(), 0);
}
$ cargo t -q
running 3 tests
.F.
failures:
---- test_visible_seats2 stdout ----
.##.##.
#.#.#.#
##...##
...L...
##...##
#.#.#.#
.##.##.
thread 'test_visible_seats2' panicked at 'assertion failed: `(left == right)`
left: `8`,
right: `0`', src/main.rs:224:5
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
failures:
test_visible_seats2
test result: FAILED. 2 passed; 1 failed; 0 ignored; 0 measured; 0 filtered out
Seems bad!
So uhh what's happening here? Let's try and find out what tiles it sees:
// in our test
dbg!(map.visible_seats(Vec2 { x: 3, y: 3 }).collect::<Vec<_>>());
assert_eq!(map.visible_seats(Vec2 { x: 3, y: 3 }).count(), 0);
$ cargo t -q seats2
running 1 test
F
failures:
---- test_visible_seats2 stdout ----
.##.##.
#.#.#.#
##...##
...L...
##...##
#.#.#.#
.##.##.
[src/main.rs:224] map.visible_seats(Vec2{x: 3, y: 3,}).collect::<Vec<_>>() = [
L,
L,
L,
L,
L,
L,
L,
L,
]
thread 'test_visible_seats2' panicked at 'assertion failed: `(left == right)`
left: `8`,
right: `0`', src/main.rs:225:5
Ohh, it sees itself! Because we're starting at pos
, not pos + (dx, dy)
.
Yup, seems like we got the initial value wrong in our call to
itertools::iterate
...
Or we could just skip one?
Ooh I like that.
// keep moving in set direction
itertools::iterate(pos, move |v| Vec2 {
x: v.x + dx,
y: v.y + dy,
})
// 👇 new!
.skip(1)
Now all our tests pass:
$ cargo t -q
running 3 tests
...
test result: ok. 3 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out
Let's adjust our Tile::next
method as specified in Part 2:
it now takes five or more visible occupied seats for an occupied seat to become empty (rather than four or more from the previous rules)
Self::OccupiedSeat => { match neighbors
.filter(|t| matches!(t, Self::OccupiedSeat))
.count()
{
// 👇 new!
// up to 4 neighbors: still okay for now
0..=4 => Self::OccupiedSeat,
// that's too many folks!
_ => Self::EmptySeat,
}
}
And change Map::<Tile>::next
to use visible_seats
instead of neighbor_tiles
:
impl Map<Tile> {
fn next(&self) -> Self {
let mut res = Self::new(self.size);
res.extend(
self.iter()
// 👇👇👇
.map(|Positioned(pos, tile)| Positioned(pos, tile.next(self.visible_seats(pos)))),
);
res
}
}
And we should be good to go!
A debug build of this program takes a bit of time:
$ cargo build --quiet
Finished dev [unoptimized + debuginfo] target(s) in 0.01s
$ time ./target/debug/day11 > /dev/null
./target/debug/day11 > /dev/null 5.68s user 0.00s system 99% cpu 5.680 total
Let's see how a release build performs:
$ cargo build --release
Finished release [optimized] target(s) in 0.01s
$ time ./target/release/day11 > /dev/null
./target/release/day11 > /dev/null 0.24s user 0.00s system 99% cpu 0.240 total
Much better!
Cool bear's hot tip
If your Rust program seems slow with cargo run
, don't forget to check how fast
it runs with optimizations enabled, by using the --release
flag!
And now let's get our actual answer:
$ cargo run --release
Finished release [optimized] target(s) in 0.01s
Running `target/release/day11`
#L#L#.L#L#L#L#L.#L#L#L#L#L.#L#L#L#.L#L#L#L#L#L#L#LL#.L#L#L#L#L.#L#L#L.#L#L#L#.L#L#L#L#L#L#L#L#L#L#
LLLLL.#L.L.LLLL.LLL..LLLLL.LLLLLLLLLLLLLLLLLLLLLLLLL.LLLLLLLL#.LLLLL#.LLLLLLL.LLLLLLL.LLLLLLLLLLLL
#L#L#.LL#L.L#LL#L#L#L#L#LL#L#L#.L..#L#L#L#L#L#L#L##L#LL#L#L#LL.##L#LL.##L#L#L#L#L#L#L.#.L#L#L#L#L#
LLLLLL#LLL.LLLL.LLLLLLLLLL.LLLLL#L.LLLLLLLLLLLLLLLLL.LLLLLLLL#.LLLLL#LLLLLLLLLLLLLLL#.L#LLLLLLLLLL
#L#L#LLL#L#L#L#.L#L#.LL#L#.L#L#LLL.#L.#L#L#L..#L#LL#L#L#L#L.LL.##L#LLL.L#L#L#L#L#L#LL.LLL#L#L#L#L#
LLLLLL#LLL.LLLL.#LLL.#LLL#.LLLLL#L#LLLLLLLLL.LLLLLLLLLLLLLL#L#.LLLLL#.LLLLLL.LLLLLLL#LL#LLLLLLLLLL
#L#L#L.L#L.#L##.LLL#.LL##LLL##L#LL.L#L#L#L#L.#L#L##L.#L#L#L.LL.##L#.LLL#L#L.L#L#L##LL.LLL#L#L#L#L#
.LL..LL.L..L.L...#L..#..L.#...LL..L...LL..LLLL.L.L.#.....L....L.LL...#.LL.L#....L...#..L....L....L
LL#LL.L#L#.L#LLLLLLL.LLL#L.LLLL#LLL#L#L#L#L#L#LL#LLL#L#LL#LLL#.LLLL#L.L#LLLL#.LLLL.LLL#L#L#L#L#LL#
#LLL#LLLLL.L#L#.L#L#.LL#.L.L#L#LL#LLLLLLLLLLLLLLLL#L.L.LLLL#LLLL#.LLLLLLL#LLL.L#L#LL#.LLLLLL#.LLLL
LL#LL.##L#.LLLL.#LLLL#LLL#.LLLLLLLL#L#L#L#L#L#L##LLL.#L#L#LLL#.LL#L#LLL#LLL#L...LLLLLLL#L#.LL#L#L#
#LLL#L.LL#L#L##.LL#L.LL#L#L#L.L#L#.LLLLLLLLL..LLLL.#.LLLLLL#LL.#LLLLL#.LL#LLL.#LL#L#L#LLLL#.LLL.LL
L.#...L.....LLL.#..L#...L......L.LL#........LL..##L..#.L#L....L..L.#.L..L..L.L#..L.......LL..#.L..
#LLLL.L#LL#L#L#LLLL#LLLL#L#L#L#L#L.LL#L#L#L#.L#LLLL#LLLLLL#LL#.LL#L.LL#L#L#L#LLL#L#L#L#LL#L#L#L#L#
LL#L#LLLL.LLLLL.##LL.#L#LL.LLLLLLL.#LLLLLLLLL#LL##LL.L#L#LL#LL.#LLLL#.LL.LLLL.#LLLLLLLL#.LLLLLLLLL
#LLLLL#LL#.L#L#.LLL#.LLLL.L#L#L#L.LLL#L#L#L#.LL#LLL#.LLLL#LLL#.L#L#LL.#LLLL.#.LL#L#L#.LL#LL#L#L#L#
LL#L#.LLLLLLLLL.##LL.#L#L#.LLLLL.#L#LLLLLLLL.#LLL#LL.L#LLLL#LL#LLLLL#.LL#L#LL..LLLLLL.#LL#.LLLLLLL
#LLLL.#L#L.#L##.LLL#.LLLLLL#L#.L#LLLL#L#L#L#.LLL##L#.LLL#.LL#L.L#L#LLL#LLL#L#.L#L##L#.L#LLL#L#L#L#
..L..#.L........##.L.#..L#L........#....LL..#L#.L#....L.......LL.L#L#....L...L.#L........#.L......
L#L#L.L.L#.L#LLLLLL#.LL#LL.L#L#LL#LL.L#L#L#L.LLL#L#L.#L#L#L#LL.#LLLLL.L#L#L#LLLLLLLLL.#.LL#L#L#L.L
#LLLL.#LLL.L#L#..LLL.#LLL##LLLLLLL.##LLLLL#LL#LLLLL#.LLLLLLL.#LLL#L#L#LLLLLLL#L#L#L#L.LL#LLLLLL#L#
.LL#LLLL##.LLLL.#L#L..L#LLLL#L#L#L.LLL#L#LLL.LL#L#LL.L#L#L#LLL.LLLL.L.L..L#L#.LLLLLLL##LL#L#L#LLLL
L#L#L.#L#L.##L#.LL#L.LLLL#LL.LLL#L#L#LLLLLLL.#LLLLL#.LLLLLLL#L.L#L#LL.#L#LLLL.L#L#L#LLLLLLLL.LL#L#
.....L#.L.#L...#..LL.#L..L...#..L.LL..#L..#.L..........#....L...L.L....L.L.#....LL.........L#..LL.
#L#L#.LLL#.LLLL.L#L#LLL#L##LLLL#L#.LLL.L#LLLLL#L#L#L.#L#L#LL#L.#L#L#L.L#L#L#L.#.L.#L#.#L#L#LLLL#LL
LLLLLLL#L#.L#L#.LLLL.#LLLL.L#LLLLLLLL#LLLL.#L#L.LLL#.LLLLLLL.LLLLLLL#.LLL.LLL.#LLLLLL.LLLLL#L#LLL#
#L#L#.LLLL.LLL#L#.L#.LL#L#.LLL#L#L.#L#L#L#LLLLL#L#LL.##.L#L#L..L#L#LL.#L#LL#LLLL##L#L.L#L#LLLLL.LL
LLLLLL##.LLL#LL.#L#L.#LLLL.##LLLLL.LLLLLL.L#.LLLLLL#LLLLLLLL.#..LLLL#LLLLLLLL.#LLLLLL.LLLLL#L#L#L#
#L#L#.LLL#.LLL#.LLLL.LL#L#.LLL#L#L#L##L#LL#L.#L#L#LL.L#L#L#LLL.L#L#LL.##L.#L#LLL#L#L#.L#L#LLLLLLLL
L..LL.#.......L.#L..#.....L..L.L..L.L...L....LLL..........LL#.LL......L.#..L.L#..L....LL..L.......
#LL##.LL#L.LL##.LLLLLL#L#L.#L#L#L#.#LLLLL#L#.L#L#L#L.#L#L#LLL#L#L#L#L##LL#L#L.LLL#L#LL#L#LL#L#L#L#
LL#LL.#L.L.#LL..#L#L.LLLLL.LLLLLLL.LL#L#LLL#.LLL#LLL.#L#L#L#L#.LLLLLL.LLLLLLL#L#LLLL#.LLL#LLLLLLL.
#LLL#.LLL#.LLLL.LLLL.#L#L#.LL#L#LL#L#LLLL#LL.L#LLL#L.LLLLLLLLL.#L#L#L.##L#L#L.LLLL#LL.#.LLL#L#L#LL
LL#LL.##LL.#LL#.L#L#.LLLLL.#LLLLLL.LLL#L#LL#.LLL#LLL##L#L#L#L#.LLL.L#.LLLLLLL.#L#LLL#LL#L#LLLLLLL#
#LLL#.LLL#.L.L#.LLLLL#L#L#.LL#L#L#.L#LLLLLLL.#L#LL#L.LLLLLLLLL.L#L#LL.#LL#L##.LLLL#LL.LLLLL#L#L#LL
LL#LL.##LL.##L#.L#L..LLLLL.#LLLLL..#LLL#L#L#.LLLLLLL.#L#L#L#L#.LLLLL#.L.LLLLL.#L#LL#L#L#L#LLLLLLL#
#LLL#LLLL#.LLLL.LLL#L#L#L#.LL#L.#..LL#LLLLLL.#L#L#L#.LLLLLL.LL#L#L#LLL##L#L##.LLLLLLL.LLLLL#L#L#LL
LLL#L.##LL.##L#.L#LL.LLLLLL#L#L#LL.#L.L#L#L#.L.LLLLL.#L##L#L#LLLLLLL..LLLLLLL.#L#L##LLL#L#LLLLLLL#
...LL#LL..#...L..L..#.............L..L...L..#.L.L..#L#.L.....L.#.L.#.L..#.L#.L..#.L..#LL..LL...#LL
#L#L#.L##L.LLLL.LL#L.LL#L#.L#L.L#L.L#L#L#L#L.L#.L#LL.LL#L.L#L#LLL#LLL.#LLLLL..LLLL#LL.#L#LL#L#LLL#
LLLLLLLLLL.#.LL.#L#LL#.LLL.#LL#L#L.LLLLLLLLL.LLLLLLL#LLLL#LLL..#.LL##.LL#L.#L.#L#LLL#.LLL#LLLLL#LL
.L#L#L#L##.LL#L.LLLL.LL#L#.LL.LLLL.#L#L#L#L#.L#L#L#L.#L#LLLL#LLLL#LLLL#LLLLL#.LLL#LLL.L#.LL#L#LLL#
#LLLL.LLLL.#LLL.#L#L.#LLLLL#L.#L#L.LLLLLLLLL.#LLLLL#.LLL#L#LLL.#LLL##.LL#L#LLL#LLLL#L.LL##LLLLL#LL
LL#L..LL##LLL#L.LLLL.LL.L#..LLLLLL.#L#L#L#.L.LL#L#LL.##L.LL#L#.LL#LLLL#L.LLLLLLL#LLLL.#LLL.L#LLLL#
#LLL#L.LLL.#LLL.#L#L.#L#LL.L#L...#LLLLLLLLL#L#LLLLL#LLL#L#LLLLL#LL#L#.#LLLLL#.LL#L##L.#L#L#LLL#LLL
LL#LL.#L##.LL#L.LLLL.LLLL#.LLL#LLL.#L#L#L#LL.LLL##LL.#L#L#L#L#LLLLLLL.#L#L#LL.#LLLLLL.LL.LLL.LLL##
LLLL#LLL#L#L#LL#L.#L.#L#L#.L#LLL#L.LLLLLL#L##L#L#L#L#LLLLLLLLL##L#L#LLLLLLLL#.LLL#L#L.L#LL#L#L#LLL
#L#LLLLLLL..#L#.LLLL.LLLL#.LLL#LLL.LL.#LLLLLL.LLLL#L.L#L#L#L#L.LL#L#L#L#L#L#L.L#L#L#L.L#L#LLLLLLL#
.LL..#....L..L#....L.......L........#L......L...#..............L.L...L.#....L#LL.....L......#L#..L
LL#LL.L###.LLLL.##L#.LLLL#LLL#L#L#.L#L##L#L#.L#L##L#LLLLL.LLL..#L#LLLLLLLL#L#.LL#L#L#L#L#L#LLLLLL#
#LLL#.LLLL#L#L#.LLLLL#L#LL.#L.LLL#.LLLLLLLL#LL#LLLLL.##L#L#L##.LLLL#L.#LL.LLLL#L#LLLL.#LLLLLL#L#LL
LL#LL.LL#L.LLLLL#L#LLLLLL#.LLLL#LL.#L.L#L#LL.LL#L#L.LLLL#L#LLL.#L#LLL.#L#L#L#.LLLL#L#.LL#L#L#.LLL#
#LL#L.#LLL.#L#L.LLLL#LL#LL.#L#LLL#.LL#LLLLL#L#LLLLL#L#LLLLLL#LLLLLL#L.LLLLLLL.#L#LLLL.#LLLLLLLL#LL
L#LLL.LL#LLLLLL.#L#L.#LLL#.LLLL#L..#LLL#L#LL.LLL##LLLLL#L#L#LL.#L#LLL#L#L#L#L.LLLL#L#LLLL#L.#L#LL#
...#.L.L.LL#..L......LL#.L..#......L...LLL....#....#..LL.#.L..L..L......L.....L#.L.....#........L.
#L.LLL#L.#.LL#L.LLLL.#LLLL.LLL.LLL.##LL#L#L#.LLLLLLL.##LLLLL#..L#L#L#.LLLL#LL.#LL#LLL.L.LLLLL#L#LL
LL#L#.LLLL.#L#L#L#L#LLL#L#.L#L##L#.L.#LLLLL..#L##L##.LLL#L#LLL.#LLLLL.#L#LLL#.LL#LL#L#LLL#L#L#LLL#
#LLLL.#L#..LLLLLLLLL.#.LLL.LLLLLLL.#LL#L#LLL.LLLLLLLL##LLLLL##.LL#L##.LLLL#LLL#LLL#LL.L#LLLLLLL#LL
LL#L#.LL#..LL#L#L#L#LLLLL#L#L#L#L#.L#LLLLL#L##L#.L#..LLL#L##.L.L#L.LL.L#L#L.#LLL#LLL#LLLL#L#L#LLL#
#LLLL.#LLL.#LLLLLLLL.#L#L#.LLLLLLL.LLL#L#LLL.LLLLLLL.#L#LL.LL#LLLL#LL.LLLLLLL.#LLL#LL.#.LLLLLLL#LL
LL#L#LL#L#LLL#L.#L#L.LLLLL.L#L#L#L.L#LLLLL#LLL#L##L#.LLLL#L#LL.##LLL#L#L#L#L#.LL#LLL#.LLL#L#L#.LL.
#LLLL.LLLL.#LLL.LLLL.L#L#L#LLLLLLL#LLL#L#LLL#LLLLLLL.L#LLLLLL#.LLL#LLL#LLLLLL.#LLL#LLL#.LLLLLLL.L#
L#L#L#.L#LLLL#L#L#L#.L#L#L#L#L#L#..L#LLL#L#L.#LL#L#L#LLL#L#L#L.##LLL#.LLL#L#LLLL#L#LL.#L#L#L#L##LL
...L...L...#...LL...LL.L.L..LL..L....L#...L#LL.L........#......L..L....#.L....#...L.L.L.LLL.#..L.#
#L#LL.#.L#.LLLL.#L#L.#L#L#L#LLL#LLL#L.LLL#LL.##LL.LL.#L.LLLLLL.#LLLL#.LLLL#L#LLLL#L#L.L#L#LLLLLLLL
LLLL#.LLLL.#L#L.LLLLLLLLLLL#L#L#L#LLL#L#L.L#.LLL##L#LLL#L#L#L#LLL#L#L.#L#L#LLL#.LLLLL.LLLLL#L#L#L#
#L#LL.#L#L.LLLL#LL#L.#L#L#.LLLL.LL.#LLLLLLLL.##LLLLL.#LLLLLLLLL#LLLLL.LLLLLL#.LLL#L#L#L#L#LLLLLLLL
LLLL#LLLLL.#L#L.#LLL.LLLLL.#LL#L##.LL#L#L#L#.LLL##L#LLL#L#L#L#.LL#L#L#L#L#L#L.L#LLLLLLLLLL.#L#L#L#
#L#LL.#L#L.LLL#.LL#L#L#L#LLL#L.LLL.#LLLLLLLL.##LLLLL.#LLLLLLLL.L#LLLLLLLLLLLL.LLL#L#L.#L#LLLLLLLLL
LLLL#.LLLL#L#LL.#LLLLLLLLL#LLLL#L#LLL#L#L#L#.LLL##L#.LL#L#L#L#.LLL#L.L#LL#L#L#L#LLLLL.#LLL#L#L.#L#
#L#LL.#L#LLLLL#LL#LL#L#L#LLLL#LLLL.#LLLLLLLLLL#LLLLLL#.LLLLLLL.L.LLL#LLL#LLLLLLLL#L#LLLL#LLLLLLLLL
LLL#L.LLLL#L#LL.LL.L.LLLL#L#LLL#L#.LL#L#LL#L#LLL#L#L#LL#L#L#L#LL#L#LL.#LLL#LL.#L#LLL..#LLL#L#L#LL#
#L.L...L#..LL..L..#.L....L...#..L..LL......LL.#.......L..LL........L#.LL#LL.......L.....#L.LL.....
LL#LL.#LLLLL#.L.#LLL.##L#L.LLLLLLL.#LLLLL#L#LLLLLLLL.#LL#L#L#..LLLLLL.#LLL#LL#L#L#.L#.LLLLL#L#L#LL
#LLL#.LL#L#LL.L.L#L#.LLLLL.#L#L#L#.LL#L#LLLL.##L##L#.LL#LLLLLLL#L#L#LLLL#LLL#.L#LLLLL.L#L#LLLLLLL#
LL#LL.#LLL.#L#L#LLLLL.#L#L.L.LLLLL.#LLLLL#L#.LLLLLLL.L#L.LL#L#.LLLLLL.#LLL#LLLLLLL#L#.LLLLL#L#L#LL
#LL.#.LL#LLLLLL.L#L#LLLLLLLL#L#L#L.LL#L#L.LL.L#L#L#L.LLL#L#LLL.L#L#L#.#L#LLL#.LL#LLLL.L#L#L#LL.LL#
..#.L....#L.L#.....L.#L......L.LL..#LLLLL......LL.L.L#.LLL...#LLL......L.L.L...#L..#..L..L...L#..L
LLLL#.LLLLL#LLL.LL#..LLLL#.LL#L#L#.L#L#L#L#L.#L#L#L#..LL#LL#LL.#L#LLL#L#.L###.LLL#LLL.#L#L#L#L.LL#
#L#L..L#L#.LL#L.#LLL.#L#LL.#LLLLLLLLLLLLLLLLLLLLLLLL.L#LLL#LL#.LLLLL#.LLLLLLL.#L#LLL#LLLLLLLLLL#LL
LL#.L.LLLL.#LLL.LL#L.LLLL#.L#L#L#L.#L#L#L#L#L#LL#L.#.LLL#LLL#LL#LL#LL.#L#L#LL.LLLL#LL.#LL#L#L#L.L#
#.LL..#L#L.L.#LL#LLL##L#LL.LLLLLLL.LLLLLLLL..LLL.LLL.L#LLL#.LL.LL#LL#.LLLLLL#L#L#LLL#.LL#LLLLLLLLL
LL##L.LLLL.#L.#.LL#L.LLL#L.L#L#L#L#L#L#L#LLL#L#LL#L#.LLL#.LLL#L#LLL#..L#L#LLL.LLLL#LL.#LLL#L#LL#L#
#....L...L..#.L...L....L......L..L#L..L..L#.LL.#.L....#..L.#.LLL.#.LLLL.........#..L#.LL#......L..
LLLLL.#L#L.LLLL.L#LL.##LLL.#L#LLLL.#L#LLLLLLLLLLLL#L.LLLLL.LL#L#LLLL#L#L#L#L#.LLLLLLL.LLLLLLLLL#.L
#L#L#.LL#..L#L#.LLL#.LLL#L.LL#L#L#.LL#L#L#LL#.L#L#.L#L#L#L#LLLLLL#L#L.#L#L#LL.#L#L#L#.L#L#L#L#L.L#
LLLLL.#LLLLL.LL.#LLL.#LLLL.#LLLLLL.L.LLLLLLL.LLLLLLLLLLLLLLL#L#LLLLLLLLLLLLL#LLLLLLLL.LLLLLLLLLLLL
#L#L#.LL#L.#L#LLL#L#.LL#L#.L#L#L#L.L#L#L#L#.L#L#L#L#.L#L#L#LLL.L#L#L#.L#.L#LLL#L#L#L#.L#L#L#L#L#L#
LLLLL.LLLL.LLLL.LLLL.#LLLL.LLLLLLL.LLLLLLLLLLLLLLLLL.LLLLLLLL#.LLLLLL.LLLLLL#.LLLLLLLLLLLLLLLLLLLL
#L#L#L#L#L#L.#L#L#L#.L#L#L#.L#L#L#L#L#L#L#L#.L#L##.L#L#L#L#L#L.#L#L#L#L#L#L#L.#L#L#L#.L#L#L#L#L#L#
there are 2059 occupied seats
And that's it for Day 11!
Here's another article just for you:
Declarative memory management
It feels like an eternity since I've started using Rust, and yet I remember vividly what it felt like to bang my head against the borrow checker for the first few times.
I'm definitely not alone in that, and there's been quite a few articles on the subject! But I want to take some time to present the borrow checker from the perspective of its , rather than as an opponent to fend with.