diff options
Diffstat (limited to 'aoc22/src')
-rw-r--r-- | aoc22/src/main.rs | 198 |
1 files changed, 0 insertions, 198 deletions
diff --git a/aoc22/src/main.rs b/aoc22/src/main.rs deleted file mode 100644 index bd374d5..0000000 --- a/aoc22/src/main.rs +++ /dev/null @@ -1,198 +0,0 @@ -extern crate regex; - -use std::io::BufReader; -use std::io::prelude::*; -use std::fs::File; -use std::collections::HashMap; -use std::collections::HashSet; - -use regex::Regex; - -use std::str::FromStr; - -#[derive(Debug, Clone, Copy, Hash, PartialEq, Eq)] -struct Node { - x: i8, - y: i8, - size: i16, - used: i16, - avail: i16, - blocker: bool -} - -impl FromStr for Node { - type Err = String; - - fn from_str(s: &str) -> Result<Self, Self::Err> { - let reg = Regex::new(r"/dev/grid/node-x(\d+)-y(\d+) +(\d+)T +(\d+)T +(\d+)T +(\d+)%").unwrap(); - let cap = match reg.captures(s) { - Some(cap) => cap, - None => return Err("Does not match regex".to_string()) - }; - Ok(Node { - x: cap.at(1).unwrap().parse().unwrap(), - y: cap.at(2).unwrap().parse().unwrap(), - size: cap.at(3).unwrap().parse().unwrap(), - used: cap.at(4).unwrap().parse().unwrap(), - avail: cap.at(5).unwrap().parse().unwrap(), - blocker: false - }) - } -} - -impl Node { - fn is_viable_pair(&self, other: &Node) -> bool { - (self.x != other.x || self.y != other.y) && self.used > 0 && self.used <= other.avail - } - - fn recalculate_avail(&mut self) { - self.avail = self.size - self.used; - debug_assert!(self.avail >= 0); - debug_assert!(self.used >= 0); - } -} - -#[derive(Clone, Hash, PartialEq, Eq)] -struct Grid { - nodes: Vec<Vec<Node>>, - goal_x: i8, - goal_y: i8 -} - -impl Grid { - fn new(nodes: Vec<Node>) -> Grid { - let mut grid_nodes = Vec::new(); - let mut next_col = Vec::new(); - - let mut current_x = 0; - - for node in nodes { - if current_x != node.x { - grid_nodes.push(next_col); - next_col = Vec::new(); - current_x += 1; - } - - next_col.push(node); - } - grid_nodes.push(next_col); - grid_nodes = Grid::normalize(grid_nodes); - - Grid { - nodes: grid_nodes, - goal_x: current_x, - goal_y: 0 - } - } - - fn normalize(mut nodes: Vec<Vec<Node>>) -> Vec<Vec<Node>> { - for x in 0..nodes.len() { - for y in 0..nodes[x].len() { - nodes[x][y].size = ((nodes[x][y].size + 50)/100) * 100; - nodes[x][y].used = ((nodes[x][y].used + 50)/100) * 100; - nodes[x][y].avail = ((nodes[x][y].avail + 50)/100) * 100; - } - } - nodes - } - - fn is_final(&self) -> bool { - self.goal_x == 0 && self.goal_y == 0 - } - - fn make_move(&self, x: i8, y: i8, dx: i8, dy: i8) -> Option<Grid> { - if x+dx < 0 || x+dx >= self.nodes.len() as i8 || y+dy < 0 || y+dy >= self.nodes[x as usize].len() as i8 { - return None; - } - if !self.nodes[x as usize][y as usize].is_viable_pair(&self.nodes[(x+dx) as usize][(y+dy) as usize]) { - return None; - } - - let mut new_grid = self.clone(); - new_grid.nodes[(x+dx) as usize][(y+dy) as usize].used += new_grid.nodes[x as usize][y as usize].used; - new_grid.nodes[(x+dx) as usize][(y+dy) as usize].recalculate_avail(); - new_grid.nodes[x as usize][y as usize].used = 0; - new_grid.nodes[x as usize][y as usize].recalculate_avail(); - - if new_grid.goal_x == x && new_grid.goal_y == y { - new_grid.goal_x = x+dx; - new_grid.goal_y = y+dy; - } - - Some(new_grid) - } - - fn available_moves(&self) -> Vec<Grid> { - let mut moves = Vec::with_capacity(4); - - for x in 0..self.nodes.len() as i8 { - for y in 0..self.nodes[x as usize].len() as i8 { - match self.make_move(x, y, -1, 0) { - Some(grid) => { moves.push(grid); }, - None => {} - }; - match self.make_move(x, y, 0, -1) { - Some(grid) => { moves.push(grid); }, - None => {} - }; - match self.make_move(x, y, 1, 0) { - Some(grid) => { moves.push(grid); }, - None => {} - }; - match self.make_move(x, y, 0, 1) { - Some(grid) => { moves.push(grid); }, - None => {} - }; - } - } - - moves - } -} - - -fn main() { - let nodes = read_input(); - - let initial = Grid::new(nodes); - println!("Initial grid has {} possible moves", initial.available_moves().len()); - - let mut explored: HashSet<Grid> = HashSet::new(); - let mut frontier: HashMap<Grid, u32> = HashMap::new(); - frontier.insert(initial, 0); - let mut found_final = false; - - while !found_final { - let (best_frontier, moves) = find_best_frontiers(&frontier); - - let new_states = best_frontier.available_moves(); - found_final = new_states.iter().any(|ref s| s.is_final()); - - for state in new_states { - if !(explored.contains(&state) || frontier.contains_key(&state)) { - frontier.insert(state, moves+1); - } - } - - frontier.remove(&best_frontier); - explored.insert(best_frontier); - } - - let (final_frontier, moves) = frontier.iter().find(|&(s, _)| s.is_final()).unwrap(); - println!("It took {} moves to get the data", moves); -} - -fn read_input() -> Vec<Node> { - let file = BufReader::new(File::open("input.txt").unwrap()); - - file.lines() - .skip(2) - .filter_map(|line| Node::from_str(line.unwrap().as_ref()).ok()) - .collect() -} - -fn find_best_frontiers(frontier: &HashMap<Grid, u32>) -> (Grid, u32) { - frontier.iter().min_by_key(|&(ref grid, &moves)| { - grid.goal_x as u32 + grid.goal_y as u32 + moves - }).map(|(&ref grid, &moves)| (grid.clone(), moves.clone())).unwrap() -} |