From a641af88aa9a8234197e4163524df326e205349c Mon Sep 17 00:00:00 2001
From: Justin Worthe <justin.worthe@gmail.com>
Date: Sat, 24 Dec 2016 10:32:40 +0200
Subject: AOC24

---
 aoc24/src/main.rs | 135 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 135 insertions(+)
 create mode 100644 aoc24/src/main.rs

(limited to 'aoc24/src/main.rs')

diff --git a/aoc24/src/main.rs b/aoc24/src/main.rs
new file mode 100644
index 0000000..c4d620e
--- /dev/null
+++ b/aoc24/src/main.rs
@@ -0,0 +1,135 @@
+use std::io::BufReader;
+use std::io::BufRead;
+use std::fs::File;
+use std::collections::HashMap;
+
+struct Map {
+    walls: Vec<Vec<bool>>,
+    destinations: Vec<(usize, usize)>,
+    start: (usize, usize)
+}
+
+impl Map {
+    fn new(input: &[String]) -> Map {
+        let mut walls = Vec::with_capacity(input.len());
+        let mut start = (0, 0);
+        let mut destinations = Vec::new();
+
+        let mut y = 0;
+        
+        for line in input {
+            let mut x = 0;
+            let mut wall_row = Vec::with_capacity(line.len());
+            for c in line.chars() {
+                wall_row.push(c == '#');
+                if c == '0' {
+                    start = (y, x);
+                }
+                else if c.is_numeric() {
+                    destinations.push((y, x));
+                }
+                
+                x += 1;
+            }
+
+            walls.push(wall_row);
+            y += 1;
+        }
+
+        Map {
+            walls: walls,
+            destinations: destinations,
+            start: start
+        }
+    }
+
+    fn is_valid_position(&self, y: i32, x: i32) -> bool {
+        y > 0 &&
+            x > 0 &&
+            (y as usize) < self.walls.len() &&
+            (x as usize) < self.walls[y as usize].len() &&
+            !self.walls[y as usize][x as usize]
+    }
+}
+
+#[derive(Clone, Hash, PartialEq, Eq)]
+struct State {
+    robot_location: (usize, usize),
+    destinations_hit: Vec<bool>
+}
+
+impl State {
+    fn new(map: &Map) -> State {
+        State {
+            robot_location: map.start,
+            destinations_hit: map.destinations.iter().map(|_| false).collect()
+        }
+    }
+
+    fn next_state(&self, movement: (i32, i32), map: &Map) -> Option<State> {
+        let (y, x) = self.robot_location;
+        let (dy, dx) = movement;
+        let y2 = y as i32 + dy;
+        let x2 = x as i32 + dx;
+
+        if !map.is_valid_position(y2, x2) {
+            return None;
+        }
+
+        let y2 = y2 as usize;
+        let x2 = x2 as usize;
+
+        Some(State {
+            robot_location: (y2, x2),
+            destinations_hit: self.destinations_hit.iter()
+                .zip(map.destinations.iter())
+                .map(|(&hit, &(dest_y, dest_x))| hit || (dest_y == y2 && dest_x == x2))
+                .collect()
+        })
+    }
+    
+    fn next_states(&self, map: &Map) -> Vec<State> {
+        [(-1, 0), (1, 0), (0, -1), (0, 1)].iter()
+            .filter_map(|&movement| self.next_state(movement, &map))
+            .collect()
+    }
+
+    fn is_complete(&self, map: &Map) -> bool {
+        self.destinations_hit.iter().all(|&x| x) && self.robot_location == map.start
+    }
+}
+
+fn main() {
+    let map = Map::new(&read_file());
+    let initial = State::new(&map);
+
+    let mut states = HashMap::new();
+    states.insert(initial, 0);
+
+    let mut moves = 0;
+    
+    while !states.iter().any(|(&ref s, _)| s.is_complete(&map)) {
+        let new_states = states.iter()
+            .filter(|&(_, &m)| m == moves)
+            .flat_map(|(&ref s, _)| s.next_states(&map))
+            .collect::<Vec<_>>();
+
+        moves += 1;
+        
+        for state in new_states {
+            if !states.contains_key(&state) {
+                states.insert(state, moves);
+            }
+        }
+    }
+
+    println!("Final state found in {} moves", moves);
+}
+
+fn read_file() -> Vec<String> {
+    let file = BufReader::new(File::open("input.txt").unwrap());
+    file.lines()
+        .map(|line| line.unwrap())
+        .filter(|line| line.len() > 0)
+        .collect()
+}
-- 
cgit v1.2.3