Contando los Domingos del Siglo XX (Desafíos del Proyecto Euler)

El Proyecto Euler presenta un conjunto de problemas que desafían las mentes inclinadas a las matemáticas y a la computación.

El problema No. 19 pide contar los domingos que cayeron en primero del mes durante el siglo xx. Realmente el mérito lo tendría quien resuelva analíticamente la cuestión. Quizá tratando el calendario como una serie, estableciendo su término general o ley de formación y encontrando un selector que permita contar los elementos que cumplen las condiciones dadas:
(día del mes = 1 & día de la semana = domingo).

Pues bien, la solución que aquí presentamos no tiene tal mérito. Se trata del siguiente algoritmo de fuerza bruta:

    cuenta:= 0;
    FOR fecha:= 1/1/1901 TO 31/12/2000 DO
       IF (fecha.díaDelMes = 1) & (fecha.DíaDeSemana = "domingo") THEN
         cuenta:= cuenta + 1
       END
    END;
    escribir cuenta

¿Es correcto? (porque eso es lo que primero que debe preocuparnos). Informalmente, sí lo es: la variable "cuenta" se inicializa en cero y se incrementa solamente si se cumple las condiciones; se recorre todo el calendario que corresponde al siglo xx: del primero de enero de 1901 hasta el 31 de diciembre del 2000. El mecanismo mediante el cual el lazo FOR irá incrementando la variable de control "fecha", manejando todas las vicisitudes del calendario que nos recuerdan en el enunciado del problema, está por refinarse.

Es obligación de quien presenta un algoritmo de fuerza bruta tratar de mejorar su eficiencia. No pretendemos lograr una complejidad menor a O(n). Ya dijimos que: famoso se haría quien presente la solución O(1), la solución analítica. Lo que haremos es esforzarnos en reducir el número de iteraciones.

Una vez identificado un "domingo", no tiene sentido probar la fecha que sigue (de antemano sabemos que será "lunes"), ni la que sigue, ni la otra, ni la otra... ¡Um!, ese FOR puede usar un paso de 7 en vez de 1: FOR fecha:= 1/1/1901 TO 31/12/2000 BY 7 DO...

¡Con cuidado! ¡La corrección de un algoritmo es lo esencial! El paso acelerado de 7-en-7 sólo puede aplicarse una vez que se haya identificado el primer domingo, no antes. El enunciado da el dato de que el 1/1/1900 fue lunes, pero eso parece más bien un distractor, o una "cáscara de banano": lo que nos interesa está a un año de distancia de ese lunes.

Aceptemos más bien comenzar nuestro recorrido del siglo xx en la penumbra; vayamos de 1-en-1, hasta encontrar el primer domingo; a partir de allí, pisamos el acelerador. 

Cuando hagamos nuestro primer gran hallazgo: no sólo un domingo, sino un domingo en día primero de mes, el paso del FOR puede ser aun mayor. Si el primero fue domingo, no habrá otro domingo interesante ese mismo mes (sólo hay un día primero en cada mes). ¡Podemos omitir el resto del mes!

¡Con cuidado! ¡La corrección...! Los meses son de longitud variable (el enunciado nos lo recuerda vehementemente). El salto seguro, para manejar bien hasta el más corto de los febreros, no puede ser de más de 28 días. ¡Ojo! Una vez hecho ese salto casi volvemos a la penumbra, y lo más sano será ir al paso de 7 hasta que ocurra otro domingo en primero. Con cualquiera de los dos saltos caemos siempre sobre otro domingo. ¿Cierto? Esto reducirá el número de iteraciones en un poco más de 7 veces (el "poco más" es gracias a los ocasionales 28). 

Es tiempo de reconocer sin embargo que ya el FOR no va a servirnos. Ciertamente es muy segura esa forma de iteración, garantiza que nunca nos quedaremos en un lazo infinito; pero la disciplina del FOR recomienda su uso para cuando el número de iteraciones se conoce de antemano, no para cuando hay "penumbras" y pasos variables como aquí. Ahí están el WHILE y el REPEAT. Confiados en encontrar al menos un domingo en día primero nos embarcaremos en un REPEAT.

Enfrentaremos de una vez el gran lío de incrementar fechas en un calendario de meses de longitud variable. Nos basaremos en algoritmos probados para sumar un valor entero a una fecha.
¿Qué sería de los programadores si no fuera por los subprogramadores?

Una solución para saber cuántos días hay entre dos fechas dadas, o para saber cuál fecha viene "k" días después de otra fecha dada, empieza por convertir las fechas en el número de días transcurridos desde el origen de los tiempos. Fijaremos ese origen de los tiempos en el día 1/1/1. La función Day (fecha) devuelve el número de días transcurridos desde 1/1/1 hasta la fecha dada. por definición Day (1/1/1) = 1. La diferencia en días entre dos fechas f2, f1 es: Day (f2) - Day (f1).

La inversa de Day convierte un número de días (transcurridos desde el origen de los tiempos) en fecha. Planteada como un procedimiento propio, sería DayToDate (k, f), que define "f" como la fecha que corresponde a "k" días desde 1/1/1.

Axiomáticamente las dos funciones mencionadas se relacionan así: DayToDate (Day (f1), f2) => f2 = f1.

Con estas funciones, la implementación de d:= d + k, sería:

Dates.DayToDate (Dates.Day (d) + k, d).

En honor de los subprogramadores presentamos el código de ambas funciones en el apéndice (al pie). Son misteriosas, es cierto. Hay constantes mágicas allí, muchos MOD y DIV, algunos números primos casi desconocidos... ¿Qué esperábamos?, ¿Acaso no es misterioso y mágico el calendario?

Y ahora la versión "final" del contador de domingos en día primero.

Usaremos el siguiente tipo, del módulo "Dates", para las fechas:

TYPE Date = RECORD day, month, year: INTEGER END;

MODULE Sundays;

IMPORT Dates, StdLog;   (* manejo de fechas y escritura de resultados *)

PROCEDURE Count*;
   VAR d: Dates.Date; vueltas, cuenta, paso: INTEGER;
BEGIN
   vueltas:= 0; cuenta:= 0; paso:= 1;
   d.day:= 1; d.month:= 1; d.year:= 1901;   (* fecha inicial *)
   REPEAT
      IF (d.day = 1) & (Dates.DayOfWeek (d) = Dates.sunday) THEN
         Dates.DayToDate (Dates.Day (d) + 28, d);
         INC (cuenta);
         paso:= 7   (* ¡alta entropía! *)
      ELSE
         Dates.DayToDate (Dates.Day (d) + paso, d)
      END;
      INC (vueltas)
   UNTIL d.year >= 2001;   (* salimos del siglo XX *)
   StdLog.Int (vueltas); StdLog.String (" iteraciones"); StdLog.Ln;
   StdLog.Int (cuenta); StdLog.String (" domingos"); StdLog.Ln
END Count;

END Sundays.

Consideraciones Finales

1. El REPEAT UNTIL requiere mayor atención que un FOR. La pregunta obligada es ¿Termina ese lazo? Veamos. Al entrar al lazo la fecha es d = 1/1/1901; dentro del lazo siempre incrementamos esa fecha en un valor positivo: de tomar la rama THEN la incrementamos en 28; de tomar la rama ELSE, en 1 (durante la penumbra de no haber encontrado ni el primer "domingo en día 1") o en 7 (fuera de la penumbra). Así pues, a fuerza de +1, +28, ó +7, llegaremos sin duda al fin del siglo. Estrictamente hablando la condición de terminación del REPEAT debería ser d > 31/12/2000, que habría que codificar basándose en: d.day, d.month y d.year. La alternativa que usamos es más eficiente. El lector debe convencerse de que tal solución no introduce peligro de contar algún domingo adicional que pertenezca al siglo xxi. Puede argumentarse que un "=", en lugar de ">=" va bien allí. Es cierto, pero por fidelidad a la disciplina del REPEAT dejaremos la condición de terminación en su forma más amplia.
2. Los algoritmos, además de correctos, eficientes, finitos, completos, deben ser generales. ¿Cómo podemos generalizar el procedimiento "Count"? Podríamos, por ejemplo, admitir como parámetros, la fecha inicial y la fecha final. Así serviría para cualquier siglo o cualquier lapso (y cortamos un gigantesco cordón umbilical que aún nos une al siglo xx). Podemos pasar otros parámetros para contar no necesariamente los domingos ni atender sólo el comienzo de los meses, sino contar por ejemplo todos los viernes 13 que ocurrieron en un lapso dado. Con la versión generalizada pudimos comprobar la conjetura de que ¡todo mes que tenga un domingo primero, tendrá también un viernes 13!
3. Hemos presentado la versión "final" en un lenguaje tan desconocido como excelentemente diseñado: Component Pascal, apoyado en el BlackBox Framework: joyas al alcance de cualquier programador. ¿Qué toca ahora al amigo lector? Le toca, usando como un pseudocódigo nuestra versión de "Count", convertirla a su lenguaje de programación favorito (Python, C#, Java, Haskell, Electron...) y comprobar que:
4. 171 domingos cayeron en primero del mes durante todo el siglo xx, que esto lo contamos en 4914 iteraciones (que hubiese sido más de 36 mil sino fuera por el paso variable). 
5. La generalización de los algoritmos va más allá de la parametrización. Estuvimos tratando de usar la misma idea de sumar un valor a una fecha para predecir las fechas de la luna llena  (un tema ligeramente más complicado porque el valor a sumar es fraccionario: días + horas, minutos, segundos...) La idea surgió la pasada noche de Navidad, que fue luna llena en 25 de diciembre. Nunca sacamos el algoritmo a la luz aquí en el blog. Creíamos que algún bug impedía predecir más allá de 8 o 10 lunas; hasta que descubrimos que el bug no era del programa; es de la tierra. Los movimientos de traslación y de rotación no son tan perfectos. Aunque no lo hemos preguntado a los astrónomos, es posible que hasta el despegue de un jet altere el espiralado viaje de nuestro planeta por el espacio.
6. Queda mucho por hacer. Los programas no se terminan nunca. Versión "final" se ponen entre comillas.

APENDICE

PROCEDURE Day* (IN d: Date): INTEGER;
      (* For date d, return the number of days since 1/1/1. Day(1/1/1) = 1 
         Precondition ValidDate(d) (not explicitly checked);
         Postcondition (result > 0) & (result < 3652062) *) 
      VAR y, m, n: INTEGER;
   BEGIN
      y := d.year; m := d.month - 3;
      IF m < 0 THEN INC(m, 12); DEC(y) END;
      n := y * 1461 DIV 4 + (m * 153 + 2) DIV 5 + d.day - 306;
      IF n > 577737 THEN n := n - (y DIV 100 * 3 - 5) DIV 4 END;
      RETURN n
   END Day;

   PROCEDURE DayToDate* (n: INTEGER; OUT d: Date);
      (* Convert the number of days since 1/1/1 into a date.
         Precondition (n > 0) & (n < 3652062) (not explicitly checked);
         Postcondition ValidDate(d) & Day(d) = n *)
      VAR c, y, m: INTEGER;
   BEGIN
      IF n > 577737 THEN
         n := n * 4 + 1215; c := n DIV 146097; n := n MOD 146097 DIV 4
      ELSE
         n := n + 305; c := 0
      END;
      n := n * 4 + 3; y := n DIV 1461; n := n MOD 1461 DIV 4;
      n := n * 5 + 2; m := n DIV 153; n := n MOD 153 DIV 5;
      IF m > 9 THEN m := m - 12; INC(y) END;
      d.year := SHORT(100 * c + y);
      d.month := SHORT(m + 3);
      d.day := SHORT(n + 1)
   END DayToDate;