Problem 11

In the 20×20 grid below, four numbers along a diagonal line have been marked in red.

        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

The product of these numbers is 26 × 63 × 78 × 14 = 1788696.

What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20×20 grid?

Solution 1:

#I used formatter so that I can use 1 function for all up or right and diagonal

s = '''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'''



#This will return list of list formatted
#cod 0 in right or
#cod 1 down or
#cod 2 and cod 3 right diagonal and left diagonal
#Only this function is bulky and unorganized

def formatter(s, cod):
    li = s.split("\n")
    lis = []
    
    for i in range(len(li)):
        lis.insert(len(lis), list(map(int, li[i].split())))
        
    lis1 = lis[:]
    if cod:
        lis2 = []
        for i in range(len(lis)):
            temp = []
            for j in range(len(lis)):
                temp += [lis[j][i]]
            lis2.insert(len(lis2), temp)
        lis = lis2        
        if cod == 2: 
            liss2 = []
            lis1.reverse()
            lis.reverse()
            for i in range(len(lis)):
                temp = []
                temp2 = []
                for j in range((i + 1)):
                    temp += [lis[j][i-j]]
                    temp2 += [lis1[j][i-j]]
                liss2.insert(len(liss2), temp)
                liss2.insert(len(liss2), temp2)
            lis = liss2
        elif cod == 3:
            lis1.reverse()
            for i in range(len(lis1)):
                lis1[i].reverse()
            liss2 = []
            for i in range(len(lis)):
                temp = []
                temp2 = []
                for j in range((i + 1)):
                    temp += [lis[j][i-j]]
                    temp2 += [lis1[j][i-j]]
                liss2.insert(len(liss2), temp)
                liss2.insert(len(liss2), temp2)
            lis = liss2

    #print("[+] Out of formatter func\n[+] Returning formatted list of len")
    #print(lis)
    return lis

def prod(li):
    li = list(map(int, li))
    return reduce(mul, li, 1)

def max_adj(s, k, i):
    li = formatter(s, i)
    ma = 0
    trace = 0
    l1 = len(li)
    for i in range(l1):
        li2 = li[i]
        l2 = len(li2)
        
        #if li contains list
        for j in range(l2 - k + 1): 
            if ma < prod(li2[j:j+k]):
                ma = prod(li2[j:j+k])
                trace = li2[j:j+k]
                
    #print("[+] Out of max_adj() func\n[+] Returning max product of "
          #+ str(k) + " adj\n[+]found at " + str(trace)
          #+ "\n" + str(ma))
    return ma


        
cod = [0,1,2,3]
ma = []
for i in cod:
    ma += [max_adj(s, 4, i)]
print("The answer is " + str(max(ma)))

This python code run :~ 0.010417938232421875
The output: 70600674