p149.py 1.73 KB
Newer Older
1 2
# 
# Solution to Project Euler problem 149
3
# Copyright (c) Project Nayuki. All rights reserved.
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
# 
# https://www.nayuki.io/page/project-euler-solutions
# https://github.com/nayuki/Project-Euler-solutions
# 


def compute():
	SIZE = 2000
	
	# Generate the pseudorandom sequence according to the lagged Fibonacci generator
	randseq = []
	for i in range(SIZE**2):
		k = i + 1
		if k <= 55:
			randseq.append((100003 - 200003*k + 300007*k*k*k) % 1000000 - 500000)
		else:
			randseq.append((randseq[-24] + randseq[-55]) % 1000000 - 500000)
	
	# Reshape the sequence into into a 2D array
	grid = [randseq[i * SIZE : (i + 1) * SIZE] for i in range(SIZE)]
	
25 26
	# For the sequence of numbers in the grid at positions (x, y), (x+dx, y+dy), (x+2*dx, y+2*dy), ... until the
	# last in-bounds indices, this function returns the maximum sum among all possible substrings of this sequence.
27
	def get_max_substring_sum(x, y, dx, dy):
28 29
		result = 0
		current = 0
30
		while 0 <= x < SIZE and 0 <= y < SIZE:
31 32
			current = max(current + grid[y][x], 0)  # Reset the running sum if it goes negative
			result = max(current, result)  # Keep track of the best seen running sum
33 34 35 36
			x += dx
			y += dy
		return result
	
37
	# Scan along all line directions and positions
38 39 40 41 42 43 44 45 46
	ans = max(
		max(get_max_substring_sum(0, i, +1,  0),  # Horizontal from left edge
		    get_max_substring_sum(i, 0,  0, +1),  # Vertical from top edge
		    get_max_substring_sum(0, i, +1, +1),  # Diagonal from left edge
		    get_max_substring_sum(i, 0, +1, +1),  # Diagonal from top edge
		    get_max_substring_sum(i, 0, -1, +1),  # Anti-diagonal from top edge
		    get_max_substring_sum(SIZE - 1, i, -1, +1))  # Anti-diagonal from right edge
		for i in range(SIZE))
	return str(ans)
47 48 49 50


if __name__ == "__main__":
	print(compute())