:::: MENU ::::

Ensaïmada numérica, el bot que las resuelve

Pues sí queridos amigos,
Un año y medio después he vuelto y os traigo el post que tanto prometí.
En este caso se trata de un pequeño proyecto de PHP que resuelve las ensaïmadas numéricas (sí, con diéresis, que por algo estamos en Mallorca).
Una ensaïmada numérica es un circuito Hamiltoniano, matemáticamente hablando. En este caso es una tabla de 10×10 en cuyas celdas encontramos todos los valores del 1 al 100 ordenados de una forma específica.
Para empezar, colocamos el valor ‘1’ en cualquiera de las celdas que tiene la tabla, sin importar ningún factor, puro azar. A posteriori, tenemos que proseguir rellenando la tabla incrementando de uno en uno el valor que tenemos, y podemos ir distribuyéndolo de forma diagonal, horizontal y vertical, es decir, podemos ir rellenando hacia arriba, abajo, los lados y diagonal, pero siempre dejando un espacio en diagonal y dos en horizontal o vertical, de forma que sería: 1xx2 (siendo x espacios libres), o en diagonal solo uno. No vale “rebotar” o “atravesar” las paredes, y si deja de haber posiciones libres, no se puede continuar, simplemente hay que empzar con una tabla nueva (o volver atrás en la actual).

Para resolver este problema he optado por fuerza bruta y puro azar en vez de recursividad por pura pereza, pero es posible hacerlo con recursividad, y de hecho no sería demasiado difícil (así que… probablemente tendréis el proyecto modificado en un futuro).

Este programa ha sido realizado en PHP, y se recomienda abrir tantas instancias de este como núcleos/hilos tenga el procesador, para acelerar el proceso. En un futuro os lo traeré en C# y/o Java y con multithreading, de forma que podréis ahorraros el trabajo de abrir múltiples instancias.

Para que funcione, debéis crear una carpeta llamada ‘soluciones’ en la raíz del programa y dentro crear un archivo llamado ‘ultima.txt’. En dicha carpeta se guardarán las soluciones en formato HTML con tablas.

Aquí tenéis un ejemplo de ensaïmada numérica generada por el programa:

Resultado al azar del programa

Resultado al azar del programa

He aquí el código: (pastebin también disponible)

<?php
/* Hecho por Martín Durán – www.maduranma.com */

echo “Buscando soluciones…\n”;
$intentos = 0;
while(true)
{
// Todos los números a 0 (para tener algo, si no ya se borrará)
for($d = 1; $d <= 100; $d++)
$r[$d] = 0;

// ¿Dónde ponemos el 1?
$intentos++;
$rs = rand(1,100);
$r[$rs] = 1;
$l = $rs; // Definimos que la última posición es dónde está el uno, hasta un futuro muy cercano

$can = true; // Para que el while continue

while($can)
{
// Obtenemos el número de posición horizontal
if(strlen($l) > 1)
$h = (substr($l, -1) == 0) ? 10 : substr($l, -1);
else
$h = $l;

// Obtenemos el número según el vertical
if(strlen($l) > 1)
if($l == 100)
$v = 10;
else
$v = ($h == 10) ? substr($l, 0, 1) : substr($l, 0, 1) + 1;
else
$v = 1;

// Ponemos que todos los valores del array $m sean true, para comprobarlos luego
for($c = 1; $c <= 8; $c++)
$m[$c] = 1;

// — Movimientos horizontales —
if($h == 8 || $h == 9 || $h == 10 || (($l + 3 > 100) ? true : (($r[$l + 3] != 0) ? true : false)))
$m[1] = 0;

if($h == 1 || $h == 2 || $h == 3 || (($l – 3 < 1) ? true : (($r[$l – 3] != 0) ? true : false)))
$m[5] = 0;

// — Movimientos verticales —
if($v == 8 || $v == 9 || $v == 10 || (($l + 30 > 100) ? true : (($r[$l + 30] != 0) ? true : false)))
$m[3] = 0;

if($v == 1 || $v == 2 || $v == 3 || (($l – 30 < 1) ? true : (($r[$l – 30] != 0) ? true : false)))
$m[7] = 0;

// — Movimiento arriba derecha —
if($h == 9 || $h == 10 || $v == 1 || $v == 2 || (($l – 18 < 1) ? true : (($r[$l – 18] != 0) ? true : false)))
$m[8] = 0;

// — Movimiento arriba izquierda —
if($h == 1 || $h == 2 || $v == 1 || $v == 2 || (($l – 22 < 1) ? true : (($r[$l – 22] != 0) ? true : false)))
$m[6] = 0;

// — Movimiento abajo derecha —
if($h == 9 || $h == 10 || $v == 9 || $v == 10 || (($l + 22 > 100) ? true : (($r[$l + 22] != 0) ? true : false)))
$m[2] = 0;

// — Movimiento abajo izquierda —
if($h == 1 || $h == 2 || $v == 9 || $v == 10 || (($l + 18 > 100) ? true : (($r[$l + 18] != 0) ? true : false)))
$m[4] = 0;

$cm = null;
$cm = array();
foreach($m as $ia => $ib)
if($ib == 1)
$cm = array_merge($cm, array($ia));

// Comprobamos que han salido movimientos
if(($cm != null) ? count($cm) >= 1 : false)
$fm = array_rand($cm); // Movimiento elegido
else
$can = false; // Aquí paramos

if($can)
foreach($cm as $ba => $bb)
if($ba == $fm)
$fm = $bb;

// Nos movemos (si podemos)
if($can)
switch($fm)
{
case 1:
$nl = ($l) + 3;
$r[$nl] = $r[$l] + 1;
$l = $nl;
break;

case 2:
$nl = ($l) + 22;
$r[$nl] = $r[$l] + 1;
$l = $nl;
break;

case 3:
$nl = ($l) + 30;
$r[$nl] = $r[$l] + 1;
$l = $nl;
break;

case 4:
$nl = ($l) + 18;
$r[$nl] = $r[$l] + 1;
$l = $nl;
break;

case 5:
$nl = ($l) – 3;
$r[$nl] = $r[$l] + 1;
$l = $nl;
break;

case 6:
$nl = ($l) – 22;
$r[$nl] = $r[$l] + 1;
$l = $nl;
break;

case 7:
$nl = ($l) – 30;
$r[$nl] = $r[$l] + 1;
$l = $nl;
break;

case 8:
$nl = ($l) – 18;
$r[$nl] = $r[$l] + 1;
$l = $nl;
break;

default:
echo ‘<script>alert(\’error\’);</script>’;
$can = false;
break;
}
}

if($r[$l]  == 100)
{
$nombre_fichero = ‘soluciones/ultima.txt’;
$gestor = fopen($nombre_fichero, ‘r’);
$contenido = fread($gestor, 11);
fclose($gestor);
$contenido = $contenido + 1;
$fp = fopen(‘soluciones/ultima.txt’, ‘w’);
fwrite($fp, $contenido);
fclose($fp);

$d = ”;
$d .= ‘<!DOCTYPE html>
<head>
<title>Soluci&oacute;n ‘ . $contenido . ‘ del circuito Hamiltoniano – Ensaimada num&eacute;rica</title>
</head>
<body style=”margin:3 0;”>
<center>
<table border=”1″ style=”font-size: 57pt;text-align: center; border: 2px solid black;” cellpadding=”2″ cellspacing=”0″>’;
for($a = 1; $a <= 10; $a++)
{
$d .= “\n\t\t\t\t<tr>”;
for($b = 1; $b <= 10; $b++)
{
$d .= “\n\t\t\t\t\t<td width=\”90\” height=\”75\” style=\”height: 89px; text-align: center; border: 2px solid black;\” >”;
$d .= ($r[(($a-1)*10)+$b] == 0) ? “\n\t\t\t\t\t\t&nbsp;” : (“\n\t\t\t\t\t\t” . $r[(($a-1)*10)+$b]);
$d .= “\n\t\t\t\t\t</td>”;
}
$d .= “\n\t\t\t\t</tr>”;
}
$d .= “\n\t\t\t</table>”;
echo “Sol. $contenido encontrada y guardada. Intentos: $intentos”;
$intentos = 0;
echo “\nBuscando soluciones…\n”;
$fp = fopen(‘soluciones/’ . $contenido . ‘.html’, ‘w’);
fwrite($fp, $d);
fclose($fp);
}
}
?>

P.D: He dejado un problema de optimización en los IFs para ver si alguien es capaz de encontrarlo, es simplemente que hay algo que no hace falta que esté. Quien lo encuentre se lleva una camiseta gratis :P

Tweet about this on TwitterShare on Facebook0Share on Google+0Share on Reddit0Email this to someone