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