The task was to find out all the constellations in the space

constellation.md

Given an MxN matrix represented by a 2D perimeter located in space and filled with stars, find the numbers of constellations.

Conditions:

The exact constellation structure to be found is the following:

0 * 0
* 0 *

If no constellation is found then the output should be 0 0. One constellation does not overlap with another. You should look for all possible positions of the given constellation, meaning you should also look for:

* 0 *
0 * 0

and

0 *
* 0
0 *

and

* 0
0 *
* 0

Input: M, N – integers, space[M,N] of {0,*}

Output: the number of all the found constellations.

Example:

For the following input:

3
3
0 * 0
* 0 *
0 * 0

The output should be: 1.

<?php
  class AstroObserver{
    public $HashTable = array();
    public $M;
    public $N;
    public $space;

    public function __construct($filename){
        $this->input_filename = $filename;
    }
    public  function Main(){
        $data = $this->readString();
        $this->M = $data[0];
        $this->N = $data[1];
        $this->space = array();
        for ($i=0; $i <$this->M; $i++) {
            $this->space[] = explode(" ", $data[2+$i]);
        }
        $result = 0;

        ///////////////
        for($row = 0; $row < $this->M; $row++) {
          for($col = 0; $col < $this->N; $col++) {
              if ($this->findConstellation($row, $col)) {
                $result++;
              }
          }
        }
        //////////////
      return $result;
    }

    protected function findConstellation($row, $col)
    {
      // make a backup
      $copy = $this->space;
      // start the process
      if ($this->isAsterisk($row, $col)) {
        if(count($this->findPartsOfTheConstellation($row, $col)) === 3) {
          // commit
          return true;
        };
      }
      // rollback
      $this->space = array_map(function($row) {
          return array_map(function($val) {
              return $val === 2 ? "*" : $val;
          }, $row);
      }, $this->space);
      return false;
    }

    protected function findPartsOfTheConstellation($row, $col, $constellations = [])
    {
      $constellations[] = [$row, $col];

      $this->space[$row][$col] = 0; // to avoid duplicates

      if (count($constellations) === 3) return $constellations;

      foreach($this->siblingAsterisks($row, $col) as $sibling) {
        // siblings of the sibling
        $ssib = $this->siblingAsterisks($sibling[0], $sibling[1]);

        if(count($ssib) > 1) {
          $this->space[$sibling[0]][$sibling[1]] = 2; // temporary need to exclude from current iteration
          continue;
        }

        if(count($ssib) > 0) {
          $constellations = array_merge($constellations, array_filter(array_map(function($element) use ($constellations) {
            foreach($constellations as $c) {
              if($c[0] === $element[0] && $c[1] === $element[1]) {
                return false;
              }
            }

            return $element;
          }, $this->findPartsOfTheConstellation($sibling[0], $sibling[1], $constellations))));
          continue;
        }

        if(count($ssib) === 0) {
            if ($constellations === 3) {
                continue; // or maybe just return?
            }
            $this->space[$sibling[0]][$sibling[1]] = 0;
            $constellations[] = [$sibling[0], $sibling[1]];
            continue;
        }
      }

      return $constellations;
    }

    protected function siblingAsterisks($row, $col) {
      $result = [];

      if ($this->isAsterisk($row - 1, $col - 1)) {
        $result[] = [$row - 1, $col - 1];
      }

      if ($this->isAsterisk($row - 1, $col + 1)) {
        $result[] = [$row - 1, $col + 1];
      }

      if ($this->isAsterisk($row + 1, $col - 1)) {
        $result[] = [$row + 1, $col - 1];
      }

      if ($this->isAsterisk($row + 1, $col + 1)) {
        $result[] = [$row + 1, $col + 1];
      }

      return $result;
    }

    protected function isAsterisk($row, $col) {
        return isset($this->space[$row][$col]) && $this->space[$row][$col] === '*';
    }

    public function readString(){
        $file = fopen($this->input_filename, "r");
        if(!$file){
            throw new Exception("File not found (404)", 1);
        }
        $line = array();
        while(!feof($file)){
            array_push($line,str_replace(array(PHP_EOL), "",fgets($file)));
        }
        return $line;
    }
}
$o = new AstroObserver($argv[1]);
echo $o->Main() . PHP_EOL;