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