<?php
class InequalitySystem{
var $variables; // Переменные
var $equations; // Уравнения
var $warnings_list;// Список warning
var $changed_variables;// Список изменённый переменных
function __construct($inequalities, $equations){
$this->warnings_list=array();
// Закидываем переменные
$this->variables=array();
foreach ($inequalities as $key => $ineq){
$tmp =(object)$ineq;
if (!isset($tmp->min)){ $tmp->min=null;}
if (!isset($tmp->value)){$tmp->value=null;}
if (!isset($tmp->max)){ $tmp->max=null;}
$ineq=(object)array(
'min' =>$tmp->min,
'value'=>$tmp->value,
'max' =>$tmp->max,
);
$t=(($ineq->min!=null) ? 1 : 0) + (($ineq->max!=null) ? 2 : 0);
switch ($t){
case 0:if ($ineq->value==null){
return false;
}else{
$ineq->min=$ineq->value;
$ineq->max=$ineq->value;
}
break;
case 1:$ineq->value=($ineq->value==null) ? $ineq->min : $ineq->value;
break;
case 2:$ineq->value=($ineq->value==null) ? $ineq->max : $ineq->value;
break;
case 3:$ineq->value=($ineq->value==null) ? (int)round(0.5*$ineq->min+0.5*$ineq->max) : $ineq->value;
break;
}
$ineq->min=($ineq->min==null) ? 0 : $ineq->min;
$this->variables[$key]=$ineq;
}
if (count($this->variables)==0){return false;}
// Закидываем Уравнения
$this->equations =array();
foreach ($equations as $equation){
$equation_variables=array();
foreach (array('key1','key2') as $key){
$compiled =$equation->{$key};
$key_variables =array();
while (preg_match('_(\\+|\\-|\\/|\\*)?{([a-z0-9-]+)}_i', $compiled, $a)){
// Ниже проводится анализ переменных
$key_variables[$a[2]]=(object)array();
$equation_variables[]=$a[2];
$compiled =str_replace('{'.$a[2].'}', '$this->variables["'.$a[2].'"]->value', $compiled);
}
$equation->{$key}=(object)array(
'compiled' =>$compiled,
'raw' =>$equation->{$key},
'variables'=>$key_variables
);
unset($a, $key_variables);
foreach ($equation->{$key}->variables as $key_name => &$key_value){
// @todo Провести анализ функции. Кроме направления считать ещё и влияние (линейное, геометрическое, сложное)
$old_value=(int)floor(eval('return '.$compiled.';'));
$this->variables[$key_name]->value++;
$new_value=(int)floor(eval('return '.$compiled.';'));
$key_value->direction=$new_value>$old_value;
$this->variables[$key_name]->value--;
}
// echo '<pre style="color: orange;">';var_dump($equation->{$key});echo '</pre>';
unset($compiled, $key_name, $key_value, $new_value, $old_value);
} // foreach as $key
$equation->variables=$equation_variables;
unset($equation_variables, $key);
$this->equations[]=$equation;
}
if (count($this->equations)==0){return false;}
unset($equation);
}
// Решаем систему
function solve(){
$this->changed_variables=array();
// Первый проход
for ($eq_num=0;$eq_num<count($this->equations);$eq_num++){
$equation=&$this->equations[$eq_num];
if ($this->is_equation_true($equation)){continue;}
// echo '<br>debug: '.__FILE__.' '.__LINE__;
if (!$this->try_solve_equation($equation)){return false;}
}
echo '<br/><span style="color: red;">line '.__LINE__.'=';var_dump($this->variables);echo '</span>';flush();
unset($eq_num, $equation);
// Последующие проходы
file_put_contents('/home/bise/www/test.d.kanaria.ru/ineq.log', '');
for ($iteration_num=0;($this->is_there_unsolved_equation())and($iteration_num<1000);$iteration_num++){
ob_start();var_dump($iteration_num, $this->changed_variables, $this->variables);
$buf=ob_get_contents();
ob_end_clean();
$buf=file_get_contents('/home/bise/www/test.d.kanaria.ru/ineq.log')."\r\n==================\r\n".$buf;
file_put_contents('/home/bise/www/test.d.kanaria.ru/ineq.log', $buf);
unset($buf);
$a=array();
foreach ($this->changed_variables as $variable){
if ($variable!=null){$a[]=$variable;}
}
$this->changed_variables=array_unique(array_shuffle($a));
echo '<br>iteration '.$iteration_num.', changed keys: ';flush();$s ='';
foreach($this->changed_variables as $variable){
$s.=','.$variable.'='.$this->variables[$variable]->value;
}
echo substr($s,1).' | ';$s='';
foreach($this->equations as $equation){
$s.=','.($this->is_equation_true($equation) ? 'true' : 'false='.$this->get_offset($equation));// ['.$equation->key1->raw.']=
}
echo substr($s,1);
// */
if (count($this->changed_variables)==0){
echo '<br>changed_variables count=0, but there is unsolved equation!';
for ($eq_num=0;$eq_num<count($this->equations);$eq_num++){
$equation=&$this->equations[$eq_num];
if ($this->is_equation_true($equation)){continue;}
if (!$this->try_solve_equation($equation)){return false;}
break;
}
continue;
}
unset($a, $variable, $equation, $s);
// Перебор переменных
$temp_changed_variables=$this->changed_variables;
for($i=0;$i<count($temp_changed_variables);$i++){
$variable =$temp_changed_variables[$i];
$equation_changed=false;
// Находим первый eque, в котором упомнена переменная
for ($eq_num=0;$eq_num<count($this->equations);$eq_num++){
$equation=&$this->equations[$eq_num];
if (!in_array($variable, $equation->variables)){continue;}
if ($this->is_equation_true($equation)){continue;}
if (!$this->try_solve_equation($equation)){return false;}
$equation_changed=true;
} //for $eq_num
if ($equation_changed){break;}
for ($j=0;$j<count($this->changed_variables);$j++){
if ($this->changed_variables[$j]==$variable){$this->changed_variables[$j]=null;}
}
} // for $i
unset($variable, $temp_changed_variables, $i, $j);
} // for $iteration_num
return !($this->is_there_unsolved_equation());
}
// Смещение между ключами
protected function get_offset($equation){
// This is how eval works, bitch!
$key1=(int)floor(eval('return '.$equation->key1->compiled.';'));
$key2=(int)floor(eval('return '.$equation->key2->compiled.';'));
return $key1-$key2;
}
protected function is_equation_true($equation){
$offset=$this->get_offset($equation);
// var_dump($equation, $key1, $key2, $offset);
// a >= b
// a < b
// a = b
switch ($equation->compare){
case '==':case '=': return $offset==0; break;
case '>' :return $offset>0;break;
case '<' :return $offset<0;break;
case '>=':case '=>':return $offset>=0; break;
case '<=':case '=<':return $offset<=0; break;
default: return null;
}
}
protected function is_there_unsolved_equation(){
for ($eq_num=0;$eq_num<count($this->equations);$eq_num++){
$equation=$this->equations[$eq_num];
if (!$this->is_equation_true($equation)){return true;}
}
return false;
}
// Пытаемся привести уравнение в порядок
protected function try_solve_equation($equation){
// Мы считаем, что try_solve_equation вызван не зря, поэтому можно не проверять, что неравенство сходится
$offset=$this->get_offset($equation);
// Шаг 1: находим направления
$u =($offset<=0); // Направление движения
$direction=array(
-1=>array(),
1=>array()
);
foreach (array('key1','key2') as $key_num){
foreach ($equation->{$key_num}->variables as $key => $value){
$num=($u ? 1 : -1)*(($key_num=='key1') ? 1 : -1)*($value->direction ? 1 : -1);
$direction[$num][]=$key;
}
}
$direction[-1]=array_unique(array_shuffle($direction[-1]));
$direction[1] =array_unique(array_shuffle($direction[1]));
unset($key_num, $num, $key, $value, $offset);
//echo '<br>equation '.$equation->key1->raw.' '.$equation->compare.' '.$equation->key2->raw;
// Шаг 2: Исправляем
foreach(array_shuffle(array(-1,1)) as $direction_key){
switch($direction_key){
case -1:
foreach ($direction[-1] as $key){
$variable =&$this->variables[$key];
//echo '<br>direction [-1]{'.$key.'}('.$variable->value.'): line '.__LINE__;flush();
$this->changed_variables[]=$key;
for($variable->value=$variable->value;
($variable->min==null) ? true : ($variable->value>$variable->min);){
if ($this->is_equation_true($equation)){return true;}
$variable->value--;
//if ($variable->max!=null){$variable->max--;}
//echo '<br> line '.__LINE__.', value='.$variable->value.', max='.$variable->max;
if ($this->is_equation_true($equation)){return true;}
//$offset=$this->get_offset($equation);
}
}
break;
case 1:
foreach ($direction[1] as $key){
$variable =&$this->variables[$key];
//echo '<br>direction [ 1]{'.$key.'}('.$variable->value.'): line '.__LINE__;flush();
$this->changed_variables[]=$key;
for($variable->value=$variable->value;
($variable->max==null) ? true : ($variable->value<$variable->max);){
if ($this->is_equation_true($equation)){return true;}
$variable->value++;
//if ($variable->min!=null){$variable->min++;}
//echo '<br> line '.__LINE__.', value='.$variable->value.', min='.$variable->min;
if ($this->is_equation_true($equation)){return true;}
//$offset=$this->get_offset($equation);
}
}
break;
}
} // foreach(array_shuffle(array(-1,1))
//echo '<br>This equation not solved';
return $this->is_equation_true($equation);
}
} // class InequalitySystem
function array_shuffle($a){
$b=$a;
shuffle($b);
return $b;
}
// Описываем переменные
$variables=array(
'effective-width' =>(object)array(
'min' =>100,
'value'=>1006,
'max' =>1006,
),
'effective-height' =>(object)array(
'min' =>500,
'value'=>534,
'max' =>534,
),
'screenshot-width'=>(object)array(
'min' =>100,
'value'=>250
),
'screenshot-height'=>(object)array(
'min' =>50,
'value'=>280,
'max' =>280
),
'margin-bottom' =>(object)array(
'min' =>1,
'value'=>10
),
'margin-right' =>(object)array(
'min' =>1,
'value'=>10
),
'screenshot-per-line'=>(object)array(
'min' =>3,
'value'=>8,
'max' =>20
),
'screenshot-lines' =>(object)array(
'min' =>1,
'max' =>10
),
'screenshot-count' =>(object)array(
'min' =>20,
'value'=>20
),
);
// Описываем систему взаимодействий
$equations_array=array(
(object)array(
'key1' =>'({effective-width}+{margin-right})-({screenshot-width}+{margin-right})*{screenshot-per-line}',
'key2' =>'0',
'compare'=>'>='
),
(object)array(
'key1' =>'({effective-height}+{margin-bottom})-({screenshot-height}+{margin-bottom})*{screenshot-lines}',
'key2' =>'0',
'compare'=>'>='
),
(object)array(
'key1' =>'{screenshot-count}',
'key2' =>'{screenshot-per-line}*{screenshot-lines}',
'compare'=>'=<'
),
(object)array(
'key1' =>'{screenshot-count}',
'key2' =>'{screenshot-per-line}*{screenshot-lines}',
'compare'=>'=>'
),
(object)array(
'key1' =>'{screenshot-width}*9/16-{screenshot-height}',
'key2' =>'-4',
'compare'=>'=>'
),
(object)array(
'key1' =>'{screenshot-width}*9/16-{screenshot-height}',
'key2' =>'4',
'compare'=>'<='
),
);
function getmicrotime(){
list($usec, $sec) = explode(" ", microtime());
return ((float)$usec + (float)$sec);
}
error_reporting(E_ALL);
echo '<pre>';
$system=new InequalitySystem($variables, $equations_array);
$a=getmicrotime();
$u=$system->solve();
$b=getmicrotime();
echo "\r\n=====================\r\nsolve=";var_dump($u);
echo "\r\n=============================================================================\r\n";
var_dump($system);
echo ($b-$a).'s';
/*
echo "\r\n";
$a=getmicrotime();
$system->check_speed();
$b=getmicrotime();
echo "\r\nspeed: ".($b-$a).'s';
*/
?>
Comments