<?php

error_reporting(-1);
mb_internal_encoding("utf-8");

abstract class Animal
{
    protected $x;
    protected $y;
    protected $field;
    protected $excludedAnimals = ["Mouse", "Cat", "Dog"];

    public function __construct(Field $field) 
    {
        $this->field = $field;
    }

    public function setX($x) 
    {
        $this->x = $x;
    }

    public function setY($y) 
    {
        $this->y = $y;
    }

    public function getX() 
    {
        return $this->x;
    }

    public function getY() 
    {
        return $this->y;
    }
        
    protected function findAvailableSteps(array $offsets)
    {
        $adjacentSteps = array_filter($offsets, [$this->field, "positionExists"]);
        $availableSteps = $this->field->findOpenSteps($adjacentSteps, 
                                                      $this->excludedAnimals); 
        $availableSteps[] = [$this->x, $this->y];
        return $availableSteps;
    }
    
    public function makeStep() 
    {
        $availableSteps = $this->findAvailableSteps($this->findOffsets($this->x,
                                                                       $this->y));
        $estimatedSteps = [];
        foreach($availableSteps as $step) {
            $estimatedSteps[] = $this->estimateStep($step);
        }
        $prices = [];
        foreach ($estimatedSteps as $step) {
            $prices[] = $step["price"];
        }
        $bestPrice = max($prices);
        $bestStep = [];
        foreach ($estimatedSteps as $step) {
            if ($step["price"] === $bestPrice) {
                $bestStep = $step;
                break;
            }
        }
        $this->x = $bestStep["x"];
        $this->y = $bestStep["y"];
    }
    
    abstract public function getLabel();
    abstract protected function findOffsets($x, $y);
    abstract protected function estimateStep($step);
}

class Mouse extends Animal 
{
    private $label = "M";

    public function getLabel() 
    {
        return $this->label;
    }
    
    public function isProtected()
    {
        $currentPos = [$this->x, $this->y];
        $adjacentMouses = $this->field->getVisibleAnimals("Mouse",
                                                          $currentPos,
                                                          3);
        if (count($adjacentMouses) >= 2) {
            return true;
        }
        return false;
    }
    
    protected function findOffsets($x, $y)
    {
        $offsets = [
            [$x - 1, $y],
            [$x, $y + 1],
            [$x + 1, $y],
            [$x, $y - 1],
        ];        
        return $offsets;
    }
    
    protected function estimateStep($step) 
    {
        $visibilityDiametr = 9;
        $price = 500;
        $estimatedStep = [];
        $visibleCats = $this->field->getVisibleAnimals("Cat", $step, $visibilityDiametr);
        if ($visibleCats) {
            $nearestCat = $this->field->getNearestAnimal("Cat", $step);
            $horizontalDiff = abs($step[0] - $nearestCat->getX());
            $verticalDiff = abs($step[1] - $nearestCat->getY());
            $price += ($horizontalDiff + $verticalDiff) * 100;
            count($visibleCats) * 3 < 60 ? $price -= count($visibleCats) * 3 : $price;
        }
        $stepOffsets = $this->findOffsets($step[0], $step[1]);
        $nextAvailableSteps = $this->findAvailableSteps($stepOffsets);
        $price += count($nextAvailableSteps) * 10;
        $estimatedStep["x"] = $step[0];
        $estimatedStep["y"] = $step[1];
        $estimatedStep["price"] = $price;
        return $estimatedStep;
    }
}

class Cat extends Animal 
{
    private $label = "K";
    private $stepsCounter = 1;
    protected $excludedAnimals = ["Cat", "Dog"];

    public function getLabel() 
    {
        return $this->label;
    }

    protected function findOffsets($x, $y)
    {
        $offsets = [
            [$x - 1, $y],
            [$x - 1, $y + 1],
            [$x, $y + 1],
            [$x + 1, $y + 1],
            [$x + 1, $y],
            [$x + 1, $y - 1],
            [$x, $y - 1],
            [$x - 1, $y - 1],
        ];
        return $offsets;
    }
    
    protected function findAvailableSteps(array $offsets)
    {
        $result = [];
        $availableSteps = parent::findAvailableSteps($offsets);
        foreach ($availableSteps as $step) {
            if (!$this->field->positionIntersectsDogs($step)) {
                $result[] = $step;
            }
        }
        return $result;
    }
    
    protected function estimateStep($step) 
    {
        $estimatedStep = [];
        $price = 500;
        $nearestMouse = $this->field->getNearestAnimal("Mouse", $step);
        if ($nearestMouse) {
            if ($nearestMouse->isProtected()) {
                $price = -1000;    
            } else {
                $horizontalDiff = abs($step[0] - $nearestMouse->getX());
                $verticalDiff = abs($step[1] - $nearestMouse->getY());
                $price -= ($horizontalDiff + $verticalDiff) * 10;
            }
        }
        $estimatedStep["x"] = $step[0];
        $estimatedStep["y"] = $step[1];
        $estimatedStep["price"] = $price;
        return $estimatedStep;
    }

    public function makeStep() 
    {
        if ($this->label === "@") {
            $this->stepsCounter = 0;
            $this->label = "K";
        } else {
            parent::makeStep();
            $this->stepsCounter++;
            $mouses = $this->field->getAnimalsByType("Mouse");
            foreach ($mouses as $m) {
                if ($m->getX() === $this->x && $m->getY() === $this->y) {
                    $this->field->removeAnimal($m);
                    $this->label = "@";
                    $this->stepsCounter = 0;
                }
            }
            if ($this->stepsCounter === 8) {
                $this->label = "@";
            }
        }
    }
}

class Dog extends Animal 
{
    private $label = "C";

    public function getLabel() 
    {
        return $this->label;
    }

    protected function findOffsets($x, $y) 
    {
        $offsets = [
                    [$x - 2, $y],
                    [$x - 2, $y + 2],
                    [$x, $y + 2],
                    [$x + 2, $y + 2],
                    [$x + 2, $y],
                    [$x + 2, $y - 2],
                    [$x, $y - 2],
                    [$x - 2, $y - 2]
                ];
        return $offsets;
    }
    
    protected function estimateStep($step)
    {
        $estimatedStep = [];
        $randomPrice = rand(1, 10000);
        $estimatedStep["x"] = $step[0];
        $estimatedStep["y"] = $step[1];
        $estimatedStep["price"] = $randomPrice;
        return $estimatedStep;
    }
    
    public function getAdjacentSteps()
    {
        $offsets = [
            [$this->x - 1, $this->y],
            [$this->x - 1, $this->y + 1],
            [$this->x, $this->y + 1],
            [$this->x + 1, $this->y + 1],
            [$this->x + 1, $this->y],
            [$this->x + 1, $this->y - 1],
            [$this->x, $this->y - 1],
            [$this->x - 1, $this->y - 1],
        ];
        return array_filter($offsets, [$this->field, "positionExists"]);
    }
}

class Field 
{
    private $size;
    private $animals;

    public function __construct($size) 
    {
        $this->size = $size;
    }

    public function getSize() 
    {
        return $this->size;
    }

    public function getAnimals() 
    {
        return $this->animals;
    }

    public function addAnimal(Animal $animal) 
    {
        $this->animals[] = $animal;
    }

    public function removeAnimal(Animal $animal) {
        $key = array_search($animal, $this->animals, true);
        unset($this->animals[$key]);
    }

    public function getAnimalsByType($type) 
    {
        $func = function($animal) use ($type) {
            if (get_class($animal) === $type) {
                return $animal;
            }
        };
        return array_filter($this->animals, $func);
    }

    public function drawSchema() 
    {
        $schema = [];
        for ($i = 0; $i <= $this->size; $i++) {
            $line = array_fill(0, $this->size + 1, ". ");
            $schema[] = $line;
        }
        foreach ($this->animals as $animal) {
            $schema[$animal->getX()][$animal->getY()] = $animal->getLabel() . " ";
        }
        return $schema;
    }

    public function positionExists($pos)
    {
        $x = $pos[0];
        $y = $pos[1];
        $haystack = range(0, $this->size);
        if (in_array($x, $haystack) && in_array($y, $haystack)) {
            return true;
        }
        return false;
    }

    public function getVisibleAnimals($type, $pos, $diametr) 
    {
        $chosenAnimals = $this->getAnimalsByType($type);
        $visibleAnimals = [];
        foreach ($chosenAnimals as $animal) {
            if (abs($pos[0] - $animal->getX()) <= floor($diametr / 2) &&
                abs($pos[1] - $animal->getY()) <= floor($diametr / 2)) {
                $visibleAnimals[] = $animal;
            }
        }
        return $visibleAnimals;
    }

    public function getNearestAnimal($type, $pos) 
    {
        $chosenAnimals = $this->getAnimalsByType($type);
        $animals = [];
        foreach ($chosenAnimals as $animal) {
            $posDiff = abs($pos[0] - $animal->getX()) +
                       abs($pos[1] - $animal->getY());
            $animals[$posDiff] = $animal;
        }
        if ($animals) {
            $minPosDiff = min(array_keys($animals));
            return $animals[$minPosDiff];        
        } 
        return null;
    }

    public function printSchema() 
    {
        $schema = $this->drawSchema();
        for ($i = $this->size; $i >= 0; $i--) {
            for ($j = 0; $j <= $this->size; $j++) {
                echo $schema[$j][$i];
            }
            echo "\n";
        }
    }
    
    public function positionIsBusy($pos)
    {
        foreach ($this->animals as $a) {
            if ($a->getX() === $pos[0] && $a->getY() === $pos[1]) {
                return get_class($a);
            }
        }
        return null;
    }
    
    public function positionIntersectsDogs($step)
    {
        $dogs = $this->getAnimalsByType("Dog");
        $dogsAdjPositions = [];
        foreach ($dogs as $d) {
            $dogsAdjPositions = array_merge($dogsAdjPositions, 
                                            $d->getAdjacentSteps());
        }
        foreach ($dogsAdjPositions as $pos) {
            if ($pos[0] === $step[0] && $pos[1] === $step[1]) {
                return true;
            }
        }
        return false;
    }
    
    public function findOpenSteps(array $steps, array $animalTypes)
    {
        $openSteps = [];
        foreach ($steps as $step) {
            if (!in_array($this->positionIsBusy($step), $animalTypes)) {
                $openSteps[] = $step;
            }
        }
        return $openSteps;  
    }    
}

class Game 
{
    private $numMouses;
    private $numCats;
    private $numDogs;
    private $numSteps;
    private $field;
    private $stepNumber = 0;

    public function __construct($numMouses, $numCats, $numDogs, $fieldSize, $numSteps) 
    {
        $this->numMouses = $numMouses;
        $this->numCats = $numCats;
        $this->numDogs = $numDogs;
        $this->numSteps = $numSteps;
        $this->field = new Field($fieldSize);
    }

    private function createAnimals($limit, $animalType) 
    {
        for ($i = 0; $i < $limit; $i++) {
            $animal = new $animalType($this->field);
            $this->field->addAnimal($animal);
        }
    }

    private function setAnimalsPositions() 
    {
        $unavailableX = [];
        $unavailableY = [];
        foreach ($this->field->getAnimals() as $animal) {
            do {
                $x = rand(1, $this->field->getSize());
                $y = rand(1, $this->field->getSize());
                $animal->setX($x);
                $animal->setY($y);
            } while (in_array($x, $unavailableX, true &&
                    in_array($y, $unavailableY, true)));
            $unavailableX[] = $animal->getX();
            $unavailableY[] = $animal->getY();
        }
    }

    private function makeReport() 
    {
        $info = "Ход: " . $this->stepNumber .
                "\tМышек: " . count($this->field->getAnimalsByType("Mouse")) .
                "\tКошек: " . count($this->field->getAnimalsByType("Cat")) .
                "\tСобак: " . count($this->field->getAnimalsByType("Dog"));
        return $info;
    }

    private function animalsMakeStep($animalClass) 
    {
        foreach ($this->field->getAnimals() as $animal) {
            if (get_class($animal) === $animalClass) {
                $animal->makeStep();
            }
        }
    }

    public function start() 
    {
        $this->createAnimals($this->numMouses, "Mouse");
        $this->createAnimals($this->numCats, "Cat");
        $this->createAnimals($this->numDogs, "Dog");
        $this->setAnimalsPositions();
        $this->stepNumber++;
        echo $this->makeReport() . "\n";
        $this->field->printSchema();
        for ($i = 1; $i < $this->numSteps; $i++) {
            $this->animalsMakeStep("Mouse");
            $this->animalsMakeStep("Cat");
            $this->animalsMakeStep("Dog");
            $this->stepNumber++;
            echo $this->makeReport() . "\n";
            $this->field->printSchema();
            if (count($this->field->getAnimalsByType("Mouse")) === 0) {
                break;
            }
        }
    }
}


$game = new Game(4, 2, 1, 15, 30);
$game->start();