lunes, 20 de diciembre de 2010

El Código de la Biblia

El 20 de diciembre va a ser el día del escepticismo, en rememoración de la muerte de Carl Sagan en 1996. El primer día del escepticismo se celebró el año pasado, y digamos que el acontecimiento no trascendió mucho.



Personalmente, los "días del X" siempre me han fastidiado un poquito, pero es que parece que cada vez hay más pseudociencias por todas partes. ¿Es esto simplemente paranoia? Creo que no; échese una ojeada, por ejemplo, a http://amazings.es/2010/12/19/experimentos-y-tendencias-en-google-labs/#comment-15379.

Así pues, quería escribir una entrada sobre el tema en este blog, y estaba pensando en qué batallita contar, ya que no hay muchas pseudociencias relacionadas con la programación. Y entonces me he acordado de la historia de El Código Secreto de la Biblia.

El origen de la historia es antiquísimo, siempre ha habido chiflados haciendo numerología con la Biblia; esos rollos de la cábala y el 666. En varias ocasiones me he topado con innumerados que creían que al ser yo matemático podría aclararles cosas como por qué las fechas importantes de su vida contienen un siete. Pista: si naciste en 1967, como yo, aproximadamente la mitad de las fechas de tu vida contienen un siete. Si tienes 3 fechas, lo más probable es que una de las cifras 3, 4, 5, 6, 7 o 8 aparezca en todas ellas; por no hablar del 9, que aparece en todas las fechas del siglo XX. Si tienes 9 fechas y te permites descartar tres "anomalías", lo más probable es que puedas quedarte con seis fechas con una cifra en común.

Cuando apuntas a la luna, el tonto se queda mirando el dedo.

Cuando señalas un número, el innumerado sólo ve cifras.

Cuando el cabalista mira una palabra, sólo ve letras, y esto es un misterio enormemente sofisticado que requiere muchos años de estudio.

Uno de las técnicas avanzadas de la cábala consiste en tomar una letra de, por ejemplo, cada siete letras de un texto, y buscar formas de conseguir formar nuevas palabras. Esto es bastante fácil en hebreo, porque las vocales no se escriben. Por ejemplo, la frase "ESTO NO TIENE SENTIDO, BURRO" se escribiría "STNTNSNTDBRR"; si empiezo en la segunda letra y tomo una letra de cada tres obtengo "TNTR", que obviamente me sugiere que estoy haciendo una ToNTeRía.

Generaciones enteras de cabalistas se quedaron ciegas buscando mensajes ocultos de esta forma en el Pentateuco (los cinco primeros libros de la Biblia, escritos por Moisés). Cuando aparecieron los primeros ordenadores en los años 60, varios matemáticos israelíes los usaron para buscar cosas, y claro, las encontraron; pero siendo matemáticos se abstuvieron mucho de decir que aquello significaba algo en concreto.

Esta situación de "laicismo matemático" no iba a durar mucho.

Primero fue el Rabí Weissmandl quien empezó a decir cosas poco prudentes; por ejemplo, afirmaba haber demostrado que la Biblia era la palabra de Dios, ya que nadie podría haber ocultado todos esos mensajes sin tener un ordenador. Y también descubrió cuál de las versiones del Pentateuco es la auténtica, ya que contenía un mayor número de ocurrencias cercanas de palabras como "martillo" y "yunque", y otros criterios similares. Lo gracioso es que otras personas usando el mismo procedimiento no llegaron a los mismos resultados; ¿quizás hay que hacerle una ceremonia de purificación a los ordenadores para que los programas funcionen correctamente?

Y luego apareció un periodista norteamericano aficionado a los misterios llamado Michael Drosnin que tenía muchas ganas de crear polémica. Drosnin habría sido simplemente un chiflado más si no fuese porque avisó en 1994 al primer ministro Isaac Rabin de que se produciría un atentado contra él; y, efectivamente, Rabin fue asesinado en 1995.

He aquí su hallazgo en la Biblia: http://www.2012supplies.com/what_is_2012/bible_code_2012.html.



Bien, no parece demasiado impresionante, especialmente si tenemos en cuenta que el nombre del asesino fue descubierto después del asesinato, y que hay que tomar una letra de cada 4.772 para conseguir las cuatro letras de Rabin.

Drosnin nunca se lo ha pensado mucho a la hora de publicar predicciones inquietantes; por ejemplo, en su primer libro sobre el código de la Biblia, en 1997, anunció que la civilización sería destruida en una guerra nuclear en 2000, y que luego Los Angeles sería rematado por la caída de un meteorito gigante en 2006. Pero cuando publicó su segundo libro, en 2002, la fecha del fin del mundo había sido desplazada a 2012. Drosnin, que es ateo, también ha leído en la Biblia que la Biblia fue escrita por unos extraterrestres, que enterraron un obelisco de acero cerca del Mar Muerto con la clave para descifrar la Biblia. Uno pensaría que Drosnin ya la ha descifrado pero, curiosamente, a pesar de ello hizo un viaje para encontrar el obelisco, sin éxito.

La lista de predicciones de Drosnin es muy larga, pero hasta la fecha sólo contiene una profecía cumplida, la de Rabin. También se le ha criticado por hacer varias trampas, como deletrear palabras usando mezclas creativas de hebreo clásico, hebreo moderno, y hasta abreviaciones del estilo de los SMS. Tras enzarzarse en una larga serie de disputas, en una famosa ocasión le espetó a un escéptico "a ver si encuentras predicciones de asesinatos en Moby Dick". Pues escuchado y hecho. Tras muchas horas de CPU invertidas en la búsqueda, se ha encontrado una bonita colección de profecías ocultadas por Herman Melville a mediados del siglo XIX en lo que simplemente parecía una novela. Unas cuantas de ellas se pueden ver en http://cs.anu.edu.au/~bdm/dilugim/moby.html; mi favorita es esta predicción de la muerte de Trotsky, que fue asesinado con un punzón de hielo.



Bueno, pensé que esta batallita encajaría bien en un blog con problemas de combinatoria.

viernes, 5 de noviembre de 2010

Olimpiadas matemáticas II

A ver si resucito este blog ahora que vuelvo a tener algo de tiempo libre...

Un tal Harazi encontró una solución especialmente breve para el problema de la entrada anterior.

Como los enlaces dejan de funcionar con una facilidad pasmosa, repito aquí el argumento de Harazi. Empieza tomando un primo p tal que p-1 sea múltiplo de 4. Entonces p divide a algún número de la forma n2+1. La gracia está en ver que n puede ser pequeño; en concreto, podemos suponer que n<p/2, simplemente porque si p divide a n2+1 entonces también divide a (p-n)2+1. Sea k=p-2n>0; entonces p divide a 4(n2+1)=(p-k)2+4, de forma que también divide a k2+4 y por tanto k≥raiz(p-4). Por tanto, p=2n+k≥2n+raiz(p-4) y ya casi hemos acabado; para obtener la desigualdad final, p≥2n+raiz(p-4)≥2n+raiz(2n+raiz(p-4)-4), que es mayor que 2n+raiz(2n) si p es suficientemente grande.

Otras páginas relacionadas con este problema (encontradas por Roberto): solución 2 comentarios otro problema parecido.

sábado, 3 de abril de 2010

Problema de las olimpiadas matemáticas

Olimpiadas matemáticas

Un amigo mío, Roberto, es doctor ingeniero aeronáutico y profesor, así que lleva una vida matemática interesante. Para él, los aviones no son cosas que vuelan, como para el resto de los mortales, sino cilindros que de metal que se van deformando. Hace mucho tiempo, a raíz de los atentados del 11S, tuvimos una charla sobre si un edificio que se está hundiendo puede girar sobre sí mismo; esencialmente, un edificio es una cosa que está hecha para aguantar su peso en una dirección concreta (la vertical), pero no en otras direcciones, de forma que lo normal es que si lo pones en una postura rara se deshaga por su propio peso. Podría parecer que lo que le gusta a Roberto es retorcer cosas con gente dentro, pero su inclinación natural es más bien evitar este tipo de cosas, por eso es ingeniero en vez de banquero. Bueno, el caso es que hace poco recibí por correo una bonita serie de fotos de un edificio volcado pero no roto, y acordándome de esta charla, se la reenvié.


El comentario de Roberto al ver estas fotos vino a ser algo así como "esto es lo que ocurre cuando haces un edificio con estructura muy dura y cimientos muy blandos". En realidad, sus palabras no fueron éstas, los ingenieros se cuidan mucho de pronunciar la palabra "duro" en vano.

Bueno, el caso es que aprovechando el intercambio de correos, Roberto me contó que había estado haciendo los problemas de la Olimpiada Matemática de 2008, y se le había resistido el tercero:

Demostrar que existen infinitos números n tales que n2+1 tiene un factor primo mayor que 2n+raíz(2n).

Es un problema muy chulo, porque está claro que es verdad, pero todos los ataques directos fallan frustrantemente, así que hay que dar un rodeo. A continuación voy a contar mi solución, que empieza siendo bonita pero acaba de una forma muy fea, la verdad, pero lo mismo quieres dejar de leer en este punto e intentar resolver el problema tú mismo.

Solución

Sea p un primo congruente con 1 módulo 4 lo suficientemente grande (luego veremos que basta que sea mayor que 29). Entonces p=a2+b2, donde a y b son primos entre sí (de lo contrario p no sería primo), y por tanto existen dos números u y v tales que a*u+b*v=1. Entonces

p*(u2+v2) = (a2+b2)*(u2+v2) = (a*u+b*v)2+(b*u-a*v)2 = 1+(b*u-a*v)2

Así que tomamos n=b*u-a*v y ya tenemos un n tal que n2+1 es un múltiplo de un primo p bastante grande para n. Demostrar que la cota p>2n+raíz(2n) se cumple es un poco feo porque iremos por casos; seguro que hay una forma inteligente de hacer esto rápidamente, pero yo no la he encontrado. Dejémosla por un momento para después y "acabemos" el problema. Para cada p construimos un n como antes. Observemos que todos estos n son diferentes entre sí; precisamente porque cumplen la cota, sabemos que su mayor factor primo es p, de forma que a cada p le corresponde un n diferente. Pero claro, hay infinitos p, de forma que también hay infinitos n como pide el problema.

Bien, pues ya hemos acabado, salvo por el detalle de demostrar la cota, cosa que haremos por casos.

El primer caso que tenemos que considerar es a=1 o b=1 (en el siguiente párrafo veremos por qué). Esto es fácil; si a=1, lo que haré es tomar u=1 y v=0, y por tanto n=b*u-a*v=b, con lo cual la desigualdad es cierta porque p = 12+b2 > 2b+raíz(2b) = 2n+raíz(2n) si b≥3, es decir, si p≥11.

Bien, ya podemos suponer que a>1 y b>1. Empezamos tomando u≅a-1 (mod b) y v≅b-1 (mod a), cosa que no podríamos hacer si a=1 o b=1, y por tanto 0≤u<b, 0≤v<a, y a*u+b*v≅1 (mod a*b). Como 0≤a*u+b*v<a*b+b*a=2*a*b, entonces o bien a*u+b*v=1, o bien a*u+b*v=a*b+1. En este segundo caso tiene que ocurrir que o bien u≥b/2 o bien v≥a/2, pero no pueden cumplirse ambas desigualdades, porque a*u+b*v sería demasiado grande; si se cumple la primera, lo que hago es escoger u=mod(a-1,b)-b, y entonces ya se cumple a*u+b*v=1.

Así pues, ya podemos suponer que |u|≤b/2 y |v|≤a/2, y que u2+v2≤(a2+b2)/4. Pero me hace falta ajustar más.

Para eliminar el caso u=b/2 (los casos u=-b/2, v=a/2, v=-a/2 se hacen igual), tenemos que a*u+b*v=1 implica b*(a+2v)=2, con lo cual b es un divisor de 2. El caso b=1 ya lo vimos antes, así que podemos suponer que b=2. Entonces u=1, v=(1-a)/2, n = b*u-a*v = 2*1-a*(1-a)/2 = (a*a-a+4)/2, p=a2+b2=a2+4, y entonces p>2n+raíz(2n) se reduce a

a2+4 > a2-a+4 + raíz(a2-a+4)

a > raíz(a2-a+4)

a2 > a2-a+4

que es cierto para a>4, es decir, para p≥52+4=29. Por cierto, la desigualdad es muy ajustada; para p=29 sale a=5, b=2, u=1, v=-2, n2+1=29*5=145 luego n=12, y por tanto

29 = p > 2n+raíz(2n) = 24+raíz(24) = 28,8989

Así que ahora podemos suponer que |u|<b/2 y |v|<a/2; como estos cuatro números son enteros, esto quiere decir que |u|≤(b-1)/2 y |v|≤(a-1)/2; pero claro, no puede ocurrir que a y b sean impares a la vez, porque entonces el primo p=a2+b2 sería par; luego sabemos que el caso |u|=(b-1)/2 y |v|=(a-1)/2 a la vez no puede ocurrir. Por tanto:

u2+v2 ≤ (b-1)2/4 + (a-1)2/4 -1/4

donde el último 1/4 lo quitamos porque acabamos de ver que el caso u2+v2=(b-1)2/4+(a-1)2/4 no puede ocurrir. Como a+b≥raíz(a2+b2),

u2+v2 ≤ (b2-2b+1+a2-2a+1-1)/4 ≤

≤ (a2+b2+1-2raiz(a2+b2))/4 = (raíz(a2+b2)-1)2/4

Bien, ya falta poco; recordemos que a2+b2=p y que p*(u2+v2) = n2+1, así que

p*(raíz(p)-1)2/4 = p*(raíz(a2+b2)-1)2/4 > p*(u2+v2) = n2+1

(p-raíz(p))2 > 4n2+4 > 4n2

p-raíz(p) > 2n

raíz(p-raíz(p)) > raíz(2n)

p-raíz(p) + raíz(p-raíz(p)) > 2n + raíz(2n)

Como p>p-raíz(p), -raíz(p) + raíz(p-raíz(p)) es un número negativo, y por tanto

p>2n+raíz(2n)

Y vaya chasco de solución; con lo bonitos que eran los dos primeros párrafos...

sábado, 13 de marzo de 2010

Figuras autoparticionables I

Figuras autoparticionables I

Teníamos que hacer en el trabajo, para una editorial, algún ejercicio sobre sómo el área de una figura aumenta como el cuadrado de su perímetro, y me acordé de una cosa que me imagino que debí de leer en algún libro de Martin Gardner vete tú a saber cuándo.

La idea es que con dos escuadras se puede construir una escuadra mayor, cuyos lados son raiz(2) veces mayores que los lados de la escuadra original; y, esto ya es menos conocido, con tres cartabones se puede hacer un cartabón cuyos lados son raiz(3) veces mayores que los lados del cartabón original.

¿Hay más cosas así? Tras pasar unas cuantas horas emborronando folios, la respuesta es que sí, pero hay pocas figuras que sean realmente originales.

La primera solución trivial es que, para todo todo par de números a y b, se pueden juntar a*b rectángulos de lados raiz(a) y raiz(b), girados 90 grados, para obtener un rectángulo cuyos lados son raiz(a*b) veces mayores que el original.

Hay una solución de éstas que no es muy familiar, el caso a=1 y b=2; es la que usamos al partir por la mitad un folio DIN A4 y obtener dos cuartillas DIN A5 semejantes al original (ver http://es.wikipedia.org/wiki/Formato_de_papel).

Cuando multiplicamos el perímetro por un número entero, como 2 en vez de raiz(2), hay montones de soluciones. Para empezar están todos los rectángulos, rombos, y romboides con bases de igual longitud. Además, todos los triángulos se pueden descomponer en cuatro triángulos semejantes en una forma; los triángulos rectángulos pueden hacerlo en dos formas; y el cartabón puede hacerlo en cuatro formas distintas.

Y luego hay un puñado de soluciones medio interesantes, de las que hemos encontrado cuatro (en realidad, las dos últimas ya las conocía, seguro que están en algún libro de Martin Gardner).

Tengo que acabar aquí porque este blog sólo deja poner cinco imágenes por entrada.

Figuras autoparticionables II

Figuras autoparticionables II

Vamos a ver ahora un par de soluciones no triviales. Ojeando el libro de matemáticas del que tenía que hacer los problemas me encontré con un teorema que me imagino que alguna vez conocí pero conseguí olvidar absolutamente. Resulta que si tienes un triángulo rectángulo y trazas su altura, lo partes en dos triángulos que son semejantes al original. Es decir, en este dibujo

los triágulos ACB, ADC y CDB son semejantes. Esto viene muy bien para encontrar más soluciones de nuestro problema, porque basta con que nos aseguremos de que dos catetos encajan un número enteros de veces en la altura para que todos los ángulos coincidan maravillosamente; si se echan las cuentas, sale que podemos encontrar soluciones para todos los valores de a2+b2. Por ejemplo, he aquí una solución en la que juntamos 13=22+32 triángulos para obtener uno semejante 13 veces mayor:

En el lado izquierdo hay 4=22 triángulos, y en el lado derecho otros 9=32 triángulos. ¿No es precioso? He pintado de azul claro dos triángulos orientados de forma diferente a los demás para mostrar que en realidad ahí hay un montón de soluciones, tenemos unas cuantas formas de reorientar los triángulos; de hecho, si hubiese muchos triángulos de 2x3, podríamos girar 90º bloques cuadrados de tamaño 6x6, o girar rectángulos dentro de rectángulos; también podríamos mezclar los triángulos del lado derecho con los del lado izquierdo.

Más soluciones, pero bastante menos bonitas. Sean r, s y t tres números enteros (a ser posible mayores que 0 para no obtener soluciones triviales), y sean a, b y c tres números tales que

Entonces con 2r(s+2t) figuras L como las de la izquierda se puede construir una figura semejante como la de la derecha:

Un ejemplo. Para construir una L que se pueda juntar en grupos de 6, primero buscamos r, s y t tales que 6=2r(s+2t); por ejemplo, r=s=t=1. Luego buscamos b y c tales que b/c=s/t, podemos escoger b=c=1, y finalmente a = raiz(3/2). Nuestra solución es:

De esta forma se pueden generar soluciones no triviales para todos los números pares salvo 2 y 4.

Figuras autoparticionables III

Figuras autoparticionables III

Las siguientes soluciones son muy vistosas pero un pelín triviales.

El número de figuras que se juntan es 36, 16 y 4, todos ellos cuadrados, lo que viene a decir que no son demasiado originales. El truco es el mismo en los casos: encontrar una figura formada por triángulos equiláteros o cuadrados tal que al unirla consigo mismo, rotada 2, 3 o 4 veces, forme un triángulo equilátero o un cuadrado, que al repetirlo forma la imagen original ampliada. Las fichas marcadas en azul indican un truco para obtener más soluciones; también podríamos cambiar la orientación de las fichas dentro de cada triángulo o cuadrado, con lo cual parece que tenemos un montón de soluciones.

¿Que cómo se encuentran figuras así? Bueno, empezamos con un triángulo equilátero dividido de la forma obvia en, digamos, 36 triangulitos. Se escoge uno cualquiera de ellos y se tachan los dos triangulitos sobre los que cae al rotarlo 120º y 240º alrededor del centro del triángulo. Se escoge otro triangulito de entre los que quedan libres y se tachan los dos rotados. Y así hasta que no quedan triangulitos libres. En ese momento se han cogido 12 triangulitos que forman una figura que al ser rotada cubre todo el triángulo.

Yo he escogido una figura con forma de serpiente, por aquello de que parece que los motivos escherianos requieren animales, pero ¿de cuántas formas se puede hacer esto? El primer triangulito se puede escoger de 36 formas; el segundo de 33; el tercero de 30... Como el orden en que se escogen los 12 triangulitos no afecta el resultado, tenemos que dividir por 12!, y como la mayoría de las figuras resultantes no tienen ninguna simetría, hay que dividir por casi 6 para eliminar duplicados, con lo cual podemos obtener cerca de 88.500 soluciones en un triángulo dividido en 36; si lo dividiésemos entre 100...

(Observación: el que 36·33·30·...·3 / 12! sea igual a 312 tiene una bonita interpretación combinatoria: el efecto de la rotación es dividir los 36 triangulitos en 12 clases de equivalencia de 3 triangulitos, y tenemos que escoger un triangulito de cada clase.)

Cuando esto mismo se hace con un cuadrado, podemos eliminar el cuadradito a 180º de distancia, o los tres cuadraditos a 90º.

Pero, además de jugar con rotaciones, podemos usar simetrías axiales; el triángulo equilátero tiene tres ejes de simetría, y el cuadrado cuatro, con lo cual tenemos mucho campo para jugar. Pero los ejes de simetría parten la figura y las soluciones que salen no son demasiado bonitas.

Dejo como ejercicio para el lector encontrar la forma en que las siguientes figuras sirven para hacer soluciones repitiendo el original 8, 9, 16, 16, 16, 16, 36, 36 y 36 veces, de izquierda a derecha y de arriba abajo. No hará falta decir que las más interesantes son la primera, porque 8 no es un cuadrado, y la última, por lo curioso del agujero, que además hace que haya un montón de soluciones diferentes según el orden en que se "abotonen" los agujeros.

Todo esto está muy bien, ¿pero hay alguna solución en la que una figura se repita 7 veces, aparte del rectángulo trivial? Yo la he buscado hasta aburrirme, y estoy dispuesto a apostar un café a que no existe.

martes, 2 de marzo de 2010

Solitario de rayas IX: Análisis del primer acotador

Para decirlo claro, el primer acotador no ha acelerado mucho la exploración del grafo. Comparemos el tiempo requerido para ir llegando a algunos puntos del árbol, los records, que son los datos que se guardan:

RecordSin acotadorPrimer acotadorAceleración
82 líneas141 s170 s-21%
89 líneas390 s456 s-17%
anchura 161,45 h1,51 h-4%
98 líneas10,26 h10,06 h2%
anchura 1712,77 h12,52 h2%
110 líneas2,09 días2,09 días0%

Es interesante ver cómo la aceleración va aumentando. Creo que lo que ocurre aquí es que cuando el récord es alto, prácticamente da igual qué cota se haya obtenido, va a servir para podar la rama. Veamos unos datos; en la siguiente tabla, las dos primeras columnas indican cuántas veces se había alcanzado un cota al llegar al récord de las 82 líneas (2,8 minutos), y el porcentaje de estas cotas que permitieron podar su rama. Las dos últimas indican lo mismo, pero al llegar al récord de 110 líneas (2,1 días).

cotarécord 82récord 110
n% podasn%podas
0570158100%729359516100%
1294770100%374383109100%
291457100%146709781100%
38238493%97683991100%
45466784%58612396100%
53139475%29856109100%
61196459%1363082499%
7867758%586387699%
8505867%218351799%
9594350%72753397%
10203237%28789097%
11199218%13635895%
12311716%6052692%
1355419%938682%
1416310%149663%
15205%7638%
160-2100%
96631172221% sobre
total
42681722023% sobre
total
total147607276%188632360677%

Por ejemplo, antes de llegar al récord de las 82 líneas, hubo 20 ocasiones en que al calcular la cota se llegó a la conclusión de que se podían añadir como mucho 15 rayas más, y en sólo una de estas 20 ocasiones (el 5%) se pudo podar la rama. Pero después de explorar un número de vértices 1000 veces mayor, se obtuvo esta cota 76 veces, y de ellas el 38% permitieron podar su rama. Más llamativo todavía es el caso de la cota 16; sólo se obtuvo dos veces, pero ya avanzado el cálculo, y las dos cotas sirvieron para podar sus respectivas ramas. Vemos que todos los porcentages de podas aumentan, confirmando que, avanzada la búsqueda, la misma cota tiene mayor probabilidad de resultar en un poda, con lo cual aceleramos un poquito.

Pero si podamos tanto, ¿cómo es que no aceleramos muchísimo más? Bueno, es que en realidad no podamos tanto; el porcentaje de veces en que se poda una rama no sube apenas, pasa del 76% al 77%. Esto se debe a que en realidad aumenta el porcentaje de ocasiones en las que no se puede obtener una cota, en cuyo caso se devuelve la "cota de error" 966; este error pasa de ser un 21% del total de acotaciones a 23%.

Es decir, en el 23% de los casos el primer acotador pone demasiados puntos y acaba desbocándose. Nunca se han puesto 17 puntos sin que la cota se disparase hasta el infinito. Es verdad que no pasa gran cosa por no poder conseguir una cota ocasionalmente, pero es que este 23% es un desastre, y encima se produce con más frecuencia en las ramas gruesas, cuando hay más rayas que añadir. Éste es el problema, que en vez de podar ramas gruesas (digamos, de profundidad 40) lo que estamos haciendo es arrancar ramitas (cota 16 como mucho), y por esto no llegamos a acelerar de verdad.

(Podar ramas de cota 16 podría parecer mucho, porque así a ojo podría pensarse que contienen del orden de 216 vértices; el problema es que incluso si siempre podásemos estas ramas, podríamos acelerar el programa en un factor de "sólo" 216=65536, con lo cual no tardaríamos 25.000 millones de años sino sólo 381.000 años. Hombre, sería un progreso, pero no va a ser suficiente para resolver el problema en un tiempo razonable. Hay que podar ramas gruesas, y para ello el acotador tiene que ser capaz de calcular cotas grandes, y para ello no puede desbocarse cuando añada un número pequeño de puntos. Este es precisamente el fallo del primer acotador.)

¿Cuánto cuesta el acotador?

Usaré para comparar el récord de 110 rayas. Sin usar acotador, en 180.247 segundos se llegó a este récord, explorando 15.900.563.680 vértices, luego explorar un vértice cuesta 11,34 millonésimas de segundo. Usando el acotador, en 180.195 segundos se exploraron 10.201.449.392 vértices y se hicieron 1.886.323.606 acotaciones, luego una acotación cuesta en promedio 34,20 millonésimas de segundo. Así pues, una acotación cuesta tanto como explorar tres vértices.

La noticia buena es que el uso del acotador redujo el número de vértices explorados en un 36%. La noticia mala es que el 36% del tiempo se invirtió en calcular acotaciones.

Cada acotación eliminó un promedio de 3,02 vértices. Si nos pudiésemos olvidar de las acotaciones que produjeron cotas de 0 o 1 raya, que siempre son exactas pero representan una pérdida de tiempo, y también de las acotaciones que no consiguieron producir ninguna cota y que por tanto no eliminaron ningún vértice, nos encontraríamos con que las 355.763.761 cotas útiles eliminaron 5.699.114.288 vértices. No es mucho; esto quiere decir que por el coste de 3 vértices nos ahorraríamos 16. Esto podría parecer bueno, pero de nuevo no nos sirve; en el mejor de los casos esto nos permitiría acelerar el programa en un factor 16/3, con lo cual bajaríamos de 25.000 millones de años a 4.700 millones.

¿Qué precisión tiene el acotador?

Cuando el acotador nos dice que a una figura se le pueden añadir como mucho n rayas, ¿hasta qué punto está lejos del máximo real? Bueno, pues mucho. La siguiente tabla, generada tras unas 24 horas de CPU, viene a confirmar que este acotador no es muy preciso. Las columnas profundidad y vértices indican el tamaño de la rama podada. Los datos se refieren únicamente a las ramas podadas, de aquí que parezcan un poco raros.

cotamáximo realprofundidadvértices
0000
111.142492.2850
21.959742.304875.4617
32.501553.047569.4554
43.117493.9344115.5819
53.526294.4857322.7194
63.709974.7724529.2670
74.024615.3114239.1521
84.253675.8014654.8526
94.432456.0947969.5210
104.802066.8321997.9958
114.075576.8079393.4930
123.925697.14832124.9150
133.660417.48019102.2030
143.171985.6347649.2213

Los datos para cotas mayores son completamente ridículos, en parte porque hay pocas ramas y al hacer la media puede salir cualquier cosa. Es un poco triste ver que el máximo real no llega a 5; y eso de que cuando la cota sea de 14 rayas en promedio sólo se puedan añadir 3 es para deprimirse. Pero al menos el número de vértices en las ramas podadas crece de forma parecida a 2profundidad.

El lado bueno es que un acotador que acotase relativamente bien hasta el nivel de 10 rayas aceleraría el programa en un factor de al menos 100.

Conclusiones

  1. El primer acotador es caro en términos de tiempo, pero no demasiado; falla por el lado de la precisión en vez de por el tiempo.
  2. El problema no es exactamente que sea pesimista, sino más bien que con demasiada frecuencia no llega a producir una cota útil.
  3. El segundo acotador debe evitar la posibilidad de pasarse poniendo puntos, y puede ser bastante más caro.

sábado, 20 de febrero de 2010

Solitario de rayas VIII: Record con 110 rayas

Usando el primer acotador, tras 2,1 días de CPU, y buceando hasta el nivel 134 del árbol binario, se ha encontrado este bicho con 110 rayas:

Se exploraron 10.201.449.392 vértices, se llamó al acotador 1.886.323.606 veces, y se podaron 1.459.117.650 ramas. La posición de esta figura en el árbol es 1111111111 1111111111 1111111111 0111111011 1110110111...; es decir, apenas se ha avanzado, tras dos días de CPU sigue en el bit 44 (42 efectivos), luego a este ritmo puede tardar unos 25.300 millones de años en acabar. Antes parecía que iba a bastar con la edad del universo, pero esto está empeorando.

jueves, 18 de febrero de 2010

Solitario de rayas VII: El primer acotador

Tengo que empezar admitiendo que medio he hecho trampas al poner este título; en realidad, ya he probado el primer acotador, así que ahora ya sé que habrá (al menos) un segundo acotador.

La idea es simple; este acotador funcionará en dos etapas:

  1. añadir todos los puntos que se pueda.
  2. averiguar el número máximo de rectas que pueden cubrir los puntos.

Ese "todos los puntos que se pueda" se complica un poquito. En realidad, el criterio que usa este acotador no es para añadir puntos, sino para añadir rayas; lo que pasa es que en cuanto decida añadir una raya, se va a olvidar de ella y va a añadir sus puntos. Éste es el criterio exacto:

  1. Las rayas añadidas no pueden "pisar" las rayas que había puestas antes de llamar al acotador (sí pueden pisar las rayas puestas por el acotador)
  2. Si la raya que se va a añadir tenía exactamente cuatro puntos marcados anteriormente, ninguno de estos puntos puede satisfacer:
    1. haber sido añadido por el acotador;
    2. tener todos sus enlaces usados en la dirección de la raya (en cualquiera de los dos sentidos);
    3. y tener al menos uno de esos enlaces pisado por la raya.

Como siempre, un ejemplo dejará claro qué quiere decir esto. Imaginemos que tenemos que acotar el número de rayas que se pueden añadir a esta figura:

Podríamos añadir una raya que cogiese el punto de la derecha, o otra que cogiese el de la izquierda, pero no ambas rayas. Bueno, pues este acotador en realidad no recuerda si ha añadido una raya o no, lo que ve es que podría añadir cualquiera de ellas, y va a añadir los dos puntos.

Hay que aclarar una cosa; si vemos sólo los puntos, ahora parecería que podríamos añadir dos rayas más, y luego otras dos, y luego otras dos... pero claro, esto haría que añadiésemos infinitos puntos, y no sería muy útil que nuestro acotador dijera siempre "como mucho puedes añadir infinitas rayas". Así que el acotador tiene que recordar cuándo no debe continuar añadiendo puntos. El criterio retorcido de arriba impide esto (si fuésemos a añadir una nueva raya, nos encontraríamos con que tendría 4 puntos marcados previamente y los puntos ahora en los extremos habrían sido añadidos por el acotador, tendrían su único enlace usado en la misma dirección de la nueva raya, y este enlace sería pisado por la nueva raya).

Entonces viene la segunda etapa del acotador. Tenemos seis puntos en fila; ¿cuántas rayas puede haber ahí? Obviamente, sólo una. Para poder poner dos rayas tendría que haber 9 puntos en fila.

Y ya hemos acabado; la cota es uno.

Lo bonito de este algoritmo es que hemos acotado el número de rayas que podemos añadir sin haber decidido qué rayas añadir. Lo malo es que a veces esta estimación va a ser muy mala. Veamos un ejemplo en que el acotador nos cuela una raya de propina; empezamos con esta figura:

El primer punto que añadiremos será S; de hecho, podemos hacerlo de dos formas, uniendo P-R o Y-N. Supongamos que unimos los puntos P-R, y por tanto el acotador recuerda (por el criterio) que no puede continuar añadiendo puntos en esa dirección, así que, de momento, U no se puede añadir.

Una vez hemos añadido S, resulta que podemos añadir T, uniendo Z-S.

Y sorpresa, ahora el criterio nos deja añadir U, porque resulta que ahora no todos los enlaces usados de S están en la misma dirección. Es decir; mientras conocíamos una única forma de llegar a S, el criterio nos impedía continuar en esa dirección; pero una vez hemos llegado a S en dos direcciones (desde N y R), como no se puede saber cual es "la primera", tenemos que dejar continuar en las dos direcciones.

Total, estamos en que el acotador ha descubierto que puede llegar a los puntos S, T y U. Esto es correcto, salvo por el detalle de que por las incompatibilidades entre rayas, se puede añadir o bien T o bien U, pero no ambos. Da igual, este acotador no recuerda incompatibilidades entre rayas. Así que a continuación decide que también puede añadir X; lo único que hay que hacer es añadir la raya T-X. Lo cual es falso...

Y entonces el acotador llega a su segunda etapa; estos son los puntos alcanzables:

que pueden albergar como mucho tres rayas; una horizontal (que se podría escoger de dos formas), una vertical, y una diagonal (que se podría escoger de dos formas). De forma que el acotador dirá que se pueden añadir como mucho 3 rayas cuando, en realidad, el máximo son dos rayas.

¿Es esto muy malo? Bueno, ya sabemos que un acotador rápido no puede ser muy preciso, así que si este acotado nos clavase sólo una raya de más estaríamos muy contentos. El problema es que una vez que empieza a añadir rayas incorrectamente se desboca y acaba añadiendo infinitas rayas incorrectas. Veamos un ejemplo "real"; empezamos con esta figura:


* *
|\ /|
| \ / |
*--#--#--#--#
| \/ |
| /\ |
# * * #
| / \ |
|/ \|
# #
/| |\
/ | | \
# # # # # # # #


# #


# #


# # # # # # # #


# #


# #


# # # #

(Perdón por volver a los gráficos en ASCII, pero es que la salida del acotador no la preparado para matlab...)

Vale, el acotador hace una primera pasada y encuentra que podría añadir 37 puntos:


B B
|\ /|
| \ / |
B--#--#--#--#
| / \/ \ |
|/ /\ \|
@--#--B--B--#--@
/| / \ |\
/ |/ \| \
@ B # # B @
| / /| |\ \ |
| / / | | \ \ |
@--#--#--#--#--B--B--#--#--#--#--B
| / \ | /
|/ \|/
# #
/| /|\
/ | / | \
@ # @ B--B--B--#--B
|\ | | / /|
| \ | | / / |
@--#--#--#--#--B--B--#--#--#--#--@
| \ | | | / / |
| \ | | |/ / |
@ B--#--B--B--#--B--B--B--@
\ | | /| /
\| |/ |/
# B #
|\ /| /|
| \ / |/ |
@--#--#--#--#--@
| / \/| |
|/ /\| |
@--B--B--B--B--@

Pero claro, una vez ha añadido estos puntos, podría usarlos para añadir nuevas rectas; en la segunda pasada, el acotador cree que puede añadir estos 132 puntos:


B B @ B B
|\/|\ \/|\/|
|/\| \ /\|/\|
B--#--#--#--# @
/| |\/ \/|\/|\ |
/ | |/\ /\|/\| \|
B--B--B--B--#--B--B--#--B--B B B @
\ | / |\/|\/ \/|\/|\/|\/| /| /| /
\|/ |/\|/\ /\|/\|/\|/\|/ |/ |/
@ B--B--B--#--B--B--#--B--B--B--B--B
\ /|\ |\/|\/|\/|\/|\/|\/|\/|\/| /| /
\ / | \|/\|/\|/\|/\|/\|/\|/\|/\|/ |/
@--B--#--#--#--#--B--B--#--#--#--#--B--B
/ \ |\/|\/|\/|\/|\/|\/|\/|\/|\/|\/| /
/ \|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/
B--B--#--B--B--B--B--B--B--B--B--#--B--B
\ |\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/| /|
\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/ |
B--B--#--B--B--B--B--B--B--B--B--#--B--B
\ |\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|
\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|
B--B--#--#--#--#--B--B--#--#--#--#--B--B
\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|
/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|
B--B--B--B--B--#--B--B--#--B--B--B--B--B
|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|
|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|
B--B--B--B--B--#--B--B--#--B--B--B--B--B
| /|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|\ |
|/ |/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\| \|
B--B--B--B--B--#--#--#--#--B--B--B--B--B
| /| /|\/|\/|\/|\/|\/|\/|\/|\/|\/|\ |\ |
|/ |/ |/\|/\|/\|/\|/\|/\|/\|/\|/\| \| \|
B--B--B--B--B--B--B--B--B--B--B--B--B--B
| /| /| /|\/|\/|\/|\/|\/|\/|\/|\ |\ |\ |
|/ |/ |/ |/\|/\|/\|/\|/\|/\|/\| \| \| \|
B--B--B--B--B--B--B--B--B--B--B--B--B--B

La razón por la que esto tiene forma cuadrada es que el acotador busca nuevas rectas dentro de un cuadrado, que va ampliando según sea necesario. Como hace la búsqueda de arriba abajo y de izquierda a derecha, las nuevas rayas aparecen "barridas" hacia abajo a la izquierda. En las siguientes pasadas el cuadrado se va ampliando y las rayas acaban invadiendo todo el plano, así que cuando el acotador cree que puede añadir más de 200 rayas nuevas abandona y en vez de devolver una cota sobre el número de rayas devuelve un -1, que viene a decir "NPI".

Bueno, el que el acotador no acote ocasionalmente no es un problema demasiado grave; simplemente exploraremos ramas del árbol que quizás nos podríamos haber ahorrado. El problema sería que no consiguiese acotar con mucha frecuencia.

¿Pero cómo funciona en la práctica? Continuará...


lunes, 15 de febrero de 2010

Solitario de rayas VI: Acotadores

La única esperanza de resolver el problema en un tiempo razonable es que no es necesario explorar todo el árbol, sino que a veces podremos podar algunas de sus ramas.

Por usar un poco de jerga; el algoritmo del que hemos hablado hasta ahora para recorrer todo el árbol (ver primero qué pasa si incluímos una raya, y ver luego qué pasa si la excluímos) es un ejemplo de Backtracking (Wikipedia lo traduce como "Vuelta atrás" pero a mí no me acaba de gustar esta traducción), y ahora queremos cambiarlo a Ramificación y poda, también llamado Ramificación y acotación, o Branch and bound.

Aunque en la Wikipedia lo explican de forma general y abstracta, la idea es sencilla: si tenemos un récord con 200 rayas, estamos en un vértice con 50 rayas, y sabemos que como mucho podremos añadir 50 rayas más, entonces no tenemos que explorar la rama que empieza en ese vértice, porque hagamos lo que hagamos no batiremos el récord. Si podamos muchas ramas y son grandes, podemos ahorrarnos cantidades enormes de trabajo.

El problema está, obviamente, en estimar el número máximo de rayas que se podrán añadir; en la jerga, "acotar el número de rayas".

En muchos problemas hay alguna forma relativamente sencilla de acotar algo; con frecuencia simplemente se calcula una fórmula matemática. En nuestro caso no tenemos tanta suerte; tendremos que usar un programa (una función en realidad) algo complicadillo al que llamaremos acotador.

Un acotador ideal tendría estas dos cualidades:

  1. rapidez
  2. precisión (la cota proporcionada debería estar muy cerca del máximo)

Desgraciadamente, las dos cosas son mutuamente excluyentes. Un extremo: como sabemos que ninguna figura tendrá más de 966 rayas, podríamos escribir un acotador velocísimo que, sin mirar siquiera a la figura, dijese que como mucho se le pueden añadir 966 rayas, y sería correcto, pero nada preciso, y absolutamente inútil, porque nunca serviría para podar una rama. El otro extremo sería escribir un acotador muy preciso que explorase toda la rama y devolviese el máximo exacto de rayas que se pueden añadir, pero entonces sería absurdamente lento; mucho más lento que usar el programa sin acotador. De hecho, no tiene sentido usar un acotador que dé la respuesta exacta y que sea rápido, porque entonces lo usaríamos directamente para resolver el problema. La gracia está en encontrar un punto medio, una forma fácil de encontrar una cota que pode mucho.

En nuestro caso, las llamadas al acotador costarán bastante tiempo, así que, para empezar, lo usaremos sólo cuando el número de rayas incluidas sea mayor que 20 y múltiplo de cinco. Lo más probable es que en el futuro decidamos cambiar esta condición.

domingo, 14 de febrero de 2010

Solitario de rayas V: Simetrías


He modificado el programa para que vaya escribiendo en un fichero el vértice del árbol que está explorando cada vez que explore diez millones de vértices (esto es unos dos o tres minutos). Así puedo interrumpir y rearrancar la búsqueda. Uno podría pensar que esto es necesario por si los apagones, pero no, la experiencia demuestra que el factor limitante aquí son las actualizaciones de Windows: cada semana mi ordenador se tiene que bajar una actualización de seguridad crítica doble rojo fosforito, y luego se reinicia.

El poder empezar a calcular a partir de una figura guardada en disco tiene una importante ventaja, y es que seleccionando varias figuras desde las que empezar podemos recorrer sólo las soluciones realmente diferentes del problema, en vez de recorrer todo el árbol ocho veces a causa de las simetrías.

Por "simetrías" me refiero a dos reflexiones (horizontal y vertical) y una la rotación de 90 grados (rotar 180 grados equivale a reflejar primero horizontalmente y luego verticalmente).

Es decir, estas dos figuras no son iguales entre sí porque no se puede convertir la una en la otra aplicando simetrías

pero estas ocho sí:

porque podemos convertir cualquiera de ellas en las otras aplicando simetrías.

(Por cierto, ¿habrá alguna figura no trivial que bajo una traslación vaya a parar a alguna figura simétrica? Es decir, que permanezca esencialmente invariante bajo una traslación. Es una pregunta tan inútilmente retorcida que lo mismo la pensaré; parte del problema será definir qué significa "no trivial", porque hay figuras así con hasta cuatro rayas.)

La mayoría de las figuras aparecerá por octuplicado, pero algunas figuras tienen alguna simetría (es decir, al aplicarles una de las simetrías caen exactamente sobre sí mismas) y aparecerán cuatro, dos, o incluso una única vez; por ejemplo:

Lo que interesa para ahorrar tiempo es no encontrar ocho veces las figuras que no tienen ninguna simetría; parece razonable pensar que las figuras con alguna simetría serán una minoría minúscula, y por tanto no nos preocuparemos de ellas.

¿Qué tiene todo que ver con leer de un fichero en el disco duro la posición desde la que se debe continuar la búsqueda? Bueno, imaginemos que queremos buscar algo en todas las figuras que tienen exactamente una de las ocho rayas de la izquierda (se ven sólo "cuatro rayas largas" porque las ocho se solapan a pares). Entonces arrancaríamos el programa empezando desde la posición de la izquierda, en la que la raya verde estaría incluida y las seis rayas negras estarían excluidas, es decir, en la lista de rayas que no se deben incluir:

Cualquier figura que tenga exactamente una de las ocho rayas podrá ser rotada y reflajada de una única manera para coincidir con estas condiciones. No es necesario indicar que la última raya (arriba a la derecha) no debe ser incluida, porque al tener que incluir la de la izquierda ya lo impedimos.

Esto funciona muy bien para el caso en que haya una única raya de esas ocho, ¿pero qué ocurre si hay dos o más, o ninguna? Me equivoqué al decir que debería ser fácil evitar todas las figuras duplicadas, porque los otros casos han resultado ser complicadillos, y hay que empezar a subdividirlos.

Es decir: el problema general, buscar en todas las figuras, primero lo dividimos en cinco casos, y cada uno de estos casos lo subdividimos en los subcasos que sean necesarios:

  1. Las figuras que tienen exactamente una de las ocho rayas. Es el caso bonito, analizado arriba, y sólo requiere un subcaso sin simetrías.
  2. Las figuras que no tienen ninguna de las ocho rayas. Tiene un subcaso muy trivial en el que no ganamos nada porque todas sus figuras siguen apareciendo por octuplicado.
  3. Las figuras que tienen exactamente dos de las ocho rayas. Tiene cinco subcasos, cuatro de ellos con simetrías, mencionados más abajo.
  4. Las figuras que tienen exactamente tres de las ocho rayas. Tiene tres subcasos sin simetrías.
  5. Las figuras que tienen exactamente cuatro de las ocho rayas. Tiene cuatro subcasos, uno con una simetría y otro con dos.

(No es posible tener más de cuatro de esas rayas porque cada vez que incluimos una, excluimos otra.)

Por ejemplo, el caso en que haya exactamente dos de esas ocho rayas puede ser subvidivido ineficientemente en estos cinco subcasos, de los que cuatro tienen simetrías (indico en azul el eje de simetría):

Obviamente, es malo que los subcasos que vayamos a usar tengan simetrías, porque permitirán que algunas figuras encajen en ellas de varias maneras.

Una forma de arreglar esto sería dividir estos subcasos con simetrías en más sub-subcasos, pero de todas formas no nos acabamos de librar de las simetrías.

¿Es esto muy malo? He echado unas cuentas suponiendo que la probabilidad de que aparezca una línea en un par de líneas solapadas es 1/3, y la probabilidad de que no aparezca ninguna es 1/3. Esto es muy discutible, pero como he construido los casos usando las primeras líneas, que "normalmente se ponen", no parece del todo equivocado. Me sale esta tabla, donde "m" se refiere al trabajo mínimo, es decir, el número de vértices que se explorarían si se evitasen todas las epeticiones:

número de casostrabajo totaltrabajo repetido
1 casom * 8m * 7
14 casosm * 1,4321m * 0,4321
36 casosm * 1,1728m * 0,1728
93 casosm * 1,0795m * 0,0795
235 casosm * 1,0387m * 0,0387
579 casosm * 1,0192m * 0,0192

Uf. Bueno, a pesar de sean números aproximados, sugieren que el trabajo duplicado es proporcional al logaritmo del número de casos dividido entre el número de casos.

No me veo arrancando un programa 579 veces para ahorrarme un 2% de trabajo, hay algo contradictorio en esta frase. De repente, la opción de dejar que el ordenador trabaje por octuplicado no parece tan mala. A menos que aparezcan cientos de voluntarios pidiendo ramas para buscar en paralelo, me parece que intentaré dividir el problema en 14 casos, y ya está.

Quizás las cosas no tengan que ser tan complicadas; yo he examinado los casos a partir de esas ocho rayas iniciales, pero ¿sería posible escoger otras rayas que hiciesen más fácil el análisis? Quién sabe; yo las he buscado y no las he encontrado. Por feo que parezca todo esto, me temo que es lo que hay.

lunes, 8 de febrero de 2010

Solitario de rayas IV: Record de 17 puntos

Hace una semana que no escribo ninguna entrada, así que lo mismo empieza a parecer que he abandonado el problema. ¡En absoluto! Es simplemente que me he entretenido jugando en vez de escribir. Como prueba exhibo este espécimen capturado por uno de mis programas exploradores, que en una inmersión de 12 horas descendió a las profundidades abisales de un árbol binario de 121 niveles buscando un ejemplar cuya distancia entre cuernos superase el record anterior de 16 puntos.

domingo, 31 de enero de 2010

Solitario de rayas III: Qué ocurrió en los bits 31 y 38


He escrito unas funcioncitas para matlab que me ayudarán a hacer los gráficos; usar paint es muy sencillo y te saca de un apuro, pero hasta ahora no he conseguido hacer dos dibujos parecidos.

He mirado qué es lo que ocurrió en los bits 31 y 38, y resulta que no ocurrió nada de particular, sino simplemente lo que ya sabe cualquiera que haya hecho unos cuantos solitarios. Con cierta frecuencia llegas a un cuello de botella, donde parece que te vas a quedar sin poder poner más rayas, pero, si consigues salir del atasco, entonces puedes añadir un montón de rayas sin apenas pensar.

Tras poner la raya número 30, las cosas están así:



Estamos en uno de los cuellos de botella; poner rayas arriba fue muy fácil, pero ahora quedan pocas opciones, y si ponemos la primera raya que vemos (la verde de trazo grueso) metemos la pata, porque a continuación sólo será posible añadir cuatro rayas más (en verde con trazo delgado).



Usar esa raya es un error; lo que habría que hacer es añadir la otra raya horizontal, cosa que nos permite "cerrar un puente" (las dos rayas verdes gruesas). Enseguida podemos poner otras cuatro rayas verdes. ¿Significa esto que hemos salido del atolladero? No del todo; la quinta raya (azul claro grueso) vuelve a ser un error, después de añadirla sólo podemos añadir dos rayas más.



Es una mala idea añadir esa diagonal, porque la queremos un poco más abajo. Así que si no la ponemos y en su lugar añadimos la horizontal del fondo, entonces sí que volvemos a tener todas las opciones que queramos, y podemos añadir sin pensar las siguientes 28 rayas que veamos.



Yo esperaba que estos cuellos de botella fuesen más frecuentes, porque ayudarán a que podamos eliminar muchas opciones. Pero en el primer intento de poner 64 rayas hemos pasado sólo por dos (o uno, según se mire). Explorar sin restricciones no es bueno. Por ejemplo, si el record tuviese 180 rayas, y tuviésemos suerte y lo encontrásemos en el segundo día de búsqueda, y los quedásemos unas horas explorando por el bit 140, la cuenta del otro día nos diría que tardaríamos 48 horas por 2140, es decir, 3·1039 años.


jueves, 28 de enero de 2010

Solitario de rayas II: Midiendo a Goliat

No me acordaba yo de lo obsesivo que puede llegar a ser este problema. No llega al extremo del Tetris, que hacía que fueses viendo fichas cayendo mientras caminabas por la calle, pero después de unas horas haciendo solitarios, cuando miro al teclado del ordenador empiezo a trazar mentalmente rayas uniendo las letras. Es especialmente hipnótico el barrer con la mirada un solitario casi acabado, cuando no tienes que aplicar ninguna estrategia, ni tienes que decidir qué rayas pones antes que otras, sino que simplemente debes buscar huecos donde añadir una nueva raya.

Ayer acabé mi primer programa y lo puse en marcha. El pobrecito era mera carne de cañón, estaba destinado a estrellarse sin posibilidad de victoria contra un enemigo muy superior numéricamente.

La noticia buena es que, a pesar de sus limitaciones, este programita ha sido capaz de encontrar una solución con 98 rayas en 11 horas:


*
|\
| \
*--*--*--*--* * *
|\ |\/|\/| |\/|\/|\
| \|/\|/\| |/\|/\| \
* * *--#--#--#--#--*--*--*--*
\ |\/|\/|\/|\/|\/|\ |\ |\ /|
\|/\|/\|/\|/\|/\| \| \| \ / |
* *--#--*--*--#--*--*--*--*
/|\/|\/|\/|\/|\/|\ |\/|\/ \/|
/ |/\|/\|/\|/\|/\| \|/\|/\ /\|
* * *--#--*--*--#--*--*--*--*
/|\/|\/|\/|\/ \/|\/|\/|\/|\/|\/|\
/ |/\|/\|/\|/\ /\|/\|/\|/\|/\|/\| \
*--#--#--#--# * *--#--#--#--# * *
\ |\/|\ |\/ \/ \/| / \/|\/|\/|\/| |
\|/\| \|/\ /\ /\|/ /\|/\|/\|/\| |
#--*--*--*--*--*--*--*--*--#--*--*--*
|\ |\/|\/ \/|\/|\/ \/|\/|\/| |\ |
| \|/\|/\ /\|/\|/\ /\|/\|/\| | \|
*--#--*--*--*--*--*--*--*--*--#--*--*
\ |\/|\ |\/|\ |\/|\/|\/|\/|\/|\/| /|\
\|/\| \|/\| \|/\|/\|/\|/\|/\|/\|/ | \
#--#--#--#--*--*--#--#--#--#--*--*--*
/ \ |\ |\ |\/|\/|\/|\/|\/|\/|\/|\/| /
/ \| \| \|/\|/\|/\|/\|/\|/\|/\|/\|/
* *--*--#--*--*--#--*--*--* * *
\ |\/|\/|\/|\/|\/|\/|\/|\/| /
\|/\|/\|/\|/\|/\|/\|/\|/\|/
*--#--*--*--#--*--*--*--*
|\/|\/ \/|\/|\/|\/| /| /
|/\|/\ /\|/\|/\|/\|/ |/
*--#--#--#--#--*--*--*--*
| / / |\ \ |\/|\/|
|/ / | \ \|/\|/\|
* * *--*--*--*--*
| / | \ |\ |
|/ | \| \|
* * * *
|
|
*

En cuanto a la anchura, lo mejor que ha encontrado tenía 16 puntos de lado a lado; me parece poco, tendré que echarle un ojo al programa a ver si tiene algún error.

La noticia mala es que durante veinte horas ha explorado 5.500 millones de figuras, y esto ha resultado ser una fracción ridículamente insignificante del problema. Echemos unas cuentas.

Para entender lo que significan los datos que pondré después, tendré que explicar lo que significan las ristras de unos y ceros. Lo que hace este programa para analizar una figura es dividirla en dos casos:

  1. buscar una raya que pueda ser añadida
  2. añadir esta raya (esto se representa con un 1) y analizar la figura obtenida
  3. quitar la raya (esto es un 0) y analizar la figura, recordando no volver a añadir nunca más esa raya
  4. acabar; volver al análisis anterior, de donde venimos.

A cada caso analizado, el programa escribe una secuencia de unos y ceros, indicando dónde está en este procedimiento; por ejemplo, la cadena "101..." quiere decir que todavía está analizando el caso en que pone la primera raya, no pone la segunda, pone la tercera,...

Un ejemplo; empezamos con estos puntos marcados:



Obviamente sólo podemos añadir cuatro rayas, que supongamos que el programa va encontrando en este orden: rojo, verde, azul, marrón.



Sólo hay 9 posibilidades, porque si decidimos poner la línea roja, entonces no podremos poner la marrón, y si decidimos poner la verde, no podremos poner la azul. Estas nueve posibilidades son exploradas mientras se recorre este árbol:



Bueno, pues esta tabla resume la búsqueda hasta ahora.


RécordTiempoPosición en el árbol
67 rayas1 seg1111111111111111111111111
1111101111110111111
111111
111111111111100111111
75 rayas4 seg1111111111111111111111111
1111101111110111111
111111
1110111011101111100111111
1111111
77 rayas20 seg1111111111111111111111111
1111101111110111111
111111
0011110110001100110111111
1100110111111111
82 rayas2,5 min1111111111111111111111111
1111101111110111111
111101
0011111010111011111011101
11111111111111
anchura 161,5 horas1111111111111111111111111
1111101111110111111
110100
1111011111111110111110011
101111111011101110111
98 rayas11 horas1111111111111111111111111
1111101111110111111
011100
1100110111001101111101110
1101111111111111111110111
11111011111111
-20 horas1111111111111111111111111
1111101111110111111
010001
1011001000110110100010110
11110101101110

Una cosa que me llama mucho la atención son esos dos bits que aparecen puestos a 0, el 31 y el 38, los marcados en verde. ¿Qué narices habrá pasado ahí para que el ordenador se haya podido dar cuenta de que esas dos rayas no deben incluirse? Han estado ahí desde el primer segundo. Tengo curiosidad, esto habrá que investigarlo.

Pero el caso es que seguimos trabajando en el bit número 44; todas las secuencias empiezan con la misma ristra de 44 unos y ceros (marcada en rojo). Vale que como hay dos bits inútiles podemos decir que estamos trabajando en el bit efectivo número 42, pero de todas formas esto sugiere que en 20 horas hemos hecho la 2-42-ava parte del trabajo. En otras palabras, este programa podría acabar dentro de unas 20*242 horas, es decir, dentro de 10.000 millones de años. Tampoco es para tanto; si hubiésemos empezado a calcular cuando el Big Bang, ya habríamos acabado (sería una forma como otra cualquiera de darle un propósito al universo).

¿Nos habremos metido con un problema demasiado grande? Al escribir esto me estoy rascando la barbilla con aire preocupado. Bueno, parece claro que nos lo vamos a tener que currar, pero nos quedan unos cuantos trucos en la manga. Por ejemplo, considerando que debido a las simetrías del problema encontraremos casi todas las soluciones por octuplicado, debería ser fácil rebajar el tiempo a unos 1.250 millones de años. Pero lo que tenemos que hacer con nuestro árbol es podarlo a lo bestia. Próximamente en este blog: branch and bound.


miércoles, 27 de enero de 2010

Solitario de rayas I: Introducción

Hace 20 años, en mi primer curso de carrera, me estuve dedicando con unos compañeros de clase a hacer un tipo de solitario que requiere papel cuadriculado. El juego empieza marcando 36 puntos de esta forma:


El juego consiste en buscar grupos de cinco puntos alineados y consecutivos de los que al menos cuatro ya estén marcados, en direcciones horizontal, vertical y diagonal. Entonces se dibuja el segmento y se marca el punto que no estuviese marcado. Tres ejemplos dejarán esto claro:


El objetivo del juego es, simplemente, añadir el mayor número posible de rayas.

¿Hasta dónde se puede llegar? Pues bastante lejos. No consigo recordar si mi récord personal era 142 o 182 rayas, pero había bastante gente que me ganaba. He aquí un solitario con 90 rayas que acabo de hacer sin estar entrenado:


El compañero que nos enseñó el juego decía que era posible llegar hasta las 2.000 rayas, pero esto se lo debió de inventar. Para justificar esto, observemos que al principio cada punto marcado tiene ocho "enlaces libres"; es decir, podría ser conectado con ocho puntos vecinos. Cuando dibujamos un segmento y marcamos el punto en uno de sus extremos, usamos siete enlaces y añadimos un punto con siete enlaces libres.


Cuando dibujamos un segmento y marcamos un punto interior, quitamos en total seis enlaces, pero añadimos un punto con seis enlaces. Y, finalmente, cuando dibujamos un segmento que une cinco puntos ya marcados, entonces perdemos 8 enlaces libres. Es decir, mientras vamos haciendo el solitario, el número de enlaces libres que tienen los puntos marcados sólo puede disminuir; y empezarán a alejarse entre sí cuando la figura se haga mayor y mayor, de forma que tarde o temprano se hará imposible añadir nuevos segmentos.

Al empezar tenemos 36 puntos, cada uno con 8 enlaces libres, con lo cual tenemos un total de 288 enlaces libres iniciales.

Bueno, pues pensemos ahora en un octógono que tenga 13 puntos en cada lado:


Esta figura tiene 4 enlaces libres en cada esquina, y 3 en cada uno de los otros puntos en su frontera, de forma que en total tiene 296 enlaces libres, más de los que tendrá cualquier figura que podamos obtener haciendo el solitario. Quizás sea posible que alguna figura del solitario no quepa en el octógono (aunque yo apostaría a que no), pero estas figuras tendrán una razón perímetro/área mayor, y por tanto menos rayas que la mejor figura. No estoy siendo muy riguroso aquí, pero me imagino que se me entiende.

Dado que en el octógono sólo caben 966 rayas (estaría bien que alguien confirmase esta cuenta), y que la mejor solución del solitario estará dentro del octógono, la mejor solución del solitario tendrá menos de 966 rayas; de hecho, podemos apostar a que tendrá bastante menos de 966 rayas.

Así pues, he aquí los dos problemas que nos proponemos resolver:
  • Encontrar la figura del solitario con el mayor número de rayas.

  • Y, de paso, encontrar la figura del solitario más alargada, para ver si cabe o no dentro del octógono.
El número de posibles subconjuntos de rayas dentro del octógono es una salvajada, algo así como 24000. Por decirlo de una forma suave, no vamos a poder analizarlos todos ni siquiera cuando tengamos ordenadores con cuatro procesadores. Pero el caso es que, cuando uno se pone a jugar al solitario, no tiene la impresión de tener muchas opciones para poner nuevas rayas, así que quizás no es tan absolutamente imposible encontrar la solución.

En otras palabras: no tenemos ni idea de si podremos resolver el problema. ¡Esto va a ser una aventura!