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?
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 |
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.
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.
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(); }
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 ); } }
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
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:
Recomiendo no pensar en órdenes de complejidad si no se tiene una solución. Primero que funcione. Luego se buscan optimizaciones. Te irá mejor 😉
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
Prueba con 5 dados de 10 caras en 3 y 4 bandejas, dime los resultados obtenidos y cuánto tiempo tarda tarda cada prueba 😉
- 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
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
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. […]