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.
| 2 | 2 | 2 |
| 2 | 2 | 1 |
| 1 | 1 | 1 |
| 2 | 1 | 2 |
| 1 | 2 | 1 |
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
Luces de Navidad
Dificultad: Media
Hoy propongo un nuevo problema por indicación de mi amigo CP, que como sabiamente indica necesita de un análisis previo del problema a resolver antes de lanzarse a la piscina de la fuerza bruta. Este problema fue propuesto en el año 1998 en la Olimpiada Informática Internacional de Setúbal para alumnos de bachillerato. ¿Puede un estudiante o titulado en ingeniería ser capaz de resolver este problema en 2 horas?
Contexto
La Navidad está a la vuelta de la esquina y estamos colocando la tradicional iluminación en la fachada de casa. Hemos instalado una tira de luces LED, numeradas de 1 a N con un mando de control con 4 botones:
- Botón 1. Al pulsar este botón todas las luces cambian su estado (de encendido a apagado, o de apagado a encendido).
- Botón 2. Al pulsar este botón todas las luces impares cambian su estado.
- Botón 3. Al pulsar este botón todas las luces pares cambian su estado.
- Botón 4. Al pulsar este botón, las luces de la secuencia 3k+1 (con k≥0) cambian su estado. Es decir, las luces 1, 4, 7, 10,... cambiarán su estado.
En la configuración inicial de la tira de luces, todas las luces están encendidas. Tenemos un contador que registra el número total de veces que pulsamos un botón. Tenemos como objetivo alcanzar una configuración donde 0, 1 o 2 luces concretas estén encendidas y otras tantas apagadas. Debemos diseñar un algoritmo que nos indique todas las configuraciones de luces que cumplan con nuestro objetivo y que podemos alcanzar con un número determinado de pulsaciones de alguno de los 4 botones.
Así por ejemplo, para una tira de 10 luces y con 1 pulsación permitida, podemos alcanzar estas 4 configuraciones:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
| Configuración inicial | ● | ● | ● | ● | ● | ● | ● | ● | ● | ● |
| Botón 1 | ○ | ○ | ○ | ○ | ○ | ○ | ○ | ○ | ○ | ○ |
| Botón 2 | ○ | ● | ○ | ● | ○ | ● | ○ | ● | ○ | ● |
| Botón 3 | ● | ○ | ● | ○ | ● | ○ | ● | ○ | ● | ○ |
| Botón 4 | ○ | ● | ● | ○ | ● | ● | ○ | ● | ● | ○ |
Si buscamos una configuración en la que la luz nº 7 esté apagada, debemos obtener como resultado del algoritmo las configuraciones resultantes de pulsar el botón 1, 2 ó 4.
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.
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.
Si desarrolláis soluciones o encontráis problemas, podéis enviar un comentario o bien un correo electrónico.
Interfaz del problema
package problems.lights;
import java.util.Collection;
public interface ILightsProblem {
/*
* This method sets the input data for the problem.
* @param numberOfLights the number of lights in the strip.
* @param numberOfPresses the number of times the buttons are pressed.
* @param onLights a list of 0, 1 or 2 integer numbers indicating the lights that must be ON at the end (ligths are numbered from 1 to numberOfLights)
* @param offLights a list of 0, 1 or 2 integer numbers indicating the lights that must be OFF at the end (ligths are numbered from 1 to numberOfLights)
* @throws IllegalArgumentException if any of the integer input parameters are zero or negative,
* the maxLength is less than the minLength or the message is null.
*/
public abstract void setData(int numberOfLights, int numberOfPresses, Integer[] onLights, Integer[] offLights);
/*
* Executes the problem if the data has been correctly set
*/
public abstract void run();
/*
* @return a collection of lights configuration that satisfy the on/off constraints specified by onLights and offLights
* It return null if the problem has not been solved yet.
*/
public abstract Collection<Boolean[]> getResult();
}
Prueba JUnit
package problems.lights;
import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;
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 LightsTest {
ILightsProblem lightsProblem;
int numberOfLights, numberOfPresses;
Integer [] onLights, offLights;
Collection<Boolean[]> expectedResult;
public LightsTest (int numberOfLights, int numberOfPresses, Integer [] onLights, Integer [] offLights, Collection<Boolean[]> expectedResult) {
this.numberOfLights = numberOfLights;
this.numberOfPresses = numberOfPresses;
this.onLights = onLights;
this.offLights = offLights;
this.expectedResult = expectedResult;
}
// creates the test data
@Parameters
public static Collection<Object[]> data() {
Collection<Boolean[]> result1 = new LinkedList<Boolean[]> () {{ add(new Boolean[] {false,false,false,false,false,false,false,false,false,false});
add(new Boolean[] {false,true ,false,true ,false,true ,false,true ,false,true });
add(new Boolean[] {false,true ,true ,false,true ,true ,false,true ,true ,false});
add(new Boolean[] {true ,false,true ,false,true ,false,true ,false,true ,false});
}};
Collection<Boolean[]> result2 = new LinkedList<Boolean[]> () {{ add(new Boolean[] {false,false,false,false,false,false,false,false,false,false});
add(new Boolean[] {false,true ,false,true ,false,true ,false,true ,false,true });
add(new Boolean[] {false,true ,true ,false,true ,true ,false,true ,true ,false});
}};
Collection<Boolean[]> result3 = new LinkedList<Boolean[]> () {{ add(new Boolean[] {false,true,true,false,true,true,false,true,true,false,true,true,false,true,true,false,true,true,false,true,true,false,true,true,false,true,true,false,true,true,false,true,true,false,true,true,false,true,true,false,true,true,false,true,true,false,true,true,false,true,true,false,true,true,false,true,true,false,true,true,false,true,true,false,true,true,false,true,true,false});
add(new Boolean[] {true,false,true,false,true,false,true,false,true,false,true,false,true,false,true,false,true,false,true,false,true,false,true,false,true,false,true,false,true,false,true,false,true,false,true,false,true,false,true,false,true,false,true,false,true,false,true,false,true,false,true,false,true,false,true,false,true,false,true,false,true,false,true,false,true,false,true,false,true,false});
}};
Object[][] data = new Object[][] { {10,1,new Integer[] {},new Integer[] {},result1},
{10,1,new Integer[] {},new Integer[] {7},result2},
{70,99999,new Integer[] {51},new Integer[] {4},result3}};
return Arrays.asList(data);
}
@Test
public void testContactProblem() {
lightsProblem = new LightsProblem();
lightsProblem.setData(numberOfLights,numberOfPresses,onLights,offLights);
lightsProblem.run();
Collection<Boolean[]> result = lightsProblem.getResult();
// checks if the mappings are equal.
Assert.assertEquals("lights: ["+numberOfLights+"], presses:["+numberOfPresses+"]: "
, expectedResult.size(), result.size() );
// now we check that the values are correct for every key
for (Boolean[] resultArray: result) {
boolean exists = false;
Iterator<Boolean[]> itb = expectedResult.iterator();
while(itb.hasNext() && !exists) {
Boolean[] expectedArray = itb.next();
Assert.assertEquals("lights: ["+numberOfLights+"], presses:["+numberOfPresses+"]: ", expectedArray.length, resultArray.length);
exists = true;
for (int pos = 0; pos < expectedArray.length && exists; pos++)
if (expectedArray[pos] != resultArray[pos])
exists = false;
}
Assert.assertTrue("lights: ["+numberOfLights+"], presses:["+numberOfPresses+"]: ", exists);
}
}
}
Test runner
package problems.lights;
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(LightsTest.class);
for (Failure failure : result.getFailures()) {
System.out.println(failure.toString());
}
if(result.wasSuccessful())
System.out.println("All tests passed!");;
}
}
Pablo Trinidad 8 noviembre, 2014
Posted In: Aprendiendo algoritmia, Tecnologería
Señales y patrones: el debate
Atención: No leer sin antes haber realizado el problema "señales y patrones".
En busca de la solución
Seguramente la dificultad media del problema de "señales y patrones" haya supuesto un plus de motivación para los que os enfrentásteis a problemas anteriores. Sin embargo es muy probable que os haya parecido más sencillo que problemas anteriores. Y es que este problema no ha envejecido bien. En los años 90, la manipulación de estructuras de datos era uno de los problemas que normalmente se resolvían desde cero. Era frecuente que los programadores fueran desarrollando sus propias bibliotecas que manipularan cadenas, listas, conjuntos, etc. En la actualidad esta funcionalidad ya viene ofrecida de serie en la mayoría de los lenguajes orientados a objetos. Esto hace que con muy poco esfuerzo podamos ofrecer una solución a este problema que en otro tiempo nos hubiera consumido más energías.
A pesar de esta simplificación tan enorme del problema de trabajar con estructuras de datos complejas, el soporte ofrecido por las bibliotecas estándar para la manipulación, búsqueda y filtrado de información casi siempre ha sido escaso. Últimamente y a raíz de la moda de crear lenguajes específicos de dominio (en inglés, DSLs) se han diseñado APIs que permiten la manipulación de datos desde código.
Un DSL, es un lenguaje que se diseña para construir aplicaciones para un dominio muy concreto, en contraposición a los lenguajes de propósito general como Java o C que permiten crear múltiples tipos de aplicaciones. Tal vez el DSL más utilizado en la actualidad sea el lenguaje de consultas SQL. Para cualquier persona que sepa un mínimo de inglés puede resultar muy natural el lenguaje utilizado, que facilita la comprensión del código fuente escrito. Existen otros lenguajes como pueden ser ANTLR, que genera parsers capaces de interpretar un lenguaje (herramienta muy utilizada para crear otros DSLs), el lenguaje R, utilizado para computación estadística, o el propio lenguaje HTML para la presentación de información en navegadores.
Crear un DSL implica la definición de las estructuras léxicas, sintácticas y semánticas, que deben implementarse en herramientas capaces de interpretarlas y ejecutarlas. Esto supone un esfuerzo importante que en ocasiones no es suficientemente rentable. Es por ello que surgen lo que se denominan DSL internos, que utilizan las estructuras que ofrecen otros lenguajes para facilitar la creación de un tipo determinado de aplicaciones. Para crear un DSL interno tan solo es necesario definir métodos que permitan encadenar varias llamadas en una sola instrucción. Basta con jugar con saltos de línea y tabulados para mejorar la legibilidad del código y que aquello parezca un DSL.
La biblioteca Guava de Google ya incorporaba estos conceptos desde sus inicios y la versión 8 de Java también se ha sumado a esta moda. En Java 8 se ha incorporado entre sus novedades un DSL interno que permite manipular cualquiera de las estructuras de datos estándar a través de un nuevo tipo de estructura denominado Stream. He aquí una pequeña muestra de lo que se puede hacer con esta DSL:
listOfPersons
.stream()
.filter(e -> e.getGender() == Person.Sex.FEMALE)
.forEach(e -> System.out.println(e.getName()));
El código anterior filtra una lista de personas, extrayendo únicamente las mujeres y escribiendo su nombre por pantalla. Aunque no sepas nada sobre esta API, es fácil entender su funcionalidad de un vistazo rápido. ¿Y por qué hablo hoy de esto? Pues porque he visto varias soluciones que utilizan de forma incorrecta las DSLs que ofrecen tanto Guava como Java 8. Un par de ejemplos de mal uso:
Lists.newArrayList(Ordering.natural().reverse().sortedCopy(map.values()));
Map<String,Integer> result = new HashMap<String,Integer>();
frecuencyMap.entrySet().stream()
.sorted((e1, e2) -> e2.getValue().compareTo(e1.getValue())).limit(topRank)
.forEach(e -> result.put(e.getKey(), e.getValue()));
La reacción que tuve al leer ambas líneas de código fue la misma: bofetada visual. Y todo por no ordenar convenientemente las líneas de código. Estas formas de ordenar el código son mucho más legibles:
Lists.newArrayList(
Ordering.natural().reverse().
sortedCopy(map.values())
);
Map<String,Integer> result = new HashMap<String,Integer>();
frecuencyMap.entrySet().stream()
.sorted((e1, e2) -> e2.getValue().compareTo(e1.getValue()))
.limit(topRank)
.forEach(e -> result.put(e.getKey(), e.getValue()));
Y si ya lo acompañamos de comentarios, eso es la releche. Los programadores solitarios que cuando evitan escribir comentarios piensan que el código fuente sólo lo van a leer ellos, están cometiendo un atropello con su "yo del futuro". Y es que cualquier programador con poca experiencia seguro que se ha encontrado con ese momento en el que te preguntas "¿de verdad he escrito yo eso?", "¿en qué momento de enfermedad mental se me ocurrió escribirlo?". Y es ahí donde echas en falta un poco de cariño en la redacción de comentarios útiles, el uso de nombres de variables y métodos comprensibles, uso de tabulados y retorno de carro, etc.
La ley de Demeter
La estructura tan particular de las DSLs internas siempre me han evocado a la diosa griega más maltratada del mundo de la informática: Demeter. Esta diosa dio nombre al grupo de investigación que propuso la citada Ley de Demeter, la ley que más programadores se pasan por el arco del triunfo digital. Te la resumo en un ejemplo sencillo:
// ¡¡¡ no hagas esto nunca !!! objeto.llamadaQueDevuelveObjeto().llamadaAMetodo();
¿Qué problemas trae esto? Pues que si la llamada intermedia devuelve null, tenemos una excepción como un templo. "No, pero eso no me pasa a mí, esto nunca devuelve null". También el sueldo de los funcionarios era intocable y 4 bajadas que llevamos ya. Aparta la soberbia y piensa que tu código siempre puede fallar. En lugar de lo anterior escribe esto:
// ¡¡¡ Me siento seguro !!!
if (objeto != null) {
OtroObjeto otroobjeto = objeto.llamadaQueDevuelveObjeto();
if (otroObjeto != null ) {
otroObjeto.llamadaAMetodo();
}
}
Este código cumple con la citada ley, evita problemas y además facilita la depuración y ejecución paso a paso del código. Un código compacto no sirve para nada si falla. ¿Alguna vez has pensado qué beneficio trae escribir poco a la hora de programar? Ninguno. Utiliza nombres largos en los métodos y atributos, que los compiladores actuales autocompletan a medida que escribes. Un nombre largo no hace que el código resultante rinda mejor o peor, que eso los compiladores ya lo tienen muy estudiado. Abusa de las llaves aunque puedas evitarlas porque el if sólo tiene una línea, que el día que una línea se convierta en dos te arrepentirás. Y sobre todo, haz honor a la ley de Demeter, que en el fondo es buena gente.
Y te estarás preguntando "Y si yo tengo que cumplirla, ¿por qué ellos no?". Échale un vistazo al mecanismo de refactorización Null Object y sé creativo. Tal vez entiendas una de las técnicas más importantes en el diseño de DSLs internas y podrás ignorar a Demeter, aunque sea solo un poquito.
Pablo Trinidad 26 octubre, 2014
Posted In: Aprendiendo algoritmia, Tecnologería
Señales y patrones
Dificultad: Media
El problema que propongo resolver hoy fue propuesto en el año 1998 en la Olimpiada Informática Internacional de Setúbal para alumnos de bachillerato. ¿Puede un estudiante o titulado en ingeniería ser capaz de resolver este problema en 2 horas?
Contexto
La Doctora Astro Insky trabaja en un centro de radiotelescopios donde recientemente se detectó una emision de microondas pulsadas enviadas desde el centro de la galaxia. Se pretenden detectar patrones a fin de determinar si las emisiones recibidas son transmitidas por alguna forma de vida inteligente extraterrestre.
Para ayudar a la Doctora Insky a encontrar la verdad, se pretende desarrollar una herramienta para analizar los patrones de bits en los archivos que se han grabado. La Doctora Insky desea encontrar patrones cuya longitud estén entre A y B (incluídos) que se repiten en las grabaciones de cada día. Se pretenden obtener los N patrones con un mayor número de ocurrencias.
Las ocurrencias de patrones pueden estar superpuestas y solamente los patrones que ocurran al menos una vez serán tenidos en cuenta. Así por ejemplo, si se buscan los patrones de longitud 2 a 4 para el mensaje 0101 se encontrará el patrón 01 con 2 apariciones, mientras que los patrones 10, 010, 101 y 0101 aparecen tan solo una vez.
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.
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.
Si desarrolláis soluciones o encontráis problemas, podéis enviar un comentario o bien un correo electrónico.
Interfaz del problema
package problems.contact;
import java.util.Map;
public interface IContactProblem {
/*
* This method sets the input data for the problem.
* @param minLength the minimal length of a pattern.
* @param maxLength the maximal length of a pattern.
* @param topRank the number of expected results in the top rank.
* @param message the message under analysis.
* @throws IllegalArgumentException if any of the integer input parameters are zero or negative,
* the maxLength is less than the minLength or the message is null.
*/
public abstract void setData(int minLength, int maxLength, String message);
/*
* Executes the problem if the data has been correctly set
*/
public abstract void run();
/*
* @return the top rank of patterns and their frequencies.
* It return null if the problem has not been solved yet.
* @throws IllegalArgumentException if the topRank parameter is less than zero
*/
public abstract Map<String,Integer> getResult(int topRank);
}
Prueba JUnit Parametrizada
package problems.contact;
import java.util.Arrays;
import java.util.Collection;
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
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 ContactTest {
IContactProblem contactProblem;
int minLength, maxLength, topRank;
String message;
Map<String,Integer> expectedResult;
public ContactTest (int minLength, int maxLength, int topRank, String message, Map<String,Integer> expectedResult) {
this.minLength = minLength;
this.maxLength = maxLength;
this.topRank = topRank;
this.message = message;
this.expectedResult = expectedResult;
}
// creates the test data
@Parameters
public static Collection<Object[]> data() {
Map<String,Integer> mapResult1 = new HashMap<String,Integer>() {{put("00",23);}};
Map<String,Integer> mapResult2 = new HashMap<String,Integer>() {{put("01",2); put("10",1);put("010",1);put("101",1);put("0101",1);}};
Object[][] data = new Object[][] { {2,4,1,"01010010010001000111101100001010011001111000010010011110010000000",mapResult1},
{2,4,5,"0101",mapResult2}};
return Arrays.asList(data);
}
@Test
public void testContactProblem() {
contactProblem = new ContactProblem();
contactProblem.setData(minLength,maxLength,message);
contactProblem.run();
Map<String,Integer> result = contactProblem.getResult(topRank);
// checks if the mappings are equal, but the frequency is not checked with equals.
Assert.assertEquals("length: ["+minLength+","+maxLength+"], top "+ topRank + ": "
, expectedResult, result );
// now we check that the values are correct for every key
for (Entry<String,Integer> entry: result.entrySet()) {
Integer frequency = expectedResult.get(entry.getKey());
Assert.assertNotNull("length: ["+minLength+","+maxLength+"], top "+ topRank + ": a frequency is null in the result", frequency);
Assert.assertEquals(entry.getValue(), frequency);
}
}
}
Test runner
package problems.contact;
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(ContactTest.class);
for (Failure failure : result.getFailures()) {
System.out.println(failure.toString());
}
if(result.wasSuccessful())
System.out.println("All tests passed!");;
}
}
Pablo Trinidad 18 octubre, 2014
Posted In: Aprendiendo algoritmia, Tecnologería
El problema de los dados: la solución (o no)
Atención: No leer sin antes haber realizado el problema de los dados.
En busca de una solución
Definitivamente el problema de los dados ha dado mucho más juego del que pensaba. Me alegra ver que poco a poco esta iniciativa empieza a mover gente. Y no sólo por los que comentan en la web. Son muchos los que me han escrito para pedir socorro, opinión, una pista... o la solución al problema.
Así que vamos a hablar de esto último: la solución. Estoy convencido de que la primera intención que ha tenido la mayoría ha sido coger unos cuantos dados o en su defecto un papel y probar con varios ejemplos en aras de encontrar una fórmula que aplicar para resolver el problema. Y en efecto es posible encontrarla si distinguimos tres casos: para dados de 10 caras o más, de 9 caras y de menos de 9 caras. Para ello necesitamos elaborar varios ejemplos y seguir el método inductivo de razonamiento, es decir, observamos varios casos, extraemos una regla e intentamos validarla. Sin embargo esa solución se rompe en el momento en el que el número de cubetas es menor que el número de dados. Os animo a que los que hayáis seguido este enfoque simplemente probéis si el resultado obtenido con 5 dados de 10 caras y 1 cubeta es de 51.
Ante la dificultad del método inductivo y la posibilidad de que las 2 horas vuelen en busca de una fórmula inexistente, muchos optan por intentar replicar un programa que simulen el método de razonamiento humano que seguimos para resolver este problema. Básicamente empezamos por probar si somos capaces de representar el 1, luego el 2 y así hasta que encontremos el primer número no representable. Afirmar que podemos representar un número es sencillo ya que basta con encontrar una forma viable de hacerlo. Sin embargo afirmar que un número no es representable es un problema mucho más complejo que requiere comprobar todas las posibles distribuciones de los dados hasta poder afirmar con total certeza que no es posible tal representación.
Puesto que esta solución sería una mala opción desde el punto de vista combinatorio, que exigiría a un computador hacer muchos cálculos, tratamos de modelar el comportamiento humano de otra forma clásica de razonar: modelar el caso N+1 a partir del caso N. Es decir, nos apoyamos en la solución del número 9 por ejemplo para indicar de qué forma alcanzamos el número 10. Así por ejemplo podemos incrementar el valor de un dado o desplazar un dado a la siguiente cubeta con el número 1 como valor, reduciendo el número de opciones para encontrar el siguiente dado. Sin duda una opción más razonable que la anterior que nos obliga a buscar menos combinaciones.
Pero son pocos los que se atreven con buscar la solución que personalmente tomé a la hora de resolver por primera vez este problema: hacer que la máquina trabaje. Como comenté al comenzar con mi malvado plan, una de las tareas más difíciles para aprender a programar es ser capaz de interpretar un problema en términos que un computador sepa ejecutar, explotando al máximo la capacidad de realizar tareas repetitivas sin cansarse ni quejarse. Es por ello que decidí calcular todas las posibles combinaciones, almacenando todos los números enteros representables para luego encontrar en la lista el primer hueco. El secreto para hacer esta tarea lo más rápido posible está en evitar cálculos redundantes, como puede ser evaluar dos veces la misma combinación de dados, que harían que esta tarea fuera aún más lenta. Puede que el rendimiento no sea el mejor respecto a otras soluciones, pero funciona para todos los casos expuestos, es realizable en poco tiempo y puede utilizarse como base a partir de la cual realizar mejoras.
Un problema, muchas soluciones
Como podéis ver, existen muchos enfoques distintos para abordar este problema. Es más, dentro de cada uno de los enfoques podemos encontrar varias formar de realizar una misma tarea. Hay tantas soluciones como personas que traten de resolver el problema. Cada una de ellas tendrá sus pros y contras, que harán que según las circunstancias unas soluciones sean mejor o peor para un propósito determinado. Por tanto en el mundo de la programación no existe una solución única y debemos siempre analizar los puntos fuertes y débiles de nuestras propuestas para encontrar NUESTRA mejor opción.
Quien me pida una solución siempre obtendrá la misma respuesta: "Depende"
Todavía existen profesores que ofrecen soluciones a los problemas que plantean. Las soluciones tienen un importante valor didáctico, pero llega un momento en el que debemos dejar de ofrecer soluciones y dejar que el ingenio comience a fluir. Acostumbrar al estudiante a que todo tiene una solución única es un error de bulto en un área tan creativa como la ingeniería. Además, conocer siempre la solución no es divertido. ¿Acaso preferimos un crucigrama o un sudoku resuelto a uno por hacer?
En la vida real, las grandes decisiones no tienen una única respuesta válida. Siempre le digo a mis alumnos que la respuesta a todas las preguntas en el mundo de la ingeniería es la misma: "Depende". Por supuesto a esta respuesta debemos acompañarla con un análisis de todos los aspectos importantes del problema, nuestras hipótesis de trabajo, ofrecer distintas soluciones estudiando los pros y contras, ofrecer alternativas, etc. Por esta razón, nunca ofreceré la solución a un problema. Si acaso, mi solución. Y hoy no va a ser ese día 😉
Analizando el rendimiento con JUnit
En este comentario planteé el cálculo de tiempos de ejecución para resolver un determinado problema. Si bien las pruebas de rendimiento bien requieren un libro completo, y JUnit no es la tecnología adecuada para dichas pruebas, existe una forma muy sencilla de limitar el tiempo de una prueba en JUnit:
@Test(timeout=5000)
public void testDiceProblem() {
diceProblem = new DiceProblemOptRefactored();
diceProblem.setData(dice,faces,trays);
diceProblem.run();
int result = diceProblem.getResult();
Assert.assertEquals("[dice:"+dice+",faces:"+faces+",trays:"+trays+"]: "
, expectedResult, result );
}
Aunque el tiempo obtenido variará en función de las capacidades técnicas del equipo, las aplicaciones que estén corriendo en paralelo, el consumo de memoria, etc. puede ser una buena referencia para alertar de problemas tales como bucles infinitos o algoritmos claramente ineficientes.
Pablo Trinidad 13 octubre, 2014
Posted In: Aprendiendo algoritmia, Tecnologería