package Advent2018;

import util.AdventOfCode;
import util.Direction;
import util.Node;

import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.stream.Collectors;
import static java.util.Comparator.*;

public class Day15 extends AdventOfCode {

    private int[][] grid;           // ASCII grid of map for display/pathfinding
    private Unit[][] unitMap;       // lookup map for Elf/Goblin units
    private List<Unit> units;       // List of units
    private int rounds;             // current round number

    class Unit {
        Node position;
        boolean elf;            // true = Elf; false = Goblin
        boolean alive = true;
        int hitPoints = 200;
        int attackPower = 3;

        int getX() { return position.getX(); }
        int getY() { return position.getY(); }
        int getHitPoints() { return hitPoints; }
        boolean isAlive() { return alive; }
        boolean isElf() { return elf; }

        boolean turn() {
            if (alive) {
                List<Unit> enemies = getEnemies(this);
                if (enemies.size() == 0) return true;
                Unit enemy = getAdjacentEnemy(this);
                if (enemy == null) {
                    move(enemies);
                    enemy = getAdjacentEnemy(this);
                    if (enemy == null) return false;
                }
                attack(enemy);
            }
            return false;
        }

        void move(List<Unit> enemies) {
            Node m = bestMove(this, enemies);
            if (m != null) {
                grid[getX()][getY()] = '.';
                unitMap[getX()][getY()] = null;
                this.position = m;
                grid[getX()][getY()] = this.elf ? 'E' : 'G';
                unitMap[getX()][getY()] = this;
            }
        }

        void attack(Unit enemy) {
            enemy.hitPoints -= this.attackPower;
            if (enemy.hitPoints <= 0) {
                enemy.alive = false;
                unitMap[enemy.getX()][enemy.getY()] = null;
                grid[enemy.getX()][enemy.getY()] = '.';
            }
        }
    }

    public Day15(List<String> input) {
        super(input);
        title = "Beverage Bandits";
        part1Description = "Score after rounds complete: ";
        part2Description = "Score for first elf win: ";
    }

    // return a list of all enemies of unit n regardless of their position
    private List<Unit> getEnemies(Unit n) {
        return units.stream()
                .filter(x -> x.elf != n.elf)
                .filter(Unit::isAlive)
                .collect(Collectors.toList());
    }

    // return the position Node for the best move for unit u
    private Node bestMove(Unit u, List<Unit> enemies) {
        List<List<Node>> paths = new ArrayList<>();

        // find all paths to valid adjacent to enemy squares
        for (Unit enemy : enemies) {
            for (Node each : getAdjacent(enemy.position)) {
                List<Node> path = bfs(u.position, each);
                if (!path.isEmpty()) paths.add(path);
            }
        }

        if (paths.size() == 0) return null;

        // find minimum length of paths
        int min = paths.stream()
                .mapToInt(List::size)
                .min().orElse(0);

        if (min == 0) return null;

        // get all paths of the min length and get correct one
        Node target = paths.stream()
                .filter(x -> x.size() == min)
                .map(x -> x.get(x.size() - 1))
                .min(comparing(Node::getY).thenComparing(Node::getX))
                .get();

        // now find all paths from the found target square
        // going BACK to the adjacent open squares around the
        // moving unit
        paths = new ArrayList<>();
        List<Node> adj = getAdjacent(u.position);
        for (Node each : adj) {
            List<Node> path = bfs(target, each);
            if (!path.isEmpty()) paths.add(path);
        }

        // find min of shortest paths
        int min2 = paths.stream()
                .mapToInt(List::size)
                .min().getAsInt();

        // find best choice of shortest
        return paths.stream()
                .filter(x -> x.size() == min2)
                .map(x -> x.get(x.size() - 1))
                .min(comparing(Node::getY).thenComparing(Node::getX))
                .get();
    }

    private List<Node> bfs(Node start, Node target) {
        Queue<Node> queue = new LinkedList<>();
        Set<Node> visited = new HashSet<>();
        Map<Node, Node> parents = new HashMap<>();

        queue.add(start);

        while (!queue.isEmpty()) {
            Node curr = queue.poll();
            if (curr.equals(target)) {
                List<Node> path = new ArrayList<>();
                curr = target;
                while (!curr.equals(start)) {
                    path.add(curr);
                    curr = parents.get(curr);
                }
                path.add(start);
                Collections.reverse(path);
                return path;
            }

            for (Node adj : getAdjacent(curr)) {
                if (!visited.contains(adj)) {
                    queue.add(adj);
                    parents.put(adj, curr);
                    visited.add(adj);
                }
            }
        }
        return new ArrayList<>();
    }

    private void sortReadingOrder() {
        units.sort(comparing(Unit::getY).thenComparing(Unit::getX));
    }

    // get open adjacent squares to Node n
    private List<Node> getAdjacent(Node n) {
        List<Node> adj = new ArrayList<>();
        for (Direction dir : Direction.values()) {
            int nx = n.getX() + dir.getDx();
            int ny = n.getY() + dir.getDy();
            if (grid[nx][ny] == '.') {
                adj.add(new Node(nx, ny));
            }
        }
        return adj;
    }


    private Unit getAdjacentEnemy(Unit u) {
        List<Unit> adj = new ArrayList<>();
        for (Direction dir : Direction.values()) {
            int nx = u.position.getX() + dir.getDx();
            int ny = u.position.getY() + dir.getDy();
            if (unitMap[nx][ny] != null
                    && unitMap[nx][ny].elf == !u.elf) {
                adj.add(unitMap[nx][ny]);
            }
        }
        if (adj.size() == 0) return null;
        if (adj.size() == 1) return adj.get(0);
        return adj.stream()
                .min(comparing(Unit::getHitPoints).thenComparing(Unit::getY)
                .thenComparing(Unit::getX)).get();
    }



    private int round() {
        //display();
        sortReadingOrder();
        for (Unit each : units) {
            if (each.alive) {
                boolean done = each.turn();
                if (done) {
                    //System.out.println(rounds);
                    return rounds * units.stream()
                            .filter(Unit::isAlive)
                            .mapToInt(Unit::getHitPoints)
                            .sum();
                }
            }
        }
        rounds++;
        return 0;
    }

    @Override
    public Object part1() {
        int result = 0;
        while (result == 0) {
            result = round();
        }
        return result;
    }

    @Override
    public Object part2() {
        AtomicInteger boost = new AtomicInteger(4);
        while (true) {
            parse();
            int elves = (int) units.stream()
                    .filter(Unit::isElf)
                    .count();
            rounds = 0;
            units.stream()
                    .filter(Unit::isElf)
                    .forEach(x -> x.attackPower = boost.get());
            int result = 0;
            while (result == 0) {
                result = round();
            }
            if (units.stream()
                    .filter(Unit::isElf)
                    .filter(Unit::isAlive)
                    .count() == elves) {
                return result;
            }
            boost.incrementAndGet();
        }
    }

    private void display() {
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                System.out.print((char) grid[j][i]);
            }
            System.out.println();
        }
    }

    @Override
    public void parse() {
        grid = new int[input.size()][input.get(0).length()];
        unitMap = new Unit[input.size()][input.get(0).length()];
        units = new ArrayList<>();
        for (int i = 0; i < input.size(); i++) {
            String line = input.get(i);
            for (int j = 0; j < line.length(); j++) {
                char c = line.charAt(j);
                if (c == 'G' || c == 'E') {
                    Unit unit = new Unit();
                    unitMap[j][i] = unit;
                    unit.position = new Node(j, i);
                    unit.elf = c == 'E';
                    units.add(unit);
                }
                grid[j][i] = c;
            }
        }
    }
}