Guest User

PT-terrenito.php

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

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×