<?php

function generate_character($x, $y, $type, $att)
{
    $char = new StdClass();
    $char->x = $x;
    $char->y = $y;
    $char->health = 200;
    $char->attack = $type==='E'?$att:3;
    $char->type = $type;
    $char->char_key = 0;
    $char->pos_value = 0;

    return $char;
}

function find_path($sx, $sy, $ex, $ey)
{
    global $dist, $characters, $ymax;

    $start = $sy * $ymax + $sx;
    $end = $ey * $ymax + $ex;

    $search = array();
    $question = array();
    foreach (array_keys($dist) as $val)
    {
        $question[$val] = PHP_INT_MAX;
    }
    $question[$start] = 0;


    while (!empty($question)) {
        $min = array_search(min($question), $question);
        if ($min == $end) break;

        $x = $min % $ymax;
        $y = (int)($min / $ymax);

        $ignore = false;
        foreach ($characters as $character) {
            if (!($character->x == $sx && $character->y == $sy) && !($character->x == $ex && $character->y == $ey) && $character->x == $x && $character->y == $y) {
                $ignore = true;
                break;
            }
        }

        if (!$ignore) {
            foreach ($dist[$min] as $key => $val) {

                if (!empty($question[$key]) && $question[$min] + $val < $question[$key]) {
                    $question[$key] = $question[$min] + $val;
                    $search[$key] = array($min, $question[$key]);
                }
            }
        }
        unset($question[$min]);
    }

    $path = array();


    if (!array_key_exists($end, $search)) {
        return false;
    }
    while ($end != $start) {
        $path[] = $end;
        $end = $search[$end][0];
    }
    $path[] = $start;
    $path = array_reverse($path);

    return $path;
}

function sort_on_position($a, $b)
{
    global $ymax;

    $ax = $a->x;
    $ay = $a->y;
    $apos = $ay * $ymax + $ax;

    $bx = $b->x;
    $by = $b->y;
    $bpos = $by * $ymax + $bx;

    if ($apos === $bpos) return 0;

    return $apos > $bpos ? 1 : -1;

}

function print_grid($grid, $characters)
{
    for ($y = 0; $y < count($grid); $y++) {
        for ($x = 0; $x < count($grid[$y]); $x++) {
            $symbol = $grid[$y][$x];
            foreach ($characters as $character) {
                if ($character->x === $x && $character->y === $y) {
                    $symbol = $character->type;
                }
            }
            echo $symbol;
        }
        echo PHP_EOL;
    }
}

function get_other_characters($characters, $type)
{
    $search_type = $type === 'E' ? 'G' : 'E';
    $result = array();
    foreach ($characters as $char_key => $character) {
        if ($character->type === $search_type) {
            $character->char_key = $char_key;
            $result[] = $character;
        }
    }

    return $result;
}

function stop_battle($characters)
{
    $types = array();
    foreach ($characters as $character) {
        $types[] = $character->type;
    }
    $types = array_unique($types);

    return count($types) === 1;
}

function get_sum($characters)
{
    $sum = 0;
    foreach ($characters as $character) {
        $sum += $character->health;
    }

    return $sum;
}

function get_closest($characters, $character)
{
    global $ymax;
    $type = $character->type;
    $others = get_other_characters($characters, $type);
    $closest = array();

    foreach ($others as $other) {
        $path = find_path($character->x, $character->y, $other->x, $other->y);

        if ($path) {
            $count = count($closest);
            if ($count === 0) {
                $closest[0] = $other;
                $closest[0]->path = $path;
                $closest[0]->pos_value = $closest[0]->y * $ymax + $closest[0]->x;
            } else {
                $cd = count($path);
                $cc = count($closest[0]->path);
                if ($cc > $cd) {
                    $closest = array();
                    $closest[0] = $other;
                    $closest[0]->path = $path;
                    $closest[0]->pos_value = $closest[0]->y * $ymax + $closest[0]->x;
                } elseif ($cc === $cd) {
                    $closest[$count] = $other;
                    $closest[$count]->path = $path;
                    $closest[$count]->pos_value = $closest[$count]->y * $ymax + $closest[$count]->x;
                }
            }
        }
    }
    return $closest;
}

function move_character(&$characters, &$character)
{
    global $ymax;

    $closest = get_closest($characters, $character);
    $closest_count = count($closest);

    if ($closest_count > 0) {
        $current_pos_value = $character->y * $ymax + $character->x;
        $found_closest = $closest[0];

        if (count($closest[0]->path) > 2) {
            for ($i = 0; $i < $closest_count; $i++) {
                if ($closest[$i]->pos_value > $current_pos_value && abs($closest[$i]->pos_value - $current_pos_value) < abs($found_closest->pos_value - $current_pos_value)) {
                    $found_closest = $closest[$i];
                }
            }

            $move_to = $found_closest->path[1];
            $mx = $move_to % $ymax;
            $my = (int)($move_to / $ymax);

            $character->x = $mx;
            $character->y = $my;
        }
    }
}

function attack_character(&$characters, &$character)
{
    global $ymax, $battle;

    $closest = get_closest($characters, $character);
    $closest_count = count($closest);

    if ($closest_count > 0) {
        $current_pos_value = $character->y * $ymax + $character->x;
        $found_closest = $closest[0];

        if (count($closest[0]->path) == 2) {
            for ($i = 0; $i < $closest_count; $i++) {
                if ($closest[$i]->health < $found_closest->health || ($closest[$i]->health === $found_closest->health && $closest[$i]->pos_value > $current_pos_value && abs($closest[$i]->pos_value - $current_pos_value) < abs($found_closest->pos_value - $current_pos_value))) {
                    $found_closest = $closest[$i];
                }
            }

            $characters[$found_closest->char_key]->health -= $character->attack;

            if ($characters[$found_closest->char_key]->health <= 0) {
                unset($characters[$found_closest->char_key]);
            }
        }
    }
}

for($att = 20; $att < 100 ; $att++) {

    $start_elves = 0;

    $input = file('input.txt');

    $grid = array();

    foreach ($input as $line) {
        $grid[] = str_split(trim($line));
    }

    $characters = array();

    $distance = array();

    $ymax = count($grid);
    $xmax = count($grid[0]);

    for ($y = 0; $y < $ymax; $y++) {
        $distance[$y] = array();
        for ($x = 0; $x < $xmax; $x++) {
            if ($grid[$y][$x] === 'E') {
                $characters[] = generate_character($x, $y, 'E', $att);
                $grid[$y][$x] = '.';
                $start_elves++;
            }
            if ($grid[$y][$x] === 'G') {
                $characters[] = generate_character($x, $y, 'G', $att);
                $grid[$y][$x] = '.';
            }
            if ($grid[$y][$x] === '.') {
                $distance[$y][$x] = 1;
            }
        }
    }

    $dist = array();

    for ($y = 0; $y < $ymax; $y++) {
        for ($x = 0; $x < $xmax; $x++) {
            if (isset($distance[$y][$x])) {
                $dpos = $y * $xmax + $x;
                $dist[$dpos] = array();
                if (isset($distance[$y][$x - 1])) {
                    $npos = $y * $xmax + $x - 1;
                    $dist[$dpos][$npos] = 1;
                }
                if (isset($distance[$y][$x + 1])) {
                    $npos = $y * $xmax + $x + 1;
                    $dist[$dpos][$npos] = 1;
                }
                if (isset($distance[$y - 1][$x])) {
                    $npos = ($y - 1) * $xmax + $x;
                    $dist[$dpos][$npos] = 1;
                }
                if (isset($distance[$y + 1][$x])) {
                    $npos = ($y + 1) * $xmax + $x;
                    $dist[$dpos][$npos] = 1;
                }
            }
        }
    }

    $battle = true;
    $rounds = 0;

    while ($battle) {
        usort($characters, 'sort_on_position');
        $round_inc = false;
        foreach ($characters as &$character) {
            if ($battle) {
                move_character($characters, $character);
                attack_character($characters, $character);
                if (stop_battle($characters)) {
                    $battle = false;
                    break;

                }
            }
        }
        if ($battle) {
            $rounds++;
        }
    }

    if($characters[0]->type === 'E' && $start_elves === count($characters)) {

        print_grid($grid, $characters);
        echo PHP_EOL;

        $sum = get_sum($characters);
        printf('Sum: %d', $sum);
        echo PHP_EOL;
        printf('Rounds: %d', $rounds);
        echo PHP_EOL;

        printf('Part 1: %d', $rounds * $sum);
        echo PHP_EOL;
        exit();
    } else {
        printf('Not found for %d', $att);
        echo PHP_EOL;
    }
}