From a641af88aa9a8234197e4163524df326e205349c Mon Sep 17 00:00:00 2001 From: Justin Worthe Date: Sat, 24 Dec 2016 10:32:40 +0200 Subject: AOC24 --- aoc24/Cargo.lock | 4 ++ aoc24/Cargo.toml | 6 +++ aoc24/input.txt | 39 ++++++++++++++++ aoc24/src/main.rs | 135 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 184 insertions(+) create mode 100644 aoc24/Cargo.lock create mode 100644 aoc24/Cargo.toml create mode 100644 aoc24/input.txt create mode 100644 aoc24/src/main.rs (limited to 'aoc24') diff --git a/aoc24/Cargo.lock b/aoc24/Cargo.lock new file mode 100644 index 0000000..d8b394a --- /dev/null +++ b/aoc24/Cargo.lock @@ -0,0 +1,4 @@ +[root] +name = "aoc24" +version = "0.1.0" + diff --git a/aoc24/Cargo.toml b/aoc24/Cargo.toml new file mode 100644 index 0000000..26becbd --- /dev/null +++ b/aoc24/Cargo.toml @@ -0,0 +1,6 @@ +[package] +name = "aoc24" +version = "0.1.0" +authors = ["Justin Worthe "] + +[dependencies] diff --git a/aoc24/input.txt b/aoc24/input.txt new file mode 100644 index 0000000..cc45a4f --- /dev/null +++ b/aoc24/input.txt @@ -0,0 +1,39 @@ +####################################################################################################################################################################################### +#...........#.....#...........#.#.......#.....#.#...............#.....#.....#.......#.......#.......#.....................#.........#.....#...#3......#...#.#.............#.......#...# +#####.#.#.###.###.#####.#.#####.#.###.###.###.#.#.#.#.#.#.###.#.###.###.###.#.#######.#.#.#.###.###.#.#.#.#####.#.#.#####.###.#.#######.#############.#.#.#.#.#.#.###.#.#.#.#.###.#.#.# +#...#.#.#.#.....#.#...#...#.....#.....#.#...#.........#.....................#.....#...#...#.......#.....#.#.........#.#.#.#.#.......................#...#...#.#.#.#.....#.#.........#.# +#.#.#.#.#.#####.#.#.#.#.#.#.#.#.###.#.#.###.#.#.#.#.#.#########.#.###.###.#.#.###.###.#.#.#.#.###.#.#.#.#.#.#.#####.#.#.###.###.#######.#.#.#.###.#.###.#.#.#####.#####.#.#.###.#.#.#.# +#.#.#...#.....#.#.....#...#.#...#.#...#.......#...........#...#...#...#.#.....#.#...#...........#.#.......#...#...#.#.........#...#.......#.#...#.....#...#.......#.#.#.............#.# +#.#######.#.#.###.#.#.#####.#.#.#.#.###.#####.#.#.###.#.#.#.#.#.#.#.#.#.#.###.#.#.#.###.#######.#######.#.#.###.#.#.#.#.#.#.###.#.#.#.#.#.###.#.#####.#.#.#.#.#.#.#.#.#.###.#.#####.#.# +#.#...#.....#.......#.......#.#.......#...#.#.....#.#.#.#.#.#.......#...#.....#.#.#.#.#.........#...#...#...#.......#...#...#.....#.....#...#.........#...#.#...#...#...#.........#.#.# +#.#.#.#.###.###.#.#.#.###.###.#.#.###.#.#.#.#####.#.###.#.#####.#####.###.#.#.#.#.###.#.#.#.###.###.#.#.#.#.#.#####.#.###.#.#.###.#.#.#.#.###.###.#######.#.###.###.#.#######.#.#.#.#.# +#.#...#...#...............#...#...#...#.#.........#.#...#...#.#...#.#.....#...#.#...#.#.#...#.#.#.#.#.....#...#...#.......#.#...#.........#.#.....#.#...#.....#.#...#.#2#.....#.......# +#.#.#####.#########.#.###.#.#####.#.#.#.#######.#.###.#.#.#.#.###.#.#.###.#.###.#.#.#.#.#.###.###.#.#.#######.#.###.#.#.#.#.#.#.#.#####.###.#.###.#.#####.#.#.###.#.#.#.###.#.###.###.# +#...#...........#.....#.......#...#0..........#...#.....#.#...#.#...#.#.#...#.#.......#.........#...#.#...#.#.#.......#...#.#.........#.#.....................#.#.#.#.....#.#.....#...# +#.###.#.#.#.#.#.###.#.#.#.#.#.###.#.#.###.#.#.#.###.###.#.#####.#.#.#.#.###.#.#.###.#.#.###.###.#.#####.#.#.#.###.#.#######.#######.#.#.#.###.#.#.#.#.#.#######.#.#.#####.#.###.###.#.# +#...#...#...#.#...........#...#.#.....#...#...#.....#.#.............#...#.........#...#.....#...#.......#...#.#.............#.........#...#.#.....#.#.........#.............#...#.....# +#.#.#.###.#.###.#.#.#.###.#.###.#######.#.#.###.#.#.#.#.###.#.###.#.#.#.#.#####.#.#.#.#####.#.#####.#.#.#.#.###.###.#.###.###.###.#.#.#.###.#.#.###.#.#.###.#########.#####.#.#.#.##### +#.#...#.#.......#...#.....#.....#...#...#.....#...#...#.........#.....#.#.........#.....#.....#.........#...#.#.....#.#...#...#.#.#...#.#...#.........#.#...#.........#.#.......#.....# +#.#####.#.###.#.#.#.###.#.#.#.#.#.#.###.#.#.#.###.###.#.###.#.###.#.#.#.###.#.#####.###.#.#.#.#.#.#####.#.#.#.#.#.#.###.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.###.#.#.#.#.#.#.#.#.###.#.#.# +#.....#...#...........#...#...........#.#.....#...#.....#...#.#.#.#...#.....#...#...#...............#...#.........#...#.....#...#.#...#.#...#.....#.....#.....#...#.#...#...#.#.......# +###.###.#.#.#####.###.#####.#.###.#.#.#####.#.###.#.###.#.###.#.#.#.#.###.#.###.#.#.#.#.###.#.###.#.#.#.#.#.#.###.#.#.#.###.###.#.#.###.#########.#.#####.###########.#.###.###.#####.# +#...#1#...#...#.......#...#...#.#...#...#...........#.#.......#.......#.#.........#.#...#...#...............#...#.....#.#...#.#.....#.........#...#.....#.#...#...#.....#.#.#.#...#...# +#.###.###.#.#.#.#####.#.#.#.#.#.#.#####.#####.#.#####.#.#.#.#.###.#.#.#.###.#.###.#.###.#.#.#####.#.#.#####.#.#.###.#.###.#.#.#.#.#.#.#####.#.#.#.#.###.#.#.###.#.#.#.#.#.#.#.###.#.#.# +#.....#.#.#.#.........#.#.#.....#.....#...#.....#...#.............#...#...#.....#...#.......#.......#.#.....#...#...#.#...#.....#.#...#.....#.#.#.#.#.#.#.......#...........#.#5#.....# +#.###.#.#.###.###.###.#.#####.#.#.###.###.#.###.#############.#######.#.###.#.###.#.#####.#.#.#.#####.#.#.#####.#.#.#.#.#.#######.#.#.###########.#.#.#.#.#.#.#.#.#.###.#.#.#.#.#.###.# +#.....#...#...................#.......#...#...#.#.....#.............#.....#...#.....#.......#.#.#.........#.........#.......#.......#...#.........#.#...#...#.....#.#.....#...#...#.#.# +#.###.###.###########.###.#####.#####.###.#.#.#.#.#.#.###.#.###.#.#######.#.#.#.#.#.#.###.#.#.#####.#.#.#.#######.#.###.#.#.###.#.#.#.###.#####.#####.#.#.#.#.###.#.###.###########.#.# +#.#.#.#...#...#.....#.....#.#.......#.....#.....#...........#.#...#.........#.#.#.#.....#.#.#...........#...#...#...#.......#...#.........#.....#.....#.....#.......#...#...#.#...#...# +#.#.#.#.#.#########.#.#.###.#.#.###.###.#.#.#.###.#####.#.#.#.#.#.#.#######.#.#.#######.#.###.#.###.###.#.###.#.#.#.#######.#######.#.#.#.#####.#.###.#.#####.#.###.#.#.###.#.#######.# +#.#...#...#.#...................#.#...#.#...#.......#.#...#.#...#.#.#.....#.#...#...#...#.#.............#.....#...........#.........#...#.#.#.....#.......#.......#.....#...#.#...#...# +###.#.#.#.#.#.#.###.#.###.#####.#.#####.#.#.###.#.#.#.#####.#.###.#####.#.#.#.#.#.#.#.###.#.#.#####.###.#.###.#####.#.#.#.#####.###.#.#.#.#.#.#######.###.#.#.#########.###.#.#######.# +#.....#...................#...#.#...#...#...........#.#.......#.#.....#.#.....#...........#.....#.........#.#...........#...#.....#...#.....#.............#.#.#.........#.#.#.#.......# +#.#.#.#.#.###.#.#.#.#.#########.###.#.#.#.#########.#.#.#.#.#.#.###########.#.#.###.###.###.#.#.#.#.#.###.#.###.#.###.#.###.###.#.###.#.#.#####.#.#.#######.#.#.###.###.#.#.#.###.##### +#...#.#.#....7#.#...#.#.........#.....#...#.#.......#.....#...........#.#...#.......#.#...#.#...#...........#...#.#...#.....#...#.#.#...........#...#.#...#...#4....#...#...#...#.....# +###.#.#.###.#####.#.#.#.#.#.#.#.#.#.#.###.#.###.#.###.#######.#.#.###.#.#####.#.#####.###.#.###.#.#.#.#.#####.###.#.###.#.#.#.#.###.#.#.###.#.#.###.#.###.#########.#.###.#.#.#.#.#.#.# +#.....#.#.#.......#.#.#.......#.#.#.............#...#.........#.......#.#.#...........#.....#.....#...#...#.#.....#...#.....#.#.#...#...#...#.....#...#...#.#...#...#.#.#.....#...#.#.# +#.###.#.#.#########.#.#.#.#######.#.#.#.#.###.###.#####.#.#.#.#.#.###.#.#.#.#.#####.#.#.###.#.#.#.#.###.###.###.#.#.#######.#.#.###.#####.#.#.###.#.#.#####.###.#.#.###.#.#########.### +#.......#...#...#...#...#.#...#...#.#.#...#.#...........#.........#...#.#.#.#.....#...#.....#.#.....#...#...#...#.#.#.#...#...#.#...#.....#...........#.#.........#.....#.#.#...#.....# +#####.###.#####.#.#####.#######.#.#.#.###.#.#######.###.#####.###.#.#.#.#.#.#####.#####.###.###.###.#.#.###.#.#.#.###.#.#.###.#.#.#####.#.###.#.#.#.###.#.#.#.#.#.###.###.#.#.###.#.#.# +#.....#.#.#.......#...#.#.#.....#.........#...#.....#6......#...#.#...........#.......#.............#...#...#...#...#.#...#...#...#.....#.........#.#...#.....#.#.#.......#...#.#.#...# +####################################################################################################################################################################################### 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>, + 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 +} + +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 { + 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 { + [(-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::>(); + + 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 { + 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