day6 solution 2

1 files changed, 42 insertions, 4 deletions

diff --git a/src/bin/day6.rs b/src/bin/day6.rs
index 5de09c1..85e46f0 100644
--- a/src/bin/day6.rs
+++ b/src/bin/day6.rs
@@ -5,7 +5,7 @@ static DAY: u8 = 6;
 fn main() {
     let input = advent::read_lines(DAY);
     println!("{DAY}a: {}", Map::new(&input).distinct_positions());
-    println!("{DAY}b: {}", 0);
+    println!("{DAY}b: {}", Map::new(&input).possible_loops());
 }
 
 #[derive(Eq, PartialEq, Hash, Clone)]
@@ -14,13 +14,14 @@ struct Position {
     y: isize,
 }
 
-#[derive(Eq, PartialEq)]
+#[derive(Eq, PartialEq, Clone)]
 enum Object {
     Obstruction,
     Floor,
     Guard,
 }
 
+#[derive(Eq, PartialEq, Hash, Clone)]
 enum Direction {
     Up,
     Down,
@@ -50,6 +51,7 @@ impl Object {
     }
 }
 
+#[derive(Eq, PartialEq, Hash, Clone)]
 struct Guard {
     pos: Position,
     direction: Direction,
@@ -66,6 +68,7 @@ impl Guard {
     }
 }
 
+#[derive(Clone)]
 struct Map {
     map: HashMap<Position, Object>,
     guard: Guard,
@@ -93,8 +96,9 @@ impl Map {
         Map { map, guard, max_dimension: Position { x: input[0].len() as isize, y: input.len() as isize } }
     }
 
-    fn distinct_positions(&mut self) -> usize {
+    fn visited_path(&mut self) -> Option<HashSet<Position>> {
         let mut visited = HashSet::new();
+        let mut guard_variants = HashSet::new();
         loop {
             let next_pos = self.guard.next_pos();
             if next_pos.x < 0 || next_pos.x >= self.max_dimension.x || next_pos.y < 0 || next_pos.y >= self.max_dimension.y {
@@ -103,6 +107,10 @@ impl Map {
             match self.map.get(&next_pos).unwrap() {
                 Object::Floor => {
                     self.guard.pos = next_pos.clone();
+                    if !guard_variants.insert(self.guard.clone()) {
+                        // position already visited with same direction => loop
+                        return None;
+                    }
                     visited.insert(next_pos);
                 },
                 Object::Obstruction => {
@@ -112,7 +120,36 @@ impl Map {
                 _ => unimplemented!(),
             }
         }
-        visited.len()
+        Some(visited)
+    }
+
+    fn distinct_positions(&mut self) -> usize {
+        self.visited_path().unwrap().len()
+    }
+
+    fn possible_loops(&mut self) -> usize {
+        let original_map = self.clone();
+        let mut loop_count = 0;
+
+        for x in 0 .. self.max_dimension.x {
+            for y in 0 .. self.max_dimension.y {
+                let pos = Position { x, y };
+                if let Some(Object::Obstruction) = self.map.get(&pos) {
+                    // no need to check
+                    continue
+                }
+                self.map.insert(pos, Object::Obstruction);
+
+                if self.visited_path().is_none() {
+                    loop_count += 1;
+                }
+
+                // reset map
+                self.map = original_map.map.clone();
+                self.guard = original_map.guard.clone();
+            }
+        }
+        loop_count
     }
 }
 
@@ -135,5 +172,6 @@ mod tests {
             "......#...",
         ].iter().map(|&x| String::from(x)).collect::<Vec<_>>();
         assert_eq!(Map::new(&input).distinct_positions(), 41);
+        assert_eq!(Map::new(&input).possible_loops(), 6);
     }
 }