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