AOC11
authorJustin Worthe <justin.worthe@gmail.com>
Sun, 11 Dec 2016 06:34:00 +0000 (08:34 +0200)
committerJustin Worthe <justin.worthe@gmail.com>
Sun, 11 Dec 2016 06:34:00 +0000 (08:34 +0200)
aoc11/Cargo.lock [new file with mode: 0644]
aoc11/Cargo.toml
aoc11/input.txt [new file with mode: 0644]
aoc11/src/main.rs

diff --git a/aoc11/Cargo.lock b/aoc11/Cargo.lock
new file mode 100644 (file)
index 0000000..b423029
--- /dev/null
@@ -0,0 +1,4 @@
+[root]
+name = "aoc11"
+version = "0.1.0"
+
index d24e75d..e0b3f68 100644 (file)
@@ -4,4 +4,4 @@ version = "0.1.0"
 authors = ["Justin Worthe <justin.worthe@gmail.com>"]
 
 [dependencies]
-regex = "0.1"
+
diff --git a/aoc11/input.txt b/aoc11/input.txt
new file mode 100644 (file)
index 0000000..d453804
--- /dev/null
@@ -0,0 +1,4 @@
+The first floor contains a strontium generator, a strontium-compatible microchip, a plutonium generator, and a plutonium-compatible microchip.
+The second floor contains a thulium generator, a ruthenium generator, a ruthenium-compatible microchip, a curium generator, and a curium-compatible microchip.
+The third floor contains a thulium-compatible microchip.
+The fourth floor contains nothing relevant.
index 7bd3f21..39a6e2f 100644 (file)
-extern crate regex;
-use regex::Regex;
 
-use std::io::BufReader;
-use std::io::prelude::*;
-use std::fs::File;
+use std::collections::HashMap;
 
-fn main() {
-    println!("Hello, world!");
+//const MICROS: usize = 2; //example
+const MICROS: usize = 7;
+
+#[derive(Debug, Clone, Copy, Hash, PartialEq, Eq)]
+struct State {
+    microchips: [[bool; MICROS]; 4],
+    generators: [[bool; MICROS]; 4],
+    elevator: usize
 }
 
-fn read_file() -> Vec<String> {
-    let file = BufReader::new(File::open("input.txt").unwrap());
-    file.lines()
-        .map(|line| line.unwrap().trim().to_string())
-        .filter(|line| line.len() > 0)
-        .collect()
+impl State {
+    fn is_final(&self) -> bool {
+        let floor = 3;
+        
+        for i in 0..MICROS {
+            if !self.microchips[floor][i] || !self.generators[floor][i] {
+                return false;
+            }
+        }
+        true
+    }
+
+    fn is_safe(&self) -> bool {
+        for floor in 0..4 {
+            for i in 0..MICROS {
+                for j in 0..MICROS {
+                    //need to be on same floor, if any other micro is there
+                    if self.generators[floor][j] && !self.generators[floor][i] && self.microchips[floor][i] {
+                        return false;
+                    }
+                }
+            }
+        }
+        true
+    }
+
+    fn valid_moves(&self) -> Vec<State> {
+        let mut moves = Vec::new();
+
+        let mut new_floors = Vec::new();
+        if self.elevator > 0 {
+            new_floors.push(self.elevator-1);
+        }
+        if self.elevator < 3 {
+            new_floors.push(self.elevator+1);
+        }
+        for &new_floor in new_floors.iter() {
+
+            //items to take can be: one micro, one generator, two micros, two generator, one of each
+
+            //one micro
+            for i in 0..MICROS {
+                if self.microchips[self.elevator][i] {
+                    moves.push(self.move_micro(i, self.elevator, new_floor));
+                }
+            }
+            //one generator
+            for i in 0..MICROS {
+                if self.generators[self.elevator][i] {
+                    moves.push(self.move_generator(i, self.elevator, new_floor));
+                }
+            }
+            //two micros
+            for i in 0..MICROS {
+                for j in i+1..MICROS {
+                    if self.microchips[self.elevator][i] && self.microchips[self.elevator][j] {
+                        moves.push(self.move_micro(i, self.elevator, new_floor).move_micro(j, self.elevator, new_floor));
+                    }
+                }
+            }
+            //two generators
+            for i in 0..MICROS {
+                for j in i+1..MICROS {
+                    if self.generators[self.elevator][i] && self.generators[self.elevator][j] {
+                        moves.push(self.move_generator(i, self.elevator, new_floor).move_generator(j, self.elevator, new_floor));
+                    }
+                }
+            }
+            //one of each
+            for i in 0..MICROS {
+                for j in 0..MICROS {
+                    if self.microchips[self.elevator][i] && self.generators[self.elevator][j] {
+                        moves.push(self.move_micro(i, self.elevator, new_floor).move_generator(j, self.elevator, new_floor));
+                    }
+                }
+            }
+        }
+
+        moves.iter().filter(|x| x.is_safe()).cloned().collect()
+    }
+
+    fn move_micro(&self, micro: usize, floor: usize, new_floor: usize) -> State {
+        let mut new_state = self.clone();
+        new_state.microchips[floor][micro] = false;
+        new_state.microchips[new_floor][micro] = true;
+        new_state.elevator = new_floor;
+        new_state
+    }
+    fn move_generator(&self, gen: usize, floor: usize, new_floor: usize) -> State {
+        let mut new_state = self.clone();
+        new_state.generators[floor][gen] = false;
+        new_state.generators[new_floor][gen] = true;
+        new_state.elevator = new_floor;
+        new_state
+    }
+}
+
+fn main() {
+    //Stronium, plutonium, thulium, ruthenium, curium, electrium, dilithium
+    let initial = State {
+        microchips:
+        [[true, true, false, false, false, true, true],
+         [false, false, false, true, true, false, false],
+         [false, false, true, false, false, false, false],
+         [false, false, false, false, false, false, false]],
+        generators:
+        [[true, true, false, false, false, true, true],
+         [false, false, true, true, true, false, false],
+         [false, false, false, false, false, false, false],
+         [false, false, false, false, false, false, false]],
+        elevator: 0
+    };
+
+    /*
+    //example
+    let initial = State {
+        microchips:
+        [[true, true],
+         [false, false],
+         [false, false],
+         [false, false]],
+        generators:
+        [[false, false],
+         [true, false],
+         [false, true],
+         [false, false]],
+        elevator: 0
+    };
+    */
+    
+    let mut states: HashMap<State, u32> = HashMap::new();
+    states.insert(initial, 0);
+
+    let mut moves = 0;
+    loop {
+        if states.iter().any(|(state, _)| state.is_final()) {
+            break;
+        }
+
+        let new_states: Vec<State> = states.iter().filter(|&(_, &x)| x == moves).flat_map(|(state, _)| state.valid_moves()).collect();
+
+        moves += 1;
+
+        for state in new_states {
+            if !states.contains_key(&state) {
+                states.insert(state, moves);
+            }
+        }
+    }
+    
+    
+    println!("Moves required: {}", moves);
 }