-1

In order to solve problem 11, I have sought to implement 4 loops. Each of the 4 loops iterates in a different direction, so for example the first loop (which I will use to demonstrate my issue below) starts vertically from the top left of the grid. The logic of the loop is to go through the top row and then move down a row and follow the same multiplication pattern. After 16 iterations there are no more combinations of numbers and so the loop stops.

In order to test whether or not the function works, I want to print a list of all the iterations to ensure that it prints 360 unique numbers. The idea being that I can then alter the code to start with figure = 0, and with each iteration I can check to see if the number produced is bigger than the current value for figure. If it is, then figure is replaced with the value of that iteration.

My issue is that the output of my code is the same list of 20 numbers 16 times. Any help with this one would be highly appreciated! I know that there are many ways of doing this, and that I can look up the answers, but I want to get my own logic/solution working before I look at any answers, and this is the main blocker at the moment.

#code starts here

twenmat = [20*20 matrix]
newlist = []
figure = 0

for items in twenmat:
    for x in range(0,20):
        y = 0
        newlist.append(twenmat[0+y][x]*twenmat[1+y][x]*twenmat[2+y][x]*twenmat[3+y][x])
        y = y + 1
        if y == 16:
            break
print(newlist)

#end of script
Bill Lynch
  • 80,138
  • 16
  • 128
  • 173
JoshZ
  • 3
  • 2
  • Show a [example]. How are you creating `twenmat`? – user202729 Jan 09 '21 at 12:05
  • 1
    But it's probably https://stackoverflow.com/a/44382900/5267751 . – user202729 Jan 09 '21 at 12:06
  • give example numerical example for `twenmat = [20*20 matrix]`, so it will be easy to investigate your code. – Nour-Allah Hussein Jan 09 '21 at 12:09
  • so twenmat is structured as a list of 20 lists. the full one is too long, so i have included here the first 6: twenmat = [[8,2,22,97,38,15,0,40,0,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,0],[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]] – JoshZ Jan 09 '21 at 13:06
  • can be found in full here: https://projecteuler.net/problem=11 – JoshZ Jan 09 '21 at 13:08

1 Answers1

0

Rather than manipulating individual coordinates, you could just shift the matrix by 1, 2 and 3 in each direction and perform cell by cell of multiplications between shifted matrices. Record the maximum of these products as you go through the 4 directions (right, down, down-right, up-right):

data =\
"""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"""

M = [ [*map(int,line.split())] for line in data.split("\n") ]

...

# shift the matrix by a positive or negative amount vertically and horizontally
# empty positions are filled with 1 so that the products aren't impacted
def shift(m,v,h):    
    if v<0 : m = [[1]*len(m)]*-v + m[:v]
    else   : m = m[v:] + [[1]*len(m)]*v
    if h<0 : m = [ [1]*-h + r[:h] for r in m ]
    else   : m = [ r[h:] + [1]*h  for r in m ]
    return m

# base matrix multiplied cell by cell with 3 shifted versions ...
maxProd = 0
for dv,dh in [(0,1),(1,0),(1,1),(-1,1)]:
    m = M  # start with non-shifted values
    for i in range(1,4):

        # multiply by each shifted copies cell by cell
        m = [ [a*b for a,b in zip(r0,r1)] 
              for r0,r1 in zip(m,shift(M,dv*i,dh*i)) ]

    # record maximum of all resulting products
    maxProd = max(maxProd,max((max(row) for row in m)))
    
print(maxProd) # 70600674

To illustrate this shifting process, let's look at the 3 shifted versions going down-right on the main diagonal (offset: 1,1):

shifted by 1:

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

shifted by 2:

31 73 55 79 14 29 93 71 40 67 53 88 30  3 49 13 36 65  1  1
95 23  4 60 11 42 69 24 68 56  1 32 56 71 37  2 36 91  1  1
16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80  1  1
32 60 99  3 45  2 44 75 33 53 78 36 84 20 35 17 12 50  1  1
81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70  1  1
20 68  2 62 12 20 95 63 94 39 63  8 40 91 66 49 94 21  1  1
58  5 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72  1  1
23  9 75  0 76 44 20 45 35 14  0 61 33 97 34 31 33 95  1  1
53 28 22 75 31 67 15 94  3 80  4 62 16 14  9 53 56 92  1  1
 5 42 96 35 31 47 55 58 88 24  0 17 54 24 36 29 85 57  1  1
 0 48 35 71 89  7  5 44 44 37 44 60 21 58 51 54 17 58  1  1
81 68  5 94 47 69 28 73 92 13 86 52 17 77  4 89 55 40  1  1
 8 83 97 35 99 16  7 97 57 32 16 26 26 79 33 27 98 66  1  1
68 87 57 62 20 72  3 46 33 67 46 55 12 32 63 93 53 69  1  1
16 73 38 25 39 11 24 94 72 18  8 46 29 32 40 62 76 36  1  1
36 41 72 30 23 88 34 62 99 69 82 67 59 85 74  4 36 16  1  1
35 29 78 31 90  1 74 31 49 71 48 86 81 16 23 57  5 54  1  1
54 71 83 51 54 69 16 92 33 48 61 43 52  1 89 19 67 48  1  1
 1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1
 1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1

shifter by 3:

23  4 60 11 42 69 24 68 56  1 32 56 71 37  2 36 91  1  1  1
71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80  1  1  1
60 99  3 45  2 44 75 33 53 78 36 84 20 35 17 12 50  1  1  1
28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70  1  1  1
68  2 62 12 20 95 63 94 39 63  8 40 91 66 49 94 21  1  1  1
 5 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72  1  1  1
 9 75  0 76 44 20 45 35 14  0 61 33 97 34 31 33 95  1  1  1
28 22 75 31 67 15 94  3 80  4 62 16 14  9 53 56 92  1  1  1
42 96 35 31 47 55 58 88 24  0 17 54 24 36 29 85 57  1  1  1
48 35 71 89  7  5 44 44 37 44 60 21 58 51 54 17 58  1  1  1
68  5 94 47 69 28 73 92 13 86 52 17 77  4 89 55 40  1  1  1
83 97 35 99 16  7 97 57 32 16 26 26 79 33 27 98 66  1  1  1
87 57 62 20 72  3 46 33 67 46 55 12 32 63 93 53 69  1  1  1
73 38 25 39 11 24 94 72 18  8 46 29 32 40 62 76 36  1  1  1
41 72 30 23 88 34 62 99 69 82 67 59 85 74  4 36 16  1  1  1
29 78 31 90  1 74 31 49 71 48 86 81 16 23 57  5 54  1  1  1
71 83 51 54 69 16 92 33 48 61 43 52  1 89 19 67 48  1  1  1
 1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1
 1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1
 1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1

Each number is moved to the next position diagonally so the product of cells at a given position corresponds to the 4 values going down-right on the main diagonal.

We do this for all directions to get the maximum product.

Alain T.
  • 40,517
  • 4
  • 31
  • 51