// Parse map
preg_match_all("/[GE]/", $input->lines->join(), $units, PREG_OFFSET_CAPTURE);
$map = (array) $input->replace(["G", "E"], ".")->lines->map(fn ($l) => $l->string);
$w = strlen($map[0]);
// Parse units : x, y, hp, team, id
$units = array_map(fn ($u, $i) => [$u[1] % $w, floor($u[1] / $w), 200, $u[0] == "E", $i], $units[0], array_keys($units[0]));
$teams = (array) set($units)->groupBy(3)->callEach()->column(4);
/**
* Get sides of a point
*/
function sides($x, $y, $map) {
return array_filter(neighbors([$x, $y]), fn ($side) => ($map[$side[1]][$side[0]] ?? false) == ".");
}
/**
* Quick shortest path between two points using BFS
*/
function shortest($from, $to, $map) {
$map[$to[1]][$to[0]] = ".";
$queue = [$from];
$values = [implode(";", $from) => 0];
while (!empty($queue)) {
$pos = array_shift($queue);
$p = implode(";", $pos);
if ($pos == $to) return $values[$p];
foreach (sides($pos[0], $pos[1], $map) as $side) {
$s = implode(";", $side);
$value = $values[$p] + 1;
if (empty($values[$s]) || $values[$s] > $value) {
$values[$s] = $value;
$queue[] = $side;
}
}
}
return INF; // No path to target
}
/**
* Find best path to closest target
*/
function path($unit, $targets, $units, $map) {
foreach ($units as $u) $map[$u[1]][$u[0]] = "#";
// Find destination
$to = array_merge(...array_map(fn ($t) => array_values(sides($units[$t][0], $units[$t][1], $map)), $targets));
$lengths = array_filter(array_map(fn ($xy) => shortest([$unit[0], $unit[1]], $xy, $map, $units), $to), fn ($l) => $l != INF);
if (empty($lengths)) return false;
$kl = array_map(fn ($k) => $lengths[$k] * 100_000 + $to[$k][1] * 1_000 + $to[$k][0], array_keys($lengths));
$bl = array_keys($lengths)[array_search(min($kl), $kl)];
$dest = $to[$bl];
// Find best first step toward destination
$sides = array_values(sides($unit[0], $unit[1], $map));
if (empty($sides)) return false;
$lengths = array_map(fn ($side) => shortest([$side[0], $side[1]], $dest, $map), $sides);
$kl = array_map(fn ($k) => $lengths[$k] * 100_000 + $sides[$k][1] * 1_000 + $sides[$k][0], array_keys($lengths));
$bl = array_search(min($kl), $kl);
return $sides[$bl];
}
/**
* Get hit target ID : lowest hp enemy in range
*/
function get_hit_target($x, $y, $targets, $units, $map) {
$sides = sides($x, $y, $map);
$can_hit = array_filter($targets, fn ($t) => in_array([$units[$t][0], $units[$t][1]], $sides));
if (empty($can_hit)) return null;
if (count($can_hit) > 1) {
usort($can_hit, function ($a, $b) use ($units) {
if ($units[$a][2] != $units[$b][2]) return $units[$a][2] <=> $units[$b][2];
return ($units[$a][1] * 1000 + $units[$a][0]) <=> ($units[$b][1] * 1000 + $units[$b][0]);
});
}
return array_values($can_hit)[0];
}
/**
* Simulate the fight
*
*/
function fight($map, $units, $teams, $dmg = [3, 3]) {
for ($t = 0; $t < 5000; $t++) {
// Order units in reading order
$order = array_keys($units);
usort($order, fn ($a, $b) =>
($units[$a][1] * 1000 + $units[$a][0]) <=> ($units[$b][1] * 1000 + $units[$b][0])
);
// Move/attack with each unit
foreach ($order as $o) {
if (empty($units[$o])) continue; // Unit was killed before its turn
$unit = $units[$o];
$targets = (array) ($teams[($unit[3] + 1) % 2] ?? []); // Other side id's
$targets = array_filter($targets, fn ($t) => !empty($units[$t])); // Keep only targets that are alive
// No more targets : fight is over
if (empty($targets)) break 2;
// Check own range for enemies
$hit_target = get_hit_target($unit[0], $unit[1], $targets, $units, $map);
// Not in range of an enemy : move toward closest target
if (is_null($hit_target)) {
$path = path($unit, $targets, $units, $map);
if (!$path) continue;
$units[$o][0] = $path[0];
$units[$o][1] = $path[1];
// Check enemies in range again
$hit_target = get_hit_target($path[0], $path[1], $targets, $units, $map);
}
// Is in range of an enemy : hit it
if (!is_null($hit_target)) {
$units[$hit_target][2] -= $dmg[(int) $unit[3]];
if ($units[$hit_target][2] <= 0) {
unset($units[$hit_target]);
$teams = (array) set($units)->groupBy(3)->callEach()->column(4);
}
}
}
}
return [array_sum(array_column($units, 2)) * $t, $units];
}
// ==================================================
// > PART 1
// ==================================================
$solution_1 = fight($map, $units, $teams)[0];
// ==================================================
// > PART 2
// ==================================================
$starting_elves = count(array_filter($units, fn ($u) => $u[3]));
for ($a = 25;; $a++) { // Jump start to 25 to save time
$outcome = fight($map, $units, $teams, [3, $a]);
$elves_alive = count(array_filter($outcome[1], fn ($u) => $u[3]));
if ($elves_alive == $starting_elves) {
$solution_2 = $outcome[0];
break;
}
}