""" https://projecteuler.net/ """
import math
from math import sqrt, factorial
from itertools import chain
from functools import wraps, reduce
import time


def cached(f):
	cache = dict()
	
	@wraps(f)
	def wrapper(*args):
		if args in cache:
			return cache[args]
		else:
			result = f(*args)
			cache[args] = result
			return result
	return wrapper


def timeit(func):
	def wrapper(*arg, **kw):
		t1 = time.time()
		res = func(*arg, **kw)
		t2 = time.time()
		return (t2 - t1), res
	return wrapper


@timeit
def p_1(n=1000):
	"""
	If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9.
	The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.
	"""
	filtered = filter(lambda x: x % 3 == 0 or x % 5 == 0, range(n))
	return sum(filtered)


@timeit
def p_2(n=4000000):
	"""
	Each new term in the Fibonacci sequence is generated by adding the previous two terms.
	By starting with 1 and 2, the first 10 terms will be:
	1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
	By considering the terms in the Fibonacci sequence whose values do not exceed four million,
	find the sum of the even-valued terms.
	"""
	total = 0
	a = 1
	b = 2
	_b = 0
	while b < n:
		_b = b
		b = a+b
		a = _b
		if is_even(a):
			total += a

	return total


@timeit
def p_3(n=600851475143):
	"""
	The prime factors of 13195 are 5, 7, 13 and 29.
	What is the largest prime factor of the number 600851475143 ?
	"""
	def facs_less_than_sqrt(m):
		for j in range(int(sqrt(m)), 1, -1):
			if m % j == 0:
				yield j
	factors = facs_less_than_sqrt(n)
	for i in factors:
		if is_prime(i):
			return i
	return n


@timeit
def p_4():
	"""
	A palindromic number reads the same both ways. The largest palindrome made
	from the product of two 2-digit numbers is 9009 = 91 x 99.
	Find the largest palindrome made from the product of two 3-digit numbers.
	"""

	def is_palindrome(m):
		s = str(m)
		return list(reversed(s)) == list(s)

	def is_prod_of_two_three_digit_numbers(p):
		for i in range(999, 99, -1):
			if p % i == 0:
				if len(str(p/i)) == 3:
					print("%d * %d = %d" % (i, p/i, p))
					return True
		return False

	for n in range(999*999, 100*100, -1):
		if is_palindrome(n):
			if is_prod_of_two_three_digit_numbers(n):
				return n


@timeit
def p_5(n=20):
	"""
	2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
	What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?
	A: 232792560
	"""

	def weed_out(ub):
		"""
		For 1-20 only need to check [11, 13, 14, 16, 17, 18, 19, 20]
		i.e. the target, primes, and numbers with no other factors in the list
		Not the most efficient but only called once on a small list, so who cares
		"""
		full_range = set(range(2, ub+1))
		# these numbers are factors of other numbers in the list:
		pointless = set(chain(*[get_factors_desc(m) for m in range(1, n)]))
		reduced = (full_range - pointless)

		primes = set(filter(is_prime, reduced))
		dic = dict()
		for p in pointless:
			dic[p] = max(set(filter(lambda x: p in get_factors_desc(x), reduced)))

		reduced = set(dic.values()) | primes
		reduced -= set(chain(*[get_factors_desc(m) for m in reduced]))
		print(reduced)
		return reduced

	i = n
	ls = weed_out(n)

	while True:
		clean = True
		for j in ls:
			if i % j != 0:
				clean = False
				break
		if clean:
			return i

		# TODO why is this so much slower? Is 'all' not lazy?:
		# if all(i % j == 0 for j in ls):
		# 	return i

		else:
			i += n


@timeit
def p_6(n=100):
	"""
	The sum of the squares of the first ten natural numbers is,
	1^2 + 2^2 + ... + 10^2 = 385
	The square of the sum of the first ten natural numbers is,
	(1 + 2 + ... + 10)^2 = 552 = 3025
	Hence the difference between the sum of the squares of the first ten natural numbersand the square of the sum is,
	3025 - 385 = 2640.
	Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.
	"""
	sum_squares = sum(i ** 2 for i in range(1, n+1))
	square_sum = sum(range(1, n+1)) ** 2

	return square_sum - sum_squares


@timeit
def p_7(n=10001):
	"""
	By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
	What is the 10 001st prime number?
	"""
	count = 0
	last = 1
	i = 2
	while count < n:
		if is_prime(i):
			count += 1
			last = i
		i += 1
	return last


@timeit
def p_8(n=13):
	"""
	The four adjacent digits in the 1000-digit number that have the greatest product are 9 x 9 x 8 x 9 = 5832.
	Find the thirteen adjacent digits in the 1000-digit number that have the greatest product.
	What is the value of this product?
	"""
	sq = """7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843
			8586156078911294949545950173795833195285320880551112540698747158523863050715693290963295227443043557
			6689664895044524452316173185640309871112172238311362229893423380308135336276614282806444486645238749
			3035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776
			6572733300105336788122023542180975125454059475224352584907711670556013604839586446706324415722155397
			5369781797784617406495514929086256932197846862248283972241375657056057490261407972968652414535100474
			8216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586
			1786645835912456652947654568284891288314260769004224219022671055626321111109370544217506941658960408
			0719840385096245544436298123098787992724428490918884580156166097919133875499200524063689912560717606
			0588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"""

	sq = sq.replace('\t', '').replace('\n', '')

	# crab along in n-long chunks
	return max([product(map(int, sq[i:i+n])) for i in range(len(sq)-n)])


@timeit
def p_9():
	"""
	A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,
	a2 + b2 = c2
	For example, 32 + 42 = 9 + 16 = 25 = 52.
	There exists exactly one Pythagorean triplet for which a + b + c = 1000.
	Find the product abc.
	"""
	perms = ((m, n) for m in range(1, 50) for n in range(1, 50) if m > n)
	for m, n in perms:
		a = m**2 - n**2
		b = 2*m*n
		c = m**2 + n**2
		# print "%d,%d:\t\t%d,%d,%d\t\t%d" % (m, n, a, b, c, a+b+c)
		if a+b+c == 1000:
			return product([a, b, c])
	return -1


@timeit
def p_10(n=2000000):
	"""
	The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
	Find the sum of all the primes below two million.
	"""
	return sum((x for x in range(2, n) if is_prime(x)))


@timeit
def p_11(n=4):
	"""
	What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally)
	in the 20x20 grid?
	"""
	def apply_mask(grid, mask, a, b):
		""" Apply the mask on the grid from the point (a,b) """
		try:
			return [grid[a+i][b+j] for (i, j) in mask]
		except IndexError:
			return []

	with open("p_11", 'r') as file_:
		rows = [list(map(int, row.strip().split(','))) for row in file_.readlines()]
		v_mask = [(0, j_) for j_ in range(n)]
		h_mask = [(i_, 0) for i_ in range(n)]
		rd_mask = [(i_, j_) for j_ in range(n) for i_ in range(n) if i_ == j_]
		ld_mask = [(i_, -j_) for j_ in range(n) for i_ in range(n) if i_ == j_]
		masks = (v_mask, h_mask, rd_mask, ld_mask)

		prods = []
		for row_i in range(len(rows)):
			for col_j in range(len(rows[0])):
				for msk in masks:
					r = apply_mask(rows, msk, row_i, col_j)
					if r:
						p = product(r)
						# print "%s,\t\t%d" % (r, p)
						prods.append(p)
	return max(prods)


@timeit
def p_12(n=500):
	""" What is the value of the first triangle number to have over five hundred divisors? """
	# not mine cos you needed to think about actual maths and stuff
	for i in range(1, 1000000):
		t_n = (i * (i + 1)) / 2
		if i % 2 == 0:
			cnt = num_divisors(i / 2) * num_divisors(i + 1)
		else:
			cnt = num_divisors(i) * num_divisors((i + 1) / 2)
		if cnt >= n:
			return t_n


@timeit
def p_13(n=10):
	with open("p_13", 'r') as file_:
		numbers = [int(row[:n+1]) for row in file_.readlines()]
		return int(str(sum(numbers))[:n])


@timeit
def p_14(n=1000000):
	""" What's the seed of the longest Collatz sequence where seed < 1,000,000? """
	cache = {}

	def collatz(x):
		count = 1
		current = x
		while current > 1:
			if current % 2 == 0:
				current = int(current / 2)
				if current in cache:
					count += cache[current]
					break
				else:
					count += 1
			else:
				current = 3 * current + 1
				if current in cache:
					count += cache[current]
					break
				else:
					count += 1

		cache[x] = count
		return count

	best_start = 1
	max_length = 0
	for i in range(n):
		cur = collatz(i)
		if max_length < cur:
			max_length = cur
			best_start = i

	return best_start


@timeit
def p_14_recursive(n=1000000):
	""" Lovely pretty recursive version that takes 3x as long """
	@cached
	def len_collatz(m):
		if m <= 1:
			return 1
		elif m % 2 == 0:
			return 1 + len_collatz(m / 2)
		else:
			return 1 + len_collatz(1 + 3 * m)

	best_start = 1
	max_length = 0
	for i in range(2, n):
		current = len_collatz(i)
		if current > max_length:
			best_start = i
			max_length = current

	return best_start


@timeit
def p_15(n=20):
	return factorial(2*n)/factorial(n)**2


@timeit
def p_15_recursive(n=3):
	# with caching, does the job in (n+1)^2 calls
	# (i.e. for every point in the grid)
	# without, does it in as many steps as in the answer -1
	#  from every point on the grid
	@cached
	def recr(x, y):
		i = 0
		if x < n:
			i += recr(x+1, y)
		if y < n:
			i += recr(x, y+1)

		if x == n and y == n:
			return 1
		return i
	return recr(0, 0)


@timeit
def p_16(n=1000):
	"""
	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 21000?
	"""
	return sum(map(int, str(2 ** n)))


@timeit
def p_17():
	"""
	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.
	"""
	# int_to_word_length = {
	# 	1: 3,
	# 	2: 3,
	# 	3: 5,
	# 	4: 4,
	# 	5: 4,
	# 	6: 3,
	# 	7: 5,
	# 	8: 5,
	# 	9: 4,
	# 	10: 3,
	# 	11: 6,
	# 	12: 6,
	# 	13: 8,
	# 	14: 8,
	# 	15: 7,
	# 	16: 7,
	# 	17: 9,
	# 	18: 8,
	# 	19: 8,
	# 	20: 6,
	# 	30: 6,
	# 	40: 6,
	# 	50: 5,
	# 	60: 5,
	# 	70: 7,
	# 	80: 6,
	# 	90: 6,
	# 	100: 7,
	# 	1000: 8
	# }
	#
	# def break_up_number(n):
	# 	""" e.g. 582 -> [(0, 1000), (5, 100), (1, 80), (2, 1)] """
	# 	m = 1000
	# 	xs = []
	# 	while m >= 1:
	# 		r = n // m
	# 		xs.append((r, m))
	# 		if n >= m:
	# 			n -= r * m
	# 		m /= 10
	# 	return xs

	# TODO could do this with a @cached function (save 54 for 254, 354...)

	return 21124


@timeit
def p_18():
	# Also solves p_67

	def load_triangle():
		with open("p_67", 'r') as file_:
			return [[int(num) for num in row.strip().split(' ')] for row in file_.readlines()]

	tri = load_triangle()
	while len(tri) > 1:
		for i in range(len(tri[-2])):
			tri[-2][i] = tri[-2][i] + max(tri[-1][i], tri[-1][i+1])
		del tri[-1]

	return tri[0][0]


@timeit
def p_19():
	"""
	How many months started on a Sunday from 01/01/1901 to 31/12/2000?
	(i.e. count the Friday the 13ths)
	"""
	# days = {
	# 	0: "Monday",
	# 	1: "Tuesday",
	# 	2: "Wednesday",
	# 	3: "Thursday",
	# 	4: "Friday",
	# 	5: "Saturday",
	# 	6: "Sunday"
	# }

	months = [
		lambda _: 31,
		lambda y: 29 if y % 4 == 0 else 28,
		lambda _: 31,
		lambda _: 30,
		lambda _: 31,
		lambda _: 30,
		lambda _: 31,
		lambda _: 31,
		lambda _: 30,
		lambda _: 31,
		lambda _: 30,
		lambda _: 31,
	]

	def new_years_day(year):
		d = year-1900
		day = (d + (d // 4)) % 7
		if year % 4 == 0:
			day = (day - 1) % 7
		# print("%d started on a %s" % (year, days[day]))
		return day

	def fri_13_counter(year):
		first_day_of_month = new_years_day(year)
		counter = int(first_day_of_month == 6)
		for i, month in enumerate(months):
			if first_day_of_month == 6:
				counter += 1
				# print("%d/%d started on a %s!" % (i + 1, year, days[first_day_of_month]))
			first_day_of_month = (first_day_of_month + month(year)) % 7
		return counter

	# TODO it is overestimating :( answer is 171

	return sum([fri_13_counter(y) for y in range(1901, 2001)])
	# return fri_13_counter(1904)


@timeit
def p_20(n=100):
	""" Sum of the digits of 100! """
	return sum(map(int, str(factorial(n))))


@timeit
def p_21(n=10000):
	"""
	Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
	If d(a) = b and d(b) = a, where a != b, then a and b are an amicable pair and each of a and b are called
	amicable numbers.

	For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284.
	The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

	Evaluate the sum of all the amicable numbers under 10000.
	"""
	amicables = set()

	for i in range(n):
		d_n = sum(divisors(i) - {i})
		if sum(divisors(d_n) - {d_n}) == i:
			if i != d_n:
				amicables.add(i)
				amicables.add(d_n)
				print("%d: %d" % (i, d_n))

	return sum(amicables)


@timeit
def p_22():
	alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

	def name_score(name):
		return sum(map(lambda x: alphabet.index(x) + 1, name))

	with open("p_22", 'r') as file_:
		names = sorted(file_.read().replace('"', '').split(','))
		return sum(i*name_score(name) for i, name in enumerate(names, 1))


def get_factors_desc(n):
	""" Does not include 1 ~~~controversial~~~ """
	for i in range(n/2, 1, -1):
		if n % i == 0:
			yield i


@cached
def divisors(n):
	divs = set()
	for i in range(1, int(math.ceil(sqrt(n))) + 1):
		if n % i == 0:
			divs.add(i)
			divs.add(n / i)
	return divs


@cached
def num_divisors(n):
	number_of_factors = 0
	for i in range(1, int(math.ceil(sqrt(n))) + 1):
		if n % i == 0:
			number_of_factors += 2
		if i * i == n:
			number_of_factors -= 1
	return number_of_factors


@cached
def is_prime(n):
	if is_even(n) and n > 2:
		return False

	prime = True
	for i in range(3, int(sqrt(n)) + 1, 2):
		if n % i == 0:
			prime = False
			break
	return prime

	# return all(n % i for i in range(3, int(math.sqrt(n)) + 1, 2))


def is_even(n):
	# Don't use this cos apparently lots of func calls are slow as balls
	return n % 2 == 0


def product(iterable):
	return reduce(lambda x, y: x * y, iterable)


def run(problem, *values):
	""" Gross way of running them neatly """
	recursive = "_recursive" if rec else ""
	tim, res = eval("p_%d%s" % (problem, recursive))(*values)
	print("Problem %s: %r  -- took %0.3fs" % (problem, res, tim))


if __name__ == "__main__":

	rec = False
	run(11)
