p149.py 1.73 KB
 Nayuki Minase committed Feb 22, 2016 1 2 ``````# # Solution to Project Euler problem 149 `````` Nayuki committed Dec 27, 2016 3 ``````# Copyright (c) Project Nayuki. All rights reserved. `````` Nayuki Minase committed Feb 22, 2016 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)] `````` Nayuki Minase committed Feb 24, 2016 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. `````` Nayuki Minase committed Feb 22, 2016 27 `````` def get_max_substring_sum(x, y, dx, dy): `````` Nayuki Minase committed Feb 24, 2016 28 29 `````` result = 0 current = 0 `````` Nayuki Minase committed Feb 22, 2016 30 `````` while 0 <= x < SIZE and 0 <= y < SIZE: `````` Nayuki Minase committed Feb 24, 2016 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 `````` Nayuki Minase committed Feb 22, 2016 33 34 35 36 `````` x += dx y += dy return result `````` Nayuki Minase committed Feb 24, 2016 37 `````` # Scan along all line directions and positions `````` Nayuki Minase committed Feb 27, 2016 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) `````` Nayuki Minase committed Feb 22, 2016 47 48 49 50 `````` if __name__ == "__main__": print(compute())``````