[PHP] Zagadka Einsteina

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(0, 4)));
  $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($elements, 1)) as $permutation)
   {
    foreach(range(0, count($elements) - 1) as $i)
    {
     yield array_merge(array_slice($permutation, 0, $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(0, 4));
  $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

Dodaj komentarz

Zezwolono używać: BBCode
Zabroniono używać: znaczników HTML

Podpis: (Wymagany)

E-mail: (Wymagany, niepublikowany)

Strona WWW: (Nie wymagana)

Token:

Treść tokena: (Przepisz tylko cyfry!)

Treść: (Wymagana)

Tagi

php webmaster webmastering programowanie strony ciekawostka www tutorial porada example artykul rada projektowanie przetwarzanie zagadka eistaina zebra puzzle permutacja permutation