Hasta el post anterior hemos usado ecuaciones bastante sencillas, en las que relacionábamos directamente elementos de nuestro problema. "Casi" se pueden considerar una transcripción directa de los requisitos.
En este post, aprenderemos a introducir variables auxiliares (que quizás no tengan un significado directo con los elementos de nuestro problema), con los que obtendremos valores intermedios de forma que podamos establecer relaciones más complejas como son "que todos los días del viaje deben ser consecutivos" y el cálculo de distancias.
Si has desayunado fuerte hoy y no te dan miedo los lunes ¡vamos con ellas!.
Álgebra de Boole
Cualquier programador conoce las funciones NOT, AND, OR y XOR que operan sobre valores booleanos; y por supuesto conoce su tremenda utilidad. ¿No sería fantástico disponer de dicha lógica? ¡pues ya la hemos usado! (por ejemplo, la restricción 5 del post anterior es un OR).
¡Pero ojo!, al contrario que cuando usamos esas funciones, aquí establecemos relaciones que deben cumplirse recíprocamente, es decir, si indicamos que A = B or C, ¡las variables B y C están condicionadas por el valor que pueda tomar A! cosa que no ocurre en un lenguaje de programación "al uso" (por supuesto que podemos relajar la reciprocidad y considerar sólo implicaciones, pero no es el caso que nos ocupa).
Resulta muy entretenido sacar las inecuaciones ¿te animas a sacarlas tu mismo?.
Por ejemplo, una relación de negación puede establecerse como:
A = 1 - B
Que lógicamente es exactamente la misma ecuación que:
B = 1 - A
Una forma muy sencilla de implicar AND para n bits es la siguiente:
n · A <= B1 + B2 + ... + Bn
A >= B1 + B2 + ... + Bn - n + 1
Si algún bit es 0, la suma de los bits es menor que n y la única forma de que n · A sea menor que n es que A = 0. Si todos los bits están a 1, su suma es n, luego en ese caso, con la segunda inecuación exigimos que A = 1. El recíproco también se cumple, ya que si A = 0 la segunda ecuación exige que al menos un bit esté a 0 y si A = 1 la primera que todos los bits estén a 1.
Un OR ya lo hicimos en la restricción 5 y en lugar de una constante grande, es más correcto establecer el número de sumandos que aparecen en la expresión:
A <= B1 + B2 + ... + Bn
n · A >= B1 + B2 + ... + Bn
Caso de ser todos los bit 0, la primera inecuación fuerza que A = 0, caso de ser alguno 1, es la segunda que fuerza A = 1. Recíprocamente, si A = 0, la segunda ecuación fuerza que todos los bits sean 0 y si es A = 1, es la primera la que implica que al menos un bit estará a 1.
El cálculo de XOR es un poco más retorcido, y (hasta donde yo se) vamos a necesitar una variable auxiliar. Una variable auxiliar que en este caso es booleana (sólo puede tomar el valor 0 o 1). Así, supongamos que queremos obtener u XOR v, lo que vamos a hacer es restringir una variable auxiliar h de la siguiente forma:
h <= u
h <= v
h >= u + v - 1
Y entonces, el valor XOR resultante lo calculamos (para restringirlo allí donde sea preciso) como:
r = u + v - 2 * h
Veamos si es verdad que es un XOR. Si r = 0, los únicos valores de u, v y h que anulan la expresión son todos 0 o todos 1, si son u, v = 0 por las dos primeras inecuaciones h = 0 y si u, v = 1, por la tercera es h = 1, por lo que se cumple. Si r = 1, los únicos valores que hacen que la expresión sume 1 son, que h = 0 y que u y v tomen valores diferentes. Si u y v toman valores diferentes, las dos primeras inecuaciones hacen que h = 0 luego también se cumple. El recíproco se comprueba directamente aplicando las ecuaciones, por lo que ya sabemos calcular el valor XOR de dos variables de nuestro problema.
Consecutivo o no consecutivo
Curiosamente, ni la informática ni las matemáticas me vinieron a la mente cuando se me presentó el problema de exigir que todos los días del viaje sean consecutivos sino que, como el potaje de la abuela, me vino el recuerdo nostálgico de aquellos días en los que, soldador en mano, "estañeaba" componentes para, por ejemplo, construir un detector de flanco (cursando la tan minusvalorada Formación Profesional).
Porque, ¡efectivamente!, si todos los días son consecutivos ¿cuantos flancos obtendremos? ¡dos! (si es de subida o de bajada sólo uno). Veámoslo más despacio.
Un detector de flanco, detecta (se dispara, marca, ...) un cambio en el valor de una señal, así, si tenemos la secuencia "0001111000111", podemos ver que "vienen ceros, subimos a unos, bajamos a ceros y subimos a unos de nuevo" ¿cuantas veces hemos "subido"?, dos. La justificación del término "flanco" proviene de la señal digital que forma dicha secuencia (ej. en la imagen previa).
Detectando días no consecutivos
Todas nuestras variables D (D1, D2, ...) indican los días seleccionados para el viaje y como en el ejemplo anterior, estarán a 0 si no son seleccionados y a 1 si sí, por lo que podemos verlos precisamente como la secuencia del párrafo anterior.
¿Pero cómo detectamos el flanco en una secuencia de bits? ¡con un XOR!, si desplazamos un bit la misma secuencia y hacemos XOR de todos los bits (¡ojo! si tenemos n bits, compararemos n + 1 parejas de bits), obtendremos tanto los flancos de subida como los de bajada, veámoslo con la misma secuencia del párrafo anterior:
| Añadiendo un 0 al final | 0 0 0 1 1 1 1 0 0 0 1 1 1 0 |
| Añadiendo un 0 al inicio | 0 0 0 0 1 1 1 1 0 0 0 1 1 1 |
| ¡XOR! | 0 0 0 1 0 0 0 1 0 0 1 0 0 1 |
Como detectamos tanto los flancos de subida como de bajada, siempre serán pares (y 0 si no hay días seleccionados).
Así, estamos convencidos de que una forma de conseguir especificar en nuestro sistema que todos los días sean consecutivos es hacer que "la suma de los XOR de los días con los días desplazados una posición sea exactamente igual a 2".
Restricción 9: los días seleccionados para la ruta deben ser consecutivos
De la misma forma que definimos nuestra variable D para los días, debemos definir otra para "almacenar" la operación XOR pero habrá una variable más que de días (recuerda, añadimos un bit). A esta variable, la llamaremos H y su índice será el número de día ¡incluyendo el día 0! (las variables D0 y Dn+1 no existen, por simplicidad podemos suponer que siempre son 0 pero puedes ver como lo resolvemos en el código F#).
En F# podemos definirla así:
Ya tenemos todos los elementos para especificar la relación deducida, primero obtenemos la variable auxiliar (¡ojo! no es el resultado del XOR):
En F# será:
Y ahora, sólo tenemos que sumar todos los cálculos XOR y exigir que sea 2:
Que en F# es:
Ciertamente es posible que estas estrategias no te parezcan evidentes o fáciles de deducir pero, ¿acaso algo lo es?, lo importante, es que estas herramientas están a nuestro alcance, que no necesitamos siquiera comprender porqué funcionan, lo importante, es que podemos utilizarlas para resolver (sin resolver) problemas que a priori nos parecen inabarcables.
Ya sólo nos queda otra interesante (no se si fácil o difícil) relación, las distancias recorridas entre checkpoints, con ella, podremos cubrir los pocos requisitos que nos quedan.
Más información |
En genbetadev | Programación declarativa: el superbuscador (I)
En genbetadev | Programación declarativa: el superbuscador (II)
En genbetadev | Programación declarativa: el superbuscador (III)
En genbetadev | Programación declarativa: el superbuscador (IV)
En genbetadev | Programación declarativa: el superbuscador (V)
