Guest User

PT-terrenito.php

a guest
Nov 23rd, 2014
179
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