main.py

# coding=utf-8
import math
from datetime import datetime, timedelta
from time import time

from helpers import Helpers


def even_fib_numbers():
	ef1 = 0
	ef2 = 2
	result = ef1 + ef2
	r = 4000000
	while ef2 <= r:
		ef3 = 4 * ef2 + ef1
		if ef3 > r:
			break
		result += ef3
		ef1 = ef2
		ef2 = ef3
	print(str(result))


def largest_prime_factor():
	n = 600851475143
	# n = 6
	result = -1
	while n % 2 == 0:
		result = 2
		n /= 2
		print("result is: " + str(result))
		print("n is: " + str(n))

	for i in range(3, int(math.sqrt(n)), 2):
		while n % i == 0:
			result = i
			n = n / i
			print("result is: " + str(result))
			print("n is: " + str(n))
	if n > 2:
		result = n
	print("result is: " + str(result))


def largest_palindrome_product():
	start = 100
	end = 999
	result = 0
	for x in range(end, start, -1):
		for y in range(end, start, -1):
			prod = x * y
			if str(prod) == str(prod)[::-1]:
				if prod > result:
					result = prod
	print("result: " + str(result))


def smallest_multiple():
	n = 20
	result = 1
	for x in range(1, n, 1):
		previous = result
		while result % x != 0:
			result = result + previous
	print("result: " + str(result))


def sum_square_difference():
	n = 100
	sum_squares = 0
	square_sums = 0
	for i in range(n + 1):
		sum_squares = sum_squares + (i * i)
	for i in range(n + 1):
		square_sums += i
	square_sums = square_sums * square_sums
	result = square_sums - sum_squares
	print(str(result))


def ten_thousand_first_prime():
	num_primes = 1
	counter = 2
	while num_primes < 10001:
		counter += 1
		if Helpers.is_prime(counter):
			num_primes += 1
	print(str(counter))


def largest_product_in_series():
	num = 7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450
	greatest_product = 0
	num_string = str(num)
	n_len = len(num_string)
	split_num = 13
	# split_num = 4
	for i in range(n_len - split_num + 1):
		portion = num_string[i:split_num + i]
		portion_list = [int(s) for s in portion]
		prod = 1
		for p in portion_list:
			prod = prod * p
		if prod > greatest_product:
			greatest_product = prod
	print(str(greatest_product))


def special_pythagorean_triplet():
	result = 0
	target = 1000
	for counter in range(1, target):
		if result != 0:
			break
		for counter_1 in range(counter + 1, target - 1):
			counter_2 = ((counter ** 2) + (counter_1 ** 2)) ** 0.5
			if counter + counter_1 + counter_2 == target:
				print("counter value is: " + str(counter))
				print("counter_1 value is: " + str(counter_1))
				print("counter_2 value is: " + str(counter_2))
				print("************HIT**************")
				result = counter * counter_1 * counter_2
				break
	Helpers.pr(int(result))


def summation_of_primes():
	"""
	The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

	Find the sum of all the primes below two million.
	:return:
	"""
	result = 0
	n = 2000000
	# n = 10
	for i in range(n):
		if Helpers.is_prime(i):
			result += i
	Helpers.pr(result)


def largest_product_in_a_grid():
	"""
	In the 20×20 grid below, four numbers along a diagonal line have been
	marked in red.

	08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
	49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
	81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
	52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 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 03 45 02 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 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
	24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
	21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
	78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
	16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
	86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
	19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
	04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
	88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
	04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
	20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
	20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
	01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

	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?
	:return:
	"""
	def get_point_value(multi_dim_arr, y_el, x_el):
		if 0 <= y_el < len(multi_dim_arr) and 0 <= x_el < len(multi_dim_arr[y_el]):
			return multi_dim_arr[y_el][x_el]
		return 0

	result = 0
	arr = [
		[8, 2, 22, 97, 38, 15, 00, 40, 00, 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, 00],
		[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, 00, 76, 44, 20, 45, 35, 14, 00, 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, 00, 17, 54, 24, 36, 29,
			85, 57],
		[86, 56, 00, 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, 0, 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]
	]
	d = 4
	for y in range(len(arr)):
		for x in range(len(arr)):
			point1, point2, point3, point4 = 1, 1, 1, 1
			for i in range(d):
				print("point1: " + str(point1))
				print("point2: " + str(point2))
				print("point3: " + str(point3))
				print("point4: " + str(point4))
				point1 *= get_point_value(arr, y, x + i)
				point2 *= get_point_value(arr, y + i, x)
				point3 *= get_point_value(arr, y + i, x + i)
				point4 *= get_point_value(arr, y + i, x - i)
				print("point1: " + str(point1))
				print("point2: " + str(point2))
				print("point3: " + str(point3))
				print("point4: " + str(point4))
				result = max(point1, point2, point3, point4, result)
				Helpers.pr(result)

	Helpers.pr(result)


def highest_divisible_triangular_number():
	"""
	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?

	:return:
	"""
	target = 500
	result = 0
	n = 1
	while Helpers.number_of_divisors(result) < target:
		result += n
		n += 1
	Helpers.pr(result)


def large_sum():
	"""
	Work out the first ten digits of the sum of the following one-hundred
	50-digit numbers.

	:return:
	"""
	nums = [
		37107287533902102798797998220837590246510135740250,
		46376937677490009712648124896970078050417018260538,
		74324986199524741059474233309513058123726617309629,
		91942213363574161572522430563301811072406154908250,
		23067588207539346171171980310421047513778063246676,
		89261670696623633820136378418383684178734361726757,
		28112879812849979408065481931592621691275889832738,
		44274228917432520321923589422876796487670272189318,
		47451445736001306439091167216856844588711603153276,
		70386486105843025439939619828917593665686757934951,
		62176457141856560629502157223196586755079324193331,
		64906352462741904929101432445813822663347944758178,
		92575867718337217661963751590579239728245598838407,
		58203565325359399008402633568948830189458628227828,
		80181199384826282014278194139940567587151170094390,
		35398664372827112653829987240784473053190104293586,
		86515506006295864861532075273371959191420517255829,
		71693888707715466499115593487603532921714970056938,
		54370070576826684624621495650076471787294438377604,
		53282654108756828443191190634694037855217779295145,
		36123272525000296071075082563815656710885258350721,
		45876576172410976447339110607218265236877223636045,
		17423706905851860660448207621209813287860733969412,
		81142660418086830619328460811191061556940512689692,
		51934325451728388641918047049293215058642563049483,
		62467221648435076201727918039944693004732956340691,
		15732444386908125794514089057706229429197107928209,
		55037687525678773091862540744969844508330393682126,
		18336384825330154686196124348767681297534375946515,
		80386287592878490201521685554828717201219257766954,
		78182833757993103614740356856449095527097864797581,
		16726320100436897842553539920931837441497806860984,
		48403098129077791799088218795327364475675590848030,
		87086987551392711854517078544161852424320693150332,
		59959406895756536782107074926966537676326235447210,
		69793950679652694742597709739166693763042633987085,
		41052684708299085211399427365734116182760315001271,
		65378607361501080857009149939512557028198746004375,
		35829035317434717326932123578154982629742552737307,
		94953759765105305946966067683156574377167401875275,
		88902802571733229619176668713819931811048770190271,
		25267680276078003013678680992525463401061632866526,
		36270218540497705585629946580636237993140746255962,
		24074486908231174977792365466257246923322810917141,
		91430288197103288597806669760892938638285025333403,
		34413065578016127815921815005561868836468420090470,
		23053081172816430487623791969842487255036638784583,
		11487696932154902810424020138335124462181441773470,
		63783299490636259666498587618221225225512486764533,
		67720186971698544312419572409913959008952310058822,
		95548255300263520781532296796249481641953868218774,
		76085327132285723110424803456124867697064507995236,
		37774242535411291684276865538926205024910326572967,
		23701913275725675285653248258265463092207058596522,
		29798860272258331913126375147341994889534765745501,
		18495701454879288984856827726077713721403798879715,
		38298203783031473527721580348144513491373226651381,
		34829543829199918180278916522431027392251122869539,
		40957953066405232632538044100059654939159879593635,
		29746152185502371307642255121183693803580388584903,
		41698116222072977186158236678424689157993532961922,
		62467957194401269043877107275048102390895523597457,
		23189706772547915061505504953922979530901129967519,
		86188088225875314529584099251203829009407770775672,
		11306739708304724483816533873502340845647058077308,
		82959174767140363198008187129011875491310547126581,
		97623331044818386269515456334926366572897563400500,
		42846280183517070527831839425882145521227251250327,
		55121603546981200581762165212827652751691296897789,
		32238195734329339946437501907836945765883352399886,
		75506164965184775180738168837861091527357929701337,
		62177842752192623401942399639168044983993173312731,
		32924185707147349566916674687634660915035914677504,
		99518671430235219628894890102423325116913619626622,
		73267460800591547471830798392868535206946944540724,
		76841822524674417161514036427982273348055556214818,
		97142617910342598647204516893989422179826088076852,
		87783646182799346313767754307809363333018982642090,
		10848802521674670883215120185883543223812876952786,
		71329612474782464538636993009049310363619763878039,
		62184073572399794223406235393808339651327408011116,
		66627891981488087797941876876144230030984490851411,
		60661826293682836764744779239180335110989069790714,
		85786944089552990653640447425576083659976645795096,
		66024396409905389607120198219976047599490197230297,
		64913982680032973156037120041377903785566085089252,
		16730939319872750275468906903707539413042652315011,
		94809377245048795150954100921645863754710598436791,
		78639167021187492431995700641917969777599028300699,
		15368713711936614952811305876380278410754449733078,
		40789923115535562561142322423255033685442488917353,
		44889911501440648020369068063960672322193204149535,
		41503128880339536053299340368006977710650566631954,
		81234880673210146739058568557934581403627822703280,
		82616570773948327592232845941706525094512325230608,
		22918802058777319719839450180888072429661980811197,
		77158542502016545090413245809786882778948721859617,
		72107838435069186155435662884062257473692284509516,
		20849603980134001723930671666823555245252804609722,
		53503534226472524250874054075591789781264330331690
	]
	num_sum = 0
	for i in nums:
		num_sum += i
	result = str(num_sum)[:10]
	Helpers.pr(result)


def longest_collatz_sequence():
	"""
	The following iterative sequence is defined for the set of positive integers:

	n → n/2 (n is even)
	n → 3n + 1 (n is odd)

	Using the rule above and starting with 13, we generate the following sequence:

	13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
	It can be seen that this sequence (starting at 13 and finishing at 1)
	contains 10 terms. Although it has not been proved yet (Collatz Problem),
	it is thought that all starting numbers finish at 1.

	Which starting number, under one million, produces the longest chain?

	NOTE: Once the chain starts the terms are allowed to go above one million.

	:return:
	"""
	start = time()
	result = 0
	top = 1000000
	longest = 0
	for i in range(1, top):
		chain = 0
		n = i
		while n != 1:
			if n % 2 == 0:
				n = n / 2
			else:
				n = n * 3 + 1
			chain += 1
		if chain > longest:
			longest = chain
			result = i
	end = time()
	print("longest is: " + str(longest))
	Helpers.pr(result)
	print("processing time: " + str(end - start))


def lattice_paths():
	"""
	Starting in the top left corner of a 2×2 grid, and only being able to move
	to the right and down, there are exactly 6 routes to the bottom right
	corner.

	How many such routes are there through a 20×20 grid?

	:return:
	"""
	# 1 * 1 grid has 2 options
	# 2 * 2 grid has 6 options
	# 2 options for first grid, plus 2 * 2 options for second grid = 6
	result = 1
	grid_size = 20
	for i in range(1, grid_size + 1):
		result = result * (grid_size + i) / i
	Helpers.pr(result)


def power_digit_sum():
	"""
	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?

	:return:
	"""
	s = datetime.utcnow()
	result = 0
	n = 2**1000
	for i in str(n):
		result += int(i)
	e = datetime.utcnow()
	print("time: " + str(e - s))
	return Helpers.pr(result)


def number_letter_counts():
	"""
	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.

	:return:
	"""
	def below_one_hundred(n):
		if n < 20:
			return uniques[n]
		return tenths[n / 10] + uniques[n % 10]

	result = 0
	uniques = [
		0,
		len("one"),
		len("two"),
		len("three"),
		len("four"),
		len("five"),
		len("six"),
		len("seven"),
		len("eight"),
		len("nine"),
		len("ten"),
		len("eleven"),
		len("twelve"),
		len("thirteen"),
		len("fourteen"),
		len("fifteen"),
		len("sixteen"),
		len("seventeen"),
		len("eighteen"),
		len("nineteen"),
	]

	tenths = [
		0,
		0,
		len("twenty"),
		len("thirty"),
		len("forty"),
		len("fifty"),
		len("sixty"),
		len("seventy"),
		len("eighty"),
		len("ninety"),
	]

	top = 1000
	hundred = len("hundred")
	thousand = len("thousand")
	for i in range(top + 1):
		if i < 100:
			result += below_one_hundred(i)
			continue
		h = int(math.floor(i / 100) % 10)
		t = int(math.floor(i / 1000))
		s = i % 100
		if i > 999:
			result += below_one_hundred(t) + thousand
		if h != 0:
			result += uniques[h] + hundred
		if s != 0:
			result += below_one_hundred(s) + len("and")
	Helpers.pr(result)


def maximum_path_sum_1():
	"""
	By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

	3
	7 4
	2 4 6
	8 5 9 3

	That is, 3 + 7 + 4 + 9 = 23.

	Find the maximum total from top to bottom of the triangle below:

	75
	95 64
	17 47 82
	18 35 87 10
	20 04 82 47 65
	19 01 23 75 03 34
	88 02 77 73 07 63 67
	99 65 04 28 06 16 70 92
	41 41 26 56 83 40 80 70 33
	41 48 72 33 47 32 37 16 94 29
	53 71 44 65 25 43 91 52 97 51 14
	70 11 33 28 77 73 17 78 39 68 17 57
	91 71 52 38 17 14 91 43 58 50 27 29 48
	63 66 04 68 89 53 67 30 73 16 69 87 40 31
	04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

	NOTE: As there are only 16384 routes, it is possible to solve this problem
	by trying every route. However, Problem 67, is the same challenge with a
	triangle containing one-hundred rows; it cannot be solved by brute force,
	and requires a clever method! ;o)

	:return:
	"""
	triangle = [
		[75],
		[95, 64],
		[17, 47, 82],
		[18, 35, 87, 10],
		[20, 4, 82, 47, 65],
		[19, 1, 23, 75, 3, 34],
		[88, 2, 77, 73, 7, 63, 67],
		[99, 65, 4, 28, 6, 16, 70, 92],
		[41, 41, 26, 56, 83, 40, 80, 70, 33],
		[41, 48, 72, 33, 47, 32, 37, 16, 94, 29],
		[53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14],
		[70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57],
		[91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48],
		[63, 66, 4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31],
		[4, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 4, 23]
	]
	# triangle2 = [
	# 	[3],
	# 	[7, 4],
	# 	[2, 4, 6],
	# 	[8, 5, 9, 3]
	# ]
	for i in range(len(triangle) - 2, -1, -1):
		for j in range(i + 1):
			triangle[i][j] += max(triangle[i+1][j], triangle[i+1][j+1])
	result = triangle[0][0]
	Helpers.pr(result)


def counting_sundays():
	"""
	You are given the following information, but you may prefer to do some
	research for yourself.

	1 Jan 1900 was a Monday.
	Thirty days has September,
	April, June and November.
	All the rest have thirty-one,
	Saving February alone,
	Which has twenty-eight, rain or shine.
	And on leap years, twenty-nine.
	A leap year occurs on any year evenly divisible by 4, but not on a century
	unless it is divisible by 400. How many Sundays fell on the first of the
	month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?

	:return:
	"""
	weekdays = {
		0: "MONDAY",
		1: "TUESDAY",
		2: "WEDNESDAY",
		3: "THURSDAY",
		4: "FRIDAY",
		5: "SATURDAY",
		6: "SUNDAY"
	}
	result = 0
	start = datetime(year=1901, month=1, day=1)
	end = datetime(year=2000, month=12, day=31)
	while start <= end:
		if start.day == 1 and weekdays.get(start.date().weekday()) == weekdays[6]:
			result += 1
		start = start + timedelta(days=1)
	print("weekday is: " + str(start.date().weekday()))
	print("day is: " + str(start.date().day))
	print("day of week is: " + weekdays.get(start.date().weekday()))
	Helpers.pr(result)


if __name__ == '__main__':
	# even_fib_numbers()
	# largest_prime_factor()
	# largest_palindrome_product()
	# smallest_multiple()
	# sum_square_difference()
	# ten_thousand_first_prime()
	# largest_product_in_series()
	# special_pythagorean_triplet()
	# summation_of_primes()
	# largest_product_in_a_grid()
	# highest_divisible_triangular_number()
	# large_sum()
	# longest_collatz_sequence()
	# lattice_paths()
	# power_digit_sum()
	# number_letter_counts()
	# maximum_path_sum_1()
	counting_sundays()