507 lines
12 KiB
Rust
507 lines
12 KiB
Rust
use std::{fmt::Debug, thread::current};
|
|
|
|
pub fn run() {
|
|
let input = include_str!("../input/day14.txt");
|
|
// let input = r#"
|
|
// O....#....
|
|
// O.OO#....#
|
|
// .....##...
|
|
// OO.#O....O
|
|
// .O.....O#.
|
|
// O.#..O.#.#
|
|
// ..O..#O..O
|
|
// .......O..
|
|
// #....###..
|
|
// #OO..#....
|
|
// "#;
|
|
let mut m: Map = input.into();
|
|
m.tilt_north();
|
|
dbg!(m.load(Direction::North));
|
|
|
|
m = input.into();
|
|
dbg!(part2(&mut m));
|
|
}
|
|
|
|
fn part2(map: &mut Map) -> usize {
|
|
// the problem says 1b cycles, but the output gets into a loop pretty quickly
|
|
// do 1k iterations and then figure out the period of the loop
|
|
let mut v = vec![];
|
|
for _ in 0..1_000 {
|
|
map.tilt_north();
|
|
map.tilt_west();
|
|
map.tilt_south();
|
|
map.tilt_east();
|
|
v.push(map.load(Direction::North));
|
|
}
|
|
|
|
dbg!(&v[0..15]);
|
|
|
|
let mut r = None;
|
|
for i in 0..990 {
|
|
let start = v.iter().skip(i).take(10);
|
|
if let Some(j) = (i + 1..990)
|
|
.filter(|j| v.iter().skip(*j).take(10).eq(start.clone()))
|
|
.next()
|
|
{
|
|
r = Some((i, j - i));
|
|
break;
|
|
}
|
|
}
|
|
|
|
let (period_start, period_length) = dbg!(r.unwrap());
|
|
|
|
let repeating = &v[period_start..(period_start + period_length)];
|
|
repeating[(1_000_000_000 - period_start - 1) % period_length]
|
|
}
|
|
|
|
#[derive(Clone, PartialEq, Eq)]
|
|
struct Map {
|
|
tiles: Vec<Vec<Tile>>,
|
|
width: usize,
|
|
height: usize,
|
|
}
|
|
|
|
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
|
|
enum Tile {
|
|
Empty,
|
|
Round,
|
|
Cube,
|
|
}
|
|
|
|
impl From<&str> for Map {
|
|
fn from(value: &str) -> Self {
|
|
let tiles = value
|
|
.trim()
|
|
.lines()
|
|
.map(|l| {
|
|
l.trim()
|
|
.chars()
|
|
.map(|c| match c {
|
|
'.' => Tile::Empty,
|
|
'O' => Tile::Round,
|
|
'#' => Tile::Cube,
|
|
_ => panic!("invalid char {:?}", c),
|
|
})
|
|
.collect::<Vec<_>>()
|
|
})
|
|
.collect::<Vec<_>>();
|
|
let width = tiles[0].len();
|
|
let height = tiles.len();
|
|
Self {
|
|
tiles,
|
|
width,
|
|
height,
|
|
}
|
|
}
|
|
}
|
|
|
|
impl Debug for Map {
|
|
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
|
|
write!(f, "Map(")?;
|
|
for row in self.tiles.iter() {
|
|
write!(f, "\n")?;
|
|
for tile in row.iter() {
|
|
write!(
|
|
f,
|
|
"{}",
|
|
match tile {
|
|
Tile::Empty => '.',
|
|
Tile::Round => 'O',
|
|
Tile::Cube => '#',
|
|
}
|
|
)?;
|
|
}
|
|
}
|
|
write!(f, ")")
|
|
}
|
|
}
|
|
|
|
enum Direction {
|
|
North,
|
|
South,
|
|
West,
|
|
East,
|
|
}
|
|
|
|
impl Direction {
|
|
fn offset(&self) -> (i32, i32) {
|
|
match self {
|
|
Self::North => (0, -1),
|
|
Self::South => (0, 1),
|
|
Self::West => (-1, 0),
|
|
Self::East => (1, 0),
|
|
}
|
|
}
|
|
|
|
fn vertical(&self) -> bool {
|
|
match self {
|
|
Self::North | Self::South => true,
|
|
_ => false,
|
|
}
|
|
}
|
|
}
|
|
|
|
impl Map {
|
|
fn tilt_north(&mut self) {
|
|
for col in 0..self.width {
|
|
let mut last_stop = -1i32;
|
|
let mut current_round = 0;
|
|
|
|
let finish_run =
|
|
|tiles: &mut Vec<Vec<Tile>>, current_round: i32, last_stop: i32, row: usize| {
|
|
if current_round == 0 {
|
|
return;
|
|
}
|
|
for i in 0..current_round {
|
|
tiles[(last_stop + 1 + i) as usize][col] = Tile::Round;
|
|
}
|
|
for i in (last_stop + 1 + current_round) as usize..row {
|
|
tiles[i][col] = Tile::Empty;
|
|
}
|
|
};
|
|
|
|
for row in 0..self.height {
|
|
match self.tiles[row][col] {
|
|
Tile::Empty => (),
|
|
Tile::Round => current_round += 1,
|
|
Tile::Cube => {
|
|
finish_run(&mut self.tiles, current_round, last_stop, row);
|
|
last_stop = row as i32;
|
|
current_round = 0;
|
|
}
|
|
}
|
|
}
|
|
finish_run(&mut self.tiles, current_round, last_stop, self.height);
|
|
}
|
|
}
|
|
|
|
fn tilt_south(&mut self) {
|
|
for col in 0..self.width {
|
|
let mut last_stop = self.height as i32;
|
|
let mut current_round = 0;
|
|
|
|
let finish_run =
|
|
|tiles: &mut Vec<Vec<Tile>>, current_round: i32, last_stop: i32, row: i32| {
|
|
if current_round == 0 {
|
|
return;
|
|
}
|
|
for i in 0..current_round {
|
|
tiles[(last_stop - 1 - i) as usize][col] = Tile::Round;
|
|
}
|
|
for i in (row + 1)..=(last_stop - 1 - current_round) {
|
|
tiles[i as usize][col] = Tile::Empty;
|
|
}
|
|
};
|
|
|
|
for row in (0..self.height).rev() {
|
|
match self.tiles[row][col] {
|
|
Tile::Empty => (),
|
|
Tile::Round => current_round += 1,
|
|
Tile::Cube => {
|
|
finish_run(&mut self.tiles, current_round, last_stop, row as i32);
|
|
last_stop = row as i32;
|
|
current_round = 0;
|
|
}
|
|
}
|
|
}
|
|
finish_run(&mut self.tiles, current_round, last_stop, -1);
|
|
}
|
|
}
|
|
|
|
fn tilt_west(&mut self) {
|
|
for row in 0..self.height {
|
|
let mut last_stop = -1i32;
|
|
let mut current_round = 0;
|
|
|
|
let finish_run =
|
|
|tiles: &mut Vec<Vec<Tile>>, current_round: i32, last_stop: i32, col: usize| {
|
|
if current_round == 0 {
|
|
return;
|
|
}
|
|
for i in 0..current_round {
|
|
tiles[row][(last_stop + 1 + i) as usize] = Tile::Round;
|
|
}
|
|
for i in (last_stop + 1 + current_round) as usize..col {
|
|
tiles[row][i] = Tile::Empty;
|
|
}
|
|
};
|
|
|
|
for col in 0..self.width {
|
|
match self.tiles[row][col] {
|
|
Tile::Empty => (),
|
|
Tile::Round => current_round += 1,
|
|
Tile::Cube => {
|
|
finish_run(&mut self.tiles, current_round, last_stop, col);
|
|
last_stop = col as i32;
|
|
current_round = 0;
|
|
}
|
|
}
|
|
}
|
|
finish_run(&mut self.tiles, current_round, last_stop, self.width);
|
|
}
|
|
}
|
|
|
|
fn tilt_east(&mut self) {
|
|
for row in 0..self.height {
|
|
let mut last_stop = self.width as i32;
|
|
let mut current_round = 0;
|
|
|
|
let finish_run =
|
|
|tiles: &mut Vec<Vec<Tile>>, current_round: i32, last_stop: i32, col: i32| {
|
|
if current_round == 0 {
|
|
return;
|
|
}
|
|
for i in 0..current_round {
|
|
tiles[row][(last_stop - 1 - i) as usize] = Tile::Round;
|
|
}
|
|
for i in (col + 1)..=(last_stop - 1 - current_round) {
|
|
tiles[row][i as usize] = Tile::Empty;
|
|
}
|
|
};
|
|
|
|
for col in (0..self.width).rev() {
|
|
match self.tiles[row][col] {
|
|
Tile::Empty => (),
|
|
Tile::Round => current_round += 1,
|
|
Tile::Cube => {
|
|
finish_run(&mut self.tiles, current_round, last_stop, col as i32);
|
|
last_stop = col as i32;
|
|
current_round = 0;
|
|
}
|
|
}
|
|
}
|
|
finish_run(&mut self.tiles, current_round, last_stop, -1);
|
|
}
|
|
}
|
|
|
|
fn move_run(
|
|
&mut self,
|
|
round_count: i32,
|
|
last_stop: i32,
|
|
dir: Direction,
|
|
run_end_index: i32,
|
|
dir_axis_index: usize,
|
|
) {
|
|
if round_count == 0 {
|
|
return;
|
|
}
|
|
|
|
let (dx, dy) = dir.offset();
|
|
let sign = -1 * (if dx != 0 { dx } else { dy });
|
|
|
|
let run_start = last_stop + sign * 1;
|
|
let round_end = last_stop + sign * (1 + round_count);
|
|
|
|
for i in run_start.min(round_end)..round_end.max(run_start) {
|
|
if dir.vertical() {
|
|
self.tiles[i as usize][dir_axis_index] = Tile::Round;
|
|
} else {
|
|
self.tiles[dir_axis_index][i as usize] = Tile::Round;
|
|
}
|
|
}
|
|
for i in round_end.min(run_end_index)..run_end_index.max(round_end) {
|
|
if dir.vertical() {
|
|
self.tiles[i as usize][dir_axis_index] = Tile::Empty;
|
|
} else {
|
|
self.tiles[dir_axis_index][i as usize] = Tile::Empty;
|
|
}
|
|
}
|
|
}
|
|
|
|
fn load(&self, dir: Direction) -> usize {
|
|
let (dx, dy) = dir.offset();
|
|
let dir_axis_count = if dir.vertical() {
|
|
self.height
|
|
} else {
|
|
self.width
|
|
};
|
|
let perpendicular_axis_count = if dir.vertical() {
|
|
self.width
|
|
} else {
|
|
self.height
|
|
};
|
|
|
|
let mut total = 0;
|
|
for i in 0..dir_axis_count {
|
|
let factor = if dx == -1 || dy == -1 {
|
|
dir_axis_count - i
|
|
} else {
|
|
i + 1
|
|
};
|
|
|
|
let mut count = 0;
|
|
for j in 0..perpendicular_axis_count {
|
|
let tile = if dir.vertical() {
|
|
self.tiles[i][j]
|
|
} else {
|
|
self.tiles[j][i]
|
|
};
|
|
if tile == Tile::Round {
|
|
count += 1;
|
|
}
|
|
}
|
|
|
|
total += factor * count;
|
|
}
|
|
total
|
|
}
|
|
}
|
|
|
|
#[cfg(test)]
|
|
mod tests {
|
|
use super::*;
|
|
|
|
#[test]
|
|
fn tilt_north() {
|
|
let mut m: Map = r#"
|
|
O....#....
|
|
O.OO#....#
|
|
.....##...
|
|
OO.#O....O
|
|
.O.....O#.
|
|
O.#..O.#.#
|
|
..O..#O..O
|
|
.......O..
|
|
#....###..
|
|
#OO..#....
|
|
"#
|
|
.into();
|
|
m.tilt_north();
|
|
assert_eq!(
|
|
m,
|
|
r#"
|
|
OOOO.#.O..
|
|
OO..#....#
|
|
OO..O##..O
|
|
O..#.OO...
|
|
........#.
|
|
..#....#.#
|
|
..O..#.O.O
|
|
..O.......
|
|
#....###..
|
|
#....#...."#
|
|
.into()
|
|
);
|
|
}
|
|
|
|
#[test]
|
|
fn tilt_south() {
|
|
let mut m: Map = r#"
|
|
O....#....
|
|
O.OO#....#
|
|
.....##...
|
|
OO.#O....O
|
|
.O.....O#.
|
|
O.#..O.#.#
|
|
..O..#O..O
|
|
.......O..
|
|
#....###..
|
|
#OO..#....
|
|
"#
|
|
.into();
|
|
m.tilt_south();
|
|
assert_eq!(
|
|
m,
|
|
r#"
|
|
.....#....
|
|
....#....#
|
|
...O.##...
|
|
...#......
|
|
O.O....O#O
|
|
O.#..O.#.#
|
|
O....#....
|
|
OO....OO..
|
|
#OO..###..
|
|
#OO.O#...O
|
|
"#
|
|
.into()
|
|
);
|
|
}
|
|
|
|
#[test]
|
|
fn tilt_west() {
|
|
let mut m: Map = r#"
|
|
O....#....
|
|
O.OO#....#
|
|
.....##...
|
|
OO.#O....O
|
|
.O.....O#.
|
|
O.#..O.#.#
|
|
..O..#O..O
|
|
.......O..
|
|
#....###..
|
|
#OO..#....
|
|
"#
|
|
.into();
|
|
m.tilt_west();
|
|
assert_eq!(
|
|
m,
|
|
r#"
|
|
O....#....
|
|
OOO.#....#
|
|
.....##...
|
|
OO.#OO....
|
|
OO......#.
|
|
O.#O...#.#
|
|
O....#OO..
|
|
O.........
|
|
#....###..
|
|
#OO..#....
|
|
"#
|
|
.into()
|
|
);
|
|
}
|
|
|
|
#[test]
|
|
fn tilt_east() {
|
|
let mut m: Map = r#"
|
|
O....#....
|
|
O.OO#....#
|
|
.....##...
|
|
OO.#O....O
|
|
.O.....O#.
|
|
O.#..O.#.#
|
|
..O..#O..O
|
|
.......O..
|
|
#....###..
|
|
#OO..#....
|
|
"#
|
|
.into();
|
|
m.tilt_east();
|
|
assert_eq!(
|
|
m,
|
|
r#"
|
|
....O#....
|
|
.OOO#....#
|
|
.....##...
|
|
.OO#....OO
|
|
......OO#.
|
|
.O#...O#.#
|
|
....O#..OO
|
|
.........O
|
|
#....###..
|
|
#..OO#....
|
|
"#
|
|
.into()
|
|
);
|
|
}
|
|
|
|
#[test]
|
|
fn load_north() {
|
|
let m: Map = r#"
|
|
OOOO.#.O..
|
|
OO..#....#
|
|
OO..O##..O
|
|
O..#.OO...
|
|
........#.
|
|
..#....#.#
|
|
..O..#.O.O
|
|
..O.......
|
|
#....###..
|
|
#....#....
|
|
"#
|
|
.into();
|
|
assert_eq!(m.load(Direction::North), 136);
|
|
}
|
|
}
|