155 lines
4.2 KiB
Rust
155 lines
4.2 KiB
Rust
#![warn(clippy::pedantic)]
|
|
#![feature(generators)]
|
|
#![feature(iter_from_generator)]
|
|
#![feature(let_chains)]
|
|
|
|
use petgraph::{algo::tarjan_scc, prelude::GraphMap, Undirected};
|
|
use std::{io::stdin, iter};
|
|
use strum::IntoEnumIterator;
|
|
|
|
use aoc::vecn::{Direction3, VecN};
|
|
|
|
type Position = VecN<3, u64>;
|
|
|
|
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
|
|
struct Face {
|
|
position: Position,
|
|
side: Direction3,
|
|
}
|
|
|
|
impl Face {
|
|
fn facing(self) -> Option<Position> {
|
|
let pos = self.position.try_map(i64::try_from).ok()? + self.side.into();
|
|
|
|
pos.try_map(u64::try_from).ok()
|
|
}
|
|
|
|
fn inverse(self) -> Option<Face> {
|
|
Some(Face {
|
|
position: self.facing()?,
|
|
side: -self.side,
|
|
})
|
|
}
|
|
|
|
fn neighbours(self) -> impl Iterator<Item = (Angle, Face)> {
|
|
iter::from_generator(move || {
|
|
let orthogonal_sides =
|
|
Direction3::iter().filter(move |&side| side != self.side && side != -self.side);
|
|
|
|
for side in orthogonal_sides.clone() {
|
|
yield (
|
|
Angle::Convex,
|
|
Face {
|
|
position: self.position,
|
|
side,
|
|
},
|
|
);
|
|
}
|
|
|
|
if let Some(facing) = self.facing() {
|
|
for side in orthogonal_sides.clone() {
|
|
if let Some(inverse) = (Face {
|
|
position: facing,
|
|
side,
|
|
})
|
|
.inverse()
|
|
{
|
|
yield (Angle::Concave, inverse);
|
|
}
|
|
}
|
|
}
|
|
|
|
for side in orthogonal_sides {
|
|
if let Some(facing) = (Face {
|
|
position: self.position,
|
|
side,
|
|
})
|
|
.facing()
|
|
{
|
|
yield (
|
|
Angle::Flat,
|
|
Face {
|
|
position: facing,
|
|
side: self.side,
|
|
},
|
|
);
|
|
}
|
|
}
|
|
})
|
|
}
|
|
}
|
|
|
|
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
|
|
enum Angle {
|
|
Concave,
|
|
Convex,
|
|
Flat,
|
|
}
|
|
|
|
fn main() {
|
|
let cubes = stdin().lines().map(|l| l.unwrap().parse().unwrap());
|
|
let faces =
|
|
cubes.flat_map(|position| Direction3::iter().map(move |side| Face { position, side }));
|
|
|
|
let mut graph = GraphMap::<Face, Angle, Undirected>::new();
|
|
for face in faces {
|
|
if let Some(inverse) = face.inverse() {
|
|
if graph.remove_node(inverse) {
|
|
continue;
|
|
}
|
|
}
|
|
|
|
graph.add_node(face);
|
|
|
|
for (angle, neighbour_face) in face.neighbours() {
|
|
if graph.contains_node(neighbour_face) {
|
|
graph.add_edge(face, neighbour_face, angle);
|
|
|
|
if let Angle::Concave = angle {
|
|
graph.remove_edge(
|
|
face,
|
|
Face {
|
|
position: face.position,
|
|
side: -neighbour_face.side,
|
|
},
|
|
);
|
|
|
|
graph.remove_edge(
|
|
neighbour_face,
|
|
Face {
|
|
position: neighbour_face.position,
|
|
side: -face.side,
|
|
},
|
|
);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
println!("{:?}", graph.node_count());
|
|
|
|
let sum_outside = tarjan_scc(&graph)
|
|
.into_iter()
|
|
.filter(|surface| {
|
|
graph
|
|
.all_edges()
|
|
.filter_map(|(start, end, angle)| {
|
|
if surface.contains(&start) || surface.contains(&end) {
|
|
Some(angle)
|
|
} else {
|
|
None
|
|
}
|
|
})
|
|
.map(|angle| match angle {
|
|
Angle::Concave => -1,
|
|
Angle::Convex => 1,
|
|
Angle::Flat => 0,
|
|
})
|
|
.sum::<i64>()
|
|
> 0
|
|
})
|
|
.map(|surface| surface.len())
|
|
.max()
|
|
.unwrap();
|
|
println!("{:?}", sum_outside);
|
|
}
|