Day 25

1 files changed, 144 insertions, 9 deletions

diff --git a/2023/src/bin/day_25.rs b/2023/src/bin/day_25.rs
index b3a610b..7bd3751 100644
--- a/2023/src/bin/day_25.rs
+++ b/2023/src/bin/day_25.rs
@@ -1,19 +1,154 @@
-use nom::IResult;
-use std::fs;
+use nom::{
+    bytes::complete::tag,
+    character::complete::{alpha1, line_ending, space1},
+    combinator::map,
+    multi::separated_list1,
+    sequence::separated_pair,
+    IResult,
+};
+use std::{collections::BTreeMap, fs};
 
 fn main() -> Result<(), Box<dyn std::error::Error>> {
-    let input = fs::read_to_string("inputs/day_2.txt")?;
-    let parsed = Example::parser(&input).unwrap().1;
-    dbg!(&parsed);
+    let input = fs::read_to_string("inputs/day_25.txt")?;
+    let parsed = Circuit::parser(&input).unwrap().1;
+    let three_cut_partition_sizes = parsed.find_non_zero_three_cut_partition_sizes();
+    dbg!(&three_cut_partition_sizes);
+    dbg!(three_cut_partition_sizes.0 * three_cut_partition_sizes.1);
 
     Ok(())
 }
 
+#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
+struct VertexId(usize);
+
 #[derive(Debug)]
-struct Example;
+struct Circuit {
+    wires: Vec<Vec<VertexId>>,
+}
+
+#[derive(Debug, Clone, Eq)]
+struct Edge {
+    a: VertexId,
+    b: VertexId,
+}
+
+impl PartialEq for Edge {
+    fn eq(&self, other: &Self) -> bool {
+        (self.a == other.a && self.b == other.b) || (self.a == other.b && self.b == other.a)
+    }
+}
+
+impl Circuit {
+    fn parser(input: &str) -> IResult<&str, Self> {
+        map(
+            separated_list1(
+                line_ending,
+                separated_pair(
+                    map(alpha1, |s: &str| s.to_owned()),
+                    tag(": "),
+                    separated_list1(space1, map(alpha1, |s: &str| s.to_owned())),
+                ),
+            ),
+            |vertices| {
+                let mut vertex_id_mapping = BTreeMap::new();
+                let mut wires = Vec::new();
+
+                for (from, tos) in vertices {
+                    let from_id = vertex_id_mapping
+                        .entry(from)
+                        .or_insert_with(|| {
+                            let new_id = VertexId(wires.len());
+                            wires.push(Vec::new());
+                            new_id
+                        })
+                        .clone();
+                    for to in tos {
+                        let to_id = vertex_id_mapping
+                            .entry(to)
+                            .or_insert_with(|| {
+                                let new_id = VertexId(wires.len());
+                                wires.push(Vec::new());
+                                new_id
+                            })
+                            .clone();
+                        wires[from_id.0].push(to_id);
+                        wires[to_id.0].push(from_id);
+                    }
+                }
+                Circuit { wires }
+            },
+        )(input)
+    }
+
+    fn find_non_zero_three_cut_partition_sizes(&self) -> (usize, usize) {
+        let cut1s = self.edges_to_traverse_everything([]);
+        for (cut1i, cut1) in cut1s.iter().enumerate() {
+            let cut2s = self.edges_to_traverse_everything([cut1.clone()]);
+            for (cut2i, cut2) in cut2s.iter().enumerate() {
+                if cut1s[0..cut1i].contains(&cut2) {
+                    continue;
+                }
+                for cut3 in self.edges_to_traverse_everything([cut1.clone(), cut2.clone()]) {
+                    if cut1s[0..cut1i].contains(&cut3) || cut2s[0..cut2i].contains(&cut3) {
+                        // if (cut2, *) didn't work, then (*, cut2) also wouldn't work.
+                        continue;
+                    }
+                    let (size1, size2) = self.partition_sizes([cut1.clone(), cut2.clone(), cut3]);
+                    if size2 > 0 {
+                        return (size1, size2);
+                    }
+                }
+            }
+        }
+        panic!("No partitions with three cuts");
+    }
+
+    fn partition_sizes(&self, cuts: [Edge; 3]) -> (usize, usize) {
+        let mut visited = vec![false; self.wires.len()];
+        let mut frontier = Vec::new();
+
+        visited[0] = true;
+        frontier.push(VertexId(0));
+        let mut visited_count = 1;
+
+        while let Some(from) = frontier.pop() {
+            for to in &self.wires[from.0] {
+                let edge = Edge::new(from, *to);
+                if !cuts.contains(&edge) && !visited[to.0] {
+                    visited[to.0] = true;
+                    visited_count += 1;
+                    frontier.push(*to);
+                }
+            }
+        }
+
+        (visited_count, self.wires.len() - visited_count)
+    }
+
+    fn edges_to_traverse_everything<const N: usize>(&self, cuts: [Edge; N]) -> Vec<Edge> {
+        let mut visited = vec![false; self.wires.len()];
+        let mut frontier = Vec::new();
+
+        visited[0] = true;
+        frontier.push(VertexId(0));
+        let mut used_edges = Vec::new();
+
+        while let Some(from) = frontier.pop() {
+            for to in &self.wires[from.0] {
+                let edge = Edge::new(from, *to);
+                if !cuts.contains(&edge) && !visited[to.0] {
+                    visited[to.0] = true;
+                    used_edges.push(edge);
+                    frontier.push(*to);
+                }
+            }
+        }
+        used_edges
+    }
+}
 
-impl Example {
-    fn parser(_input: &str) -> IResult<&str, Self> {
-        todo!()
+impl Edge {
+    fn new(a: VertexId, b: VertexId) -> Edge {
+        Edge { a, b }
     }
 }