Advent of Code 2018/15

use std::io::prelude::*;
use std::io::BufReader;
use std::fs::File;

const FIELD_SIZE: usize = 32;

type BoolField = [[bool; FIELD_SIZE]; FIELD_SIZE];

#[derive(Debug,PartialEq,Eq,Clone,Copy)]
enum Faction {
  Elf,
  Goblin,
}

#[derive(Debug,Clone)]
struct Unit {
  faction: Faction,
  hp: i32,
  attack: i32,
  pos: (usize, usize), // (y, x)
}

fn neighbours(pos: (usize, usize)) -> [(usize, usize); 4] {
  [(pos.0, pos.1 + 1), (pos.0, pos.1 - 1), (pos.0 + 1, pos.1), (pos.0 - 1, pos.1)]
}

// Returns true if a fight happened.
fn fight(active: usize, units: &mut Vec<Unit>) -> bool {
  let faction = units[active].faction;
  let mut enemies = Vec::new();
  for &pos in &neighbours(units[active].pos) {
    for (j, u) in units.iter().enumerate() {
      if u.hp > 0 && u.faction != faction && u.pos == pos {
        enemies.push(j);
      }
    }
  }
  if let Some(enemy) = enemies.into_iter().min_by_key(|&j| (units[j].hp, units[j].pos)) {
    units[enemy].hp -= units[active].attack;
    true
  }
  else {
    false
  }
}

// Returns true if combat is done.
fn step(active: usize, walls: &BoolField, units: &mut Vec<Unit>) -> bool {

  if units[active].hp <= 0 {
    return false;
  }

  if fight(active, units) {
    return false;
  }

  let mut occupied = walls.clone();
  for u in units.iter() {
    if u.hp > 0 {
      occupied[u.pos.0][u.pos.1] = true;
    }
  }

  // Find all candidate target squares.
  let mut target_squares = Vec::new();
  let mut have_enemies = false;
  for u in units.iter() {
    if u.faction == units[active].faction || u.hp <= 0 {
      continue;
    }
    have_enemies = true;
    for (y, x) in &neighbours(u.pos) {
      if !occupied[*y][*x] {
        target_squares.push((*y, *x));
      }
    }
  }
  if !have_enemies {
    return true;
  }
  if target_squares.is_empty() {
    return false;
  }
  target_squares.sort();
  target_squares.dedup();

  // Find the distance from the active unit to each square until a target square is found.
  let mut distances = [[None; FIELD_SIZE]; FIELD_SIZE];
  distances[units[active].pos.0][units[active].pos.1] = Some(0);
  let mut prev_boundary = vec![units[active].pos];
  let mut new_boundary;
  let mut found_squares = Vec::new();
  let mut distance = 0;
  while !prev_boundary.is_empty() && found_squares.is_empty() {
    new_boundary = Vec::new();
    distance += 1;
    for pos in prev_boundary {
      for &pos2 in &neighbours(pos) {
        if !occupied[pos2.0][pos2.1] && distances[pos2.0][pos2.1].is_none() {
          distances[pos2.0][pos2.1] = Some(distance);
          new_boundary.push(pos2);
          if target_squares.contains(&pos2) {
            found_squares.push(pos2);
          }
        }
      }
    }
    prev_boundary = new_boundary;
  }
  if found_squares.is_empty() {
    return false;
  }
  let target_square = found_squares.into_iter().min().unwrap();

  // Go along all shortest paths to find the move square.
  prev_boundary = vec![target_square];
  while distance > 1 {
    new_boundary = Vec::new();
    distance -= 1;
    for pos in prev_boundary {
      for &pos2 in &neighbours(pos) {
        if distances[pos2.0][pos2.1] == Some(distance) {
          new_boundary.push(pos2);
        }
      }
    }
    prev_boundary = new_boundary;
  }
  units[active].pos = prev_boundary.into_iter().min().unwrap();

  fight(active, units);
  false
}

fn read_field() -> (BoolField, Vec<Unit>) {
  let file = File::open("i15").unwrap();
  let lines = BufReader::new(file).lines().map(|l| l.unwrap());

  let mut walls = [[false; FIELD_SIZE]; FIELD_SIZE];
  let mut units = Vec::new();

  for (y, line) in lines.enumerate() {
    for (x, c) in line.chars().enumerate() {
      match c {
        '#' => walls[y][x] = true,
        'E' => units.push(
            Unit {
              faction: Faction::Elf,
              hp: 200,
              attack: 3,
              pos: (y, x),
            }
          ),
        'G' => units.push(
            Unit {
              faction: Faction::Goblin,
              hp: 200,
              attack: 3,
              pos: (y, x),
            }
          ),
        '.' => {},
        _ => panic!("Bad input!"),
      }
    }
  }

  return (walls, units);
}

// Returns true if elves win without losses.
fn run_combat(elf_attack: i32, walls: BoolField, mut units: Vec<Unit>) -> bool {
  let num_elves = units.iter().filter(|u| u.faction == Faction::Elf).count();
  for u in &mut units {
    if u.faction == Faction::Elf {
      u.attack = elf_attack;
    }
  }
  let winners;
  let mut iteration = 0;
  'outer: loop {
    units.sort_by_key(|u| u.pos);
    for i in 0 .. units.len() {
      if step(i, &walls, &mut units) {
        winners = units[i].faction;
        break 'outer;
      }
    }
    units = units.into_iter().filter(|u| u.hp > 0).collect();
    iteration += 1;
  }
  units = units.into_iter().filter(|u| u.hp > 0).collect();
  let survivors = units.len();
  let score = iteration * units.iter().map(|u| u.hp).sum::<i32>();
  println!("Elf attack: {:?}", elf_attack);
  println!("{:?} victory!", winners);
  println!("{:?} survivors", survivors);
  println!("Score: {:?}", score);
  println!("--------------------");

  if winners == Faction::Elf && survivors == num_elves {
    true
  }
  else {
    false
  }
}

fn main() {
  let (walls, units) = read_field();
  for i in 3.. {
    if run_combat(i, walls.clone(), units.clone()) {
      break;
    }
  }
}