In the 20×20 grid below, four numbers along a diagonal line have been marked in red. The product of these numbers is 26 × 63 × 78 × 14 = 1788696.
What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20×20 grid?
In [142]:
"""
In, the, 20×20, grid, below,, four, numbers, along, a, diagonal, line, have, been, marked, in, red.
The, product, of, these, numbers, is, 26, ×, 63, ×, 78, ×, 14, =, 1788696.
What, is, the, greatest, product, of, four, adjacent, numbers, in, the, same, direction
(up,, down,, left,, right,, or, diagonally), in, the, 20×20, grid?
"""
import numpy
import time, timeit
def diag():
n = numpy.array(
[[ 8, 2, 22, 97, 38, 15, 0, 40, 0, 75, 4, 5, 7, 78, 52, 12, 50, 77, 91, 8],
[49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48, 4, 56, 62, 0],
[81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30, 3, 49, 13, 36, 65],
[52, 70, 95, 23, 4, 60, 11, 42, 69, 24, 68, 56, 1, 32, 56, 71, 37, 2, 36, 91],
[22, 31, 16, 71, 51, 67, 63, 89, 41, 92, 36, 54, 22, 40, 40, 28, 66, 33, 13, 80],
[24, 47, 32, 60, 99, 3, 45, 2, 44, 75, 33, 53, 78, 36, 84, 20, 35, 17, 12, 50],
[32, 98, 81, 28, 64, 23, 67, 10, 26, 38, 40, 67, 59, 54, 70, 66, 18, 38, 64, 70],
[67, 26, 20, 68, 2, 62, 12, 20, 95, 63, 94, 39, 63, 8, 40, 91, 66, 49, 94, 21],
[24, 55, 58, 5, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72],
[21, 36, 23, 9, 75, 0, 76, 44, 20, 45, 35, 14, 0, 61, 33, 97, 34, 31, 33, 95],
[78, 17, 53, 28, 22, 75, 31, 67, 15, 94, 3, 80, 4, 62, 16, 14, 9, 53, 56, 92],
[16, 39, 5, 42, 96, 35, 31, 47, 55, 58, 88, 24, 0, 17, 54, 24, 36, 29, 85, 57],
[86, 56, 0, 48, 35, 71, 89, 7, 5, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58],
[19, 80, 81, 68, 5, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77, 4, 89, 55, 40],
[ 4, 52, 8, 83, 97, 35, 99, 16, 7, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66],
[88, 36, 68, 87, 57, 62, 20, 72, 3, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69],
[ 4, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18, 8, 46, 29, 32, 40, 62, 76, 36],
[20, 69, 36, 41, 72, 30, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74, 4, 36, 16],
[20, 73, 35, 29, 78, 31, 90, 1, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57, 5, 54],
[ 1, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52, 1, 89, 19, 67, 48]]
)
max_value = 0
max_reg = {}
for i in range(20):
for j in range(20):
v_fila = v_diag_sup = v_diag_inf = v_col = 1
if j < 17:
for k in range(4):
v_fila *= n[i][j + k]
v_col *= n[j + k][i]
if i < 17:
v_diag_inf *= n[i + k][j + k]
if i < 17 and j > 2:
for k in range(4):
v_diag_sup *= n[i + k][j - k]
# La forma mas elegante y concisa y rapida (aunque parezca mentira)
# almacenando datos en un diccionario con los distintos valores que han
# ido siendo los mayores, y las posiciones en que se dan
if max_value < max(v_fila, v_diag_sup, v_diag_inf, v_col):
max_value = max(v_fila, v_diag_sup, v_diag_inf, v_col)
max_reg[(i, j)] = max_value
# maxi.append({(i, j): max(v_fila, v_diag_sup, v_diag_inf, v_col)})max(v_fila, v_diag_sup, v_diag_inf, v_col)})
return max_reg
inicio = time.time()
print(max(diag().values()))
print("Tiempo: {:.5f} segundos".format(time.time() - inicio))
# RESULTADO 70.600.674 Tiempo: 0.00259 segundos
# Muy buen tema en StackOverflow
# http://stackoverflow.com/questions/8023306/get-key-by-value-in-dictionary
The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
Let us list the factors of the first seven triangle numbers:
1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28
We can see that 28 is the first triangle number to have over five divisors.
What is the value of the first triangle number to have over five hundred divisors?
In [4]:
import cython # Su uso no mejora al trabajar sobretodo con listas. Hay que pasarlas a listas
# de C mediante gestion dinamica para aprovecharlo realmente
from math import sqrt
import time, timeit
@cython.locals(i=cython.int)
def divisores(numero):
a = [i for i in range(1, numero // 2 + 1) if not numero % i]
a.append(numero)
return a
# Hacer esto asi y no con sum(lista) es infinitamente mas rapido
@cython.cfunc
@cython.returns(cython.int)
@cython.locals(numero=cython.int)
def numero_divisores(numero):
return sum(2 for i in range(1, int(sqrt(numero)) + 1) if not numero % i)
@cython.cfunc
@cython.returns(cython.int)
@cython.locals(i=cython.int)
def gen_triangular():
for i in range(1000000):
yield sum(range(i))
@cython.cfunc
@cython.returns(cython.int)
@cython.locals(i=cython.int)
def main():
for i in generador:
if numero_divisores(i) > 500:
return i
In [5]:
inicio = time.time()
generador = gen_triangular()
print("El primer numero triangular con mas de 500 divisores es {}".format(main()))
print("Tiempo: {:.5f} segundos".format(time.time() - inicio))
# Sin cython: 6.50812 segundos
Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.
In [7]:
r = open('./numero_ejercicio_13.txt')
s = 0
for i in r:
s += int(i)
print(s)
In [78]:
from IPython.display import HTML
HTML('<iframe src="https://projecteuler.net/problem=14" width=800 height=400></iframe>')
Out[78]:
In [2]:
## VERSION RECURSIVA SIN MEJORAS
# Tiempo: 55.16645 segundos (con operacion binaria aprox lo mismo)
# Resultado 837.799
import time
def collatz(n, lista):
lista.append(n)
if n == 1:
return 1, lista
elif n % 2:
return collatz(int(n*3 + 1), lista)
else:
return collatz(n >> 1, lista)
start = time.time()
max_len = max_num = 0
lista = []
for i in range(1, 27):
lista = collatz(i, [])[1]
length = len(lista)
if length > max_len:
max_len = length
max_num = i
print("La cadena del numero {} tiene {} elementos".format(max_num, max_len))
print("Tiempo: {:.5f} segundos".format(time.time() - start))
In [12]:
## VERSION RECURSIVA - CONTADOR EN VEZ DE LISTA
# Tiempo: 46.91166 segundos; MEJOR que con listas
# Resultado 837.799
import time
def collatz(n, count):
count += 1
if n == 1:
return 1, count
elif n % 2:
return collatz(int(n*3 + 1), count)
else:
return collatz(n >> 1, count)
start = time.time()
max_len = max_num = 0
length = 0
for i in range(1, 10000):
length = collatz(i, 0)[1]
if length > max_len:
max_len = length
max_num = i
print("La cadena del numero {} tiene {} elementos".format(max_num, max_len))
print("Tiempo: {:.5f} segundos".format(time.time() - start))
In [31]:
## VERSION ITERATIVA SIN MEJORAS
# Tiempo: 25.73280 segundos; MEJOR que recursivas
# Resultado 837.799
import time
def collatz(n):
count = 1 # Para contar el propio 1
while n > 1:
if n % 2:
n = 3*n + 1
else:
n = n >> 1
count += 1
return n, count
start = time.time()
max_len = max_num = 0
for i in range(1, 100000):
num, length = collatz(i)
if length > max_len:
max_len = length
max_num = i
print("La cadena del numero {} tiene {} elementos".format(max_num, max_len))
print("Tiempo: {:.5f} segundos".format(time.time() - start))
In [1]:
%load_ext cythonmagic
In [24]:
%%cython
## VERSION ITERATIVA CYTHON
# Tiempo: 15.87660 segundos; MEJOR que recursivas
# Resultado 837.799 - 525 elementos
# Con declaraciones -> 14.21716 segundos
import time
# import numpy as np
# cimport numpy as np
cimport cython
@cython.cfunc
@cython.cdivision(True) # Directiva a true para evitar comprobaciones
# @cython.locals(n=cython.int) ## no puedo ponerlo porque se ralla
@cython.locals(count=cython.int)
def collatz(n):
# count = cython.declare(cython.int, 1) # Para contar el propio 1
count = 1
while n > 1:
if n % 2:
n = 3*n + 1
else:
n = n >> 1
count += 1
return n, count
@cython.cdivision(True)
def main():
# DECLARACIONES
cdef int max_len, max_num, num, length
start = cython.declare(cython.double, time.time())
max_len = 0
for i in range(1, 300000):
num, length = collatz(i)
if length > max_len:
max_len = length
max_num = i
print("La cadena del numero {} tiene {} elementos".format(max_num, max_len))
print("Tiempo: {:.5f} segundos".format(time.time() - start))
main()
In [6]:
%%cython
## VERSION ITERATIVA CYTHON - CON CACHE
# Tiempo: 1.50683 segundos; MEJORA enorme
# Resultado 837.799 - 525 elementos
import time
# import numpy as np
# cimport numpy as np
cimport cython
CACHE = {}
@cython.cfunc
@cython.cdivision(True) # Directiva a true para evitar comprobaciones
# @cython.locals(n=cython.int) ## no puedo ponerlo porque se ralla
@cython.locals(count=cython.int)
def collatz(n):
global CACHE
CACHE[1] = 1
CACHE[2] = 2
count, aux = 0, n
# aux = n
while n > 1:
if n in CACHE:
count += CACHE[n]
CACHE[aux] = count
return n, count
else:
if n % 2:
n = 3*n + 1
else:
n = n >> 1
count += 1
CACHE[aux] = count
return n, count
@cython.cdivision(True)
def main():
# DECLARACIONES
cdef int max_len, max_num, num, length
start = cython.declare(cython.double, time.time())
max_len = 0
for i in range(2, 1000000):
num, length = collatz(i)
if length > max_len:
max_len = length
max_num = i
print("La cadena del numero {} tiene {} elementos".format(max_num, max_len))
print("Tiempo: {:.5f} segundos".format(time.time() - start))
main()
In [5]:
from IPython.display import HTML
HTML('<iframe src="https://projecteuler.net/problem=15" width=800 height=400></iframe>')
Out[5]:
In [83]:
## PARA RESOLVER ESTE PROBLEMA HACE FALTA TENERLO CLARO DESDE EL PRINCIPIO
## CON EL METODO DE LA ULTIMA CELDA ES INFINITAMENTE MAS FACIL Y RAPIDO
# Para entender este metodo, hay que pensar a partir de un caso base de n = 2
# y a partir de ahi ir viendo caminos posibles a cada celda desde una hipotetica
# casilla 0,0
# Al aumentar para mayores n's se sigue la misma matematica por lo que podemos
# aplicar lo hallado para n = 2. Programarlo es tremendamente facil
def lattice_paths(n: "Integer") -> "Iterable[Int]":
camino = [[0]*(n + 1) for i in range(n + 1)]
for row in range(n + 1):
for col in range(n + 1):
if row == 0 or col == 0:
camino[row][col] = 1
else:
camino[row][col] = camino[row - 1][col] + camino[row][col - 1]
return camino
start = time.time()
for i in range(100):
lattice_paths(20)
print("Tiempo: {:.5f} segundos".format(time.time() - start))
In [3]:
## FORMA MAS RAPIDA. COPIADA DE WEB. POCO INTUITIVA
## AUN CONSIGUE MAYOR VELOCIDAD CON CYTHON Y MALLOC
import time
def route_num(cube_size):
L = [1] * cube_size
for i in range(cube_size):
for j in range(i):
L[j] = L[j]+L[j-1]
L[i] = 2 * L[i - 1]
return L[cube_size - 1]
start = time.time()
n = route_num(20)
elapsed = (time.time() - start)
print("{} found in {} seconds".format(n,elapsed))
In [2]:
## Calculando factoriales (con combinatoria), mucho mas rapido
# ( 40 20 )
import time
def combinaciones(n, k):
n = factorial(n) / (factorial(k)*factorial(n - k))
return int(n)
def factorial(n):
a = 1
while n > 1:
a *= n
n -= 1
return int(a)
start = time.time()
for i in range(100):
combinaciones(40, 20)
print("Tiempo: {:.5f} segundos".format(time.time() - start))
In [2]:
"""
2^15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.
What is the sum of the digits of the number 2^1000?
"""
import time, timeit
def suma_digitos(base=2, exp=1):
suma = 0
res = str(base**exp)
for i in range(len(res)):
suma += int(res[i])
return suma
start = time.time()
print(suma_digitos(2, 1000))
print("tiempo = {:.5f} seg".format(time.time() - start))
In [1]:
"""
If the numbers 1 to 5 are written out in words: one, two, three, four, five, then
there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.
If all the numbers from 1 to 1000 (one thousand) inclusive were written out in
words, how many letters would be used?
NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and
forty-two) contains 23 letters and 115 (one hundred and fifteen) contains
20 letters. The use of "and" when writing out numbers is in compliance with
British usage.
"""
import time, timeit
def number_to_letter(n: "Int") -> "str":
# 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
u = [ 0, 3, 3, 5, 4, 4, 3, 5, 5, 4, 3, 6, 6, 8, 8, 7, 7, 8, 9, 8 ]
d = [ 0, 4, 6, 6, 6, 5, 5, 7, 6, 6 ]
c = [ 0, 7, 10, 12, 11, 11, 10, 12, 12, 11 ]
m = [ 0, 11 ]
suma_and = 3
count = 0
for i in range(n, 0, -1):
plus = 0
aux = i
while i > 0:
if i > 999:
plus += m[1]
i -= 1000
elif i > 99:
centena = int(str(i)[0])
i -= centena * 100
plus += c[centena] + suma_and
elif i > 19:
decena = int(str(i)[0])
i -= decena * 10
plus += d[decena]
else:
plus += u[i]
i = 0
count += plus
return count
start = time.time()
respuesta = number_to_letter(1000)
print(respuesta)
print("tiempo = {:.5f} seg".format(time.time() - start))
assert respuesta == 21124
In [19]:
u = [0, 3, 3, 5, 4, 4, 3, 5, 5, 4, 3, 6, 6, 8, 8, 7, 7, 8, 9, 8]
d = [0, 4, 6, 6, 6, 5, 5, 7, 6, 6]
c = [0, 10, 10, 12, 11, 11, 10, 12, 12]
In [20]:
## NO TENGO BIEN EL PROBLEMA
## El planteamiento si, pero hay algun numero en ingles
## que no se escribir y me jode la cuenta.
## He buscado la solucion y la he puesto en el resultado
## no se donde fallo
In [1]:
from IPython.display import HTML
HTML('<iframe src="https://projecteuler.net/problem=18" width=800 height=400></iframe>')
Out[1]:
In [60]:
import time
start = time.time()
num_int = []
# numbers = open('problem18.txt')
numbers = open('problem67.txt')
# Creamos matriz con enteros
for i in numbers:
num_int.append([int(j) for j in i.split()])
a = [[int(j) for j in i] for i in numbers]
def camino(lista):
n = lista[::-1]
while len(n) > 0:
j = 0
while j < (len(n[0]) - 1):
n[1][j] += max(n[0][j], n[0][j + 1])
j += 1
aux = n.pop(0)
return aux
print(camino(num_int))
print("Tiempo = {:.5f} seg".format(time.time() - start))
# [7273]
# Tiempo = 0.00553 seg
# No hago mas pruebas porque me ha salido eficiente de cojones
In [15]:
from IPython.display import HTML
HTML('<iframe src="https://projecteuler.net/problem=19" width=800 height=400></iframe>')
Out[15]:
In [1]:
from IPython.display import HTML
HTML('<iframe src="https://projecteuler.net/problem=20" width=800 height=400></iframe>')
Out[1]:
In [13]:
import time
start = time.time()
def fact(n):
f = 1
while n > 0:
f *= n
n -= 1
return f
suma = 0
res = fact(100)
for i in str(res):
suma += int(i)
# print(res)
print(suma)
print("Tiempo = {:.5f} seg".format(time.time() - start))
# 648
# Tiempo = 0.00040 seg
In [ ]: