프로젝트 오일러 011

문제 자체는 사뭇 간단해 보이지만, 실제로 숫자들을 곱하는 방향을 생각하면 그렇지 않을 수도 있습니다. 이 문제를 해결하는 여러 가지 방법이 있겠지만, 직관적으로는 특정한 지점에서 시작해서 왼쪽, 오른쪽, 그리고 우하단, 좌하단 방향으로 4개씩 숫자를 골라서 곱하는 것을 생각할 수 있습니다. 이 때에는 고른 숫자가 격자에서 어디에 위치해있나를 보고 계산할 수 없는 방향은 제외해야겠죠.

다른 방법으로는 격자 내에서 시작점을 골라 4x4 격자를 하나 구한 다음, 이 격자에서 곱할 수 있는 10개 조의 숫자들의 곱을 나열하고, 이렇게 곱해진 값들 중에서 최대값을 고르는 방법도 있겠습니다.

제가 주요하게 생각하는 점은, ‘격자’를 어떤 형태로 표현할 것인가 하는 것입니다. 어쩌면 대부분의 사람들은 각 행을 리스트로 보고, 행들의 리스트로 각자를 생각할지도 모르겠습니다. 그런데, 그게 정말 최선일까요?

1차원 리스트로 격자 표현하기

Julia나 R처럼 리스트(배열)의 인덱스가 1로 시작하는 언어도 있지만, 다른 대부분의 언어에서 인덱스는 0부터 시작합니다. 이러한 특성을 가진 언어에서는 폭이 일정한 격자라면 격자 자체를 1차원 배열로 생각해도 됩니다. 오히려 2차원 배열로 접근하는 것보다 더 간단할 수 있습니다.

0부터 99까지 100개의 정수를 10 × 10 격자에 배치하되, 이것이 단일 리스트라고 생각해봅시다. 같은 열에서의 인덱스 값은 10씩 (격자의 폭만큼) 차이가 납니다. 그리고 좌우로 움직이는 경우에는 인덱스 값이 1씩 차이가 납니다. 그러면 R행, C열에 있는 요소의 인덱스는, i = R * w + C로 표현할 수 있습니다. 반대로 i 번째 요소는 (i ÷ W, i % W)의 좌표로 환산할 수 있습니다. 대각선의 경우에도, 오른쪽 아래로 나아가는 방향에선 (w + 1) 만큼, 왼쪽 아래로 나아가는 방향으로는 (w - 1)만큼의 차이로 요소를 구하면 쉽게 얻을 수 있습니다. 이건 슬라이스 문법이나, 지능형리스트를 사용하여 부분열을 얻을 때 매우 유리한 방법입니다.

자 그러면 (R, C)에 있는 값으로부터 네 방향으로 4개 숫자의 곱을 얻는 방법을 생각해봅시다.

• C < 17 이라면 오른쪽으로 네 개의 수를 곱할 수 있습니다.
• R < 17 이라면 아래쪽으로 네 개의 수를 곱할 수 있습니다.
• C < 17 and R < 17 이라면 오른쪽 아래 대각선의 네 개 수를 곱할 수 있습니다.
• C > 2 and R < 17 이라면 왼쪽 아래 대각선의 네 개의 수를 곱할 수 있습니다.

이 원리를 이용해서 격자 내 i 번째 위치에서 가로, 세로, 우하방, 좌하방으로 4개의 숫자의 곱 중 최대값을 구하는 함수를 작성합니다. 이를 0 ~ 399 범위에 대해서 반복하고 다시 그 중의 최대값을 구하면 됩니다.

• 리스트의 숫자를 모두 곱하기 위해서는 prod 함수를 하나 작성합니다. reduce()를 사용하면 합계나 누적곱을 구할 때 편하겠죠.
• 슬라이스 문법을 적극적으로 사용합니다.

from functools import reduce

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

prod = lambda ys: reduce(lambda x, y: x * y, ys)

xs = [int(x) for x in s.strip().split()]


def process(i):
    r, c = divmod(i, 20)
    # 네 방향으로의 숫자의 곱을 0으로 초기화함
    a, b, c, d = 0, 0, 0, 0
    if c < 17:
        a = prod(xs[i:i+3])
        if r < 17:
            c = prod(xs[i:i+21*4:21])
            if c > 2:
                d = prod(xs[i:i+19*4:19])
    if r < 17:
        b = prod(xs[i:i+20*4:20])
    return max(a, b, c, d)


print(max([process(i) for i in range(400)]))

행렬 사용하기

Julia와 같은 언어에서는 격자를 배열로 다루기가 되려 복잡하다고 했습니다. 그렇지만 Julia는 행렬을 바로 다룰 수 있습니다. 즉 (R, C) 위치에서 xs[R:R+4, C:C+4]로 부분 행렬을 얻을 수 있습니다. 대각선은 선형 대수학에서 자주 사용되는 라이브러리인 LinearAlgebra를 통해 diag(), rotl90() 과 같은 함수를 사용해서 얻습니다. 참고로 Julia는 prod()함수는 기본 라이브러리에서 지원합니다.

using LinearAlgebra

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

xs = parse.(Int, split(s)) |> x -> reshape(x, 20, 20)'

process(ws) = begin
    a = prod(ws[1, :])
    b = prod(ws[:, 1])
    c = diag(ws) |> prod
    d = (prod ∘ diag ∘ rotl90)(ws)
    max(a, b, c, d)
end

let res = 0
    for i in 1:17
        for j in 1:17
            temp = process(xs[i:i+3, j:j+3])
            if res < temp; res = temp; end
        end
    end
    println(res)
end