La colonia de bacterias

Dificultad: Muy fácil

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.

Contexto

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:

• Nacimiento: en toda casilla vacía que tenga exactamente tres vecinos.
• Muerte por aislamiento: toda bacteria que ocupe una casilla con uno o ningún vecinos
• Muerte por asfixia: toda bacteria que ocupe una casilla con más de tres vecinos.
• Supervivencia: toda bacteria que ocupe una casilla con dos o tres vecinos.

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.

Ejemplos

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:

Objetivo

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?

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

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.

Interfaz del problema

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();
}

Prueba JUnit

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]);
		}	
	}


}

Test Runner

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