diff options
Diffstat (limited to '2018')
| -rw-r--r-- | 2018/input/15.txt | 32 | ||||
| -rw-r--r-- | 2018/src/day15.rs | 372 | ||||
| -rw-r--r-- | 2018/src/main.rs | 6 |
3 files changed, 408 insertions, 2 deletions
diff --git a/2018/input/15.txt b/2018/input/15.txt new file mode 100644 index 0000000..742953f --- /dev/null +++ b/2018/input/15.txt @@ -0,0 +1,32 @@ +################################ +#################..############# +#################.############## +#################.####..######## +############G..G...###..######## +##########...G...........####### +##########.#.......#.G########## +########...#.....#...G..######## +#######G.###............G####### +###########..G..#.......######## +####..#####............######### +###.G.###.......G.....G.######## +###..#####....#####.......###### +####..#####..#######........E..# +#.##..####..#########.........E# +#....###.GG.#########........### +##....#.G...#########.......#### +#....G...G..#########......##### +#..........G#########.....###### +#.....G......#######......###### +#........##...#####.......###### +#G###...##............#....##### +#..#######................E##### +#.########...............####### +#..#######..............######## +#####..#....E...##.......####### +#####.G#.......#.E..#EE.######## +#####...E....#....#..########### +#######.......E....E.########### +#######.###....###.....######### +#######.####.######.....######## +################################ diff --git a/2018/src/day15.rs b/2018/src/day15.rs new file mode 100644 index 0000000..29ec1a2 --- /dev/null +++ b/2018/src/day15.rs @@ -0,0 +1,372 @@ +use std::io; +use std::io::BufRead; +use std::cmp::Ordering; +use std::collections::BinaryHeap; + +const DEBUG_MODE: bool = false; + +macro_rules! debug { + ( $stmt:stmt ) => { + if DEBUG_MODE { + $stmt + } + } +} + +macro_rules! d_println { + ( $($tt:tt)* ) => { + debug!(println!($($tt)*)); + } +} + +// Stolen from day 7 +#[derive(PartialEq, Eq)] +struct Decreasing<T>(T); + +impl<T: PartialOrd> PartialOrd for Decreasing<T> { + fn partial_cmp(&self, other: &Self) -> Option<Ordering> { + other.0.partial_cmp(&self.0) + } +} + +impl<T: Ord> Ord for Decreasing<T> { + fn cmp(&self, other: &Self) -> Ordering { + other.0.cmp(&self.0) + } +} + +type Position = (usize, usize); // (y, x) + +macro_rules! at { + ( ( $vec:expr ) [ $e:expr ] ) => {{ + let pos = $e; + &$vec[pos.0][pos.1] + }}; + + ( ( $vec:expr ) [ $e:expr ] = $val:expr ) => {{ + let pos = $e; + $vec[pos.0][pos.1] = $val; + }}; + + ( $vec:ident [ $e:expr ] ) => { at!(($vec)[$e]) }; + ( $vec:ident [ $e:expr ] = $val:expr ) => { at!(($vec)[$e] = $val) }; +} + +macro_rules! neighbours { + ( $point:expr, $w:expr, $h:expr ) => {{ + let point = $point; + let w: usize = $w; + let h: usize = $h; + (&[(-1, 0), (0, -1), (0, 1), (1, 0)]) + .iter() + .map(move |(dy, dx)| (point.0 as isize + dy, point.1 as isize + dx)) + .filter(move |&(y, x)| x >= 0 && x < w as isize && y >= 0 && y < h as isize) + .map(|(y, x)| (y as usize, x as usize)) + }} +} + +fn make_grid<T: Copy>(w: usize, h: usize, val: T) -> Vec<Vec<T>> { + std::iter::repeat(vec![val; w]).take(h).collect() +} + +#[derive(Clone)] +enum Cell { + Wall, + Empty, + Entity(bool, i16), +} + +impl Cell { + fn from(c: char) -> Self { + match c { + '#' => Cell::Wall, + '.' => Cell::Empty, + 'E' => Cell::Entity(true, 200), + 'G' => Cell::Entity(false, 200), + _ => unreachable!(), + } + } + + fn is_entity(&self) -> bool { + match self { + Cell::Entity(_, _) => true, + _ => false, + } + } + + fn is_entity_of(&self, typ: bool) -> bool { + match self { + &Cell::Entity(t, _) => t == typ, + _ => false, + } + } + + fn is_empty(&self) -> bool { + match self { + Cell::Empty => true, + _ => false, + } + } + + fn to_entity(&self) -> (bool, i16) { + match self { + &Cell::Entity(typ, hp) => (typ, hp), + _ => panic!("Cell::to_entity called on a non-entity") + } + } +} + +struct GridRef<'a> { + grid: &'a Vec<Vec<Cell>>, + w: usize, + h: usize, +} + +struct DistMap { + dist: Vec<Vec<i32>> +} + +impl<'a> GridRef<'a> { + fn new(grid: &'a Vec<Vec<Cell>>) -> Self { + let w = grid[0].len(); + let h = grid.len(); + + GridRef { grid, w, h } + } + + fn can_attack(&self, pos: Position, owntype: bool) -> Vec<Position> { + neighbours!(pos, self.w, self.h).filter(|&p| at!((self.grid)[p]).is_entity_of(!owntype)).collect() + } + + fn dist_flood(&self, origin: Position) -> DistMap { + let mut dm = DistMap { dist: make_grid(self.w, self.h, -1) }; + + at!((dm.dist)[origin] = 0); + + let mut qu = BinaryHeap::new(); + qu.push((Decreasing(0), origin)); + + let mut seen = make_grid(self.w, self.h, false); + + while qu.len() > 0 { + let (Decreasing(d), pt) = match qu.pop() { + Some(item) => item, + None => unreachable!(), + }; + + if *at!(seen[pt]) { + continue; + } + at!(seen[pt] = true); + + at!((dm.dist)[pt] = d); + + for neighbour in neighbours!(pt, self.w, self.h) { + if at!((self.grid)[neighbour]).is_empty() { + qu.push((Decreasing(d + 1), neighbour)); + } + } + } + + dm + } +} + +impl DistMap { + fn dist_to(&self, target: Position) -> Option<i32> { + match *at!((self.dist)[target]) { + -1 => None, + d => Some(d), + } + } +} + +fn print_grid(grid: &Vec<Vec<Cell>>) { + for row in grid { + let mut entities = Vec::new(); + + for cell in row { + match cell { + &Cell::Empty => print!("."), + &Cell::Wall => print!("#"), + &Cell::Entity(typ, hp) => { + let typchar = if typ { 'E' } else { 'G' }; + entities.push((typchar, hp)); + print!("{}", typchar); + } + } + } + + if entities.len() > 0 { + for (i, (typchar, hp)) in entities.iter().enumerate() { + if i == 0 { + print!(" "); + } else { + print!(", "); + } + print!("{}({})", typchar, hp); + } + } + + println!(""); + } + + println!(""); +} + +fn remove_vec_mask<T>(vec: &mut Vec<T>, mask: &[bool]) { + let len = vec.len(); + for i in 0..len { + let j = len - 1 - i; + if mask[j] { + vec.swap_remove(j); + } + } +} + +fn simulation(mut grid: Vec<Vec<Cell>>, elf_attack: i16) -> (i32, bool) { + let mut entities: Vec<Position> = grid + .iter() + .enumerate() + .map(|(y, row)| + row.iter() + .enumerate() + .filter(|(_, cell)| cell.is_entity()) + .map(move |(x, _)| (y, x))) + .flatten() + .collect(); + + let mut num_left = entities.iter().fold((0, 0), |(nf, nt), &pos| { + match at!(grid[pos]) { + &Cell::Entity(true, _) => (nf, nt + 1), + &Cell::Entity(false, _) => (nf + 1, nt), + _ => (nf, nt) + } + }); + + let initial_elves = num_left.1; + + let mut last_completed = 0; + + 'outer: for round in 1.. { + d_println!("=== ROUND {} ===", round); + + let mut toremove = vec![false; entities.len()]; + + for i in 0..entities.len() { + if toremove[i] { + continue; + } + + if num_left.0 == 0 || num_left.1 == 0 { + d_println!("No more entities of one of the types, combat ended"); + break 'outer; + } + + let entpos = entities[i]; + let entity = at!(grid[entpos]).to_entity(); + + d_println!("- entity at ({}, {}): {}", entpos.0, entpos.1, if entity.0 { "Elf" } else { "Goblin" }); + + let gr = GridRef::new(&grid); + + if gr.can_attack(entpos, entity.0).len() == 0 { + let distmap = gr.dist_flood(entpos); + + let mut targets: Vec<Position> = entities + .iter() + .filter(|&&pos| at!(grid[pos]).is_entity_of(!entity.0)) + .map(|&pos| neighbours!(pos, gr.w, gr.h).filter(|&pos2| at!(grid[pos2]).is_empty())) + .flatten() + .collect(); + targets.sort(); + + d_println!(" can't attack, moving; targets {:?}", targets.iter().map(|&target| (target, distmap.dist_to(target))).collect::<Vec<_>>()); + + let target = match targets + .iter() + .filter(|&&target| distmap.dist_to(target).is_some()) + .min_by_key(|&&target| distmap.dist_to(target).unwrap()) { + Some(&target) => target, + None => continue, + }; + + d_println!(" selected target ({}, {})", target.0, target.1); + + let distmap2 = gr.dist_flood(target); + let nextpos = neighbours!(entpos, gr.w, gr.h) + .filter(|&pos| distmap2.dist_to(pos).is_some()) + .min_by_key(|&pos| distmap2.dist_to(pos).unwrap()) + .unwrap(); + + d_println!(" nextpos=({}, {})", nextpos.0, nextpos.1); + + at!(grid[nextpos] = (*at!(grid[entpos])).clone()); + at!(grid[entpos] = Cell::Empty); + entities[i] = nextpos; + } + + let entpos = entities[i]; + let gr = GridRef::new(&grid); + + d_println!(" now at ({}, {})", entpos.0, entpos.1); + + let targets = gr.can_attack(entpos, entity.0); + if targets.len() > 0 { + let target = targets.iter().min_by_key(|&p| at!(grid[p]).to_entity().1).unwrap(); + let other = at!(grid[target]).to_entity(); + + d_println!(" attack! target=({}, {}), other type {}", target.0, target.1, if other.0 { "Elf" } else { "Goblin" }); + + let attack_power = if entity.0 { elf_attack } else { 3 }; + + if other.1 - attack_power <= 0 { + d_println!(" other died"); + + if other.0 { + num_left.1 -= 1; + } else { + num_left.0 -= 1; + } + at!(grid[target] = Cell::Empty); + + for j in 0..entities.len() { + if entities[j] == *target { + toremove[j] = true; + d_println!(" removing entity index {}", j); + } + } + } else { + at!(grid[target] = Cell::Entity(other.0, other.1 - attack_power)); + } + } + } + + remove_vec_mask(&mut entities, &toremove); + + last_completed = round; + + entities.sort(); + + debug!(print_grid(&grid)); + } + + let sum_remaining: i32 = entities.iter().map(|&pos| match at!(grid[pos]) { + &Cell::Entity(_, hp) => hp as i32, + _ => 0, + }).sum(); + + let score = last_completed * sum_remaining; + + (score, num_left.1 == initial_elves) +} + +pub fn main<T: BufRead>(reader: T) -> io::Result<(String, String)> { + let grid: Vec<Vec<Cell>> = reader.lines().map(|l| l.unwrap().chars().map(|c| Cell::from(c)).collect()).collect(); + + let part1 = simulation(grid.clone(), 3).0; + + let part2 = (4..).map(|ap| simulation(grid.clone(), ap)).find(|&(_, win)| win).unwrap().0; + + Ok((part1.to_string(), part2.to_string())) +} diff --git a/2018/src/main.rs b/2018/src/main.rs index 3e44615..6154c99 100644 --- a/2018/src/main.rs +++ b/2018/src/main.rs @@ -4,6 +4,7 @@ use std::fs::File; use std::process::exit; use argparse::{ArgumentParser, StoreTrue, Store}; +mod benchmark; mod day1; mod day2; mod day3; @@ -18,9 +19,9 @@ mod day11; mod day12; mod day13; mod day14; -mod benchmark; +mod day15; -static NUM_DAYS: i32 = 14; +static NUM_DAYS: i32 = 15; fn day_switch<T: BufRead>(day: i32, reader: T) -> io::Result<(String, String)> { match day { @@ -38,6 +39,7 @@ fn day_switch<T: BufRead>(day: i32, reader: T) -> io::Result<(String, String)> { 12 => day12::main(reader), 13 => day13::main(reader), 14 => day14::main(reader), + 15 => day15::main(reader), _ => Err(Error::new(ErrorKind::Other, "Invalid day")) } } |