Michał Szymczak

Lead programmer

Wypowiedzi

• Wszystko
• Tylko fora

• 
  Wpis na grupie PHP w temacie Codility - rozwiązania zadań - wyniki

  18.05.2013, 20:54

  Na zyczenie, Beta 2010, rozwiązanie na 100%, zlozonosc O(N).
  Zeby bylo bardziej rozrywkowo, porozdzielalem odpowiedzialnosc na obiekty, wiec mozna sie wgryzac w kod stopniowo. Najwazniejszy trick to metoda countOverlapingDiscs , ktora uwzglednia 'kumulacje' i dzieki temu mamy zlozonosci liniowa. Tak na marginesie na to rozwiazanie w pare minut wpadla moja dziewczyna ktora nie ma pojecia o zlozonosci i programowaniu :D
  
  

  
  
  
  
  function solution($A) {
  
      $plane = new Plane(0, count($A) - 1);
  
      $disc = new Disc($plane);
  
      for ($discCentre = 0; $discCentre <= $plane->getMaxRightPointOnAxis(); $discCentre++) {
  
          $discRadius = $A[$discCentre];
  
          $plane->addDisc(Disc::configureAndGetDisk($disc, $discCentre, $discRadius));
  
      }
  
      return $plane->countOverlapingDiscs();
  
  }
  
  
  
  class Disc {
  
      private $maxRightPointOnAxis;
  
      private $minLeftPointOnAxis;
  
      private $leftRange;
  
      private $rightRange;
  
      public function __construct(Plane $plane) {
  
          $this->maxLeftPointOnAxis = $plane->getMaxLeftPointOnAxis();
  
          $this->maxRightPointOnAxis = $plane->getMaxRightPointOnAxis();
  
      }
  
      public static function configureAndGetDisk($usedDisc, $centre, $radius) {
  
          $usedDisc->leftRange = max($usedDisc->maxLeftPointOnAxis, $centre - $radius);
  
          $usedDisc->rightRange = min($usedDisc->maxRightPointOnAxis, $centre + $radius);
  
          return $usedDisc;
  
      }
  
      public function getLeftRange()
  
      {
  
          return $this->leftRange;
  
      }
  
      public function getRightRange()
  
      {
  
          return $this->rightRange;
  
      }
  
  }
  
  
  
  class Plane {
  
      private $maxRightPointOnAxis;
  
      private $minLeftPointOnAxis;
  
      private $discsBoundaries = array();
  
      public function __construct($maxLeftPointOnAxis, $maxRightPointOnAxis) {
  
          $this->maxLeftPointOnAxis = $maxLeftPointOnAxis;
  
          $this->maxRightPointOnAxis = $maxRightPointOnAxis;
  
      }
  
      public function getMaxLeftPointOnAxis() {
  
          return $this->maxLeftPointOnAxis;
  
      }
  
      public function getMaxRightPointOnAxis() {
  
          return $this->maxRightPointOnAxis;
  
      }
  
      public function addDisc(Disc $disc) {
  
          if (!isset($this->discsBoundaries[$disc->getLeftRange()])) {
  
              $this->discsBoundaries[$disc->getLeftRange()] = array('L' => 0, 'R' => 0);
  
          }
  
          if (!isset($this->discsBoundaries[$disc->getRightRange()])) {
  
              $this->discsBoundaries[$disc->getRightRange()] = array('L' => 0, 'R' => 0);
  
          }
  
          $this->discsBoundaries[$disc->getLeftRange()]['L']++;
  
          $this->discsBoundaries[$disc->getRightRange()]['R']++;
  
      }
  
      public function getSequenceOfBoundaries() {
  
          $boundariesSequence = array();
  
          for ($position = $this->maxLeftPointOnAxis; $position <= $this->maxRightPointOnAxis; $position++) {
  
              if(isset($this->discsBoundaries[$position])) {
  
                  $boundaries = $this->discsBoundaries[$position];
  
                  for($i = 0; $i < $boundaries['L']; $i++) {
  
                      $boundariesSequence[] = 'L';
  
                  }
  
                  for($i = 0; $i < $boundaries['R']; $i++) {
  
                      $boundariesSequence[] = 'R';
  
                  }
  
              }
  
          }
  
          return $boundariesSequence;
  
      }
  
      public function countOverlapingDiscs() {
  
          $sumOfOverlaps = 0;
  
          $maxValue = 10000000;
  
          $defaulValueWhenTooMuchOverlapings = -1;
  
          $discsCumulation = 0;
  
          foreach($this->getSequenceOfBoundaries() as $boundaryType) {
  
              if ('L' === $boundaryType ) {
  
                  $sumOfOverlaps = $sumOfOverlaps + $discsCumulation;
  
                  if ($sumOfOverlaps > $maxValue) {
  
                      return $defaulValueWhenTooMuchOverlapings;
  
                  }
  
                  $discsCumulation++;
  
              } else {
  
                  $discsCumulation--;
  
              }
  
          }
  
          return $sumOfOverlaps;
  
      }
  
  }