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