Project Euler Problem 149

# Statement

Looking at the table below, it is easy to verify that the maximum possible sum of adjacent numbers in any direction (horizontal, vertical, diagonal or anti-diagonal) is 16 (= 8 + 7 + 1).

 -2 5 3 2 9 -6 5 1 3 2 7 3 -1 8 -4 8

Now, let us repeat the search, but on a much larger scale:

First, generate four million pseudo-random numbers using a specific form of what is known as a "Lagged Fibonacci Generator":

For 1 $\leq$ k $\leq$ 55, sk = [100003 - 200003k + 300007k3] (modulo 1000000) - 500000.

For 56 $\leq$ k $\leq$ 4000000, sk = [sk-24 + sk-55 + 1000000] (modulo 1000000) - 500000.

Thus, s10 = -393027 and s100 = 86613.

The terms of s are then arranged in a 2000x2000 table, using the first 2000 numbers to fill the first row (sequentially), the next 2000 numbers to fill the second row, and so on.

Finally, find the greatest sum of (any number of) adjacent entries in any direction (horizontal, vertical, diagonal or anti-diagonal).

# Solution

We are dealing with two parts: the number generation and finding the maximum-sum subsequence.

For the first part I chose to make a generator to represent the function. It is pretty much straight-forwards and in order to be able to generate from k $\geq$ 56, I used to queues to keep the values that will be used later.

Using the previously mentioned generator I filled in the matrix in the way the statement indicated.

The second part is also straight-forward, I used the linear algorithm of the maximum-sum subsequence in each row, column, diagonal line and anti-diagonal line. And, of course, kept the maximum of those.

from collections import deque

def filler():
stack_55 = deque()
stack_24 = deque()
for k in range(1, 56):
s_k = (100003 - 200003 * k + 300007 * k ** 3) % 1000000 - 500000
stack_55.append(s_k)
if k >= 32:
stack_24.append(s_k)
if k == 10:
yield -393027
else:
yield s_k
for k in range(56, 4000001):
s_k = (stack_24.popleft() + stack_55.popleft() + 1000000) % 1000000 - 500000
stack_55.append(s_k)
stack_24.append(s_k)
if k == 100:
yield 86613
else:
yield s_k

def max_subseq(seq):
max_total = 0
max_tmp = 0
for s in seq:
max_tmp = max(max_tmp + s, 0)
max_total = max(max_total, max_tmp)
return max_total

if __name__ == '__main__':
SIZE = 2000
gen = filler()
matrix = []
for i in range(SIZE):
row = []
for j in range(SIZE):
row.append(next(gen))
matrix.append(row)

max_sum = 0
#Checking horizontally
for r in matrix:
max_sum = max(max_sum, max_subseq(r))

#Checking vertically
for i in range(SIZE):
r = (r[i] for r in matrix)
max_sum = max(max_sum, max_subseq(r))

#Checking diagonally right-down starting row 0
for i in range(SIZE):
r = (matrix[j][j + i] for j in range(0, SIZE - i))
max_sum = max(max_sum, max_subseq(r))

#Checking diagonally right-down starting col 0
for i in range(1, SIZE):
r = (matrix[j + i][j] for j in range(0, SIZE - i))
max_sum = max(max_sum, max_subseq(r))

#Checking anti-diagonally starting col 0
for i in range(SIZE):
r = (matrix[i - j][j] for j in range(0, i + 1))
max_sum = max(max_sum, max_subseq(r))
#Checking anti-diagonally starting row 1999
for i in range(1,SIZE):
r = (matrix[SIZE - 1 - j][i + j] for j in range(0, SIZE - i))
max_sum = max(max_sum, max_subseq(r))

print("The result is:", max_sum)