Projektowanie stron WWW od podszewki
Losowy artykuł: Wyjątki od reguły

Artykuły na każdy temat

[PHP] Zagadka Einsteina

Dodano 13.02.2017r. o 18:10
W sumie to dawno temu miałem puścić to w obieg lecz jak zwykle brakowało mi czasu przez co leżało odłogiem. Pamiętam, że kiedyś trafiłem na YT materiał przedstawiający zagadnienie i zacząłem szukać. Dla osób nie w temacie polecam zapoznać się z teorią. Podczas szperania w internecie natrafiłem na ciekawą stronę poruszającą miedzy innymi omawiane zagadnienie jednak brakowało przykładu z użyciem PHP stąd uznałem, że w wolnym czasie skonstruuje. Głównie interesowały mnie sprawy wydajności na ile PHP poradzi sobie z metodą brute force przy użyciu permutacji. Przełożyłem pierwotną wersje kodu C++ na PHP i jako tako to wyszło. Ogólnie można to napisać optymalniej jednak kto by się tym przejmował, nie?

Plik index.php wygląda nastepująco:
Kod:
<?php
set_time_limit(0);
require './einstein.class.php';
$einsteins_riddle = new einstein();
$einsteins_riddle -> find_solution();
?>
Natomiast klasa wygląda tak:
Kod:
<?php
class einstein
{
 private $permutations;
 private $nations = ['British''Swedish''Danish''Norvegian''German'];
 private $numbers = ['One''Two''Three''Four''Five'];
 private $colors = ['Red''Green''Blue''White''Yellow'];
 private $drinks = ['Milk''Coffee''Water''Beer''Tea'];
 private $smokes = ['PallMall''Dunhill''Blend''BlueMaster''Prince'];
 private $pets = ['Dog''Cat''Fish''Horse''Bird'];

 function __construct()
 {
  $this -> permutations iterator_to_array($this -> permutations(range(04)));
  $this -> nations array_flip($this -> nations);
 }

 function __destruct()
 {
  // Just kill me
 }

 private function permutations($elements)
 {
  if(count($elements) < 1)
  {
   yield $elements;
  }
  else
  {
   foreach($this -> permutations(array_slice($elements1)) as $permutation)
   {
    foreach(range(0count($elements) - 1) as $i)
    {
     yield array_merge(array_slice($permutation0$i), [$elements[0]], array_slice($permutation$i));
    }
   }
  }
 }

 public function find_solution()
 {
  for($p[0] = 0$p[0] < 120; ++$p[0])
  {
   $number $this -> permutations[$p[0]];

   if($this -> is_possible($number) === true)
   {
    for($p[1] = 0$p[1] < 120; ++$p[1])
    {
     $color $this -> permutations[$p[1]];

     if($this -> is_possible($number$color) === true)
     {
      for($p[2] = 0$p[2] < 120; ++$p[2])
      {
       $drunk $this -> permutations[$p[2]];

       if($this -> is_possible($number$color$drunk) === true)
       {
        for($p[3] = 0$p[3] < 120; ++$p[3])
        {
         $smoke $this -> permutations[$p[3]];

         if($this -> is_possible($number$color$drunk$smoke) === true)
         {

          for($p[4] = 0$p[4] < 120; ++$p[4])
          {
           $pet $this -> permutations[$p[4]];

           if($this -> is_possible($number$color$drunk$smoke$pet) === true)
           {
            $this -> show_solution($number$color$drunk$smoke$pet);
           }
          }

          $pet null;
         }
        }

        $smoke null;
       }
      }

      $drunk null;
     }
    }

    $color null;
   }
  }
 }

 private function is_possible($number null$color null$drink null$smoke null$pet null)
 {
  // Rule #9
  if($number !== null && $this -> numbers[$number[$this -> nations['Norvegian']]] !== 'One')
  {
   return false;
  }

  // Rule #1
  if($color !== null && $this -> colors[$color[$this -> nations['British']]] !== 'Red')
  {
   return false;
  }

  // Rule #3
  if($drink !== null && $this -> drinks[$drink[$this -> nations['Danish']]] !== 'Tea')
  {
   return false;
  }

  // Rule #13
  if($smoke !== null && $this -> smokes[$smoke[$this -> nations['German']]] !== 'Prince')
  {
   return false;
  }

  // Rule #2
  if($pet !== null && $this -> pets[$pet[$this -> nations['Swedish']]] !== 'Dog')
  {
   return false;
  }

  if($number === null || $color === null || $drink === null || $smoke === null || $pet === null)
  {
   return true;
  }

  for($p[0] = 0$p[0] < 5; ++$p[0])
  {
   // Rule #5
   if($this -> colors[$color[$p[0]]] === 'Green' && $this -> drinks[$drink[$p[0]]] !== 'Coffee')
   {
    return false;
   }

   // Rule #6
   if($this -> smokes[$smoke[$p[0]]] === 'PallMall' && $this -> pets[$pet[$p[0]]] !== 'Bird')
   {
    return false;
   }

   // Rule #7
   if($this -> colors[$color[$p[0]]] === 'Yellow' && $this -> smokes[$smoke[$p[0]]] !== 'Dunhill')
   {
    return false;
   }

   // Rule #8
   if($this -> numbers[$number[$p[0]]] === 'Three' && $this -> drinks[$drink[$p[0]]] !== 'Milk')
   {
    return false;
   }

   // Rule #12
   if($this -> smokes[$smoke[$p[0]]] === 'BlueMaster' && $this -> drinks[$drink[$p[0]]] !== 'Beer')
   {
    return false;
   }

   // Rule #14
   if($this -> colors[$color[$p[0]]] === 'Blue' && $this -> numbers[$number[$p[0]]] !== 'Two')
   {
    return false;
   }

   for($p[1] = 0$p[1] < 5; ++$p[1])
   {
    // Rule #4
    if($this -> colors[$color[$p[0]]] === 'Green' && $this -> colors[$color[$p[1]]] === 'White' && $number[$p[1]] - $number[$p[0]] !== 1)
    {
     return false;
    }

    $different $number[$p[0]] - $number[$p[1]];

    if($different 0)
    {
     $different = -$different;
    }

    // Rule #10
    if($this -> smokes[$smoke[$p[0]]] === 'Blend' && $this -> pets[$pet[$p[1]]] === 'Cat' && $different !== 1)
    {
     return false;
    }

    // Rule #11
    if($this -> pets[$pet[$p[0]]] === 'Horse' && $this -> smokes[$smoke[$p[1]]] === 'Dunhill' && $different !== 1)
    {
     return false;
    }

    // Rule #15
    if($this -> smokes[$smoke[$p[0]]] === 'Blend' && $this -> drinks[$drink[$p[1]]] === 'Water' && $different !== 1)
    {
     return false;
    }
   }
  }

  return true;
 }

 private function show_solution($number$color$drunk$smoke$pet)
 {
  header('Content-Type: text/plain; charset=utf-8');
  echo 'Found a solution:'.PHP_EOL;
  $this -> print_array('Nation'array_flip($this -> nations), range(04));
  $this -> print_array('Number'$this -> numbers$number);
  $this -> print_array('Color'$this -> colors$color);
  $this -> print_array('Drunk'$this -> drinks$drunk);
  $this -> print_array('Smoke'$this -> smokes$smoke);
  $this -> print_array('Pet'$this -> pets$pet);
 }

 private function print_array($label$names$data)
 {
  printf('%-12s%-12s%-12s%-12s%-12s%-12s'.PHP_EOL$label.':'$names[$data[0]], $names[$data[1]], $names[$data[2]], $names[$data[3]], $names[$data[4]]);
 }
}
?>

Komentarze

Brak komentarzy

Dodaj komentarz

Zostaw komentarz jeżeli możesz! Nie bądź przysłowiowym botem! Nie bądź obojętny! Ciebie to nic nie kosztuje, a mi sprawi uśmiech na twarzy.
Zezwolono używać: BBCode
Zabroniono używać:
znaczników HTML

(Wymagany)

(Wymagany, niepublikowany)

(Nie wymagana)

Token:

Obrazek dla bota

(Przepisz tylko cyfry!)

(Wymagana)