From 5dbe77f73ca88e179457d24ddae67d8c47157436 Mon Sep 17 00:00:00 2001 From: Justin Worthe Date: Sun, 11 Dec 2016 08:34:00 +0200 Subject: AOC11 --- aoc11/Cargo.lock | 4 ++ aoc11/Cargo.toml | 2 +- aoc11/input.txt | 4 ++ aoc11/src/main.rs | 174 ++++++++++++++++++++++++++++++++++++++++++++++++++---- 4 files changed, 170 insertions(+), 14 deletions(-) create mode 100644 aoc11/Cargo.lock create mode 100644 aoc11/input.txt diff --git a/aoc11/Cargo.lock b/aoc11/Cargo.lock new file mode 100644 index 0000000..b423029 --- /dev/null +++ b/aoc11/Cargo.lock @@ -0,0 +1,4 @@ +[root] +name = "aoc11" +version = "0.1.0" + diff --git a/aoc11/Cargo.toml b/aoc11/Cargo.toml index d24e75d..e0b3f68 100644 --- a/aoc11/Cargo.toml +++ b/aoc11/Cargo.toml @@ -4,4 +4,4 @@ version = "0.1.0" authors = ["Justin Worthe "] [dependencies] -regex = "0.1" + diff --git a/aoc11/input.txt b/aoc11/input.txt new file mode 100644 index 0000000..d453804 --- /dev/null +++ b/aoc11/input.txt @@ -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. diff --git a/aoc11/src/main.rs b/aoc11/src/main.rs index 7bd3f21..39a6e2f 100644 --- a/aoc11/src/main.rs +++ b/aoc11/src/main.rs @@ -1,18 +1,166 @@ -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 { - 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 { + 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 = HashMap::new(); + states.insert(initial, 0); + + let mut moves = 0; + loop { + if states.iter().any(|(state, _)| state.is_final()) { + break; + } + + let new_states: Vec = 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); } -- cgit v1.2.3