Luces de Navidad

Dificultad: Media

Hoy propongo un nuevo problema por indicación de mi amigo CP, que como sabiamente indica necesita de un análisis previo del problema a resolver antes de lanzarse a la piscina de la fuerza bruta. Este problema 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 Navidad está a la vuelta de la esquina y estamos colocando la tradicional iluminación en la fachada de casa. Hemos instalado una tira de luces LED, numeradas de 1 a N con un mando de control con 4 botones:

• Botón 1. Al pulsar este botón todas las luces cambian su estado (de encendido a apagado, o de apagado a encendido).
• Botón 2. Al pulsar este botón todas las luces impares cambian su estado.
• Botón 3. Al pulsar este botón todas las luces pares cambian su estado.
• Botón 4. Al pulsar este botón, las luces de la secuencia 3k+1 (con k≥0) cambian su estado. Es decir, las luces 1, 4, 7, 10,... cambiarán su estado.

En la configuración inicial de la tira de luces, todas las luces están encendidas. Tenemos un contador que registra el número total de veces que pulsamos un botón. Tenemos como objetivo alcanzar una configuración donde 0, 1 o 2 luces concretas estén encendidas y otras tantas apagadas. Debemos diseñar un algoritmo que nos indique todas las configuraciones de luces que cumplan con nuestro objetivo y que podemos alcanzar con un número determinado de pulsaciones de alguno de los 4 botones.

Así por ejemplo, para una tira de 10 luces y con 1 pulsación permitida, podemos alcanzar estas 4 configuraciones:

	1	2	3	4	5	6	7	8	9	10
Configuración inicial	●	●	●	●	●	●	●	●	●	●
Botón 1	○	○	○	○	○	○	○	○	○	○
Botón 2	○	●	○	●	○	●	○	●	○	●
Botón 3	●	○	●	○	●	○	●	○	●	○
Botón 4	○	●	●	○	●	●	○	●	●	○

Si buscamos una configuración en la que la luz nº 7 esté apagada, debemos obtener como resultado del algoritmo las configuraciones resultantes de pulsar el botón 1, 2 ó 4.

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.lights;

import java.util.Collection;

public interface ILightsProblem {
	/*
	 * This method sets the input data for the problem.
	 * @param numberOfLights the number of lights in the strip.
	 * @param numberOfPresses the number of times the buttons are pressed.
	 * @param onLights a list of 0, 1 or 2 integer numbers indicating the lights that must be ON at the end (ligths are numbered from 1 to numberOfLights)
	 * @param offLights a list of 0, 1 or 2 integer numbers indicating the lights that must be OFF at the end (ligths are numbered from 1 to numberOfLights) 
	 * @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 numberOfLights, int numberOfPresses, Integer[] onLights, Integer[] offLights);
	
	/*
	 * Executes the problem if the data has been correctly set
	 */
	public abstract void run();
	
	/*
	 * @return a collection of lights configuration that satisfy the on/off constraints specified by onLights and offLights
	 * It return null if the problem has not been solved yet.
	 */
	public abstract Collection<Boolean[]> getResult();
}

Prueba JUnit

package problems.lights;

import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;

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 LightsTest {
	ILightsProblem lightsProblem;
	int numberOfLights, numberOfPresses;
	Integer [] onLights, offLights;
	Collection<Boolean[]> expectedResult;
	
	
	public LightsTest (int numberOfLights, int numberOfPresses, Integer [] onLights, Integer [] offLights, Collection<Boolean[]> expectedResult) {
			this.numberOfLights = numberOfLights;
			this.numberOfPresses = numberOfPresses;
			this.onLights = onLights;
			this.offLights = offLights;
			this.expectedResult = expectedResult;
	}
	
	 // creates the test data
	@Parameters
	public static Collection<Object[]> data() {
		Collection<Boolean[]> result1 = new LinkedList<Boolean[]> () {{	add(new Boolean[] {false,false,false,false,false,false,false,false,false,false});
																		add(new Boolean[] {false,true ,false,true ,false,true ,false,true ,false,true });
																		add(new Boolean[] {false,true ,true ,false,true ,true ,false,true ,true ,false});
																		add(new Boolean[] {true ,false,true ,false,true ,false,true ,false,true ,false});
																	}};
		Collection<Boolean[]> result2 = new LinkedList<Boolean[]> () {{	add(new Boolean[] {false,false,false,false,false,false,false,false,false,false});
																	add(new Boolean[] {false,true ,false,true ,false,true ,false,true ,false,true });
																	add(new Boolean[] {false,true ,true ,false,true ,true ,false,true ,true ,false});
																}};
		Collection<Boolean[]> result3 = new LinkedList<Boolean[]> () {{	add(new Boolean[] {false,true,true,false,true,true,false,true,true,false,true,true,false,true,true,false,true,true,false,true,true,false,true,true,false,true,true,false,true,true,false,true,true,false,true,true,false,true,true,false,true,true,false,true,true,false,true,true,false,true,true,false,true,true,false,true,true,false,true,true,false,true,true,false,true,true,false,true,true,false});
																add(new Boolean[] {true,false,true,false,true,false,true,false,true,false,true,false,true,false,true,false,true,false,true,false,true,false,true,false,true,false,true,false,true,false,true,false,true,false,true,false,true,false,true,false,true,false,true,false,true,false,true,false,true,false,true,false,true,false,true,false,true,false,true,false,true,false,true,false,true,false,true,false,true,false});
					
															}};
		Object[][] data = new Object[][] { 	{10,1,new Integer[] {},new Integer[] {},result1},
											{10,1,new Integer[] {},new Integer[] {7},result2},
											{70,99999,new Integer[] {51},new Integer[] {4},result3}};
						

	    return Arrays.asList(data);
	  }

	
	@Test
	public void testContactProblem() {
		lightsProblem = new LightsProblem();
		lightsProblem.setData(numberOfLights,numberOfPresses,onLights,offLights);
		lightsProblem.run();
		Collection<Boolean[]> result = lightsProblem.getResult();
		// checks if the mappings are equal.
		Assert.assertEquals("lights: ["+numberOfLights+"], presses:["+numberOfPresses+"]: "
							, expectedResult.size(), result.size() );
		// now we check that the values are correct for every key
		for (Boolean[] resultArray: result) {
			boolean exists = false;
			Iterator<Boolean[]> itb = expectedResult.iterator();
			while(itb.hasNext() && !exists) {
				Boolean[] expectedArray = itb.next();
				Assert.assertEquals("lights: ["+numberOfLights+"], presses:["+numberOfPresses+"]: ", expectedArray.length, resultArray.length);
				exists = true;
				for (int pos = 0; pos < expectedArray.length && exists; pos++)
					if (expectedArray[pos] != resultArray[pos])
						exists = false;
			}
			Assert.assertTrue("lights: ["+numberOfLights+"], presses:["+numberOfPresses+"]: ", exists);
		}
	}
}

Test runner

package problems.lights;

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

Pablo Trinidad 8 noviembre, 2014

Posted In: Aprendiendo algoritmia, Tecnologería