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.
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:
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.
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:
* | |||
* | * | ||
* | |||
* |
* | * | ||
* | * | * | |
* | * | ||
* | * | ||
* | * | ||
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?
* | * | ||
* | * | ||
* | |||
* | * |
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.
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.
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(); }
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]); } } }
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
Aquí tienes mi solución al reto: https://github.com/serrodcal/bacteriaColony
Sólo pasa dos test de todos los que vienen definidos. Me gustaría seguir mirandolo y completarlo.
He dedicado dos horas justas, teniendo que instalar Eclipse y configurando JUnit. La primera hora obtuve un código que no serivió porque al principio no entendí bien el problema.
El código no será lo mejor del mundo, pero carga bien la matriz y devuelve bien el resultado. El problema es que seguramente las relgas no esten aplicadas bien al 100%. Supera un test que ejecuta el método run() pero el resto alguna casilla difere.
Saludos.
Aquí dejo mi solución https://github.com/JesusTinoco/bacteriaColony
Le dediqué casi dos horas para plantear una solución correcta. Pasa todos los test. Espero que la solución planteada no sea tan mala.
Saludos!
Muchas gracias por participar. El viernes publico comentarios sobre vuestras soluciones en una nueva entrada.
Buenas , aquí dejo mi solución (corregida) :
https://drive.google.com/file/d/0B8pb6om2L_V1Qld4U3dIRmdiNUU/view?usp=sharing
Pasa todos los tests y tiene algún que otro método de control de más que he considerado interesante implementar, además de una clase de Test para ver con mis propios ojos los resultados que se iban obteniendo en cada generación.
Saludos.