From 2f2c1fe8e23e353ac97e1c7d250f587dbe1ba1c2 Mon Sep 17 00:00:00 2001 From: Justin Worthe Date: Thu, 22 Dec 2016 15:51:41 +0200 Subject: AOC22 work in progress Has crazy hack optimization to work for the data set, assuming all data is about moving the 'gap' around. It hasn't run to completion yet. --- aoc22/src/main.rs | 212 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 212 insertions(+) create mode 100644 aoc22/src/main.rs (limited to 'aoc22/src') diff --git a/aoc22/src/main.rs b/aoc22/src/main.rs new file mode 100644 index 0000000..c07d628 --- /dev/null +++ b/aoc22/src/main.rs @@ -0,0 +1,212 @@ +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 { + 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>, + goal_x: i8, + goal_y: i8 +} + +impl Grid { + fn new(nodes: Vec) -> 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); + + for x in 0..grid_nodes.len() { + for y in 0..grid_nodes[x].len() { + let mut is_blocker = true; + if x > 0 && grid_nodes[x-1][y].size >= grid_nodes[x][y].used { + is_blocker = false; + } + if x < grid_nodes.len()-1 && grid_nodes[x+1][y].size >= grid_nodes[x][y].used { + is_blocker = false; + } + if y > 0 && grid_nodes[x][y-1].size >= grid_nodes[x][y].used { + is_blocker = false; + } + if y < grid_nodes[x].len()-1 && grid_nodes[x][y+1].size >= grid_nodes[x][y].used { + is_blocker = false; + } + grid_nodes[x][y].blocker = is_blocker; + } + } + for x in 0..grid_nodes.len() { + for y in 0..grid_nodes[x].len() { + grid_nodes[x][y].size = if grid_nodes[x][y].blocker { 2 } else { 1 }; + grid_nodes[x][y].used = if grid_nodes[x][y].used > 0 { grid_nodes[x][y].size } else { 0 }; + grid_nodes[x][y].avail = grid_nodes[x][y].size - grid_nodes[x][y].used; + } + } + + Grid { + nodes: grid_nodes, + goal_x: current_x, + goal_y: 0 + } + } + + 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 { + 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 { + 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 = HashSet::new(); + let mut frontier: HashMap = 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 { + 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) { + 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() +} -- cgit v1.2.3