<?php
/**
* Copyright (c) <2015>, Ghali Ahmed<ghaliano2005@gmail.com>
*
* All rights reserved.
* Redistribution and use in source and binary forms, with or without modification,
* are permitted provided that the following conditions are met:
* 1. Redistributions of source code must retain the above copyright notice,
* this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright notice,
* this list of conditions and the following disclaimer in the documentation and/or
* other materials provided with the distribution.
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
* THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
* IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
* INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
* (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*
* This class find similarity for given cel on 2D array
* the search strategie can be easly modified with the given direction
* @Exemple: when the given direction array is: [[0, 1],[-1, 0],[0, -1],[1, 0]]
* the script will look recursively to the right, top, bottom, left, right of the given cel
* @author Ghali Ahmed<ghaliano2005@gmail.com>
* @version 1.0
*/
class MathMatrixHelper
{
protected $atomes = [];
protected $tile = [];
protected $visited = [];
protected $tileDim = 20;
private $maxNest;
/**
* Direction to find friend cell
*/
protected $directions = [];
public function __construct($atomes, $directions, $tileDim)
{
$this->atomes = $atomes;
$this->directions = $directions;
$this->tileDim = $tileDim;
$this->maxNest = ini_set('xdebug.max_nesting_level', 0);
$this->init();
}
public function init()
{
$i = 0;
while ($i < $this->tileDim) {
$j = 0;
$this->tile[$i] = [];
while ($j < $this->tileDim) {
$this->tile[$i][$j] = $this->atomes[array_rand($this->atomes)];
$this->visited[$i][$j] = [];
$j++;
}
$i++;
}
}
public function getAllConnexion($i, $j, &$result = [])
{
foreach ($this->directions as $key => $direction) {
$iTarget = $i + $direction[0];
$jTarget = $j + $direction[1];
if (isset($this->tile[$iTarget][$jTarget])) {
if (($this->tile[$i][$j] == $this->tile[$iTarget][$jTarget])
&& !isset($this->visited[$i][$j][$key])
&& !isset($this->visited[$iTarget][$jTarget][$key])) {
$result[] = "$i:$j";
$this->visited[$i][$j][$key] = true;
$this->getAllConnexion($iTarget, $jTarget, $result);
}
}
}
return $result;
}
/**
* Search for connexion in regular mode until there length reached the max value
* @var $m x0
* @var $n y0
*/
public function getRegularConnexion($m, $n, $max, $onlyFirst=false)
{
$result = [];
$len = count($this->tile);
foreach ($this->directions as $key => $direction) {
if (!isset($result[$key])) {
$result[$key] = [];
}
for ($i = 0; $i < $len; $i++) {
$iTarget = $m + $i*$direction[0];
$jTarget = $n + $i*$direction[1];
if ($this->tile[$m][$n] != @$this->tile[$iTarget][$jTarget]) {
break;
} else {
$result[$key][] = "$iTarget:$jTarget";
if ($onlyFirst && (count($result[$key]) == $max)) {
return $result[$key];
}
}
}
if (!$onlyFirst && count($result[$key]) <$max) {
$result[$key] = [];
}
};
return $this->flatten($result);
}
/**
* Print array like a matrix
* and display connexion with special color
*/
public function printTile($result, $m, $n)
{
$linePattern = "[%s]<br />";
$itemPattern = "%s<span style='%s'>%s</span>";
$output = "";
for ($i = 0; $i<$this->tileDim; $i++) {
$sep = '';
$j = 0;
$str = '';
for ($j = 0; $j<$this->tileDim; $j++) {
$in = in_array("$i:$j", $result);
$from = $i == $m && $j == $n;
$str .= sprintf($itemPattern, $sep, ($in ? 'color: red;' : '').($from ? 'border: 1px solid;' : ''), @$this->tile[$i][$j]);
$sep = ',';
}
$output .= sprintf($linePattern, $str);
}
print '<pre>'.$output.'</pre>';
}
public function __destruct()
{
if (!empty($this->maxNest)) {
ini_set('xdebug.max_nesting_level', $this->maxNest);
}
}
/**
* Thnaks to http://stackoverflow.com/users/28835/too-much-php
* http://stackoverflow.com/questions/1319903/how-to-flatten-a-multidimensional-array
*/
protected function flatten(array $array)
{
$return = array();
array_walk_recursive($array, function($a) use (&$return) { $return[] = $a; });
return $return;
}
}
$letters = ['a', 'b'];
$directions = [
'knight' => [[2, 1],[2, -1],[-2, 1],[-2, -1],[1, 2],[-1,2],[1,-2],[-1,-2]],
'plus' => [[0, 1],[-1, 0],[0, -1],[1, 0]],
'plus_and_coin' => [[0, 1],[-1, 0],[0, -1],[1, 0],[1, 1],[-1, 1],[1, -1],[-1, -1]],
];
$strategie = 'plus_and_coin';
$x = 6;
$y = 6;
$matrix = new MathMatrixHelper($letters, $directions[$strategie], 40);
print '<b>getAllConnexion:</b><br>';
$startTime = microtime(true);
//$result = $matrix->getAllConnexion($x, $y);
//$matrix->printTile($result, $x, $y);
print '<b>getRegularConnexion:</b><br>';
$result = $matrix->getRegularConnexion($x, $y, 5, false);
$matrix->printTile($result, $x, $y);
$endTime = microtime(true);
echo "Execution time : ".($endTime - $startTime)." seconds<br/><br/>";
|