Day 8 part 1

Part 2 needs some sort of cycle detection. Meh

1 files changed, 164 insertions, 9 deletions

diff --git a/2023/src/bin/day_8.rs b/2023/src/bin/day_8.rs
index b3a610b..b96b43a 100644
--- a/2023/src/bin/day_8.rs
+++ b/2023/src/bin/day_8.rs
@@ -1,19 +1,174 @@
-use nom::IResult;
-use std::fs;
+use nom::{
+    branch::alt,
+    bytes::complete::tag,
+    character::complete::{alpha1, char as nom_char, line_ending},
+    combinator::{map, value},
+    multi::{many1, separated_list1},
+    sequence::{pair, preceded, separated_pair, terminated},
+    IResult,
+};
+use std::{collections::BTreeMap, fs, ops::Range};
 
 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_8.txt")?;
+    let directions = Directions::parser(&input).unwrap().1;
+    dbg!(directions.steps_from_a_to_z());
+    dbg!(directions.ghost_steps_from_a_to_z());
 
     Ok(())
 }
 
 #[derive(Debug)]
-struct Example;
+struct Directions {
+    turns: Vec<Turn>,
+    packed_map: Vec<PackedFork>,
+    packed_ghost_starts: Range<u16>,
+    packed_ghost_destinations: Range<u16>,
+}
+
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+enum Turn {
+    Left,
+    Right,
+}
+
+#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone)]
+struct Location(String);
+
+#[derive(Debug)]
+struct Fork {
+    left: Location,
+    right: Location,
+}
+
+#[derive(Debug)]
+struct PackedFork {
+    left: u16,
+    right: u16,
+}
+
+impl Directions {
+    fn parser(input: &str) -> IResult<&str, Self> {
+        map(
+            separated_pair(
+                many1(Turn::parser),
+                pair(line_ending, line_ending),
+                separated_list1(
+                    line_ending,
+                    separated_pair(Location::parser, tag(" = "), Fork::parser),
+                ),
+            ),
+            |(turns, map)| {
+                let map: BTreeMap<Location, Fork> = map.into_iter().collect();
+                let mut locations: Vec<Location> = map.keys().cloned().collect();
+                locations.sort_by_key(|l| l.0.chars().rev().collect::<String>());
+
+                Directions {
+                    turns,
+                    packed_map: locations
+                        .iter()
+                        .map(|l| {
+                            let unpacked_fork = map.get(l).unwrap();
+                            PackedFork {
+                                left: locations
+                                    .iter()
+                                    .position(|f| *f == unpacked_fork.left)
+                                    .unwrap() as u16,
+                                right: locations
+                                    .iter()
+                                    .position(|f| *f == unpacked_fork.right)
+                                    .unwrap() as u16,
+                            }
+                        })
+                        .collect(),
+                    packed_ghost_starts: 0
+                        ..locations.iter().position(|l| !l.ghost_start()).unwrap() as u16,
+                    packed_ghost_destinations: locations.iter().position(|l| l.ghost_end()).unwrap()
+                        as u16
+                        ..locations.len() as u16,
+                }
+            },
+        )(input)
+    }
+
+    fn steps_from_a_to_z(&self) -> usize {
+        let mut step_count = 0;
+        let mut current_location: u16 = 0;
+
+        for dir in self.turns.iter().cycle() {
+            let current_fork: &PackedFork = &self.packed_map[current_location as usize];
+            current_location = match dir {
+                Turn::Left => current_fork.left,
+                Turn::Right => current_fork.right,
+            };
+            step_count += 1;
+
+            if current_location == self.packed_map.len() as u16 - 1 {
+                return step_count;
+            }
+        }
+        unreachable!()
+    }
+
+    fn ghost_steps_from_a_to_z(&self) -> usize {
+        let mut step_count = 0;
+        let mut current_locations: Vec<u16> = self.packed_ghost_starts.clone().collect();
+
+        for dir in self.turns.iter().cycle() {
+            for current_location in &mut current_locations {
+                let current_fork: &PackedFork = &self.packed_map[*current_location as usize];
+                *current_location = match dir {
+                    Turn::Left => current_fork.left,
+                    Turn::Right => current_fork.right,
+                };
+            }
+            step_count += 1;
+
+            if current_locations
+                .iter()
+                .all(|l| self.packed_ghost_destinations.contains(l))
+            {
+                return step_count;
+            }
+        }
+        unreachable!()
+    }
+}
+
+impl Turn {
+    fn parser(input: &str) -> IResult<&str, Self> {
+        alt((
+            value(Turn::Left, nom_char('L')),
+            value(Turn::Right, nom_char('R')),
+        ))(input)
+    }
+}
+
+impl Location {
+    fn parser(input: &str) -> IResult<&str, Self> {
+        map(alpha1, |l: &str| Location(l.to_string()))(input)
+    }
+
+    fn ghost_start(&self) -> bool {
+        self.0.ends_with("A")
+    }
+
+    fn ghost_end(&self) -> bool {
+        self.0.ends_with("Z")
+    }
+}
 
-impl Example {
-    fn parser(_input: &str) -> IResult<&str, Self> {
-        todo!()
+impl Fork {
+    fn parser(input: &str) -> IResult<&str, Self> {
+        map(
+            preceded(
+                tag("("),
+                terminated(
+                    separated_pair(Location::parser, tag(", "), Location::parser),
+                    tag(")"),
+                ),
+            ),
+            |(left, right)| Fork { left, right },
+        )(input)
     }
 }