Programando sobre el terreno

Dificultad: Media

Este problema está inspirado en una propuesta de este mismo año en la Olimpiada Informática Croata para alumnos de bachillerato. El problema debe ejecutarse en menos de 1 segundo para todos los casos de prueba ¿Puede un estudiante o titulado en ingeniería ser capaz de resolver este problema en 2 horas?

Contexto

Deseamos adquirir una finca para construir una casa. Puesto que ya no quedan terrenos buenos en España a un precio razonable, hemos decidido adquirir un terreno irregular en una montaña ya que son más baratos. Hemos encontrado varios terrenos rectangulares que pueden encajar en lo que buscamos, pero no podemos modificar la altura del mismo ni añadiendo ni quitando tierra. Por tanto debemos conformarnos con la estructura del terreno y decidir para cada uno de ellos cómo colocar nuestra casa.

Disponemos del mapa de cada terreno, dibujado como una cuadrícula en la que cada casilla representa un espacio de 100 metros cuadrados. Para cada casilla disponemos de la altura en metros de ese terreno. Queremos que la planta de la casa sea rectangular, pudiendo ocupar uno o más espacios contiguos. A modo de ejemplo mostramos un mapa de un terreno en el que coloreamos dos lugares donde es posible construir una casa de 200 y otra de 400 metros cuadrados.

Queremos en primer término calcular el número total de formas diferentes en el que podemos construir una casa para un terreno dado. Así para el ejemplo anterior podemos construir una casa de 27 formas diferentes.

Reconocimiento

Podrás enviar tu solución haciendo uso del formulario de abajo para que la compruebe personalmente. Puedes enviarlo todo en un archivo zip, aunque lo más recomendable es hacer uso de Git/SVN para evitar el envío de archivos y poder actualizar el código en caso de encontrar errores sin necesidad de realizar reenvíos. Es importante que además comentes tu solución en los comentarios y ofrezcas tu código de forma abierta. A cambio recibirás un badge de Credly que reconocerá tu esfuerzo y pericia.

Además y a fin de poder discutir algunos aspectos interesantes del mantenimiento del software, este problema evolucionará con nuevos requisitos a fin de ayudarnos a encontrar la mejor parcela para nuestra casa. Propondré una evolución por cada respuesta a este mensaje así que animaos a intentar resolver este problema y así desbloquear nuevos niveles 😉

Usted debe estar logueado para enviar un post.

Interfaces y pruebas

A continuación se ofrece el marco para desarrollar la solución en lenguaje Java. En este problema pretende que se saque partido de las estructuras de datos que ofrece Java, pudiéndose si se estima necesario crear otras clases auxiliares que ayuden a la resolución del problema.

Se ofrece una interfaz del problema que habrá que implementar para su resolución. Se aporta un fichero de JUnit 4 que deberán utilizarse como ejemplo para comprobar que la solución es correcta al menos para los casos definidos y que apoya el seguimiento de un desarrollo dirigido por pruebas. Por último, se ofrece un lanzador de pruebas (Test Runner) para aquellos que no utilicen un entorno de desarrollo que integre las pruebas de JUnit 4 en su interfaz.

En esta ocasión he introducido pruebas parametrizadas de JUnit, que permite definir varias pruebas que únicamente se diferencian en los parámetros de entrada de una forma sencilla (ver el método data para más detalle). Se recomienda que además de las pruebas facilitadas, se intente desarrollar otras pruebas antes de la resolución del problema.

Interfaz del problema

package problems.terrain;

public interface ITerrainProblem {
	/*
	 * This method sets the input data for the problem.
	 * @param map a bidimensional array that represents the height at any point in the terrain.
	 * @throws IllegalArgumentException if the map is null or the map has a shape different than a rectangle. 
	 */
	public abstract void setData(Integer[][] map);
	
	/*
	 * Executes the problem if the data has been correctly set
	 */
	public abstract void run();
	
	/*
	 * @return the number of possible places where the house could be built upon.
	 * It return null if the problem has not been solved yet.
	 */
	public abstract Integer getResult();
}

Prueba JUnit

package problems.terrain;

import java.util.Arrays;
import java.util.Collection;

import org.junit.Assert;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.Parameterized;
import org.junit.runners.Parameterized.Parameters;

@RunWith(Parameterized.class)
public class TerrainTest {
	ITerrainProblem terrainProblem;
	Integer [][] map;
	Integer expectedResult;
	
	
	public TerrainTest (Integer [][] map, Integer expectedResult) {
			this.map = map;
			this.expectedResult = expectedResult;
	}
	
	 // creates the test data
	@Parameters
	public static Collection<Object[]> data() {
		Integer[][] map1 = new Integer [][] {{2,2,2},{2,2,1},{1,1,1},{2,1,2},{1,2,1}};
		Integer[][] map2 = new Integer [][] {{1,1,1},{1,1,1},{2,2,2},{2,2,2}};
		Integer[][] map3 = new Integer [][] {{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},{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},{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},{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},{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},{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},{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},{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},{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},{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},{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},{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},{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},{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},{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},{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},{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},{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},{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},{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},{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},{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},{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},{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},{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},{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},{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},{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},{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},{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},{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},{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},{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},{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},{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},{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},{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},{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},{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},{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},{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},{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},{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},{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},{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},{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},{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},{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},{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},{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}};
		
		Object[][] data = new Object[][] { 	{map1,27}, {map2,36}, {map3,3071} };
						

	    return Arrays.asList(data);
	  }

	
	@Test(timeout=1000)
	public void testContactProblem() {
		terrainProblem = new TerrainProblem();
		terrainProblem.setData(map);
		terrainProblem.run();
		Integer result = terrainProblem.getResult();
		// checks if the mappings are equal.
		Assert.assertEquals("Map: " + map
							, expectedResult, result );
	}
}

Test runner

package problems.terrain;

import org.junit.runner.JUnitCore;
import org.junit.runner.Result;
import org.junit.runner.notification.Failure;

public class TestRunner {
   public static void main(String[] args) {
      Result result = JUnitCore.runClasses(TerrainTest.class);
      for (Failure failure : result.getFailures()) {
         System.out.println(failure.toString());
      }
      if(result.wasSuccessful())
    	 System.out.println("All tests passed!");;
   }
}  

Pablo Trinidad 23 noviembre, 2014

Posted In: Aprendiendo algoritmia, Tecnologería