From ca19e1d4aac6d2da8dae9b60f5b13962b7aff0b8 Mon Sep 17 00:00:00 2001
From: tomsmeding <tom.smeding@gmail.com>
Date: Sat, 15 Dec 2018 19:38:16 +0100
Subject: 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.
---
2018/src/day15.rs | 372 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
2018/src/main.rs | 6 +-
2 files changed, 376 insertions(+), 2 deletions(-)
create mode 100644 2018/src/day15.rs
(limited to '2018/src')
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"))
}
}
--
cgit v1.2.3-70-g09d2