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)
The Python file is available for download here.
