El algoritmo de Tomohiko Sakamoto para torpes (o no)

Calculando el día de la semana

Calculando el día de la semana

Ayer nos íbamos a la cama con la noticia de la aparición de un nuevo algoritmo informático que devuelve el día de la semana de una fecha dada. Lo curioso es que no es cualquier algoritmo, si no que es el más corto, eficaz, simple y optimizado que se conoce hasta ahora. En sólo unas pocas líneas de código (en lenguaje C), su autor, Tomohiko Sakamoto, concentra toda la esencia de la algoritmia más genial para realizar un cálculo que siempre ha tenido un encanto especial para los programadores.

Intentaremos explicar de forma clara y concisa cómo funciona este algoritmo, aunque tampoco es fácil, pero lo intentaremos. Simplemente abstrayéndonos un poco y relajando nuestras neuronas, creemos que es bastante evidente y cristalino (o no).

Vemos primero el código de Tomohiko Sakamoto. Después la explicación.

#include <stdio.h>
 
 
int dow(int y, int m, int d) {
	static int t[] = {0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4};
	y -= m < 3;
	return (y + y/4 - y/100 + y/400 + t[m-1] + d) % 7;
}
 
int main(void) {
	const char *days[] = {"Sunday", "Monday", "Tuesday", "Wednesday",
				"Thursday", "Friday", "Saturday"};
	printf("%s\n", days[dow(2013, 5, 13)]);
	return 0;
}

El 1 de enero del año 1 después de Cristo, considerado el inicio de la era cristiana, es (fue) un lunes en el calendario gregoriano, calendario originario de Europa y actualmente utilizado de manera oficial en casi todo el mundo. Por lo tanto, el 0 de enero de ese año 1 fue domingo (este día técnicamente no existe, pero Sakamoto lo tiene en cuenta porque, aunque el estándar ISO 8601 del año 2004 estableció que la semana comienza en lunes, en Estados Unidos y en muchos otros países anglófonos el primer día es el domingo).

Cada cuatro años tenemos un año bisiesto con un día más en el calendario. Años bisiestos, pues, son todos aquellos divisibles entre 4 (con resto 0), salvo los años seculares (los últimos de cada siglo; los terminados en dos ceros [00]), excepto los divisibles entre 400. Por lo tanto, un año terminado en 00, tal que xx00, no puede ser bisiesto a menos que xx sea divisible entre 4.

Con estas premisas claras, Tomohiko Sakamoto determina que la fórmula y/4 - y/100 + y/400 devuelve el número de años bisiestos que hay desde el año 1 después de Cristo hasta el año dado.

La parte más difícil de entender es y -= m < 3. Esta sentencia especifica que si el mes en menor de 3 (enero o febrero), el año se hace igual al año menos 1 (y = y - 1) ; si es mayor de tres, el año se queda igual, o lo que es lo mismo que el año es igual al año menos cero (y = y - 0). Se entiende pues que, si el mes no es ni enero ni febrero, no podemos contar el 29 de febrero (si existe) del año dado.

Así pues, y + y/4 - y/100 + y/400 devuelve el día 0 de enero (realmente el 31 de diciembre del año anterior) del año dado. Además, como cada año tiene 365 días, es decir, es divisible entre 7 (días por semana) con un resto de 1 (día), a no ser que sea bisiesto, al día de la fecha dada se le incrementa ese resto de 1; en caso de ser bisiesto se incrementa en 2 (días).

La matriz t simplemente es un juego de números de días pasados desde que comienza el mes m+1. Por lo que t[m-1] + d es el número de días pasados en el año y hasta la fecha dada. La fórmula final (y + y/4 - y/100 + y/400 + t[m-1] + d) % 7 es el resto del número de días desde el 0 de enero del año 1 después de Cristo hasta la fecha dada, lo que realmente es el día de la semana solicitado (teniendo en cuenta que el 0 es el domingo).

La matriz constante days guarda cadenas para sustituir los números devueltos por sus valores textuales.

La verdad es que es una delicia de algoritmo y, además, muy fácil de traducir a otros lenguajes de programación. Nuestro más alto respeto al autor.

Escribe tu comentario

eBook ‘retroPLOF!’

retroPLOF!

Especifica tu dirección de correo electrónico y pulsa 'Comprar ahora'. Puedes pagar con tu cuenta de PayPal o con cualquier tarjeta bancaria.

E-mail envío eBook:

Sigue teknoPLOF! vía…
 
RSS
Twitter
Facebook
Google
 
Ready Set Click!

Utilizamos cookies propias y de terceros para mejorar la experiencia de navegación. Más información.

CERRAR