From 281055020820980c53658e206ff3bab97f04bf15 Mon Sep 17 00:00:00 2001
From: =?utf8?q?Gr=C3=A9gory=20Burri?= <gregory.burri@matisa.ch>
Date: Tue, 4 Aug 2020 13:15:35 +0200
Subject: [PATCH] New (slow) version for day 18 part 1.

---
 src/day18.rs | 292 ++++++++++++++++++++++++++++++++++-----------------
 src/main.rs  |   4 +-
 2 files changed, 197 insertions(+), 99 deletions(-)

diff --git a/src/day18.rs b/src/day18.rs
index 58558c6..824505e 100644
--- a/src/day18.rs
+++ b/src/day18.rs
@@ -28,113 +28,188 @@ impl Vault {
         Vault { tunnels, entrance }
     }
 }
-/*
-#[derive(Debug)]
-struct Node {
-    parent: Option<Rc<Node>>,
-    length_to_parent: u32,
-    key: char,
-}
 
-struct NodeIterator {
-    current: Option<Rc<Node>>
-}
+mod v1 {
+    use super::*;
 
-impl NodeIterator {
-    fn from(node: Rc<Node>) -> NodeIterator { NodeIterator { current: Some(node) } }
-}
+    #[derive(Debug)]
+    struct Node {
+        parent: Option<Rc<Node>>,
+        length_to_parent: u32,
+        key: char,
+    }
 
-impl Iterator for NodeIterator {
-    type Item = Rc<Node>;
-    fn next(&mut self) -> Option<Rc<Node>> {
-        let next = self.current.as_ref().map(|n| Rc::clone(n));
-        self.current =
-            match self.current.as_ref() {
-                Some(n) => n.parent.as_ref().map(|n| Rc::clone(n)),
-                None => None
-            };
-        next
+    struct NodeIterator {
+        current: Option<Rc<Node>>
     }
-}
 
-impl Node {
-    fn new(parent: Option<Rc<Node>>, length_to_parent: u32, key: char) -> Self {
-        Node { parent, length_to_parent, key }
+    impl NodeIterator {
+        fn from(node: Rc<Node>) -> NodeIterator { NodeIterator { current: Some(node) } }
     }
-}
 
+    impl Iterator for NodeIterator {
+        type Item = Rc<Node>;
+        fn next(&mut self) -> Option<Rc<Node>> {
+            let next = self.current.as_ref().map(|n| Rc::clone(n));
+            self.current =
+                match self.current.as_ref() {
+                    Some(n) => n.parent.as_ref().map(|n| Rc::clone(n)),
+                    None => None
+                };
+            next
+        }
+    }
 
-fn iter(node: Rc<Node>) -> NodeIterator {
-    NodeIterator::from(node)
-}
+    impl Node {
+        fn new(parent: Option<Rc<Node>>, length_to_parent: u32, key: char) -> Self {
+            Node { parent, length_to_parent, key }
+        }
+    }
 
-fn nb_of_keys(node: Rc<Node>) -> u32 { iter(node).count() as u32 - 1 }
 
-fn length(node: Rc<Node>) -> u32 { iter(node).fold(0, |sum, node| sum + node.length_to_parent) }
+    fn iter(node: Rc<Node>) -> NodeIterator {
+        NodeIterator::from(node)
+    }
 
-fn can_open(node: Rc<Node>, door: char) -> bool {
-    let key_needed = door.to_ascii_lowercase();
-    iter(node).any(|node| node.key == key_needed)
-}
+    fn nb_of_keys(node: Rc<Node>) -> u32 { iter(node).count() as u32 - 1 }
 
-fn has_key(node: Rc<Node>, key: char) -> bool {
-    iter(node).any(|node| node.key == key)
-}
-*/
-/*
-pub fn nb_steps_to_collect_all_key(vault: &Vault) -> u32 {
-    //dbg!(vault);
-
-    fn find_keys(from : (i32, i32), parent: Rc<Node>, vault: &Vault) -> Vec<Rc<Node>> {
-        let mut to_visit = vec![(from, 1)];
-        let mut visited_positions: HashSet<(i32, i32)> = HashSet::new();
-        let mut reachable_keys = Vec::<Rc<Node>>::new();
-
-        //println!("find_keys: from:{:?}", from);
-        //println!("Nb of keys: {}", nb_of_keys(Rc::clone(&parent)));
-
-        while let Some((pos, steps)) = to_visit.pop() {
-            //println!("Pos to visit: {:?}", pos);
-            visited_positions.insert(pos);
-            //steps += 1;
-            for pos_d in &[(-1, 0), (0, 1), (1, 0), (0, -1)] {
-                let adjacent = (pos.0 + pos_d.0, pos.1 + pos_d.1);
-                //println!("Adjacent: {:?}", adjacent);
-                if adjacent.0 >= 0 && adjacent.0 < vault.tunnels.len() as i32 && adjacent.1 >= 0 && adjacent.1 < vault.tunnels[0].len() as i32 && !visited_positions.contains(&adjacent) {
-                    match vault.tunnels[adjacent.0 as usize][adjacent.1 as usize] {
-                        // Simple floor or a door or a owned key.
-                        c if c == FLOOR_SYMBOL || c == START_SYMBOL || c.is_ascii_uppercase() && can_open(Rc::clone(&parent), c) || c.is_ascii_lowercase() && has_key(Rc::clone(&parent), c) => {
-                            //println!("-> To visit");
-                            to_visit.push((adjacent, steps + 1));
-                        },
-                        c if c.is_ascii_lowercase() => { // A non-owned key.
-                            //println!("-> A new key! {:?}", c);
-                            visited_positions.insert(adjacent);
-                            let node = Rc::new(Node::new(Some(Rc::clone(&parent)), steps, c));
-                            reachable_keys.append(&mut find_keys(adjacent, node, vault));
-                        },
-                        WALL_SYMBOL | _ => (), //println!("-> WALL"),
+    fn length(node: Rc<Node>) -> u32 { iter(node).fold(0, |sum, node| sum + node.length_to_parent) }
+
+    fn can_open(node: Rc<Node>, door: char) -> bool {
+        let key_needed = door.to_ascii_lowercase();
+        iter(node).any(|node| node.key == key_needed)
+    }
+
+    fn has_key(node: Rc<Node>, key: char) -> bool {
+        iter(node).any(|node| node.key == key)
+    }
+
+    pub fn nb_steps_to_collect_all_key(vault: &Vault) -> u32 {
+        //dbg!(vault);
+
+        fn find_keys(from : (i32, i32), parent: Rc<Node>, vault: &Vault) -> Vec<Rc<Node>> {
+            let mut to_visit = vec![(from, 1)];
+            let mut visited_positions: HashSet<(i32, i32)> = HashSet::new();
+            let mut reachable_keys = Vec::<Rc<Node>>::new();
+
+            //println!("find_keys: from:{:?}", from);
+            //println!("Nb of keys: {}", nb_of_keys(Rc::clone(&parent)));
+
+            while let Some((pos, steps)) = to_visit.pop() {
+                //println!("Pos to visit: {:?}", pos);
+                visited_positions.insert(pos);
+                //steps += 1;
+                for pos_d in &[(-1, 0), (0, 1), (1, 0), (0, -1)] {
+                    let adjacent = (pos.0 + pos_d.0, pos.1 + pos_d.1);
+                    //println!("Adjacent: {:?}", adjacent);
+                    if adjacent.0 >= 0 && adjacent.0 < vault.tunnels.len() as i32 && adjacent.1 >= 0 && adjacent.1 < vault.tunnels[0].len() as i32 && !visited_positions.contains(&adjacent) {
+                        match vault.tunnels[adjacent.0 as usize][adjacent.1 as usize] {
+                            // Simple floor or a door or a owned key.
+                            c if c == FLOOR_SYMBOL || c == START_SYMBOL || c.is_ascii_uppercase() && can_open(Rc::clone(&parent), c) || c.is_ascii_lowercase() && has_key(Rc::clone(&parent), c) => {
+                                //println!("-> To visit");
+                                to_visit.push((adjacent, steps + 1));
+                            },
+                            c if c.is_ascii_lowercase() => { // A non-owned key.
+                                //println!("-> A new key! {:?}", c);
+                                visited_positions.insert(adjacent);
+                                let node = Rc::new(Node::new(Some(Rc::clone(&parent)), steps, c));
+                                reachable_keys.append(&mut find_keys(adjacent, node, vault));
+                            },
+                            WALL_SYMBOL | _ => (), //println!("-> WALL"),
+                        }
                     }
                 }
             }
-        }
 
-        if reachable_keys.is_empty() {
-            reachable_keys.push(parent);
+            if reachable_keys.is_empty() {
+                reachable_keys.push(parent);
+            }
+
+            reachable_keys
         }
 
-        reachable_keys
+        let root = Rc::new(Node::new(None, 0, START_SYMBOL));
+        let nodes = find_keys(vault.entrance, root, vault);
+
+        nodes.iter().map(|n| (length(Rc::clone(n)), nb_of_keys(Rc::clone(n)))).sorted_by(|(l1, n1), (l2, n2)| n1.cmp(&n2).then(l1.cmp(&l2))).nth(0).unwrap().0
+    }
+}
+
+mod v2 {
+    use super::*;
+
+    #[derive(Debug)]
+    struct Path {
+        to_visit: Vec<(i32, i32)>,
+        visited: HashSet<(i32, i32)>,
+        keys: Vec<char>
     }
 
-    let root = Rc::new(Node::new(None, 0, START_SYMBOL));
-    let nodes = find_keys(vault.entrance, root, vault);
+    impl Path {
+        pub fn new(initial_position: (i32, i32)) -> Self {
+            Path { to_visit: vec![initial_position], visited: HashSet::new(), keys: Vec::new() }
+        }
+    }
 
-    nodes.iter().map(|n| (length(Rc::clone(n)), nb_of_keys(Rc::clone(n)))).sorted_by(|(l1, n1), (l2, n2)| n1.cmp(&n2).then(l1.cmp(&l2))).nth(0).unwrap().0
+    pub fn nb_steps_to_collect_all_key(vault: &Vault) -> u32 {
+        let nb_of_keys: usize = vault.tunnels.iter().map(|line| line.iter().fold(0, |acc, c| if c.is_ascii_lowercase() { acc + 1 } else { acc })).sum();
+
+        println!("nb_of_keys = {}", nb_of_keys);
+
+        let mut paths = vec![Path::new(vault.entrance)];
+
+        let mut step = 0;
+        loop {
+            step += 1;
+            let mut new_paths: Vec<Path> = Vec::new();
+
+            //println!("{:?}", paths);
+
+            for i in (0 .. paths.len()).rev() {
+                let mut path = &mut paths[i];
+
+                let to_visit = path.to_visit.clone();
+                path.to_visit.clear();
+
+                let visited = path.visited.clone();
+                path.visited.clear();
+
+                for pos in to_visit {
+                    path.visited.insert(pos);
+                    for pos_d in &[(-1, 0), (0, 1), (1, 0), (0, -1)] {
+                        let adjacent = (pos.0 + pos_d.0, pos.1 + pos_d.1);
+                        if adjacent.0 >= 0 && adjacent.0 < vault.tunnels.len() as i32 && adjacent.1 >= 0 && adjacent.1 < vault.tunnels[0].len() as i32 && !visited.contains(&adjacent) {
+                            let c = vault.tunnels[adjacent.0 as usize][adjacent.1 as usize];
+
+                            if c.is_ascii_lowercase() && !path.keys.contains(&c) {
+                                if path.keys.len() + 1 == nb_of_keys {
+                                    return step;
+                                }
+
+                                let mut new_path = Path { to_visit: vec![adjacent], visited: HashSet::new(), keys: path.keys.clone() };
+                                new_path.keys.push(c);
+                                new_paths.push(new_path);
+                            }
+                            // Simple floor or a door or a owned key.
+                            else if c == FLOOR_SYMBOL || c == START_SYMBOL || c.is_ascii_lowercase() || c.is_ascii_uppercase() && path.keys.contains(&c.to_ascii_lowercase()) {
+                                path.to_visit.push(adjacent);
+                            }
+                        }
+                    }
+                }
+
+                if path.to_visit.len() == 0 {
+                    paths.remove(i);
+                }
+            }
+
+            paths.append(&mut new_paths);
+        }
+    }
 }
-*/
 
 pub fn nb_steps_to_collect_all_key(vault: &Vault) -> u32 {
-    42
+    v2::nb_steps_to_collect_all_key(vault)
 }
 
 #[cfg(test)]
@@ -149,8 +224,11 @@ mod tests {
              #########";
 
         let vault = Vault::parse(input);
-        let steps = nb_steps_to_collect_all_key(&vault);
-        println!("Steps: {}", steps);
+
+        let steps_v1 = v1::nb_steps_to_collect_all_key(&vault);
+        let steps_v2 = v2::nb_steps_to_collect_all_key(&vault);
+
+        println!("Steps: {}", steps_v1);
     }
 
     #[test]
@@ -163,8 +241,13 @@ mod tests {
              ########################";
 
         let vault = Vault::parse(input);
-        let steps = nb_steps_to_collect_all_key(&vault);
-        println!("Steps: {}", steps);
+
+        let steps_v1 = v1::nb_steps_to_collect_all_key(&vault);
+        let steps_v2 = v2::nb_steps_to_collect_all_key(&vault);
+
+        assert_eq!(steps_v1, steps_v2);
+
+        println!("Steps: {}", steps_v1);
     }
 
     #[test]
@@ -177,26 +260,36 @@ mod tests {
              ########################";
 
         let vault = Vault::parse(input);
-        let steps = nb_steps_to_collect_all_key(&vault);
-        println!("Steps: {}", steps);
+
+        let steps_v1 = v1::nb_steps_to_collect_all_key(&vault);
+        let steps_v2 = v2::nb_steps_to_collect_all_key(&vault);
+
+        assert_eq!(steps_v1, steps_v2);
+
+        println!("Steps: {}", steps_v1);
     }
 
     #[test]
     fn part1_sample4() {
         let input =
             "#################
-             #..G..c...e..H..#
+             #i.G..c...e..H.p#
              ########.########
-             #..A..b...f..D..#
+             #j.A..b...f..D.o#
              ########@########
-             #..E..a...g..B..#
+             #k.E..a...g..B.n#
              ########.########
-             #..F..d...h..C..#
+             #l.F..d...h..C.m#
              #################";
 
         let vault = Vault::parse(input);
-        let steps = nb_steps_to_collect_all_key(&vault);
-        println!("Steps: {}", steps);
+
+        //let steps_v1 = v1::nb_steps_to_collect_all_key(&vault);
+        //let steps_v2 = v2::nb_steps_to_collect_all_key(&vault);
+
+        //assert_eq!(steps_v1, steps_v2);
+
+        //println!("Steps: {}", steps_v2);
     }
 
     #[test]
@@ -210,7 +303,12 @@ mod tests {
              ########################";
 
         let vault = Vault::parse(input);
-        let steps = nb_steps_to_collect_all_key(&vault);
-        println!("Steps: {}", steps);
+
+        let steps_v1 = v1::nb_steps_to_collect_all_key(&vault);
+        let steps_v2 = v2::nb_steps_to_collect_all_key(&vault);
+
+        assert_eq!(steps_v1, steps_v2);
+
+        println!("Steps: {}", steps_v1);
     }
 }
\ No newline at end of file
diff --git a/src/main.rs b/src/main.rs
index f249fb7..ef4a7a7 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -127,8 +127,8 @@ fn day16() -> String {
     let signal_raw = fs::read_to_string("data/day16.input").unwrap();
     let signal = day16::parse(&signal_raw);
     let output_part_1 = day16::fft(&signal, &[0, 1, 0, -1], 100, 0, 8, 1);
-    //let output_part_2 = day16::part2(&signal);
-    format!("part1: {}, part2: {}", day16::digits_as_string(&output_part_1), /*day16::digits_as_string(&output_part_2)*/ "<skipped: take too long>")
+    // let output_part_2 = day16::part2(&signal);
+    format!("part1: {}, part2: {}", day16::digits_as_string(&output_part_1), /*day16::digits_as_string(&output_part_2)*/ "<skipped: take too long ~ 1 min>")
 }
 
 fn day17() -> String {
-- 
2.45.2