Señales y patrones

Dificultad: Media

El problema que propongo resolver hoy fue propuesto en el año 1998 en la Olimpiada Informática Internacional de Setúbal para alumnos de bachillerato. ¿Puede un estudiante o titulado en ingeniería ser capaz de resolver este problema en 2 horas?

Contexto

La Doctora Astro Insky trabaja en un centro de radiotelescopios donde recientemente se detectó una emision de microondas pulsadas enviadas desde el centro de la galaxia. Se pretenden detectar patrones a fin de determinar si las emisiones recibidas son transmitidas por alguna forma de vida inteligente extraterrestre.

Para ayudar a la Doctora Insky a encontrar la verdad, se pretende desarrollar una herramienta para analizar los patrones de bits en los archivos que se han grabado. La Doctora Insky desea encontrar patrones cuya longitud estén entre A y B (incluídos) que se repiten en las grabaciones de cada día. Se pretenden obtener los N patrones con un mayor número de ocurrencias.

Las ocurrencias de patrones pueden estar superpuestas y solamente los patrones que ocurran al menos una vez serán tenidos en cuenta. Así por ejemplo, si se buscan los patrones de longitud 2 a 4 para el mensaje 0101 se encontrará el patrón 01 con 2 apariciones, mientras que los patrones 10, 010, 101 y 0101 aparecen tan solo una vez.

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.

Interfaces y pruebas

A continuación se ofrece el marco para desarrollar la solución en lenguaje Java. En este problema pretende que se saque partido de las estructuras de datos que ofrece Java, pudiéndose si se estima necesario crear otras clases auxiliares que ayuden a la resolución del problema.

Se ofrece una interfaz del problema que habrá que implementar para su resolución. 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.contact;

import java.util.Map;

public interface IContactProblem {
	/*
	 * This method sets the input data for the problem.
	 * @param minLength the minimal length of a pattern.
	 * @param maxLength the maximal length of a pattern.
	 * @param topRank the number of expected results in the top rank.
	 * @param message the message under analysis. 
	 * @throws IllegalArgumentException if any of the integer input parameters are zero or negative, 
	 * the maxLength is less than the minLength or the message is null.
	 */
	public abstract void setData(int minLength, int maxLength, String message);
	
	/*
	 * Executes the problem if the data has been correctly set
	 */
	public abstract void run();
	
	/*
	 * @return the top rank of patterns and their frequencies. 
	 * It return null if the problem has not been solved yet.
	 * @throws IllegalArgumentException if the topRank parameter is less than zero
	 */
	public abstract Map<String,Integer> getResult(int topRank);
}

Prueba JUnit Parametrizada

package problems.contact;

import java.util.Arrays;
import java.util.Collection;
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;

import org.junit.Assert;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.Parameterized;
import org.junit.runners.Parameterized.Parameters;

@RunWith(Parameterized.class)
public class ContactTest {
	IContactProblem contactProblem;
	int minLength, maxLength, topRank;
	String message;
	Map<String,Integer> expectedResult;
	
	
	public ContactTest (int minLength, int maxLength, int topRank, String message, Map<String,Integer> expectedResult) {
			this.minLength = minLength;
			this.maxLength = maxLength;
			this.topRank = topRank;
			this.message = message;
			this.expectedResult = expectedResult;
	}
	
	 // creates the test data
	@Parameters
	public static Collection<Object[]> data() {
		Map<String,Integer> mapResult1 = new HashMap<String,Integer>() {{put("00",23);}};
		Map<String,Integer> mapResult2 = new HashMap<String,Integer>() {{put("01",2); put("10",1);put("010",1);put("101",1);put("0101",1);}};
	    Object[][] data = new Object[][] { {2,4,1,"01010010010001000111101100001010011001111000010010011110010000000",mapResult1},
	    								   {2,4,5,"0101",mapResult2}};

	    return Arrays.asList(data);
	  }

	
	@Test
	public void testContactProblem() {
		contactProblem = new ContactProblem();
		contactProblem.setData(minLength,maxLength,message);
		contactProblem.run();
		Map<String,Integer> result = contactProblem.getResult(topRank);
		// checks if the mappings are equal, but the frequency is not checked with equals.
		Assert.assertEquals("length: ["+minLength+","+maxLength+"], top "+ topRank + ": "
							, expectedResult, result );
		// now we check that the values are correct for every key
		for (Entry<String,Integer> entry: result.entrySet()) {
			Integer frequency = expectedResult.get(entry.getKey());
			Assert.assertNotNull("length: ["+minLength+","+maxLength+"], top "+ topRank + ": a frequency is null in the result", frequency);
			Assert.assertEquals(entry.getValue(), frequency);
		}
	}
}

Test runner

package problems.contact;

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(ContactTest.class);
      for (Failure failure : result.getFailures()) {
         System.out.println(failure.toString());
      }
      if(result.wasSuccessful())
    	 System.out.println("All tests passed!");;
   }
}  

Pablo Trinidad 18 octubre, 2014

Posted In: Aprendiendo algoritmia, Tecnologería