417 lines
10 KiB
Rust
417 lines
10 KiB
Rust
//! Day 10
|
|
|
|
use std::collections::{HashMap, HashSet};
|
|
|
|
use itertools::Itertools;
|
|
|
|
use crate::util::grid::{Direction, Griterator, NeighborsCfg, Pos};
|
|
|
|
pub const DAY: u8 = 10;
|
|
pub const TITLE: &str = "Pipe Maze";
|
|
|
|
#[derive(Debug)]
|
|
struct Maze {
|
|
nodes: HashMap<Pos, Node>,
|
|
start: Pos,
|
|
h: usize,
|
|
w: usize,
|
|
ncfg: NeighborsCfg,
|
|
}
|
|
|
|
#[derive(Debug)]
|
|
struct Node {
|
|
a: Pos,
|
|
b: Pos,
|
|
c: char,
|
|
d: Direction,
|
|
pipe_dist: Option<i32>,
|
|
}
|
|
|
|
impl Maze {
|
|
fn print(&self) {
|
|
Griterator::new(self.ncfg.tl.unwrap(), self.ncfg.br.unwrap()).for_each(|p| {
|
|
if p.x == 0 {
|
|
println!();
|
|
}
|
|
if self.loop_part(p) {
|
|
print!("{}", self.nodes[&p].c);
|
|
} else {
|
|
print!("·");
|
|
}
|
|
});
|
|
println!();
|
|
}
|
|
|
|
fn print_ws(&self, set: &HashSet<Pos>) {
|
|
Griterator::new(self.ncfg.tl.unwrap(), self.ncfg.br.unwrap()).for_each(|p| {
|
|
if p.x == 0 {
|
|
println!();
|
|
}
|
|
if set.contains(&p) {
|
|
print!("X");
|
|
} else if self.loop_part(p) {
|
|
print!("{}", self.nodes[&p].c);
|
|
} else {
|
|
print!("·");
|
|
}
|
|
});
|
|
println!();
|
|
}
|
|
|
|
fn loop_part(&self, p: Pos) -> bool {
|
|
self.nodes
|
|
.get(&p)
|
|
.map(|n| n.pipe_dist.is_some())
|
|
.unwrap_or_default()
|
|
}
|
|
|
|
fn pipe_fill_start(&mut self) {
|
|
let start_conns = self
|
|
.start
|
|
.neighbors(&self.ncfg)
|
|
.filter(|p| {
|
|
self.nodes
|
|
.get(p)
|
|
.map(|nd| nd.connection(self.start).is_some())
|
|
.unwrap_or_default()
|
|
})
|
|
.collect_vec();
|
|
|
|
for p in &start_conns {
|
|
self.pipe_fill(self.start, 0, *p);
|
|
}
|
|
|
|
assert_eq!(start_conns.len(), 2);
|
|
|
|
let conn_dirs: (Direction, Direction) = start_conns
|
|
.iter()
|
|
.map(|d| self.start.direction(*d).unwrap())
|
|
.sorted()
|
|
.collect_tuple()
|
|
.unwrap();
|
|
let (c, dr) = match conn_dirs {
|
|
(Direction::North, Direction::South) => ('│', Direction::North),
|
|
(Direction::East, Direction::West) => ('─', Direction::East),
|
|
(Direction::North, Direction::East) => ('└', Direction::North),
|
|
(Direction::North, Direction::West) => ('┘', Direction::West),
|
|
(Direction::South, Direction::West) => ('┐', Direction::South),
|
|
(Direction::East, Direction::South) => ('┌', Direction::East),
|
|
_ => panic!(),
|
|
};
|
|
|
|
self.nodes.insert(
|
|
self.start,
|
|
Node {
|
|
a: start_conns[0],
|
|
b: start_conns[1],
|
|
c,
|
|
d: dr,
|
|
pipe_dist: Some(0),
|
|
},
|
|
);
|
|
}
|
|
|
|
fn pipe_fill(&mut self, from: Pos, from_v: i32, p: Pos) {
|
|
if let Some(nd) = self.nodes.get_mut(&p) {
|
|
if let Some(to) = nd.connection(from) {
|
|
let mut ndv;
|
|
ndv = from_v + 1;
|
|
if let Some(old_ndv) = nd.pipe_dist {
|
|
ndv = ndv.min(old_ndv);
|
|
}
|
|
nd.pipe_dist = Some(ndv);
|
|
self.pipe_fill(p, ndv, to);
|
|
}
|
|
}
|
|
}
|
|
|
|
fn space_fill(&self, set: &mut HashSet<Pos>, p: Pos) {
|
|
if !self.loop_part(p) && set.insert(p) {
|
|
p.neighbors(&self.ncfg)
|
|
.for_each(|n| self.space_fill(set, n))
|
|
}
|
|
}
|
|
|
|
/// On a line from the position to the outside, check if there is an odd
|
|
/// amount of pipes to be crossed
|
|
fn is_enclosed(&self, start: Pos) -> bool {
|
|
print!("{start:?} ");
|
|
|
|
let mut n = 0;
|
|
let mut was_curved = false;
|
|
|
|
for x in (start.x..self.w as i64) {
|
|
let p = Pos { x, y: start.y };
|
|
if let Some(node) = self.nodes.get(&p) {
|
|
if node.pipe_dist.is_none() {
|
|
continue;
|
|
}
|
|
print!("{x};");
|
|
match (node.a.y == p.y, node.b.y == p.y) {
|
|
// Horizontal pipe
|
|
(true, true) => {}
|
|
// Curved pipe
|
|
(true, false) | (false, true) => {
|
|
if was_curved {
|
|
n += 1;
|
|
}
|
|
was_curved = !was_curved;
|
|
}
|
|
// Vertical pipe
|
|
(false, false) => {
|
|
n += 1;
|
|
was_curved = false;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
println!(" ({n})");
|
|
n % 2 > 0
|
|
}
|
|
}
|
|
|
|
impl Node {
|
|
fn new(a: Pos, b: Pos, c: char, dr: Direction) -> Self {
|
|
Self {
|
|
a,
|
|
b,
|
|
c,
|
|
d: dr,
|
|
pipe_dist: None,
|
|
}
|
|
}
|
|
|
|
fn connection(&self, p: Pos) -> Option<Pos> {
|
|
if self.a == p {
|
|
Some(self.b)
|
|
} else if self.b == p {
|
|
Some(self.a)
|
|
} else {
|
|
None
|
|
}
|
|
}
|
|
|
|
fn straight(&self) -> bool {
|
|
(self.a.x == 0 && self.b.x == 0) || (self.a.y == 0 && self.b.y == 0)
|
|
}
|
|
}
|
|
|
|
fn parse(input: Vec<String>) -> Maze {
|
|
let mut nodes = HashMap::new();
|
|
let mut start = None;
|
|
|
|
let h = input.len();
|
|
let w = input[0].len();
|
|
|
|
for (y, line) in input.iter().enumerate() {
|
|
for (x, c) in line.chars().enumerate() {
|
|
let p = Pos::usize(x, y);
|
|
let n = match c {
|
|
'|' => Node::new(
|
|
p.offset(Direction::South),
|
|
p.offset(Direction::North),
|
|
'│',
|
|
Direction::North,
|
|
),
|
|
'-' => Node::new(
|
|
p.offset(Direction::West),
|
|
p.offset(Direction::East),
|
|
'─',
|
|
Direction::East,
|
|
),
|
|
'L' => Node::new(
|
|
p.offset(Direction::East),
|
|
p.offset(Direction::North),
|
|
'└',
|
|
Direction::North,
|
|
),
|
|
'J' => Node::new(
|
|
p.offset(Direction::North),
|
|
p.offset(Direction::West),
|
|
'┘',
|
|
Direction::West,
|
|
),
|
|
'7' => Node::new(
|
|
p.offset(Direction::West),
|
|
p.offset(Direction::South),
|
|
'┐',
|
|
Direction::South,
|
|
),
|
|
'F' => Node::new(
|
|
p.offset(Direction::South),
|
|
p.offset(Direction::East),
|
|
'┌',
|
|
Direction::East,
|
|
),
|
|
'S' => {
|
|
start = Some(p);
|
|
continue;
|
|
}
|
|
'.' => continue,
|
|
_ => panic!("invalid char {c}"),
|
|
};
|
|
nodes.insert(p, n);
|
|
}
|
|
}
|
|
|
|
Maze {
|
|
nodes,
|
|
start: start.unwrap(),
|
|
h,
|
|
w,
|
|
ncfg: NeighborsCfg {
|
|
diag: false,
|
|
tl: Some(Pos::usize(0, 0)),
|
|
br: Some(Pos::usize(w - 1, h - 1)),
|
|
},
|
|
}
|
|
}
|
|
|
|
pub fn part1(input: Vec<String>) -> String {
|
|
let mut maze = parse(input);
|
|
maze.pipe_fill_start();
|
|
|
|
maze.nodes
|
|
.iter()
|
|
.max_by_key(|(_, n)| n.pipe_dist)
|
|
.unwrap()
|
|
.1
|
|
.pipe_dist
|
|
.unwrap()
|
|
.to_string()
|
|
}
|
|
|
|
pub fn part2(input: Vec<String>) -> String {
|
|
// return cheat2(input);
|
|
|
|
let mut maze = parse(input);
|
|
// Find the pipe
|
|
maze.pipe_fill_start();
|
|
|
|
// Find a start position from the outside
|
|
let start_pos = Griterator::new(maze.ncfg.tl.unwrap(), maze.ncfg.br.unwrap())
|
|
.find(|p| maze.loop_part(*p))
|
|
.unwrap();
|
|
|
|
let mut p = start_pos;
|
|
let mut d = maze.nodes[&p].d;
|
|
let mut inside_starts = HashSet::new();
|
|
loop {
|
|
let n = &maze.nodes[&p];
|
|
|
|
// Look on the right side of the moving direction
|
|
let p_r = p.offset(d.rotate_90(1));
|
|
// If there is no pipe on the right, add to inside positions
|
|
if !maze.loop_part(p_r) {
|
|
inside_starts.insert(p_r);
|
|
}
|
|
if !n.straight() {
|
|
let p_x = p.offset(d.rotate_45(1));
|
|
if !maze.loop_part(p_x) {
|
|
inside_starts.insert(p_x);
|
|
}
|
|
}
|
|
|
|
// Move to the next pipe
|
|
let nxt_p = p.offset(d);
|
|
if nxt_p == start_pos {
|
|
break;
|
|
}
|
|
|
|
// Get direction of next pipe
|
|
let nxt_node = &maze.nodes[&nxt_p];
|
|
let pnn = if nxt_node.a == p {
|
|
nxt_node.b
|
|
} else {
|
|
nxt_node.a
|
|
};
|
|
d = nxt_p.direction(pnn).unwrap();
|
|
|
|
p = nxt_p;
|
|
}
|
|
|
|
let mut inside = HashSet::new();
|
|
inside_starts
|
|
.iter()
|
|
.for_each(|p| maze.space_fill(&mut inside, *p));
|
|
// maze.print_ws(&inside_starts);
|
|
|
|
inside.len().to_string()
|
|
}
|
|
|
|
#[cfg(test)]
|
|
mod tests {
|
|
use super::*;
|
|
|
|
#[test]
|
|
fn t_example1() {
|
|
assert_eq!(part1(crate::read_example(DAY, 1)), "8");
|
|
}
|
|
|
|
#[test]
|
|
fn t_part1() {
|
|
assert_eq!(part1(crate::read_input(DAY)), "6846");
|
|
}
|
|
|
|
#[test]
|
|
fn t_example2_1() {
|
|
let input = r#"...........
|
|
.S-------7.
|
|
.|F-----7|.
|
|
.||.....||.
|
|
.||.....||.
|
|
.|L-7.F-J|.
|
|
.|..|.|..|.
|
|
.L--J.L--J.
|
|
..........."#
|
|
.lines()
|
|
.map(str::to_string)
|
|
.collect_vec();
|
|
assert_eq!(part2(input), "4");
|
|
}
|
|
|
|
#[test]
|
|
fn t_example2_2() {
|
|
let input = r#"...........
|
|
.S------7.
|
|
.|F----7|.
|
|
.||....||.
|
|
.||....||.
|
|
.|L-7F-J|.
|
|
.|..||..|.
|
|
.L--JL--J.
|
|
.........."#
|
|
.lines()
|
|
.map(str::to_string)
|
|
.collect_vec();
|
|
assert_eq!(part2(input), "4");
|
|
}
|
|
|
|
#[test]
|
|
fn t_example2_3() {
|
|
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..."#
|
|
.lines()
|
|
.map(str::to_string)
|
|
.collect_vec();
|
|
assert_eq!(part2(input), "8");
|
|
}
|
|
|
|
#[test]
|
|
fn t_example2() {
|
|
assert_eq!(part2(crate::read_example(DAY, 2)), "10");
|
|
}
|
|
|
|
#[test]
|
|
fn t_part2() {
|
|
assert_eq!(part2(crate::read_input(DAY)), "325");
|
|
}
|
|
}
|