365 lines
8.5 KiB
Rust
365 lines
8.5 KiB
Rust
use std::collections::HashSet;
|
|
use std::fmt::Debug;
|
|
|
|
pub fn run() {
|
|
let input = include_str!("../input/day10.txt").trim();
|
|
// let input = r#".....
|
|
// .S-7.
|
|
// .|.|.
|
|
// .L-J.
|
|
// ....."#;
|
|
|
|
let mut g: Grid = input.into();
|
|
dbg!(g.find_furthest_from_start());
|
|
|
|
let p = g.loop_path();
|
|
g.replace_start();
|
|
g.replace_junk(&p);
|
|
dbg!(g.count_enclosed(&p));
|
|
}
|
|
|
|
#[derive(Clone)]
|
|
struct Grid {
|
|
chars: Vec<char>,
|
|
width: usize,
|
|
height: usize,
|
|
}
|
|
|
|
impl Debug for Grid {
|
|
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
|
|
write!(f, "Grid(\n{}\n)", self.chars.iter().collect::<String>())
|
|
}
|
|
}
|
|
|
|
impl From<&str> for Grid {
|
|
fn from(value: &str) -> Self {
|
|
let width = value
|
|
.char_indices()
|
|
.filter(|(_, c)| *c == '\n')
|
|
.next()
|
|
.unwrap()
|
|
.0;
|
|
let height = value.len() / (width + 1) + 1;
|
|
Self {
|
|
chars: value.chars().collect(),
|
|
width,
|
|
height,
|
|
}
|
|
}
|
|
}
|
|
|
|
impl Grid {
|
|
fn at(&self, col: isize, row: isize) -> char {
|
|
let idx = row * (self.width as isize + 1) + col;
|
|
if idx >= 0 && idx < self.chars.len() as isize {
|
|
self.chars[idx as usize]
|
|
} else {
|
|
'.'
|
|
}
|
|
}
|
|
|
|
fn start_pos(&self) -> Option<(isize, isize)> {
|
|
for row in 0..self.height as isize {
|
|
for col in 0..self.width as isize {
|
|
if self.at(col, row) == 'S' {
|
|
return Some((col, row));
|
|
}
|
|
}
|
|
}
|
|
None
|
|
}
|
|
|
|
fn start_type(&self, (col, row): (isize, isize)) -> char {
|
|
let up = ['|', '7', 'F'].contains(&self.at(col, row - 1));
|
|
let down = ['|', 'J', 'L'].contains(&self.at(col, row + 1));
|
|
let left = ['-', 'F', 'L'].contains(&self.at(col - 1, row));
|
|
let right = ['-', '7', 'J'].contains(&self.at(col + 1, row));
|
|
if up && down {
|
|
'|'
|
|
} else if left && right {
|
|
'-'
|
|
} else if up && right {
|
|
'L'
|
|
} else if up && left {
|
|
'J'
|
|
} else if down && left {
|
|
'7'
|
|
} else if down && right {
|
|
'F'
|
|
} else {
|
|
panic!()
|
|
}
|
|
}
|
|
|
|
fn replace_start(&mut self) {
|
|
let start = self.start_pos().unwrap();
|
|
let c = self.start_type(start);
|
|
self.chars[start.1 as usize * (self.width + 1) + start.0 as usize] = c;
|
|
}
|
|
|
|
fn connected(&self, (col, row): (isize, isize), c: char) -> [(isize, isize); 2] {
|
|
match c {
|
|
'|' => [(col, row - 1), (col, row + 1)],
|
|
'-' => [(col - 1, row), (col + 1, row)],
|
|
'L' => [(col, row - 1), (col + 1, row)],
|
|
'J' => [(col, row - 1), (col - 1, row)],
|
|
'7' => [(col, row + 1), (col - 1, row)],
|
|
'F' => [(col, row + 1), (col + 1, row)],
|
|
_ => panic!(),
|
|
}
|
|
}
|
|
|
|
fn walk_loop(&self, mut f: impl FnMut((isize, isize), (isize, isize))) {
|
|
let start = self.start_pos().unwrap();
|
|
let start_c = self.start_type(start);
|
|
let mut prev = [start, start];
|
|
let mut cur = self.connected(start, start_c);
|
|
f(start, start);
|
|
loop {
|
|
f(cur[0], cur[1]);
|
|
|
|
if cur[0] == cur[1] {
|
|
break;
|
|
}
|
|
|
|
let mut new = [(0, 0); 2];
|
|
for i in 0..=1 {
|
|
let cur_connections = self.connected(cur[i], self.at(cur[i].0, cur[i].1));
|
|
let next = if prev[i] == cur_connections[0] {
|
|
cur_connections[1]
|
|
} else {
|
|
cur_connections[0]
|
|
};
|
|
new[i] = next;
|
|
}
|
|
|
|
prev = cur;
|
|
cur = new;
|
|
}
|
|
}
|
|
|
|
fn find_furthest_from_start(&self) -> usize {
|
|
let mut steps = 0;
|
|
self.walk_loop(|_, _| steps += 1);
|
|
// minus one, since the walk_loop fn is called for the start node
|
|
steps - 1
|
|
}
|
|
|
|
fn loop_path(&self) -> Vec<(isize, isize)> {
|
|
let mut v = vec![];
|
|
self.walk_loop(|a, b| {
|
|
v.push(a);
|
|
if a != b {
|
|
v.push(b);
|
|
}
|
|
});
|
|
v
|
|
}
|
|
|
|
fn replace_junk(&mut self, loop_path: &[(isize, isize)]) {
|
|
for row in 0..self.height {
|
|
for col in 0..self.width {
|
|
if !loop_path.contains(&(col as isize, row as isize)) {
|
|
self.chars[row * (self.width + 1) + col] = '.';
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
fn is_enclosed(&self, (col, mut row): (isize, isize)) -> bool {
|
|
// even-odd rule, walking up
|
|
let mut enclosed = false;
|
|
while row >= 0 && col >= 0 {
|
|
if ['-', 'L', 'F'].contains(&self.at(col, row)) {
|
|
enclosed = !enclosed;
|
|
}
|
|
row -= 1;
|
|
}
|
|
enclosed
|
|
}
|
|
|
|
fn count_enclosed(&self, loop_path: &[(isize, isize)]) -> usize {
|
|
let mut enclosed = 0;
|
|
for row in 0..self.height as isize {
|
|
for col in 0..self.width as isize {
|
|
if !loop_path.contains(&(col, row)) && self.is_enclosed((col, row)) {
|
|
enclosed += 1;
|
|
}
|
|
}
|
|
}
|
|
enclosed
|
|
}
|
|
}
|
|
|
|
#[cfg(test)]
|
|
mod tests {
|
|
use super::*;
|
|
|
|
#[test]
|
|
fn test_parse_grid() {
|
|
let input = r#".....
|
|
.S-7.
|
|
.|.|.
|
|
.L-J.
|
|
....."#;
|
|
let g: Grid = input.into();
|
|
assert_eq!(g.width, 5);
|
|
assert_eq!(g.height, 5);
|
|
assert_eq!(g.at(1, 1), 'S');
|
|
assert_eq!(g.at(10, 10), '.');
|
|
assert_eq!(g.at(4, 4), '.');
|
|
assert_eq!(g.start_pos(), Some((1, 1)));
|
|
}
|
|
|
|
#[test]
|
|
fn test_find_furthest_from_start() {
|
|
let input = r#".....
|
|
.S-7.
|
|
.|.|.
|
|
.L-J.
|
|
....."#;
|
|
let g: Grid = input.into();
|
|
assert_eq!(g.find_furthest_from_start(), 4);
|
|
|
|
let input = r#"..F7.
|
|
.FJ|.
|
|
SJ.L7
|
|
|F--J
|
|
LJ..."#;
|
|
let g: Grid = input.into();
|
|
assert_eq!(g.find_furthest_from_start(), 8);
|
|
}
|
|
|
|
#[test]
|
|
fn test_loop_path() {
|
|
let input = r#".....
|
|
.S-7.
|
|
.|.|.
|
|
.L-J.
|
|
....."#;
|
|
let g: Grid = input.into();
|
|
let mut p = g.loop_path();
|
|
p.sort();
|
|
let mut expected = vec![
|
|
(1, 1),
|
|
(1, 2),
|
|
(1, 3),
|
|
(2, 3),
|
|
(3, 3),
|
|
(3, 2),
|
|
(3, 1),
|
|
(2, 1),
|
|
];
|
|
expected.sort();
|
|
assert_eq!(p, expected);
|
|
}
|
|
|
|
#[test]
|
|
fn test_is_enclosed() {
|
|
let input = r#".....
|
|
.S-7.
|
|
.|.|.
|
|
.L-J.
|
|
....."#;
|
|
let g: Grid = input.into();
|
|
assert!(g.is_enclosed((2, 2)));
|
|
|
|
let input = r#"...........
|
|
.S-------7.
|
|
.|F-----7|.
|
|
.||.....||.
|
|
.||.....||.
|
|
.|L-7.F-J|.
|
|
.|..|.|..|.
|
|
.L--J.L--J.
|
|
..........."#;
|
|
let g: Grid = input.into();
|
|
assert!(g.is_enclosed((2, 6)));
|
|
assert!(!g.is_enclosed((3, 3)));
|
|
}
|
|
|
|
#[test]
|
|
fn test_count_enclosed1() {
|
|
let input = r#".....
|
|
.S-7.
|
|
.|.|.
|
|
.L-J.
|
|
....."#;
|
|
let mut g: Grid = input.into();
|
|
let p = g.loop_path();
|
|
g.replace_start();
|
|
assert_eq!(g.count_enclosed(&p), 1);
|
|
}
|
|
|
|
#[test]
|
|
fn test_count_enclosed2() {
|
|
let input = r#"...........
|
|
.S-------7.
|
|
.|F-----7|.
|
|
.||.....||.
|
|
.||.....||.
|
|
.|L-7.F-J|.
|
|
.|..|.|..|.
|
|
.L--J.L--J.
|
|
..........."#;
|
|
let mut g: Grid = input.into();
|
|
let p = g.loop_path();
|
|
g.replace_start();
|
|
assert_eq!(g.count_enclosed(&p), 4);
|
|
}
|
|
|
|
#[test]
|
|
fn test_count_enclosed3() {
|
|
let input = r#"..........
|
|
.S------7.
|
|
.|F----7|.
|
|
.||OOOO||.
|
|
.||OOOO||.
|
|
.|L-7F-J|.
|
|
.|II||II|.
|
|
.L--JL--J.
|
|
.........."#;
|
|
let mut g: Grid = input.into();
|
|
let p = g.loop_path();
|
|
g.replace_start();
|
|
assert_eq!(g.count_enclosed(&p), 4);
|
|
}
|
|
|
|
#[test]
|
|
fn test_count_enclosed4() {
|
|
let input = r#".F----7F7F7F7F-7....
|
|
.|F--7||||||||FJ....
|
|
.||.FJ||||||||L7....
|
|
FJL7L7LJLJ||LJ.L-7..
|
|
L--J.L7...LJS7F-7L7.
|
|
....F-J..F7FJ|L7L7L7
|
|
....L7.F7||L7|.L7L7|
|
|
.....|FJLJ|FJ|F7|.LJ
|
|
....FJL-7.||.||||...
|
|
....L---J.LJ.LJLJ..."#;
|
|
let mut g: Grid = input.into();
|
|
let p = g.loop_path();
|
|
g.replace_start();
|
|
assert_eq!(g.count_enclosed(&p), 8);
|
|
}
|
|
|
|
#[test]
|
|
fn test_count_enclosed5() {
|
|
let input = r#"FF7FSF7F7F7F7F7F---7
|
|
L|LJ||||||||||||F--J
|
|
FL-7LJLJ||||||LJL-77
|
|
F--JF--7||LJLJ7F7FJ-
|
|
L---JF-JLJ.||-FJLJJ7
|
|
|F|F-JF---7F7-L7L|7|
|
|
|FFJF7L7F-JF7|JL---7
|
|
7-L-JL7||F7|L7F-7F7|
|
|
L.L7LFJ|||||FJL7||LJ
|
|
L7JLJL-JLJLJL--JLJ.L"#;
|
|
let mut g: Grid = input.into();
|
|
let p = g.loop_path();
|
|
g.replace_start();
|
|
g.replace_junk(&p);
|
|
assert_eq!(g.count_enclosed(&p), 10);
|
|
}
|
|
}
|