El problema de los dados
Dificultad: Fácil
El problema que propongo resolver hoy fue propuesto en el año 1997 en la Olimpiada Informática Española para alumnos de bachillerato. ¿Puede un estudiante o titulado en ingeniería ser capaz de resolver este problema en 2 horas?
Contexto
En unos trabajos arqueológicos recientes, se han encontrado restos de una hipotética civilización precolombina. Los restos encontrados apuntan a que dicha civilización utilizaba un método algo original para representar números, mediante dados. Los dados se disponen en bandejas divididas en porciones, numeradas consecutivamente de izquierda a derecha a partir del cero.
El número representado se calcula como la suma del valor de la cara visible de cada dado, ponderándolo adecuadamente según la porción de la bandeja que se encuentra: un dado que tenga el número X en la cara visible y que se encuentre en la posición de número r tiene como valor X*10^r (X multiplicado por 10 elevado a r). Por ejemplo, el número 1.024 puede representarse de las maneras siguientes (con dados de seis caras y una bandeja dividida en cuatro porciones):
| Unid.millar | Centenas | Decenas | Unidades | Núm. representado |
|---|---|---|---|---|
| 1 | - | 2 | 4 | 1.024 |
| - | 6, 4 | 1 | 6, 6, 2 | 1.024 |
| - | 4, 5 | 6, 6 | 4 | 1.024 |
Ahora bien, existe un fallo en este sistema de numeración: hay números que no pueden representarse. Por ejemplo, si disponemos de 2 dados de 6 caras, es imposible representar el número 17; no existe ninguna distribución de los dados que permita obtenerlo. Se pide un programa que calcule el menor número no representable con N dados de k caras, suponiendo que la bandeja está dividida en N porciones y que en cada porción caben N dados.
Ejemplos:
| Dados | Caras | Cubetas | Resultado |
|---|---|---|---|
| 2 | 4 | 2 | 9 |
| 2 | 6 | 2 | 17 |
| 3 | 4 | 3 | 19 |
| 3 | 6 | 3 | 77 |
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.
Algo de código y pruebas
De nuevo ofrezco el marco para desarrollar la solución en lenguaje Java. El tipo de problemas que estoy proponiendo no pretende sacar partido de la orientación a objetos sino de la programación procedimental, ofreciendo un marco para que los que no estén familiarizados con los objetos puedan desarrollar soluciones en igualdad de condiciones.
Por un lado se ofrece una interfaz del problema que habrá que implementar para su resolución. En segundo lugar 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.dice;
public interface IDiceProblem {
/*
* This method sets the input data for the problem.
* @param dice the total number of dice.
* @param faces the number of faces each die has.
* @param trays the number of trays (units, tens, hundreds, etc.) the numbering system has.
* @throws IllegalArgumentException if any of the input parameters are zero or negative.
*/
public abstract void setData(int diceNumber, int faces, int trays);
/*
* Executes the problem if the data has been correctly set
*/
public abstract void run();
/*
* @return the first number that is impossible to be represented with the provided system.
*/
public abstract int getResult();
}
Prueba JUnit parametrizada
package problems.dice;
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;
import problems.dice.DiceProblemOptRefactored;
import problems.dice.IDiceProblem;
@RunWith(Parameterized.class)
public class DiceProblemTest {
IDiceProblem diceProblem;
int dice, faces, trays, expectedResult;
public DiceProblemTest (int dice, int faces, int trays, int result) {
this.dice = dice;
this.faces = faces;
this.trays = trays;
this.expectedResult = result;
}
// creates the test data
@Parameters
public static Collection<Object[]> data() {
Object[][] data = new Object[][] { {3,4,3,19}, {2,6,2,17}, {3,6,3,77}, {2,4,2,9} };
return Arrays.asList(data);
}
@Test
public void testDiceProblem() {
diceProblem = new DiceProblemOpt();
diceProblem.setData(dice,faces,trays);
diceProblem.run();
int result = diceProblem.getResult();
Assert.assertEquals("[dice:"+dice+",faces:"+faces+",trays:"+trays+"]: "
, expectedResult, result );
}
}
Test Runner
package problems.dice;
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(DiceProblemTest.class);
for (Failure failure : result.getFailures()) {
System.out.println(failure.toString());
}
if(result.wasSuccessful())
System.out.println("All tests passed!");
}
}
Pablo Trinidad 8 octubre, 2014
Posted In: Aprendiendo algoritmia, Tecnologería
La colonia de bacterias: el debate
Atención: No leer sin antes haber realizado el problema de la colonia de bacterias.
Ninguna prueba es suficiente
Cuando se aplica un enfoque de desarrollo dirigido por pruebas (TDD), la principal novedad a nivel metodológico es comenzar el diseño de una solución con las pruebas que nos harán comprobar finalmente que el funcionamiento es el deseado. Para ello debemos imaginar cómo se va a utilizar una determinada interfaz, cuál va a ser el comportamiento que va a observar un usuario de dicha interfaz desde fuera, sin acceso alguno al código fuente. Con este enfoque se acaba mejorando la usabilidad de las propias interfaces, que ya no vienen definidas por los caprichos, vicios y/o estilo de programación del desarrollador de la implementación, sino que tienen al consumidor de la interfaz como prioridad en el diseño. Y la interfaz no podrá modificarse porque la implementación sea más o menos complicada. Debemos adaptarnos a ella.
Aunque se recomienda separar el rol de probador y programador, esto no es siempre posible y cuando estamos solos ante el peligro debemos asumir un cambio de roles en el que en un momento diseñas pruebas y en otro diseñas código. Para evitar que el código pervierta las pruebas, os recomiendo que establezcáis una regla que impida realizar el paso de un rol a otro sin al menos 15 minutos de descanso entre ambos. Así evitáis la tentación de cambiar las pruebas sin "haberlo dejado macerar" un rato. En este caso, ir a pensar a cualquier rincón alicatado que tengáis a mano fomentará un mejor funcionamiento de vuestras neuronas.
En el caso de la colonia de bacterias habéis partido de pruebas desarrolladas por otra persona ajena al código y que os ha impuesto una interfaz y un comportamiento que se infiere de la documentación en el código y de los propios ejemplos de uso de las pruebas. Al ir desarrollando una solución, habéis podido comprobar en cada momento si vuestro código es correcto o no respecto a las pruebas. Sin embargo, las pruebas facilitadas no son suficientemente exhaustivas y dejan muchos casos de uso sin probar, y por tanto comprometiendo la calidad de la implementación de vuestra solución.
En el mundo del software, es imposible realizar pruebas completas del código fuente. Una prueba es completa cuando se comprueban las salidas obtenidas para todas las posibles entradas. De esta manera, para un único método de una interfaz deberíamos probar todas las combinaciones de valores que puedan tomar cada uno de los parámetros de entrada. Así para un método suma(int izq, int der), debemos probar todas las posibles combinaciones de números. Ya que un número entero de 32 bits puede tomar 4.294.967.296 valores, para dos números tenemos un total de 1.8446744E18 posibles combinaciones. En el caso del método setData tenemos dos números enteros además de una lista de posiciones de bacterias. ¿Somos acaso capaces de probar todos los posibles escenarios?
Realizar pruebas completas es imposible; ser exhaustivo es una obligación.
Ya que no es posible realizar pruebas completas, debemos ser al menos exhaustivos en el diseño de pruebas. Se deben escoger aquellos casos que prueben el mayor número de comportamientos diferentes posibles. Así por ejemplo, en la colonia de bacterias una prueba de una sola iteración en la que sólo existe una bacteria sólo prueba la muerte de la misma al no tener comida. Esta prueba es menos efectiva que crear una colonia donde en una sola iteración muera una bacteria, se genere una nueva y otra sobreviva. Sin embargo, al encontrar un error en el primer caso sabemos que existe un error en la regla de muerte por inhanición, mientras que encontrar el error en el segundo caso es más complejo al deber discriminar cuál o cuáles de las tres reglas de evolución está fallando.
Pero las pruebas no se acaban con los casos de prueba habituales. Un buen probador debe tener una mente perversa que le lleve a pensar mal de los programadores. Un buen probador debe pensar que quien utiliza la interfaz no se ha leido la documentación sobre su uso, envía accidentamente parámetros incorrectos, utiliza los métodos en un orden inadecuado, etc. Con las pruebas anteriormente facilitadas habéis trabajado con un probador novato. En el capítulo de hoy os animo a probar vuestro código con la siguiente prueba unitaria:
package problems.bacteriaColony;
import org.junit.Assert;
import org.junit.Before;
import org.junit.Test;
public class BacteriaColonyIntensiveTest {
IBacteriaColonyProblem colonyProblem;
@Before
public void setup() {
colonyProblem = new BacteriaColonyProblem();
}
@Test
public void testBacteriaProblem1DoubleSetData() {
int [][]bacteria = {{0,2},{1,1},{1,2},{2,2},{3,2}};
boolean [][]expected = {{false,true,true,false},
{false,true,true,true},
{false,false,true,true},
{false,false,false,false}};
colonyProblem.setData(4,1,bacteria);
colonyProblem.setData(4,1,bacteria);
colonyProblem.run();
checkResult(expected,colonyProblem.getResult());
}
@Test
public void testBacteriaProblem1Iter2TwoRun() {
int [][]bacteria = {{0,2},{1,1},{1,2},{2,2},{3,2}};
boolean [][]expected = {{false,true,false,true},
{false,false,false,false},
{false,true,false,true},
{false,false,false,false}};
colonyProblem.setData(4,2,bacteria);
colonyProblem.run();
colonyProblem.run();
checkResult(expected,colonyProblem.getResult());
}
@Test
public void testBacteriaProblem2() {
colonyProblem.run();
}
@Test
public void testBacteriaProblemTwoSetData() {
int [][]unusedBacteria = {{0,2},{1,1},{1,2},{2,2},{3,2}};
colonyProblem.setData(4,2,unusedBacteria);
int [][]bacteria = {{0,2},{1,1},{1,2},{2,2},{3,2}};
boolean [][]expected = {{false,true,true,false},
{false,true,true,true},
{false,false,true,true},
{false,false,false,false}};
colonyProblem.setData(4,1,bacteria);
colonyProblem.run();
checkResult(expected,colonyProblem.getResult());
}
@Test (expected=IllegalArgumentException.class)
public void testBacteriaIllegalData() {
int [][]bacteria = {{0,2},{1,1},{1,2},{2,2},{3,2}};
colonyProblem.setData(-1,-1,bacteria);
}
private void checkResult (boolean[][] expected, boolean[][] result) {
Assert.assertEquals("Colony width error", expected.length, result.length);
for (int x = 0; x < result.length; x++) {
Assert.assertEquals("Colony height error", expected[x].length, result[x].length);
for (int y = 0; y < result[x].length; y++)
Assert.assertEquals ("Incorrect value at ["+x+","+y+"]",
expected[x][y], result[x][y]);
}
}
}
¿Era vuestro código correcto? ¿Podemos hacer pruebas mejores y más exhaustivas? ¿Podemos confiar siempre en que nuestro código fuente funciona? ¡Responded a estas preguntas en los comentarios!
Pablo Trinidad 3 octubre, 2014
Posted In: Aprendiendo algoritmia, Tecnologería
La colonia de bacterias
Dificultad: Muy fácil
Hoy planteo un sencillo problema de programación que casi se puede considerar un clásico de la programación y que ha sido propuesto en multitud de ediciones de olimpiadas informáticas en diferentes paises con pequeñas variantes. Se considera un problema básico pero que ayuda a plantearse algunas cuestiones importantes sobre la gestión de tablas, memoria y que ayudará a introducir algunos conceptos básicos sobre legibilidad del código.
Contexto
Un laboratorio de investigación distribuye una colonia de bacterias en un cultivo, que se puede considerar como una superficie cuadriculada de N filas y N columnas; cada casilla de esta superficie puede estar vacía o puede contener una bacteria. A partir de cualquier configuración inicial, la colonia evoluciona generación a generación según unas leyes genéticas fijas y determinadas y que dependen del número de vecinos que tenga cada casilla.
Para todas y cada una de las generaciones las leyes genéticas son:
- Nacimiento: en toda casilla vacía que tenga exactamente tres vecinos.
- Muerte por aislamiento: toda bacteria que ocupe una casilla con uno o ningún vecinos
- Muerte por asfixia: toda bacteria que ocupe una casilla con más de tres vecinos.
- Supervivencia: toda bacteria que ocupe una casilla con dos o tres vecinos.
La casilla que ocupa la fila i y la columna j se identifica mediante (i, j) (0<=i<N, 0<=j<N). Los vecinos de una casilla (i, j) son las posiciones (i-1, j-1), (i-1, j), (i-1, j+1), (i, j-1), (i, j+1), (i+1, j-1), (i+1, j) e (i+1, j+1) que estén comprendidas dentro de la superficie y que estén ocupadas por una bacteria.
Ejemplos
Para una superficie 4x4, la colonia de la izquierda de la figura siguiente evoluciona en las dos próximas generaciones tal y como se muestra:
| * | |||
| * | * | ||
| * | |||
| * |
| * | * | ||
| * | * | * | |
| * | * | ||
| * | * | ||
| * | * | ||
Objetivo
El objetivo será crear un programa que sea capaz de simular evolución de cualquier colonia inicial durante un cierto número de transiciones. En concreto, ¿quién puede indicarme cuál será la evolución de esta colonia tras 500 iteraciones?
| * | * | ||
| * | * | ||
| * | |||
| * | * |
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.
Algo de código y pruebas
A fin de homogeneizar la resolución de este problema, voy a facilitar código fuente para aquellos que están familiarizados con el lenguaje Java (cuyo uso es mayoritario en mi entorno). En primer lugar una interfaz del problema que habrá que implementar para su resolución. En segundo lugar 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.
Si desarrolláis soluciones o encontráis problemas, podéis enviar un comentario o bien un correo electrónico.
Interfaz del problema
package problems.bacteriaColony;
public interface IBacteriaColonyProblem {
/*
* This method sets the input data for the problem.
* @param size Width and height of the colony, i.e. size=4 creates a 4x4 matrix.
* @param transitions Number of transition steps to compute in the problem.
* @param bacteriaPosition An array of bacteria positions as (i,j) pairs
* such that 0 <= i,j < size.
* @throws IllegalArgumentException if bacteriaPosition is null, size or
* transitions are 0 or negative numbers,
* or the bacteriaPosition is not a list of pairs.
*/
public abstract void setData(int size, int transitions, int [][]bacteriaPosition);
/*
* Executes the problem if the data has been correctly set
*/
public abstract void run();
/*
* @return a boolean matriz of size x size dimensions. True value indicates a living bacteria;
* false value represents an empty space.
*/
public abstract boolean[][] getResult();
}
Prueba JUnit
package problems.bacteriaColony;
import org.junit.Assert;
import org.junit.Before;
import org.junit.Test;
public class BacteriaColonyTest {
IBacteriaColonyProblem colonyProblem;
@Before
public void setup() {
colonyProblem = new BacteriaColonyProblem();
}
@Test
public void testBacteriaProblem1Iter1() {
int [][]bacteria = {{0,2},{1,1},{1,2},{2,2},{3,2}};
boolean [][]expected = {{false,true,true,false},
{false,true,true,true},
{false,false,true,true},
{false,false,false,false}};
colonyProblem.setData(4,1,bacteria);
colonyProblem.run();
checkResult(expected,colonyProblem.getResult());
}
@Test
public void testBacteriaProblem1Iter2() {
int [][]bacteria = {{0,2},{1,1},{1,2},{2,2},{3,2}};
boolean [][]expected = {{false,true,false,true},
{false,false,false,false},
{false,true,false,true},
{false,false,false,false}};
colonyProblem.setData(4,2,bacteria);
colonyProblem.run();
checkResult(expected,colonyProblem.getResult());
}
@Test
public void testBacteriaProblem2() {
int [][]bacteria = {{1,1}};
boolean [][]expected = {{false,false,false},
{false,false,false},
{false,false,false}};
colonyProblem.setData(3,1,bacteria);
colonyProblem.run();
checkResult(expected,colonyProblem.getResult());
}
@Test
public void testBacteriaProblem3Iter1() {
int [][]bacteria = {{1,1},{2,1},{2,2}};
boolean [][]expected = {{false,false,false},
{false,true,true},
{false,true,true}};
colonyProblem.setData(3,1,bacteria);
colonyProblem.run();
checkResult(expected,colonyProblem.getResult());
}
@Test
public void testBacteriaProblem3Iter2() {
int [][]bacteria = {{1,1},{2,1},{2,2}};
boolean [][]expected = {{false,false,false},
{false,true,true},
{false,true,true}};
colonyProblem.setData(3,16,bacteria);
colonyProblem.run();
checkResult(expected,colonyProblem.getResult());
}
@Test
public void testBacteriaProblem4() {
int [][]bacteria = {{1,1},{2,1},{2,2}};
boolean [][]expected = {{false,false,false,false,false},
{false,true,true,false,false},
{false,true,true,false,false},
{false,false,false,false,false},
{false,false,false,false,false}};
colonyProblem.setData(5,15,bacteria);
colonyProblem.run();
checkResult(expected,colonyProblem.getResult());
}
@Test (expected=IllegalArgumentException.class)
public void testBacteriaIllegalData() {
colonyProblem.setData(0,1,null);
}
private void checkResult (boolean[][] expected, boolean[][] result) {
Assert.assertEquals("Colony width error", expected.length, result.length);
for (int x = 0; x < result.length; x++) {
Assert.assertEquals("Colony height error", expected[x].length, result[x].length);
for (int y = 0; y < result[x].length; y++)
Assert.assertEquals ("Incorrect value at ["+x+","+y+"]",
expected[x][y], result[x][y]);
}
}
}
Test Runner
package problems.bacteriaColony;
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(BacteriaColonyTest.class);
for (Failure failure : result.getFailures()) {
System.out.println(failure.toString());
}
if(result.wasSuccessful())
System.out.println("All tests passed!");;
}
}
Pablo Trinidad 29 septiembre, 2014
Posted In: Aprendiendo algoritmia, Tecnologería