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!");
   }
}  

8 octubre, 2014

Posted In: Aprendiendo algoritmia, Tecnologería

7 Comments

  • Rafa Haro dice:

    Antes de nada, enhorabuena por la iniciativa Pablo. Me he picado por contestar el primero así que no tengo código (aunque prometo buscar un hueco). SPOILER 🙂 : voy a exponer una primera solución que quizás no sea la más eficiente. Tengo la intuición de que puede encontrarse una expresión matemática para encontrar el menor número no representable, pero eso llevaría un poco más de tiempo. Creo que el truco puede estar en jugar con la diferencia entre la mínima representación de un dado en una bandeja y la mínima en la siguiente. Pero bueno. El algoritmo:

    Con estos problemillas, lo que creo que se debe intentar es ver si puedes encontrar un algoritmo que sea linear en cuanto al número total de datos. Casi siempre hay una solución exponencial muy pobre generando todas las posibilidades. Para hacerlo lineal hay que saber primero donde parar y en este caso parece claro que tu bucle debe parar en el mayor número representable que es N*(K*10^N) si no me equivoco. Lo que yo haría probablemente es, mediante programación dinámica, ir generando números y marcar un array de booleanos del tamaño anterior con true usando como índice los números generados. Se pueden generar (creo) con tres bucles simplemente aplicando la formula. Luego se itera hasta el encontrar el primer falso. 
    
    A partir de ahí probablemente hay muchas heurísticas que requieren pensar más. Probablemente podemos descartar los pares por ejemplo. Pero son conjeturas, no tengo ahora mismo una formula que lo certifique
    
  • Pablo Trinidad dice:

    Recomiendo no pensar en órdenes de complejidad si no se tiene una solución. Primero que funcione. Luego se buscan optimizaciones. Te irá mejor 😉

  • JesúsTinoco dice:

    Una hora y cincuenta minutos, vivo al limite. Es la primera solución que se me ha ocurrido en estas dos horas que he tenido libre. Cada vez me doy más cuenta de lo importante que es hacer TDD, nunca es tarde para empezar. Pasa todos los test de esta entrada, estoy seguro que no pasará los de la siguiente.

    https://github.com/JesusTinoco/diceNumber

    • Pablo Trinidad dice:

      Prueba con 5 dados de 10 caras en 3 y 4 bandejas, dime los resultados obtenidos y cuánto tiempo tarda tarda cada prueba 😉

    • JesúsTinoco dice:

      - 5 dados, 10 caras y 3 bandejas: 3111 es el resultado y el tiempo 67 milisegundos
      - 5 dados, 10 caras y 4 bandejas: 21111 es el resultado y el tiempo 176 milisegundos

  • CP dice:

    Tengo dos soluciones en PHP (para que os sangren los ojos), hechas en unos 20-25 minutos cada una. No tengo tiempo ni mucho menos ganas de aprender Java. 😛

    La solución de fuerza bruta: http://pastebin.com/FjMPJ0RD

    Uso: php problema-dados-PT.php N k
    
    con N y k de acuerdo al enunciado (N = nº de dados = nº de bandejas = nº de huecos,  k = número de caras).
    
    Calcula el total de números que un único dado puede generar (1..k elevado a 1, 10...10^N = kN combinaciones), y luego calcula progresivamente todas las posibles sumas con 2, 3, ... N dados, lo que es horriblemente ineficiente. Una optimización obvia sería calcular los resultados de combinar 2, 4, ... 2^floor(log2 (N)) dados y luego hacer una descomposición binaria de N, pero tampoco es que sea para tirar cohetes. : P
    
    Me da la impresión de que es un problema que debe tener una solución matemática cerrada, o al menos ser susceptible de una solución mucho más optimizada con algo de análisis matemático. De entrada, para el caso k 10 debe andar ahí. Al final esto te lleva a que las combinaciones críticas tienen una combinación de dados muy concreta, y que el fallo se produce debido a la inabilidad de añadir un dado con valor 1 a las unidades en algún momento.
    
    Por otra parte, el enunciado del problema tiene un agujero lógico, y es que si una civilización usa dados de k caras para mostrar sus números, lo lógico es que use un sistema de numeración en base k. Aunque eso le quitaría la gracia al problema. : P
    

    Esta solución se la mandé ayer a PT por mail, y a raíz de su respuesta he hecho otra bastante más elegante, pero tendréis que esperar a que PT reproduzca aquí su comentario. 😉

  • […] Atención: No leer sin antes haber realizado el problema de los dados. […]

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.