[Python][Julia]Project euler11 (プロジェクトオイラー11)

Project euler Ploblem 11 (プロジェクトオイラー11)

Largest Product in a Grid

備忘のために残しておく。

問題

問題文 (意訳)

以下20×20のグリッドがある。
4つの数が斜めの線にそって赤色となっている。(グリッドは省略)
これら4つの数の積は26 × 63 × 78 × 14 = 1788696.
縦・横・右斜め・左斜めで4つの数の最も大きい積を求めよ。

原文

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?

解答

答え

70600674

解答の方針

各行ごとにリストへ入れていき、
縦・横・右下斜め ↘ ・左下斜め↙ごとに４つの数字の積を求め、最大のものを比較して求める。

Pythonのコード

Python Ploblem11

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


lst1 = str.splitlines()

lst = []
for i in lst1:
    l = i.split(' ')
    l = [int(x) for x in l]
    lst.append(l)


def seek_ans(grid: int,adjacent_num: int,list: list) -> int:
    max_num = 1
    # 横方向
    for r in range(grid):
        for c in range(grid - adjacent_num + 1):
            num = 1
            for i in range(adjacent_num):
                num *= lst[r][c+i]
                if max_num < num:
                    max_num = num
    # 縦方向
    for c in range(grid):
        for r in range(grid - adjacent_num + 1):
            num = 1
            for i in range(adjacent_num):
                num *= lst[r+i][c]
                if max_num < num:
                    max_num = num
    
    # 右下↘️方向
    for r in range(grid - adjacent_num + 1):
        for c in range(grid - adjacent_num + 1):
            num = 1
            for i in range(adjacent_num):
                num *= lst[r+i][c+i]
                if max_num < num:
                    max_num = num
    
    # 左下↙️方向
    for r in range(grid - adjacent_num + 1):
        for c in range(grid - 1,adjacent_num - 2,-1):
            num = 1
            for i in range(adjacent_num):
                num *= lst[r+i][c-i]
                if max_num < num:
                    max_num = num
    return max_num


print(seek_ans(grid = 20, adjacent_num = 4,list = lst))

Juliaのコード

Julia Ploblem11

str = """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"""


lst1 = split(str, "\n")
lst = []
for i in lst1
    l = split(i, ' ')
    l = [parse(Int, x) for x in l]
    push!(lst, l)
end

function seek_ans(grid::Int, adjacent_num::Int, lst)::Int
    max_num = 1
    # 横方向    
    for r in 1:grid
        for c in 1:(grid - adjacent_num + 1)
            num = 1
            for i in 1:adjacent_num
                num *= lst[r][c+i-1]
                if max_num < num
                    max_num = num
                end
            end
        end
    end
    # 縦方向    
    for c in 1:grid
        for r in 1:(grid - adjacent_num + 1)
            num = 1
            for i in 1:adjacent_num
                num *= lst[r+i-1][c]
                if max_num < num
                    max_num = num
                end
            end
        end
    end
    # 右下↘️方向    
    for r in 1:(grid - adjacent_num + 1)
        for c in 1:(grid - adjacent_num + 1)
            num = 1
            for i in 1:adjacent_num
                num *= lst[r+i-1][c+i-1]
                if max_num < num
                    max_num = num
                end
            end
        end
    end
    # 左下↙️方向
    for r in 1:(grid - adjacent_num + 1)
        for c in (grid - 1):-1:(adjacent_num)
            num = 1
            for i in 1:adjacent_num
                num *= lst[r+i-1][c-i+1]
                if max_num < num
                    max_num = num
                end
            end
        end
    end
    
    return max_num
end

println(seek_ans(20, 4, lst))