Day 15

God dammit this one wasn't fun. The amount of edge cases and arbitrary
rules made this more of a chore than a puzzle.

The code could probably be shorter, but any sane amount of code
structure and clarity demanded this size.

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"))
     }
 }