:::: MENU ::::

Llevemos el factorial al extremo

En este post vamos a utilizar como lenguaje C# y Scala, no obstante sería posible hacerlo con otros lenguajes con sus correspondientes librerías de BigInteger.

Si habéis hecho cualquier curso, universitario, por internet, etc; para practicar recursividad, siempre se suele plantea el siguiente ejercicio:

Haga un método recursivo para calcular n! (n factorial).

Cuando se nos plantea el ejercicio, siempre hacemos algo así:

public static UInt32 Fact(UInt32 n)
{
    if (n < 2)
        return 1;
    return n * Fact(n - 1);
}

Tenemos un UInt32 llamado n, es decir, un int pero sin signo, de forma que no puede ser negativo, como argumento.
Si n es menor que 2, sabemos que 1! y 0! son 1, así que devolvemos 1 directamente.
De lo contrario, devolvemos n * (n-1)!.

«Bien, ya le he enseñado a hacer el ejercicio a mi alumna de repaso», pensé.
Pero luego empecé a darle vueltas a la cabeza; sé cuanto es el máximo para enteros de 32 bits, también el de 64 bits…
Sabía que los factoriales, al ser exponenciales, se dispararían en cuanto a dígitos se refiere, así que busqué en Google: «factorial de 1.000», «factorial de 2.000», «factorial de 3.000″… Así hasta llegar a 10.000, numero posterior al cual no encontré resultados…

En ese momento yo y mi curiosidad, y aprovechando que mi alumna utilizaba C#, me propuse calcular todos los factoriales de 0! a 1.000.000! (simplemente por curiosidad) con la librería BigInteger.

public static BigInteger Fact(BigInteger n)
{
    if (n < 2)
        return 1;
    return n * Fact(n - 1);
}

Sí, era fácil adaptarlo… El problema fue que al ponerlo en práctica descubrí que haciéndolo recursivamente llegaba a un límite muy por debajo de lo esperado, en concreto alrededor de 7.000!, ya que depende del tamaño de la pila de llamadas del sistema, y esta no es muy grande (en mi caso), por lo que hacerlo de esta forma no era la solución.

StackOverflowException

Si bien es cierto que se puede cambiar el límite de la pila (en Unix suele ser mayor por defecto) y algunos compiladores podrían hacerlo con saltos, no es el caso, así que optaremos por un clásico bucle for.

A la función que nos devuelve el Factorial sin recursividad, la llamaremos NRFact(n).

public static BigInteger NRFact(UInt32 n)
{
    BigInteger r = 1;
    for (; n > 1; n--)
        r *= n;
    return r;
}

Si nos fijamos, es un simple for que va decrementando n y multiplicándolo por r en cada iteración, siendo este inicialmente 1.
El bucle for no tiene inicializador ya que n per se es el valor inicial.

Con esto ya podemos calcular factoriales enormes. Necesita cierto tiempo para calcular valores grandes, ya que tiene que iterar muchas veces y el proceso de multiplicación es más costoso de forma exponencial conforme aumentemos n.

No obstante, yo no quería quedarme ahí, así que decidí hacer un programa que calculase los factoriales de 0 a 1.000.000 y, de esa forma, poder mostrarlos luego en una página web, o de la forma deseada, pues calcularlos es costoso y podemos necesitarlos de forma más rápida, así que decidí guardarlos como documentos de texto plano cuyo nombre era el valor a factorializar.

Aquí entraba en cuestión el que las memorias secundarias (como es el caso de un SSD) no son comparables de ninguna forma en cuanto a velocidad con las primarias (como puede ser la RAM), por lo que se crea un gran cuello de botella, y tarda muchísimo más en guardar el resultado en disco que calcularlo en sí.

O eso pensé yo al obtener tiempos de más de 6 segundos… Hasta que pasé mi código de C# a Scala, es decir, ejecutado en la Java Virtual Machine y utilizando el IO de Java, y pasó de 6 segundos a escasos 100 milisegundos por archivo escrito.
Diréis que en C# hay diferentes alternativas y así es, probé muchísimas alternativas para escribir los archivos, incluso intenté hacerlo asíncrono o crear 8 threads escribiendo un archivo por vez… Pero no mejoró en absoluto.

Diferencia Milisegundos/archivo guardado.
Menor es mejor.

Es importante recalcar que ambos tardan 0 milisegundos en calcular cada factorial (al menos en los números que se manejan ahora), la diferencia es puramente en sus librerías de I/O y/o rendimiento.

Por ello, os dejo el código completo para ir generando los Factoriales y guardarlos en .txt en Scala:

package main

import java.math.BigInteger
import java.io._

object Factorial {
  def main(args: Array[String]): Unit = {
    var r = new BigInteger("1")
    for(i <- 1 to 1000000) {    // Aquí ponemos el valor límite a calcular
      val startTime = System.currentTimeMillis
      r = r multiply new BigInteger(i.toString)

      val fileName = "C:\\Factorial\\" + i + ".txt";  // Aquí la ruta
      val file = new File(fileName)
      if(!file.exists) {
        file.createNewFile
        val writer = new BufferedWriter(new FileWriter(fileName))
        writer.write(r.toString)
        writer.close
      }

      println(i + " - " + (System.currentTimeMillis - startTime) + "ms")
    }
  }
}

Con el fin de poder visualizar los factoriales ya calculados por mi programa (cuyo objetivo es llegar a 1.000.000! gradualmente), podéis acceder al siguiente enlace.


Calcular PI con lanzamientos

¿Nunca has escuchado que se puede calcular PI de forma aproximada con granos de arroz?

Pues muchas de esas formas de calcular PI de forma aproximada se pueden realizar programáticamente, ya que al fin y al cabo se basan en el azar y en la colocación en un plano de elementos.

Para esto, nosotros vamos a utilizar «agujas» (o cualquier elemento que tenga dicha forma, ya sean palillos u otro que queramos imaginar).

¿Por qué agujas? La fórmula que utilizamos es derivada de La aguja de Buffon, acerca de la cual os dejo un artículo interesante:
http://www.estadisticaparatodos.es/taller/buffon/buffon.html

¡Vamos a ello!
Se nos dice que, si tenemos un plano dividido en filas del mismo alto que el tamaño de unas simples agujas, siendo esas divisiones marcadas con lápiz, y lanzamos una cantidad N de agujas sobre ese plano, con la cantidad de colisiones entre las agujas y las líneas marcadas N’ y una simple fórmula obtendremos aproximadamente PI.

A todo esto y aplicando la lógica, no hace falta decir que a mayor número de intentos, mayor «precisión» obtendremos, siempre sabiendo que es imposible obtener el número exacto, y más sabiendo que tiene infinitos decimales.

La fórmula que nos proporcina La aguja de Buffon es la siguiente:

 π = 2N/N'
Siendo
N los lanzamientos totales
N' la cantidad de colisionens

Por tanto, teniendo dicha fórmula, nos ponemos manos a la obra y obtenemos dicho código (PHP):

<?php
// Config
$times = 1000000; // Lanzamientos de aguja
$size = 30; // Tamaño de aguja
$lines = 40; // Cantidad de líneas
$separation = $size; // Separación entre líneas (tiene que ser igual al tamaño)

$gridsize = $lines * $separation;

$count = 0;

for($i = 0; $i < $times; $i++)
{
	// Generamos aguja
	$position = rand(0, $gridsize);
	$angle = rand(0, 90);
	
	// Detectamos las líneas de arriba y abajo (nos ahorramos generar un tablero y recorrerlo en busca de colisiones)
	$upper = floor($position / $separation) * $separation;
	$bottom = ceil($position / $separation) * $separation;
	
	// Borde arriba y abajo de la aguja
	$up = $position - sin(deg2rad($angle)) * $size/2;
	$down = $position + sin(deg2rad($angle)) * $size/2;
	
	if($up <= $upper || $down >= $bottom)	// Si tocan o pasan por encima...
		$count++;							// Sumamos 1 al contador
	
	// Para debuggear:
	// echo 'Pos: ', $position, ' | a: ', $angle, ' | Upper: ', $upper, ' | Bottom: ', $bottom, ' | Up: ', $up, ' | Down: ', $down, "\n";
}

echo 'Colisiones: ', $count, '/', $times, "\n";

// Calculemos PI
echo 'PI = ', 2*$times/$count; // Aplicamos la fórmula

while(true){} // Mantengamos la consola abierta para ver el Output

Como siempre, aquí os dejo el enlace a paste.bin:
https://pastebin.com/KtFpbYVa

Y con simplemente con este trocito de código, habremos aproximado PI de forma casera. Cuanto más aumentemos $times, más cerca de 3,14 estará el resultado.

Os recomiendo también ir probando con otros tamaños de agujas o cantidad de líneas, puede ser que varíe el resultado, pese a que la teoría indique que no.

Aquí podemos ver 2 resultados de prueba:
633840/1000000 colisiones // PI = 3.1553704404897
632918/1000000 colisiones // PI = 3.1599670099444
No son lo más preciso del mundo, pero nos puede valer :)

Y con esto, ¡me despido y os deseo una feliz semana!


La evolución: Local Storage & Session Storage

¡Hola programadores!
Como ya dije hace un tiempo, me niego a poner el cartelito de las cookies, pero bueno, luego en la práctica no es para nada necesario y en realidad… si os quedáis hasta abajo, veréis que en este tema, no influye.

Sea como fuere, no vengo a hablar de esto, si no de la evolución de la web. Y es que Local Storage y Session Storage (aunque personalmente desprecio completamente la segunda), nos permite ver hacia dónde apunta el desarrollo web, y es que estas no pueden ser accedidas por el servidor.

¿Qué significa esto?
Muy fácil: así como las cookies son accedidas por el servidor, normalmente, ya que se mandan junto a las cabeceras, para controlar el logueo de los usuarios; el Local Storage, que no es más que un objeto en JavaScript en el cual podemos guardar strings, u objetos (si contamos que podemos hacer uso de funciones como stringify o parse de JSON), que es almacenado en el navegador al igual que las cookies, no puede ser leído ni se envía mediante las cabeceras al servidor.
Esto último implica que tenemos que usar JavaScript sí o sí para poder interactuar con dichos objetos, de esa forma esto marca una tendencia hacia tener un cliente que muestra la web a base de pequeños datos, como pueden ser objetos JSON, XML (que ya va quedando obsoleto…) u otros métodos como la utilización de node.js, en lugar de que sea el servidor que pre-procese el HTML añadiéndole el contenido.
Obviamente con cookies ya se podía hacer esto, permitiendo además que el servidor leyera directamente de ellas la información que necesitaba para identificar al usuario, pero que las nuevas tecnologías como es LocalStorage apunten a evitarlo, implica y marca una tendencia a seguir.

¿Es mejor?
En caso de usar node.js/websockets, no nos va a afectar, puesto que podíamos leer las cookies desde JavaScript con el objeto docmuent.cookie, pero eso reduce en un pequeñísimo porcentaje la carga de la web, puesto que no tiene que enviar las cookies mediante las cabeceras.
Si usamos PHP puro, podemos olvidarnos, pero lo que sí que podemos hacer, al igual que antes (solo que ahora creando la necesidad implícita de transferir los tokens de las sesiones mediante el método get o post en una petición ajax, y siendo esto una práctica que utilizan servicios como Habbo Hotel para cargar, por ejemplo, las notícias) es enviar con ajax, como he mencionado anteriormente, una petición al servidor, adjuntando también un token, y que este nos devuelva todos los datos necesarios para la web, que además serán colocados con JavaScript.
Con esto último, reduciremos considerablemente el tiempo de carga de nuestra web, o como mínimo el de repuesta del servidor, ya que una vez servido el HTML y los scripts por primera vez, no necesitaremos obtenerlo de nuevo para cambiar su contenido, puesto que podremos hacerlo con solo obtener objetos JSON (u otras maneras) y reemplazando el contenido de elementos por otros, como por ejemplo un campo de nombre de usuario.
No solo, además, podremos cambiar solo el contenido en cuanto a texto, sino que podremos también cambiar el HTML, implicando así que podremos cargar páginas distintas en una sola página, y gracias a funciones como ‘location.pathname.replace’, podremos incluso cambiar la dirección en la barra de direcciones, de forma que si un usuario copia un link al visualizar una foto y se lo pasa a otra persona, podremos cargar la foto directamente al cargar la página (como ya hace twitter o facebook).

Por supuesto, para proyectos pequeños en los cuales la carga del servidor no sea tan importante (ya que obviamente la diferencia será de milisegundos, y que si solo se ve una página será contraproducente), no necesitamos usar dicha nueva tecnología, que además de ser más tediosa y larga a la hora de desarrollar, también aumenta la carga en el navegador, mucho más que una simple página estática en HTML puro, de forma que si hacemos un pequeño blog o una web de empresa, con ni tan solo un millón de visitas mensual, no recomiendo hacerlo bajo ningún concepto.

Entonces… ¿Cookies o LocalStorage?
Fácil, como he aclarado en el párrafo anterior, según el tamaño del proyecto, cargar el cliente en exceso y/o si la carga del servidor no importa, usar LocalStorage es contraproducente. En cambio, si es un gran proyecto como Twitter o Facebook, entonces, usar el cliente como base para cargar toda la web puede ser la mejor opción. Por ende, yo usaría cookies si queremos tirar de servidor y LocalStorage si de JavaScript va la película.
A excepción de si usamos PHP, entonces usar LocalStorage no vale la pena del todo, de cualquier forma vamos a transferir los datos al servidor mediante cabeceras (ojo, si que nos puede servir para controlar qué datos le enviamos, y además, recordemos que si los datos son sensibles o solo se requieren para el funcionamiento temporal de la web, puede ser mejor usar LocalStorage).
Y sí, eso último que acabo de decir se hace posible con LocalStorage, pues este nos permitirá almacenar parámetros como el color de fondo que preferimos u otros detalles (incluso que pueden ser asignados por el servidor al iniciar sesión) y así no tener que cargarlos cada vez, reduciendo una petición al servidor por cambio/carga nueva de página.

Por ende, y contando que cada uno tiene sus pros y sus contras y que no nos vamos a saltar el cartelito de las cookies (puesto que este también es regulado por la famosa ‘ The Cookie Law’), va a depender del caso el hecho de usar uno u otro.

Para los que reclamen por la seguridad: ambos son IGUAL de seguros en cuanto a que el cliente los puede leer y modificar con tan solo la consola JavaScript, pero las cookies se enviarán al servidor en las cabeceras, mientras que el LocalStorage/SessionStorage permanece en el navegador si no lo enviamos nosotros con JavaScript.

Espero que os haya servido de ayuda esta pequeña reflexión.
¡Un saludo a todos!


Snowflake – Un nuevo juego en el blog

Hola a todos,
Debido a un alto aburrimiento, así como a las ganas de poseer un cubo de VeryPuzzle llamado Snow Mystery (sí, con dos ‘y’es, no lo he escrito mal), decidí ponerme a programar en un ratillo libre que tenía, y acabé por hacer el cubo de forma un tanto peculiar.

Para todos los que no lo sepáis, tengo una gran afición por los cubos de Rubik, y de hecho estoy pensando en abrir otro canal de YouTube (otro más para la colección) de cubos, puesto que es algo de lo que me gusta hablar, y creo que tengo una colección suficiente para ello.

El juego no usa la tecnología de canvas de HTML5, pues simplemente me aburría y quería hacerlo a lo rápido, no a lo «pro». Por ende, son simples divs a las cuales les cambio el color de fondo cambiándoles la clase en un simple script que intercambia colores y posiciones tanto al pulsar las flechitas, al pulsar los propios copos o al pulsar el botón de Shuffle, o mezcla, en sí.

Así que bueno, ya que jugar es gratis, aquí tenéis el link:

¡Entra al juego!


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";
$tries = 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?
$tries++;
$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_move = true; // Para que el while continue

while($can_move)
{
	// 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)))
		$m[1] = 0;
       
	if($h == 1 || $h == 2 || $h == 3 || (($l - 3 < 1) ? true : ($r[$l - 3] != 0)))
		$m[5] = 0;
       
	// --- Movimientos verticales ---
	if($v == 8 || $v == 9 || $v == 10 || (($l + 30 > 100) ? true : ($r[$l + 30] != 0)))
		$m[3] = 0;
	       
	if($v == 1 || $v == 2 || $v == 3 || (($l - 30 < 1) ? true : ($r[$l - 30] != 0)))
		$m[7] = 0;
	       
	// --- Movimiento arriba derecha ---
	if($h == 9 || $h == 10 || $v == 1 || $v == 2 || (($l - 18 < 1) ? true : ($r[$l - 18] != 0)))
		$m[8] = 0;
	       
	// --- Movimiento arriba izquierda ---
	if($h == 1 || $h == 2 || $v == 1 || $v == 2 || (($l - 22 < 1) ? true : ($r[$l - 22] != 0)))
		$m[6] = 0;
       
	// --- Movimiento abajo derecha ---
	if($h == 9 || $h == 10 || $v == 9 || $v == 10 || (($l + 22 > 100) ? true : ($r[$l + 22] != 0)))
		$m[2] = 0;
       
	// --- Movimiento abajo izquierda ---
	if($h == 1 || $h == 2 || $v == 9 || $v == 10 || (($l + 18 > 100) ? true : ($r[$l + 18] != 0)))
		$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_move = false; // Aquí paramos
       
	if($can_move)
		foreach($cm as $ba => $bb)
			if($ba == $fm)
				$fm = $bb;
       
	// Nos movemos (si podemos)
	if($can_move)
		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 'Error';
				$can_move = false;
				break;
		}
	}
 
	if($r[$l]  == 100)
	{
		$file_name = 'soluciones/last.txt';
		$file = fopen($file_name, 'r+');
		$last = fread($file, 11);
        ftruncate($file, 0);
        rewind($file);
		$last = $last + 1;
		fwrite($file, $last);
		fclose($file);
	       
		$content = '<!DOCTYPE html>
	<head>
		<title>Soluci&oacute;n ' . $last . ' del circuito Hamiltoniano - Ensaimada num&eacute;rica</title>
	</head>
	<body style="margin:3 0;">
			<table border="1" style="font-size: 57pt;text-align: center; border: 2px solid black;" cellpadding="2" cellspacing="0">';
		for($a = 1; $a <= 10; $a++)
		{
			$content .= "\n\t\t\t\t<tr>";
			for($b = 1; $b <= 10; $b++)
			{
				$content .= "\n\t\t\t\t\t<td width=\"90\" height=\"75\" style=\"height: 89px; text-align: center; border: 2px solid black;\" >";
				$content .= ($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]);
				$content .= "\n\t\t\t\t\t</td>";
			}
			$content .= "\n\t\t\t\t</tr>";
		}
		$content .= "\n\t\t\t</table></body></html>";
		echo 'Sol. $contenido encontrada y guardada. Intentos:',  $tries;
				$tries = 0;
		echo "\nBuscando soluciones...\n";
		$file = fopen('soluciones/' . $last . '.html', 'w');
		fwrite($file, $content);
		fclose($file);
	}
}

Páginas:12345