daily pastebin goal
65%
SHARE
TWEET

PT-terrenito.php

a guest Nov 23rd, 2014 170 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. <?php
  2.  
  3. class Terrenito {
  4.  
  5.         private $terreno = NULL;
  6.         private $width = NULL;
  7.         private $height = NULL;
  8.  
  9.         private function load ($a) {
  10.                 // $a -> array de entrada
  11.                
  12.                 if (!is_array($a)) return false;               
  13.                
  14.                 $this->terreno = array_values($a);
  15.                
  16.                 if (!is_array($this->terreno[0])) return false;
  17.                
  18.                 $this->height = count($a);
  19.                 $this->width = count($this->terreno[0]);
  20.  
  21.                 if ($this->height == 0 || $this->width == 0) return false;
  22.                
  23.                 for ($n = 1; $n != $this->height; $n++) {
  24.                         if (!is_array($this->terreno[$n])) return false;
  25.                        
  26.                         $this->terreno[$n] = array_values($this->terreno[$n]);
  27.                        
  28.                         if (count($this->terreno[$n]) != $this->width) return false;
  29.                
  30.                 }
  31.        
  32.                 return true;
  33.         }
  34.  
  35.         private function countWays ($x, $y) {
  36.        
  37.                 // Return the amount of ways you can place a house with the top left corner at $x, $y.
  38.                
  39.                 $combinationCount = 0; // aquí las contamos
  40.                
  41.                 $myVal = $this->terreno[$y][$x];
  42.                
  43.                 // Obtener la extensión en vertical del mismo valor.
  44.                
  45.                 for ($n = $y+1; $n != $this->height; $n++)
  46.                         if ($this->terreno[$n][$x] != $myVal) break;
  47.                        
  48.                 // La zona con valor myVal es de ($x, $y) a ($x, $n-1)
  49.                
  50.                 $maxY = $n-1; // ie. de $x,$y a $x, $maxY.
  51.                
  52.                 $xWidth = $this->width; // aquí vamos a ir guardando el número de casillas en horizontal que
  53.                                         // repiten el valor buscado, con un límite máximo del número encontrado
  54.                                         // para la fila anterior; inicializamos al valor máximo para la primera
  55.                                         // pasada
  56.                
  57.                 for ($n = $y; $n <= $maxY; $n++) { // para cada fila de las posibles
  58.                
  59.                         // encontrar el número de casillas en horizontal que repiten el valor buscado, con el límite
  60.                         // del valor de la fila anterior. es decir, el ancho del mayor rectángulo que cabe ocupando las filas
  61.                         // $y a $n
  62.                        
  63.                         for ($m = $x+1, $xCount = 1; $m != $this->width; $m++,$xCount++) {
  64.                                 if ($this->terreno[$n][$m] != $myVal || $xCount >= $xWidth) break;
  65.                         }
  66.                
  67.                         $xWidth = $xCount;
  68.                         $combinationCount += $xCount;
  69.                 }
  70.        
  71.                 return $combinationCount;
  72.        
  73.         }
  74.        
  75.  
  76.         public function __construct ($a) {
  77.                 if (!$this->load($a)) {
  78.                         $this->terreno = NULL;
  79.                         $this->width = NULL;
  80.                         $this->height = NULL;
  81.                         return false;
  82.                 }
  83.        
  84.        
  85.                 return true;
  86.        
  87.         }
  88.        
  89.         public function solve() {
  90.        
  91.                 $count = 0;
  92.        
  93.                 for ($x = 0; $x != $this->width; $x++)
  94.                         for ($y = 0; $y != $this->height; $y++)
  95.                                 $count += $this->countWays($x,$y);
  96.        
  97.                 return $count;
  98.         }
  99.  
  100. }
  101.  
  102. // -------- tests
  103.  
  104. $unitTests = array(
  105.         [[2,2,2],
  106.         [2,2,1],
  107.         [1,1,1],
  108.         [2,1,2],
  109.         [1,2,1]],
  110.        
  111.         [[1,1,1],
  112.         [1,1,1],
  113.         [2,2,2],
  114.         [2,2,2]],
  115.        
  116.         [[4,5,10,9,2,7,7,9,2,7,6,4,8,9,4,3,9,10,8,1,8,5,5,3,6,1,4,2,1,4,4,10,4,9,9,9,5,5,3,1,7,1,8,5,6,6,6,3,9,3],
  117.         [10,7,9,9,4,6,9,2,3,4,1,1,2,10,8,9,6,6,3,7,1,9,5,9,10,2,2,5,8,2,7,2,5,3,6,7,8,6,8,3,3,9,10,2,3,7,5,1,9,5],
  118.         [8,7,2,1,2,5,1,4,8,9,5,10,9,10,3,3,4,6,7,4,9,9,8,6,8,7,3,5,9,5,7,2,7,6,10,5,3,9,5,10,5,2,5,2,9,10,4,1,5,4],
  119.         [2,6,8,3,9,1,7,6,10,2,5,3,5,3,9,8,6,6,7,2,5,5,6,10,9,2,5,1,2,3,3,9,10,10,8,4,10,7,10,9,7,4,10,10,10,2,1,1,10,2],
  120.         [3,7,1,10,10,3,2,8,4,9,10,8,10,1,4,2,10,3,10,2,3,1,3,3,10,6,4,3,10,2,1,9,10,2,3,6,10,5,3,1,4,3,10,8,9,1,3,3,1,5],
  121.         [2,9,1,5,10,4,2,9,9,8,7,3,3,2,8,5,6,6,5,6,7,7,4,3,10,9,8,7,6,3,7,2,5,6,9,1,2,5,8,2,6,4,7,4,6,8,7,1,3,6],
  122.         [7,5,5,9,2,4,10,4,3,8,7,7,7,4,9,4,3,7,5,4,1,9,5,6,9,10,5,4,1,2,5,9,1,6,5,4,9,4,3,1,7,9,9,4,8,9,10,5,9,5],
  123.         [1,9,4,8,1,10,10,9,6,7,1,7,3,10,2,2,10,4,5,3,1,8,6,3,2,6,5,9,3,8,6,8,5,1,7,6,5,5,7,10,2,5,7,3,10,7,3,7,1,7],
  124.         [9,3,3,7,2,1,4,2,7,3,3,8,3,1,9,6,8,5,10,5,10,7,4,7,7,3,7,2,2,9,7,3,10,4,7,1,9,1,7,6,5,6,3,9,3,6,1,4,2,9],
  125.         [9,9,8,4,2,4,4,2,9,7,7,2,9,4,5,8,5,4,6,10,3,4,3,7,7,5,5,5,8,2,8,1,7,7,7,4,3,3,7,6,6,10,8,9,10,2,1,10,4,8],
  126.         [10,8,6,10,10,10,6,1,6,7,3,7,2,10,7,10,3,7,7,6,2,3,8,3,8,1,10,5,5,6,2,9,2,7,2,9,4,10,4,10,2,5,9,9,6,5,2,4,6,7],
  127.         [5,1,7,9,6,7,5,8,6,10,2,2,8,2,8,2,5,9,5,5,1,3,7,5,5,6,10,7,4,10,10,1,7,8,9,3,3,3,10,8,6,3,1,2,3,8,3,8,4,9],
  128.         [1,4,4,1,5,4,10,4,2,6,4,5,9,7,7,4,5,8,10,8,3,7,1,5,6,1,9,2,8,4,1,7,9,2,8,2,4,9,6,5,8,3,5,10,5,3,4,8,3,1],
  129.         [8,7,8,1,2,1,1,1,8,1,9,4,2,2,3,2,9,10,5,1,4,7,4,2,4,9,9,1,6,1,1,4,7,6,9,10,8,1,6,4,4,5,6,1,6,8,9,3,4,8],
  130.         [5,3,6,5,10,6,6,2,4,1,1,8,3,9,8,9,7,6,7,10,4,4,1,7,6,4,2,3,10,8,10,9,2,10,9,4,3,5,9,2,7,4,9,9,1,10,10,8,10,8],
  131.         [5,1,2,3,10,2,4,6,6,5,10,6,10,8,4,2,3,10,10,9,5,2,8,8,9,10,9,5,8,3,3,9,6,6,7,9,9,2,10,1,4,8,10,8,5,6,8,1,2,1],
  132.         [1,6,9,3,5,10,2,3,6,4,8,4,9,10,10,10,10,7,5,2,3,5,3,8,1,10,7,9,6,4,2,4,2,3,4,2,6,4,8,5,2,8,8,1,7,9,2,5,1,2],
  133.         [2,8,4,4,6,3,10,5,1,6,10,2,5,8,4,9,5,5,8,5,10,9,10,3,2,5,5,6,1,4,3,5,1,8,10,5,9,8,7,10,2,10,5,2,7,8,7,8,7,5],
  134.         [3,8,7,5,1,4,4,6,9,7,2,7,1,3,5,8,2,6,2,5,7,9,1,6,2,4,4,9,8,9,3,2,6,9,7,6,9,2,4,8,9,1,5,1,3,3,8,1,6,9],
  135.         [3,1,7,7,8,6,7,1,6,6,1,1,2,5,10,2,3,10,5,5,2,8,10,4,8,10,6,9,6,7,5,3,3,6,9,1,2,5,5,3,8,7,2,5,10,9,2,10,5,6],
  136.         [5,1,5,2,1,7,9,5,1,10,2,4,10,4,6,7,4,8,8,3,9,4,3,2,10,9,2,5,1,10,10,5,3,7,9,5,4,7,7,1,3,6,8,9,6,2,2,9,4,3],
  137.         [1,2,4,9,6,1,5,10,7,8,2,5,3,3,9,10,5,8,8,6,7,10,9,4,3,4,4,5,6,5,3,1,3,4,6,2,5,9,10,1,7,10,10,1,3,7,1,1,8,6],
  138.         [8,10,4,9,8,10,5,5,4,6,5,5,5,6,2,10,3,10,7,7,2,3,3,9,1,10,8,6,6,9,3,7,5,3,1,6,8,7,6,8,3,8,1,8,1,9,7,5,3,2],
  139.         [9,3,5,7,7,1,2,6,4,8,10,7,9,3,10,2,1,7,5,4,7,8,7,3,9,2,5,2,6,6,3,9,2,7,9,1,8,8,4,10,6,7,3,3,5,10,4,7,4,10],
  140.         [1,6,5,4,2,5,9,10,2,8,1,4,3,4,8,7,3,5,2,3,2,4,9,3,4,7,1,3,7,1,9,6,5,10,4,9,3,8,10,10,5,5,1,5,5,10,4,7,8,7],
  141.         [4,5,6,1,6,10,2,4,6,1,4,2,8,3,6,2,4,1,10,2,8,9,3,9,1,7,9,3,2,2,3,2,5,5,10,10,2,5,6,7,10,10,4,1,2,10,7,4,7,5],
  142.         [4,5,4,7,3,3,8,5,10,2,4,1,5,8,3,3,5,5,7,7,9,6,9,7,10,9,4,1,6,1,8,2,5,1,9,10,5,10,6,4,5,5,5,5,6,4,6,10,4,6],
  143.         [5,6,4,6,4,10,7,2,3,6,4,2,6,3,4,5,9,3,9,1,7,4,10,8,4,5,10,4,2,6,10,8,10,1,3,1,10,1,7,1,1,9,10,1,9,8,8,1,9,2],
  144.         [2,4,8,8,1,3,1,1,7,6,2,3,6,6,8,3,1,2,8,9,7,6,6,8,6,3,3,5,1,7,3,1,1,4,7,6,2,5,4,9,4,9,2,7,5,8,7,8,8,8],
  145.         [10,3,5,2,3,9,5,7,10,8,5,9,4,2,8,1,7,5,6,3,6,10,6,6,8,8,3,3,6,1,5,6,6,6,6,4,3,3,9,3,1,5,8,4,10,1,3,7,8,1],
  146.         [5,9,5,3,3,3,3,3,5,10,3,9,2,5,9,4,8,9,6,5,7,6,5,7,8,6,3,6,1,7,2,3,3,4,5,8,6,1,1,9,10,9,1,5,5,8,5,2,5,9],
  147.         [4,8,9,3,9,6,9,6,4,2,2,3,5,3,7,8,10,7,4,7,8,3,5,9,2,10,8,5,4,5,9,3,2,5,9,10,2,1,2,7,4,9,1,8,6,7,3,2,10,1],
  148.         [5,9,7,10,6,2,3,3,2,5,8,3,6,7,10,2,1,7,2,1,5,7,8,1,1,7,3,3,6,3,8,9,1,3,1,6,3,4,9,2,1,1,9,3,1,3,4,6,4,7],
  149.         [5,8,6,2,1,10,10,3,9,9,5,9,6,5,10,10,8,4,5,9,3,10,9,10,4,10,3,6,10,3,2,4,9,9,2,5,7,2,6,4,6,10,4,9,4,6,6,7,1,2],
  150.         [5,10,8,6,7,6,2,3,9,7,8,3,6,10,7,3,10,8,8,2,7,1,7,10,1,7,5,10,7,1,7,1,9,8,7,8,1,9,5,10,2,9,8,8,5,6,6,9,3,7],
  151.         [7,10,6,9,7,5,4,10,4,6,3,2,10,3,5,2,4,6,9,6,8,1,7,3,4,3,5,6,3,2,3,4,7,1,5,4,9,2,4,6,4,7,2,10,4,1,5,5,7,5],
  152.         [6,4,8,5,2,8,1,6,4,4,3,5,6,3,1,5,9,1,4,10,2,3,7,2,7,7,1,9,4,2,3,9,8,5,4,10,7,1,2,9,10,8,3,5,2,6,7,3,4,2],
  153.         [5,2,3,1,2,8,8,10,5,7,6,4,3,5,6,1,10,6,7,5,8,10,1,4,8,3,10,3,4,3,1,4,6,1,10,1,4,8,7,9,3,4,9,4,1,3,4,8,3,9],
  154.         [2,6,4,6,1,10,6,3,2,5,6,9,10,4,1,6,7,7,8,8,7,4,7,9,7,1,10,5,4,4,8,9,3,6,3,9,9,8,8,5,5,7,2,1,10,2,9,1,2,3],
  155.         [8,8,8,9,3,5,3,7,5,6,4,1,9,3,2,4,4,7,3,4,6,5,8,6,10,1,6,1,9,4,10,8,7,5,9,6,10,4,1,6,9,8,2,9,7,1,1,7,5,5],
  156.         [3,10,8,8,3,1,2,7,7,4,6,3,10,3,9,1,4,8,1,4,8,4,5,10,3,5,3,7,2,10,1,2,3,7,4,1,8,4,4,1,9,1,5,2,3,2,1,1,3,9],
  157.         [3,5,6,8,1,1,3,10,6,10,2,4,1,4,7,5,10,8,9,3,1,7,2,3,5,5,4,5,3,3,3,7,7,8,6,1,7,8,3,1,7,8,10,10,8,6,9,8,8,1],
  158.         [9,3,4,6,1,3,4,9,7,9,5,5,9,9,6,9,8,7,3,9,9,4,9,5,7,5,10,3,7,2,9,4,10,6,3,3,7,5,7,7,5,8,1,7,9,4,2,2,2,3],
  159.         [2,5,1,3,10,10,3,1,7,8,7,9,2,9,2,3,9,8,1,9,8,6,9,6,7,3,5,10,7,10,3,7,9,10,10,10,1,7,1,8,8,8,1,1,6,4,2,4,3,1],
  160.         [7,9,1,6,9,6,4,8,6,5,10,10,8,7,5,1,9,4,3,3,3,5,7,2,3,6,8,7,7,4,2,6,6,5,7,10,1,10,9,3,1,7,7,10,1,2,3,7,7,10],
  161.         [4,9,6,10,1,3,7,10,10,10,10,2,9,10,8,6,5,9,4,7,7,4,7,1,5,4,2,3,5,5,2,2,4,1,5,2,6,9,7,7,9,9,10,1,4,9,2,3,1,8],
  162.         [9,4,8,9,2,6,1,10,10,4,6,2,10,3,8,9,3,7,3,3,5,6,10,3,4,3,5,8,5,7,1,4,10,8,5,2,5,4,10,4,5,9,2,3,5,9,2,9,3,7],
  163.         [9,5,7,8,1,8,4,7,1,4,3,8,10,2,7,9,5,7,5,5,3,9,3,3,3,5,5,9,10,7,10,5,6,10,3,9,7,5,4,5,1,10,9,5,7,4,3,2,4,4],
  164.         [10,2,5,6,5,4,10,10,10,7,9,1,7,7,6,1,2,7,8,7,2,1,3,3,8,1,7,6,2,7,3,7,6,6,5,1,2,5,3,4,5,2,7,5,10,6,7,5,3,9],
  165.         [10,8,7,1,3,8,2,10,4,6,9,6,7,10,7,9,9,10,5,9,4,5,4,10,5,3,8,4,1,2,10,7,4,3,4,8,9,6,4,10,10,2,9,10,5,1,5,7,10,7]]
  166. );
  167.  
  168. $unitTestResults = array(27,36,3071);
  169.  
  170. $numTests = count($unitTests);
  171.  
  172. for ($n=0;$n!=$numTests;$n++) {
  173.         echo "test ". ($n+1).": valor esperado = {$unitTestResults[$n]}, valor obtenido = ";
  174.         $runner = new Terrenito($unitTests[$n]);
  175.         $result = $runner->solve();
  176.        
  177.         echo $result . " - ";
  178.         if ($result == $unitTestResults[$n]) echo "PASADO\n";
  179.         else echo "ERROR\n";
  180.  
  181. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top