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