Euler #30

https://projecteuler.net/problem=30 => "Digit fifth powers"

Un poco de culturilla matemática, se trata de "números narcisistas"

def checkSumDigits(number, power):
 _sum = 0
 for digit in str(number):
  _sum += (int(digit))**power
 return _sum == number

final_sum = 0
for a in range(2, 10**6):
 if checkSumDigits(a, 5):
  print a
  final_sum += a
print final_sum

Euler #29

https://projecteuler.net/problem=29 => Distinct Powers

numbers = []
for a in range(2, 101):
 for b in range(2, 101):
  n = a**b
  if not n in numbers:
   numbers.append(n)

numbers.sort() 
print len(numbers)

Euler #28

https://projecteuler.net/problem=28 => Number spiral diagonals

Los problemas en "2D" son siempre entretenidos. El problema es bastante sencillo, pero hay que tener cuidado y llevar un control de en qué dirección vamos y a cuándo "hay que torcer".

import sys

if len(sys.argv) != 2:
 print "Usage: 028.py <SIZE>"
 sys.exit()

table = []
size = int(sys.argv[1])
if size % 2 == 0:
 print "Only odd numbers"
 sys.exit()

for _ in range(0, size):
 row = []
 for _ in range(0, size):
  row.append(0)
 table.append(row)

directions = ((0,1), (1,0),(0,-1),(-1,0))

def get_next_direction(current): 
 i = directions.index(current)
 if i == len(directions) - 1:
  i = 0
 else:
  i += 1
 return directions[i]

max_num = size**2
x = size/2
y = size/2
diagonal_sum = 0
current_direction = (-1,0)
for a in range(1, max_num+1):
 if x == y or x + y == size - 1:
  diagonal_sum += a
 table[x][y] = a
 new_direction = get_next_direction(current_direction)
 x1 = x + new_direction[0]
 y1 = y + new_direction[1]
 if table[x1][y1] == 0:
  x, y = x1, y1
  current_direction = new_direction
 else:
  x, y = x + current_direction[0], y + current_direction[1]

#for row in table:
# print row
print "diagonal_sum", diagonal_sum

Euler #27

https://projecteuler.net/problem=27 => Cuadratic primes

Este problema es muy sencillo, simplemente hay que iterar entre todos los valores posibles para los dos coeficientes (-999 <= a <= 999 y -1000 <= b <= 1000) y comprobar cuántos números primos consecutivos permite calcular el polinomio n² + an + b.

La primera implementación es sencilla y bastante rápida, apenas unos segundos. Pese a que es un problema con un orden de complejidad polinómico por definición (cuadrático para las posibles combinaciones de a y b más otros ciclo para comprobar los números primos), dado que los valores del programa son pequeños, se resuelve en un tiempo razonable.

Pero claro, siempre se quiere optimizar. Así que pensé "si al comprobar si un número es primo o no, puedo tenerlos ya guardados en una lista y así no tengo que calcular lo mismo una y otra vez".

Veamos la implementación, sólo cambia lo siguiente: una lista de números primos inicialmente vacía y una comprobación previa. El resto del código es igual. Sin embargo, al ejecutarlo, nos encontramos con que tarda bastante más tiempo.

¿Qué ha pasado? Fácil, que la supuesta optimización ha resultado ser peor. Con pensar 5 segundos se da uno cuenta por qué: cada vez que queremos saber si un número es primo debemos buscarlo en una lista que cada vez es más grande. Además, debemos asignar memoria y hacer diversas operaciones internas en la lista para redimensionarla al añadir un nuevo elemento. Desconozco la implementación exacta de la búsqueda en listas de Python, pero no puede ser mejor que del orden de O(log n).





Otra forma de crear esta caché de números primos es utilizar un diccionario Python, que requiere menos manejo de memoria, pero la verdad, la mejora, para las dimensiones de este problema, es mínima.

Conclusión: si optimizas, ten cuidado, no sea que lo estropees.

Euler #26

https://projecteuler.net/problem=26 => Reciprocal cycles

Este ha costado un poco más sacarlo, y ha sido gracias al número 1/17 cuando me he dado cuenta que un número sí que se podía repetir en el periodo (asumí que no). Sabiendo eso, la comprobación para ver si estamos empezando un nuevo periodo solo debe tener en cuenta si estamos repitiendo un resto. Veamos una implementación en Python:

from decimal import Decimal, getcontext

getcontext().prec = 40

def Div(D, d):
 return (D/d, D%d)

def GetPeriod(d):
 period = []
 remainders = []
 index = 0
 c, r = Div(1, d)
 if r == 0:
  return []
 if c != 0:
  period.append(c)
 while True:
  D = 10*r
  c, r = Div(D, d)
  if r == 0:
   return []
  period.append(c)
  if r in remainders:  
   return period[period.index(c):index]
  index += 1
  remainders.append(r)

 return period


longestList = []
longestInt = 1
for a in range(1, 1000):
 period = GetPeriod(a)
 if len(period) > len(longestList):
  longestList = period
  longestInt = a

print "Longest period for ", longestInt, " => ", longestList, " (len: ", len(longestList), ")"

Baúl de los recuerdos: "Euroconversor"

1 de enero de 2002... entra en vigor el Euro en España. La de código que se escribió en los meses previos para adaptar lo que no estaba preparado. Recuerdo que, con la tontería, me dio por escribir una pequeña utilidad, "Eurocalculadora", que se pusieron de moda en 2001. Todo el mundo tenía una en su web, yo hice una para "desktop" en Python+Glade.

Glade era un editor de interfaces de usuario en GTK que guardaba la descripción de la misma en un XML que posteriormente se podía parsear con el lenguaje que tuviera "bindings" a GTK y libglade.

En Windows (W2000, si no recuerdo mal)

En Linux (gestor de ventanas, IceWM)

No es un código del que sentirse orgulloso, pero bueno, eran mis primeros pasos con Python :)



euroconversor.py:

from funciones import interfaz
app=interfaz.EuroConversor()
  app.a_correr()

uno.glade

<?xml version="1.0"?>
<GTK-Interface>
<project>
  <name>Aplicacion</name>
  <program_name>aplicacion</program_name>
  <directory></directory>
  <source_directory>src</source_directory>
  <pixmaps_directory>pixmaps</pixmaps_directory>
  <language>C</language>
  <gnome_support>False</gnome_support>
  <gettext_support>False</gettext_support>
</project>
<widget>
  <class>GtkWindow</class>
  <name>window1</name>
  <signal>
    <name>destroy</name>
    <handler>on_window1_destroy</handler>
    <last_modification_time>Thu, 08 Aug 2002 16:22:11 GMT</last_modification_time>
  </signal>
  <title>Conversor</title>
  <type>GTK_WINDOW_TOPLEVEL</type>
  <position>GTK_WIN_POS_CENTER</position>
  <modal>False</modal>
  <allow_shrink>False</allow_shrink>
  <allow_grow>False</allow_grow>
  <auto_shrink>False</auto_shrink>
  <widget>
    <class>GtkVBox</class>
    <name>vbox2</name>
    <homogeneous>False</homogeneous>
    <spacing>0</spacing>
    <widget>
     <class>GtkLabel</class>
      <name>label1</name>
      <label>Euro Conversor:
Introduzca la cantidad a convertir</label>
      <justify>GTK_JUSTIFY_CENTER</justify>
      <wrap>False</wrap>
      <xalign>0.5</xalign>
      <yalign>0.5</yalign>
      <xpad>10</xpad>
      <ypad>10</ypad>
      <child>
        <padding>0</padding>
 <expand>True</expand>
 <fill>True</fill>
      </child>
    </widget>
    <widget>
      <class>GtkHBox</class>
      <name>hbox2</name>
      <homogeneous>False</homogeneous>
      <spacing>0</spacing>
      <child>
 <padding>0</padding>
 <expand>True</expand>
 <fill>True</fill>
      </child>
      <widget>
 <class>GtkLabel</class>
 <name>label2</name>
 <label>Pesetas</label>
 <justify>GTK_JUSTIFY_RIGHT</justify>
 <wrap>False</wrap>
 <xalign>0.5</xalign>
 <yalign>0.5</yalign>
 <xpad>5</xpad>
 <ypad>5</ypad>
 <child>
   <padding>0</padding>
   <expand>True</expand>
   <fill>True</fill>
 </child>
      </widget>
      <widget>
 <class>GtkEntry</class>
 <name>entry1</name>
 <can_focus>True</can_focus>
 <signal>
   <name>key_press_event</name>
   <handler>on_entry1_key_press_event</handler>
   <last_modification_time>Mon, 12 Aug 2002 13:18:49 GMT</last_modification_time>
 </signal>
 <editable>True</editable>
 <text_visible>True</text_visible>
 <text_max_length>0</text_max_length>
 <text></text>
 <child>
   <padding>5</padding>
   <expand>False</expand>
   <fill>True</fill>
 </child>
      </widget>
    </widget>
    <widget>
      <class>GtkHBox</class>
      <name>hbox3</name>
      <homogeneous>False</homogeneous>
      <spacing>0</spacing>
      <child>
 <padding>0</padding>
 <expand>True</expand>
 <fill>True</fill>
      </child>
      <widget>
 <class>GtkLabel</class>
 <name>label3</name>
 <label>Euros</label>
 <justify>GTK_JUSTIFY_RIGHT</justify>
 <wrap>False</wrap>
 <xalign>0.5</xalign>
 <yalign>0.5</yalign>
 <xpad>5</xpad>
        <ypad>5</ypad>
 <child>
   <padding>0</padding>
   <expand>True</expand>
   <fill>False</fill>
 </child>
      </widget>
      <widget>
 <class>GtkEntry</class>
 <name>entry2</name>
 <can_focus>True</can_focus>
 <signal>
   <name>key_press_event</name>
   <handler>on_entry2_key_press_event</handler>
   <last_modification_time>Mon, 12 Aug 2002 13:18:59 GMT</last_modification_time>
 </signal>
 <editable>True</editable>
 <text_visible>True</text_visible>
 <text_max_length>0</text_max_length>
 <text></text>
 <child>
   <padding>5</padding>
   <expand>False</expand>
   <fill>True</fill>
 </child>
      </widget>
    </widget>
  </widget>
</widget>
</GTK-Interface>

__init__.py

__all__ = ["interfaz", "conversiones"]

conversiones.py

def validar_entrada1( texto ):
    try:
         return str(long(texto))
    except ValueError:
         return ""

def validar_entrada2( texto ):
    try:
         return str(float(texto))
    except ValueError:
         return ""

def pelas_a_euros( entrada ): #Aquí viene lo que han tecleado
    return "%.2f" % (float(entrada)/166.386)

def euros_a_pelas( entrada ): #Aquí viene lo que han tecleado
    return "%d" % (float(entrada)*166.386)

interfaz.py

import libglade, gtk
from funciones import conversiones

class EuroConversor:
    def __init__(self):
        self.arbol = libglade.GladeXML( "aplicacion.glade", "window1" )
        self.caja1 = self.arbol.get_widget( "entry1" )
        self.caja2 = self.arbol.get_widget( "entry2" )

        manejadores = { "on_entry1_key_press_event" : self.pasar,
                        "on_entry2_key_press_event" : self.pasar,
                       }
        self.arbol.signal_autoconnect( manejadores )
        self.arbol.signal_connect( "on_window1_destroy", self.salir )

    def a_correr(self):
        gtk.mainloop()

    def salir(self, obj):
        print "Saliendo..."
        gtk.mainquit()

    def pasar(self, obj, ev):
        """  En 'obj' viene el objeto que llama (la caja de texto),
             En 'ev' viene el evento, dir(ev) = keyval, send_event, state, string, time, type, window
        """
        nombre = libglade.get_widget_name( obj )
        if nombre == "entry1":
           entrada_validada1 = conversiones.validar_entrada1(obj.get_text() + ev.string)
           if entrada_validada1:
                self.caja2.set_text( conversiones.pelas_a_euros( entrada_validada1 ) )
           else:
                self.caja1.set_text( "" )
                self.caja2.set_text( "" )
        elif nombre == "entry2":
           entrada_validada2 = conversiones.validar_entrada2(obj.get_text() + ev.string)
           if entrada_validada2:
                self.caja1.set_text( conversiones.euros_a_pelas( entrada_validada2 ) )
           else:
                self.caja1.set_text( "" )
                self.caja2.set_text( "" )

Baúl de los recuerdos: "Power Helper"

De vez en cuando toca alguna intervención nocturna y uno aprovecha para revisar cosas pendientes... tenía un directorio con backups antiguos y rebuscando, rebuscando... he encontrado algunos programillas que hice hace tiempo.

Ahí va uno, que en su día llamé "Power Helper", era un script en Tcl/Tk que servía para controlar los perfiles de rendimiento de la CPU, administración de energía. Lo usé mucho tiempo en un portátil que tenía.



No recuerdo cuándo escribí este programa, pero sería entre 2001 y 2003, que fue una época en la que estuve experimentando con muchos lenguajes de script.

Me llamó mucho la atención en su día Tcl. Su estilo muy similar a una shell y sus tipos de datos eran bastante curiosos.

#!/usr/bin/wish

set governors [exec cat /sys/devices/system/cpu/cpu0/cpufreq/scaling_available_governors]

proc show_message {tit mes} {
    tk_messageBox -icon info -title $tit -message $mes
}

proc show_governor {} {
    show_message "Rendimiento"  "Perfil de rendimiento: [exec cat /sys/devices/system/cpu/cpu0/cpufreq/scaling_governor]"
}

proc show_Batería {} {
    show_message "Batería"  "Estado de la batería:\n[string trim [exec acpi]]\n[exec cat /proc/acpi/battery/BAT1/state]"
}

proc show_cpu {} {
    show_message "CPU"  "Información CPU:\n[exec cat /proc/cpuinfo]"
}

proc Hibernar {} {
    exec /bin/echo 4 > /proc/acpi/sleep
}

proc set_governor {g} {
    exec cpufreq-set {-g} "$g"
    show_governor
}

button .show -text {Perfil de rendimiento} -width 30 -command show_governor
pack .show -padx 5 -pady 3

foreach {g} $governors {
    button .g$g -text "Cambiar a perfil $g" -width 30 -command "set_governor $g"
    pack .g$g -padx 5 -pady 3
}

button .batstate -text "Estado de la batería" -width 30 -command show_Batería
pack .batstate -padx 5 -pady 3

button .cpu -text "Información CPU" -width 30 -command show_cpu
pack .cpu -padx 5 -pady 3

button .hibernar -text "Hibernar" -width 30 -command Hibernar
pack .hibernar -padx 5 -pady 3

button .end -text {Salir} -width 30 -command exit
pack .end -padx 5 -pady 3

wm title . "Power helper"

Euler #25

https://projecteuler.net/problem=25 => 1000-digit Fibonacci number

Volvemos a intentar cumplir los nuevos propósitos: vamos a probar con un lenguaje que no conocemos: Go.

Primera aproximación, por fuerza bruta, tras varias horas, no obtenemos resultado alguno:

package main

import ("math"
        "fmt")

func fib(n int) int {
    if n <= 2 {
        return 1
    }
    return fib(n-1) + fib(n-2)
}

func main() {
    nDigits := 1000
    limit := int(math.Pow(10, float64(nDigits) - 1)) - 1    
    index := 1
    for {
        num := fib(index)
        if num > limit {
            fmt.Printf("Index => %d\n", index)
            return
        }
        index++
    } 
}

El problema es que cada vez que iteramos, se empieza todo de nuevo. La mejora que vamos a intentar es ir guardando los números de Fibonacci que vamos generando en algún tipo de estructura de datos. Al igual que con C cuando manejamos enteros muy grandes, nos volvemos a encontrar con problemas de desbordamiento, hay que utilizar números enteros de precisión arbitraria (definidos en el package math/big de Go). Al implementarlo, de nuevo, me siento desbordado con los detalles del lenguaje y me doy por vencido, como en el anterior intento, que dejé la implementación en Perl sin hacer.

Implementamos en Python:

fib_numbers_cache = {}

def fib(num):
 if num in fib_numbers_cache:
  return fib_numbers_cache[num]
 if num <= 2:
  fibNum = 1
 else:
  fibNum = fib(num - 1) + fib(num - 2)
 fib_numbers_cache[num] = fibNum
 return fibNum

n = 1
n_digits = 1000
fib_num_max = 10**(n_digits - 1) - 1
while True:
 fn = fib(n)
 if fn > fib_num_max:
  print "END: ", n, "=>", fn
  break
 n += 1

Tras varios intentos de implementar las cosas en distintos lenguajes, siempre vuelvo al que más me gusta, que es Python ;)

Euler #24

https://projecteuler.net/thread=24 => Lexicographic permutations

En el anterior problema me propuse utilizar lenguajes con los que no estuviese muy familiarizado, y este problema lo empecé a hacer con Perl... pero es que no me gusta nada, nada, nada.

Al final, a fuerza bruta y en Python:

def get_permutations (arr):
 if len(arr) < 2:
  return [[arr]]
 elif len(arr) == 2:
  return [[arr[0], arr[1]], [arr[1], arr[0]]]
 else:
  permuts = []
  for a in arr:
   arr2 = arr[:]
   arr2.remove(a)
   for p in get_permutations(arr2):
    p.insert(0, a)
    permuts.append(p)
  return permuts

res = get_permutations([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
print res[999999]

Con el módulo itertools se hace en prácticamente una línea, pero no vale así, es trampa :D

En el foro de Euler comentan varias formas alternativas de afrontar el problema.

Euler #23

A partir de ahora, voy a intentar resolver cada problema utilizando un lenguaje con el que no esté familiarizado. Hoy toca Ruby, que lo empecé a cacharrear hace 15 años, pero no profundicé mucho en su día. Cuando apareció Ruby On Rails yo ya estaba en otra cosa...

Vamos allá con el problema: https://projecteuler.net/problem=23

Como comentaba, no estoy familiarizado con Ruby, seguro que en este código estoy haciendo cosas sin utilizar los modismos del lenguaje, pero bueno, allá va:

#!/usr/bin/env ruby

$divisors_precalculated = []

def divisors_sum number
  if $divisors_precalculated[number] != nil
    return $divisors_precalculated[number] 
  end
  sum = 0
  i = 1
  max = number / 2
  while i <= max
    if number % i == 0
      sum += i
    end
    i += 1
  end
  $divisors_precalculated[number] = sum
  return sum
end

def is_abundant number
  return divisors_sum(number) > number
end

total = 0

for current_number in 1..28123
  is_sum_of_two_abundant_numbers = false
  fist_half = current_number - 1
  second_half = 1
  while second_half <= fist_half
    if is_abundant(fist_half) and is_abundant(second_half)
      is_sum_of_two_abundant_numbers = true
      break
    end
    fist_half -= 1
    second_half += 1
  end
  if !is_sum_of_two_abundant_numbers
    puts current_number.to_s + ' cannot be written as the sum of two abundant numbers'
    total += current_number
  end
end

puts "Result: " + total.to_s

Lo único relevante en el problema es lo costoso que es encontrar divisores, así que los vamos guardando en una variable global (la que lleva un $ por delante). Se podría hacer todo dentro de una clase y que esta global pasase a ser una variable miembro de la clase, pero para un problema de este tipo, con el estilo procedimental nos apañamos.

Después lo que hacemos es iterar por los números y para cada uno de ellos, calculamos todas sus posibles sumas y si alguna de ellas es de dos números abundantes, ya no tenemos en cuenta el número.

Euler #22

https://projecteuler.net/problem=22 => Names scores

Este problema ha sido interesante resolverlo porque ilustra cómo se simplifica un problema cuando el lenguaje que utilizamos tiene funcionalidades de alto nivel. Primero veamos la implementación en C, en la que reconozco que he copiado un poco a los maestros Kernighan y Ritchie en su clásico libro:

#include <stdio.h>
#include <string.h>

#define MAXLENGHT 47000
#define NWORDS 5163

void swap(char *v[], int i, int j) {
    char *temp;
    temp = v[i];
    v[i] = v[j];
    v[j] = temp;
}

void myqsort(char *v[], int left, int right) {
    int i, last;
    if (left >= right) return;
    swap(v, left, (left + right)/2);
    last = left;
    for (i = left + 1; i <= right; i++) 
        if (strcmp(v[i], v[left]) < 0)
            swap(v, ++last, i);
    swap(v, left, last);
    myqsort(v, left, last - 1);
    myqsort(v, last + 1, right);
}

int evaluate_word(char *word) {
    int len = strlen(word);
    int value = 0;
    for (int i = 0; i < len; i++) 
        value += (word[i] - 'A' + 1);
    return value;
}

int main() {
    FILE *fp;
    char line[MAXLENGHT];
    char *words[NWORDS];
    char delimiter[] = "\",\"";
    char *word;
    double sum = 0.0;

    fp = fopen("p022_names.txt", "r");
    int cont = 0;
    if (fp != NULL && fgets(line, MAXLENGHT, fp) != NULL) {
        word = strtok(line, delimiter);
        while (word != NULL) {
            words[cont] = word;
            word = strtok(NULL, delimiter);
            cont++;
        }
    }
    fclose(fp);

    myqsort(words, 0, NWORDS-1);

    for (int i = 1; i <= NWORDS; i++) {
       sum += i * evaluate_word(words[i-1]);
    }

    printf("%.0f", sum);
    return 0;
}

Veamos el mismo problema en Python:

#!/usr/bin/env python

def get_value(name):
 s = 0
 for c in name:
  s += (ord(c) - ord('A') + 1)
 return s

f = open('p022_names.txt', 'r')
txt = f.read().strip().replace('"', '')
names = txt.split(',')
names.sort()
cont = 1
total = 0
for name in names:
 total += cont * get_value(name)
 cont += 1

print total

La diferencia en cuanto a la facilidad de escribirlo en Python (o cualquier otro lenguaje de alto nivel) es clara, pero veamos los tiempos de ejecución:



167ms Python vs 39ms para C. La ejecución en Python tarda 4 veces más aproximadamente. Para un conjunto de datos más grande, en el que el tiempo de ejecución de las rutinas de ordenación depende del tamaño... la diferencia podría ser más acusada. Vamos a comprobarlo copiando el diccionario del sistema.



Son 234.371 palabras. Vamos a dejar el fichero en las mismas condiciones, esto es, con las palabras en mayúsculas, entrecomilladas y separadas por comas:

cat /usr/share/dict/words | tr '[:lower:]' '[:upper:]' | sort | uniq | tr '\n' "," | sed -e 's/,/","/g' > p022_words.txt

Editamos el fichero para corregir la primera y última comilla, cambiamos los nombres de los ficheros en el código fuente y allá vamos:



Ahora Python es unas 8 veces más lento que C.

Euler #21

https://projecteuler.net/problem=21

En este problema lo complicado es caer en la cuenta que 6 y 28 no se pueden considerar como números amigos, puesto que son "amigos de sí mismos" ;)

def get_divisors(num):
	divisors = []
	for x in range(1, num/2 + 1):
		if num % x == 0:
			divisors.append(x)
	return divisors

def find_amicable_for(num):
	sum_divs = sum(get_divisors(num))
	if sum(get_divisors(sum_divs)) == num and sum_divs != num:
		return sum_divs
	return False


if __name__ == '__main__':
	print get_divisors(28)
	amicables = []
	for x in range(1, 10000):
		a = find_amicable_for(x)
		if a is not False:
			amicables.append(a)

	print amicables
	print sum(amicables)

Euler #19, #20

https://projecteuler.net/problem=19 => Counting Sundays

Volvemos a implementar en C. Divertido problema. Mi aproximación ha sido la siguiente: si el 1/1/1900 es lunes, el 7/1/1900 es domingo. Si somos capaces de calcular el número de días que hay desde cualquier fecha al 1/1/1900, el resto de la división por 7 de este número nos dará el día de la semana (siendo 1 el lunes y 0 el domingo). El resto consiste en iterar por las fechas que nos piden.

#include <stdio.h>
#include <stdlib.h>
#define SUNDAY 0


int is_leap_year(int year) {
    return (year % 400 == 0 || (year % 4 == 0 && year % 100 != 0));
}

int days_in_month(int month, int year) {
    switch (month) {
        case 1:
        case 3:
        case 5:
        case 7:
        case 8:
        case 10:
        case 12:
            return 31;
        case 2:
            return is_leap_year(year) ? 29 : 28;
        default:
            return 30;
    }
}

int days_to_init(int day, int month, int year) {
    int days = 0;
    int month0 = 1;
    int year0 = 1900;
    days += day;
    while (month > month0) {
        days += days_in_month(month - 1, year);
        month--;
    }
    while (year > year0) {
        days += is_leap_year(year - 1) ? 366 : 365;
        year--;
    }

    return days;
}

/* 1 => Monday .... 7 => Sunday */
int day_of_week(int day) {
    return day % 7;
}

int main(int argc, char *argv[]) {
    int n_sundays = 0;
    int days;
    for (int year_start = 1901; year_start <= 2000; year_start++) {
        for (int month_start = 1; month_start <= 12; month_start++) {
            days = days_to_init(1, month_start, year_start);
            if (day_of_week(days) == SUNDAY) {
                printf("%d/%d/%d es domingo\n", 1, month_start, year_start);
                n_sundays++;
            }
        }
    }
    printf("%d domingos caen en primero de mes.\n", n_sundays);
    return 0;
}

---

https://projecteuler.net/problem=20 => Factorial digit sum

Este problema también es sencillo, solo hay que recorrer las cifras y sumarlas.
En Python:

def fact(n):
    if n <= 1:
        return 1
    else:
        return n * fact(n -1)

s = 0
for a in str(fact(100)):
    s += int(a)
print s

En C es latoso por la limitación de los tipos núméricos, ningún tipo entero (ni siquiera un unsigned long) es suficiente para contener este número tan grande.

Euler #18

https://projecteuler.net/problem=18

Este problema se me resistió un poco al principio por tratar de hacerlo a lo bruto y sin pensar mucho (es decir, calculando todas las posibles rutas).

En StackOverflow encontré una pequeña pista: ir reduciendo cada fila, desde abajo hasta arriba, calculando la máxima suma en cada interacción. Una vez tomada esta aproximación, el código es trivial:

Python:

   1 #!/usr/bin/env python2
   2 data = [
   3 ['75'],
   4 ['95', '64'],
   5 ['17', '47', '82'],
   6 ['18', '35', '87', '10'],
   7 ['20', '04', '82', '47', '65'],
   8 ['19', '01', '23', '75', '03', '34'],
   9 ['88', '02', '77', '73', '07', '63', '67'],
  10 ['99', '65', '04', '28', '06', '16', '70', '92'],
  11 ['41', '41', '26', '56', '83', '40', '80', '70', '33'],
  12 ['41', '48', '72', '33', '47', '32', '37', '16', '94', '29'],
  13 ['53', '71', '44', '65', '25', '43', '91', '52', '97', '51', '14'],
  14 ['70', '11', '33', '28', '77', '73', '17', '78', '39', '68', '17', '57'],
  15 ['91', '71', '52', '38', '17', '14', '91', '43', '58', '50', '27', '29', '48'],
  16 ['63', '66', '04', '68', '89', '53', '67', '30', '73', '16', '69', '87', '40', '31'],
  17 ['04', '62', '98', '27', '23', '09', '70', '98', '73', '93', '38', '53', '60', '04', '23']]
  18 
  19 for row in range(len(data) - 2, -1, -1):
  20     for col in range(row+1):
  21         data[row][col] = max((int(data[row][col]) + int(data[row + 1][col + 0]), int(data[row][col]) + int(data[row + 1][col + 1])))
  22 
  23 print data[0][0]
  24