NokitaKaze

Решение системы неравенств v0.0.1

Jul 13th, 2014
306
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. <?php
  2.  class InequalitySystem{
  3.   var $variables;    // Переменные
  4.   var $equations;    // Уравнения
  5.   var $warnings_list;// Список warning
  6.   var $changed_variables;// Список изменённый переменных
  7.  
  8.   function __construct($inequalities, $equations){
  9.    $this->warnings_list=array();
  10.    
  11.    // Закидываем переменные
  12.    $this->variables=array();
  13.    foreach ($inequalities as $key => $ineq){
  14.     $tmp =(object)$ineq;
  15.     if (!isset($tmp->min)){  $tmp->min=null;}
  16.     if (!isset($tmp->value)){$tmp->value=null;}
  17.     if (!isset($tmp->max)){  $tmp->max=null;}
  18.     $ineq=(object)array(
  19.      'min'  =>$tmp->min,
  20.      'value'=>$tmp->value,
  21.      'max'  =>$tmp->max,
  22.     );
  23.    
  24.     $t=(($ineq->min!=null) ? 1 : 0) + (($ineq->max!=null) ? 2 : 0);
  25.     switch ($t){
  26.      case 0:if ($ineq->value==null){
  27.        return false;
  28.       }else{
  29.        $ineq->min=$ineq->value;
  30.        $ineq->max=$ineq->value;
  31.       }
  32.       break;
  33.      case 1:$ineq->value=($ineq->value==null) ? $ineq->min : $ineq->value;
  34.       break;
  35.      case 2:$ineq->value=($ineq->value==null) ? $ineq->max : $ineq->value;
  36.       break;
  37.      case 3:$ineq->value=($ineq->value==null) ? (int)round(0.5*$ineq->min+0.5*$ineq->max) : $ineq->value;
  38.       break;
  39.     }
  40.    
  41.     $ineq->min=($ineq->min==null) ? 0 : $ineq->min;
  42.     $this->variables[$key]=$ineq;
  43.    }
  44.    if (count($this->variables)==0){return false;}
  45.    
  46.    // Закидываем Уравнения
  47.    $this->equations    =array();
  48.    foreach ($equations as $equation){
  49.     $equation_variables=array();
  50.     foreach (array('key1','key2') as $key){
  51.      $compiled =$equation->{$key};
  52.      $key_variables    =array();
  53.      while (preg_match('_(\\+|\\-|\\/|\\*)?{([a-z0-9-]+)}_i', $compiled, $a)){
  54.       // Ниже проводится анализ переменных
  55.       $key_variables[$a[2]]=(object)array();
  56.       $equation_variables[]=$a[2];
  57.       $compiled =str_replace('{'.$a[2].'}', '$this->variables["'.$a[2].'"]->value', $compiled);
  58.      }
  59.      
  60.      $equation->{$key}=(object)array(
  61.       'compiled' =>$compiled,
  62.       'raw'      =>$equation->{$key},
  63.       'variables'=>$key_variables
  64.      );
  65.      unset($a, $key_variables);
  66.      
  67.      foreach ($equation->{$key}->variables as $key_name => &$key_value){
  68.       // @todo Провести анализ функции. Кроме направления считать ещё и влияние (линейное, геометрическое, сложное)
  69.       $old_value=(int)floor(eval('return '.$compiled.';'));
  70.       $this->variables[$key_name]->value++;
  71.       $new_value=(int)floor(eval('return '.$compiled.';'));
  72.       $key_value->direction=$new_value>$old_value;
  73.       $this->variables[$key_name]->value--;
  74.      }
  75.      //     echo '<pre style="color: orange;">';var_dump($equation->{$key});echo '</pre>';
  76.      unset($compiled, $key_name, $key_value, $new_value, $old_value);
  77.     } // foreach as $key
  78.     $equation->variables=$equation_variables;
  79.     unset($equation_variables, $key);
  80.    
  81.     $this->equations[]=$equation;
  82.    }
  83.    if (count($this->equations)==0){return false;}
  84.    unset($equation);
  85.   }
  86.  
  87.   // Решаем систему
  88.   function solve(){
  89.    $this->changed_variables=array();
  90.    // Первый проход
  91.    for ($eq_num=0;$eq_num<count($this->equations);$eq_num++){
  92.     $equation=&$this->equations[$eq_num];
  93.     if ($this->is_equation_true($equation)){continue;}
  94.    
  95.     //    echo '<br>debug: '.__FILE__.' '.__LINE__;
  96.     if (!$this->try_solve_equation($equation)){return false;}
  97.    }
  98.    echo '<br/><span style="color: red;">line '.__LINE__.'=';var_dump($this->variables);echo '</span>';flush();
  99.    unset($eq_num, $equation);
  100.    
  101.    // Последующие проходы
  102.    file_put_contents('/home/bise/www/test.d.kanaria.ru/ineq.log', '');
  103.    for ($iteration_num=0;($this->is_there_unsolved_equation())and($iteration_num<1000);$iteration_num++){
  104.    
  105.     ob_start();var_dump($iteration_num, $this->changed_variables, $this->variables);
  106.     $buf=ob_get_contents();
  107.     ob_end_clean();
  108.     $buf=file_get_contents('/home/bise/www/test.d.kanaria.ru/ineq.log')."\r\n==================\r\n".$buf;
  109.     file_put_contents('/home/bise/www/test.d.kanaria.ru/ineq.log', $buf);
  110.     unset($buf);
  111.    
  112.     $a=array();
  113.     foreach ($this->changed_variables as $variable){
  114.      if ($variable!=null){$a[]=$variable;}
  115.     }
  116.     $this->changed_variables=array_unique(array_shuffle($a));
  117.     echo '<br>iteration '.$iteration_num.', changed keys: ';flush();$s ='';
  118.     foreach($this->changed_variables as $variable){
  119.      $s.=','.$variable.'='.$this->variables[$variable]->value;
  120.     }
  121.     echo substr($s,1).' | ';$s='';
  122.     foreach($this->equations as $equation){
  123.      $s.=','.($this->is_equation_true($equation) ? 'true' : 'false='.$this->get_offset($equation));// ['.$equation->key1->raw.']=
  124.     }
  125.     echo substr($s,1);
  126.     // */
  127.     if (count($this->changed_variables)==0){
  128.      echo '<br>changed_variables count=0, but there is unsolved equation!';
  129.      for ($eq_num=0;$eq_num<count($this->equations);$eq_num++){
  130.       $equation=&$this->equations[$eq_num];
  131.       if ($this->is_equation_true($equation)){continue;}
  132.       if (!$this->try_solve_equation($equation)){return false;}
  133.       break;
  134.      }
  135.      continue;
  136.     }
  137.     unset($a, $variable, $equation, $s);
  138.    
  139.     // Перебор переменных
  140.     $temp_changed_variables=$this->changed_variables;
  141.     for($i=0;$i<count($temp_changed_variables);$i++){
  142.      $variable =$temp_changed_variables[$i];
  143.      $equation_changed=false;
  144.      // Находим первый eque, в котором упомнена переменная
  145.      for ($eq_num=0;$eq_num<count($this->equations);$eq_num++){
  146.       $equation=&$this->equations[$eq_num];
  147.       if (!in_array($variable, $equation->variables)){continue;}
  148.       if ($this->is_equation_true($equation)){continue;}
  149.      
  150.       if (!$this->try_solve_equation($equation)){return false;}
  151.       $equation_changed=true;
  152.      } //for $eq_num
  153.      if ($equation_changed){break;}
  154.      
  155.      for ($j=0;$j<count($this->changed_variables);$j++){
  156.       if ($this->changed_variables[$j]==$variable){$this->changed_variables[$j]=null;}
  157.      }
  158.     } // for $i
  159.     unset($variable, $temp_changed_variables, $i, $j);
  160.    
  161.    }  // for $iteration_num
  162.    
  163.    return !($this->is_there_unsolved_equation());
  164.   }
  165.  
  166.   // Смещение между ключами
  167.   protected function get_offset($equation){
  168.    // This is how eval works, bitch!
  169.    $key1=(int)floor(eval('return '.$equation->key1->compiled.';'));
  170.    $key2=(int)floor(eval('return '.$equation->key2->compiled.';'));
  171.    return $key1-$key2;
  172.   }
  173.  
  174.   protected function is_equation_true($equation){
  175.    $offset=$this->get_offset($equation);
  176.    // var_dump($equation, $key1, $key2, $offset);
  177.    // a >= b
  178.    // a < b
  179.    // a = b
  180.    switch ($equation->compare){
  181.     case '==':case '=': return $offset==0; break;
  182.     case '>' :return $offset>0;break;
  183.     case '<' :return $offset<0;break;
  184.     case '>=':case '=>':return $offset>=0; break;
  185.     case '<=':case '=<':return $offset<=0; break;
  186.     default: return null;
  187.    }
  188.   }
  189.  
  190.   protected function is_there_unsolved_equation(){
  191.    for ($eq_num=0;$eq_num<count($this->equations);$eq_num++){
  192.     $equation=$this->equations[$eq_num];
  193.     if (!$this->is_equation_true($equation)){return true;}
  194.    }
  195.    return false;
  196.   }
  197.  
  198.   // Пытаемся привести уравнение в порядок
  199.   protected function try_solve_equation($equation){
  200.    // Мы считаем, что try_solve_equation вызван не зря, поэтому можно не проверять, что неравенство сходится
  201.    $offset=$this->get_offset($equation);
  202.    
  203.    // Шаг 1: находим направления
  204.    $u =($offset<=0); // Направление движения
  205.    $direction=array(
  206.     -1=>array(),
  207.      1=>array()
  208.    );
  209.    foreach (array('key1','key2') as $key_num){
  210.     foreach ($equation->{$key_num}->variables as $key => $value){
  211.      $num=($u ? 1 : -1)*(($key_num=='key1') ? 1 : -1)*($value->direction ? 1 : -1);
  212.      
  213.      $direction[$num][]=$key;
  214.     }
  215.    }
  216.    
  217.    $direction[-1]=array_unique(array_shuffle($direction[-1]));
  218.    $direction[1] =array_unique(array_shuffle($direction[1]));
  219.    unset($key_num, $num, $key, $value, $offset);
  220.    //echo '<br>equation '.$equation->key1->raw.' '.$equation->compare.' '.$equation->key2->raw;
  221.    
  222.    // Шаг 2: Исправляем
  223.    foreach(array_shuffle(array(-1,1)) as $direction_key){
  224.     switch($direction_key){
  225.      case -1:
  226.       foreach ($direction[-1] as $key){
  227.        $variable =&$this->variables[$key];
  228.        //echo '<br>direction [-1]{'.$key.'}('.$variable->value.'): line '.__LINE__;flush();
  229.        
  230.        $this->changed_variables[]=$key;
  231.        for($variable->value=$variable->value;
  232.            ($variable->min==null) ? true : ($variable->value>$variable->min);){
  233.         if ($this->is_equation_true($equation)){return true;}
  234.         $variable->value--;
  235.         //if ($variable->max!=null){$variable->max--;}
  236.         //echo '<br> line '.__LINE__.', value='.$variable->value.', max='.$variable->max;
  237.         if ($this->is_equation_true($equation)){return true;}
  238.        
  239.         //$offset=$this->get_offset($equation);
  240.        }
  241.       }
  242.       break;
  243.      case  1:
  244.       foreach ($direction[1] as $key){
  245.        $variable =&$this->variables[$key];
  246.        //echo '<br>direction [ 1]{'.$key.'}('.$variable->value.'): line '.__LINE__;flush();
  247.        
  248.        $this->changed_variables[]=$key;
  249.        for($variable->value=$variable->value;
  250.            ($variable->max==null) ? true : ($variable->value<$variable->max);){
  251.         if ($this->is_equation_true($equation)){return true;}
  252.         $variable->value++;
  253.         //if ($variable->min!=null){$variable->min++;}
  254.         //echo '<br> line '.__LINE__.', value='.$variable->value.', min='.$variable->min;
  255.         if ($this->is_equation_true($equation)){return true;}
  256.        
  257.         //$offset=$this->get_offset($equation);
  258.        }
  259.       }
  260.       break;
  261.     }
  262.    } // foreach(array_shuffle(array(-1,1))
  263.    
  264.    //echo '<br>This equation not solved';
  265.    return $this->is_equation_true($equation);
  266.   }
  267.  
  268.  
  269.  
  270.  } // class InequalitySystem
  271.  
  272.  
  273.  function array_shuffle($a){
  274.   $b=$a;
  275.   shuffle($b);
  276.   return $b;
  277.  }
  278.  
  279. // Описываем переменные
  280.  $variables=array(
  281.   'effective-width' =>(object)array(
  282.    'min'  =>100,
  283.    'value'=>1006,
  284.    'max'  =>1006,
  285.   ),
  286.   'effective-height' =>(object)array(
  287.    'min'  =>500,
  288.    'value'=>534,
  289.    'max'  =>534,
  290.   ),
  291.  
  292.   'screenshot-width'=>(object)array(
  293.    'min'  =>100,
  294.    'value'=>250
  295.   ),
  296.   'screenshot-height'=>(object)array(
  297.    'min'  =>50,
  298.    'value'=>280,
  299.    'max'  =>280
  300.   ),
  301.  
  302.   'margin-bottom'    =>(object)array(
  303.    'min'  =>1,
  304.    'value'=>10
  305.   ),
  306.   'margin-right'    =>(object)array(
  307.    'min'  =>1,
  308.    'value'=>10
  309.   ),
  310.  
  311.   'screenshot-per-line'=>(object)array(
  312.    'min'  =>3,
  313.    'value'=>8,
  314.    'max'  =>20
  315.   ),
  316.   'screenshot-lines' =>(object)array(
  317.    'min'  =>1,
  318.    'max'  =>10
  319.   ),
  320.  
  321.   'screenshot-count' =>(object)array(
  322.    'min'  =>20,
  323.    'value'=>20
  324.   ),
  325.  
  326.  );
  327. // Описываем систему взаимодействий
  328.  $equations_array=array(
  329.   (object)array(
  330.    'key1'   =>'({effective-width}+{margin-right})-({screenshot-width}+{margin-right})*{screenshot-per-line}',
  331.    'key2'   =>'0',
  332.    'compare'=>'>='
  333.   ),
  334.  
  335.   (object)array(
  336.    'key1'   =>'({effective-height}+{margin-bottom})-({screenshot-height}+{margin-bottom})*{screenshot-lines}',
  337.    'key2'   =>'0',
  338.    'compare'=>'>='
  339.   ),
  340.  
  341.   (object)array(
  342.    'key1'   =>'{screenshot-count}',
  343.    'key2'   =>'{screenshot-per-line}*{screenshot-lines}',
  344.    'compare'=>'=<'
  345.   ),
  346.   (object)array(
  347.    'key1'   =>'{screenshot-count}',
  348.    'key2'   =>'{screenshot-per-line}*{screenshot-lines}',
  349.    'compare'=>'=>'
  350.   ),
  351.   (object)array(
  352.    'key1'   =>'{screenshot-width}*9/16-{screenshot-height}',
  353.    'key2'   =>'-4',
  354.    'compare'=>'=>'
  355.   ),
  356.   (object)array(
  357.    'key1'   =>'{screenshot-width}*9/16-{screenshot-height}',
  358.    'key2'   =>'4',
  359.    'compare'=>'<='
  360.   ),
  361.  
  362.  );
  363.  
  364.  function getmicrotime(){
  365.   list($usec, $sec) = explode(" ", microtime());
  366.   return ((float)$usec + (float)$sec);
  367.  }
  368.  
  369.  error_reporting(E_ALL);
  370.  echo '<pre>';
  371.  $system=new InequalitySystem($variables, $equations_array);
  372.  $a=getmicrotime();
  373.  $u=$system->solve();
  374.  $b=getmicrotime();
  375.  echo "\r\n=====================\r\nsolve=";var_dump($u);
  376.  echo "\r\n=============================================================================\r\n";
  377.  var_dump($system);
  378.  echo ($b-$a).'s';
  379.  
  380. /*
  381.  echo "\r\n";
  382.  $a=getmicrotime();
  383.  $system->check_speed();
  384.  $b=getmicrotime();
  385.  echo "\r\nspeed: ".($b-$a).'s';
  386. */
  387. ?>
RAW Paste Data