Project Euler. #11. Largest product in a grid

By | 2013/02/28

Project Euler (http://projecteuler.net/) 문제11

In the 20 * 20 grid below, four numbers along a diagonal line have been marked in red.
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?

아래의 20 * 20 사각형에서, 대각선방향의 네 숫자가 빨간색으로 표시되어있다.
이 숫자들의 곱은 26 * 63 * 78 * 14 = 1788696 이다.
20 * 20의 사각형에서 같은 방향으로 (위로, 아래로, 왼쪽으로, 우측으로 또는 대각선으로) 인접한 네 숫자의 곱이 가장 큰 수는?

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


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

def prodOfHorr(h, v):
    horrProd = 1
    for i in range(h, h+4):
        if i>=len(numbers[0]):
            return 0
        horrProd*=int(numbers[v][i])
    return horrProd

def prodOfVert(h, v):
    vertProd = 1
    for i in range(v, v+4):
        if i>=len(numbers):
            return 0
        vertProd*=int(numbers[i][h])
    return vertProd

def prodOfDiag(h, v):
    diagProd = 1
    for i in range(0, 4):
        if h>=len(numbers[0]) or v>=len(numbers):
            return 0
        diagProd*=int(numbers[v][h])
        h+=1
        v+=1
    return diagProd

def prodOfReversedDiag(h, v):
    ReverseDiagProd = 1
    for i in range(0, 4):
        if h<0 or v>=len(numbers):
            return 0
        ReverseDiagProd*=int(numbers[v][h])
        h-=1
        v+=1
    return ReverseDiagProd

given = given.split("\n")
numbers = []
greatestProd = 0

for g in given:
    numbers.append(g.split())

for i in range(0, len(numbers[0])):
    for j in range(0, len(numbers)):
        m = max(prodOfHorr(i, j), prodOfDiag(i, j), prodOfVert(i, j), prodOfReversedDiag(i, j))
        if  m > greatestProd:
            greatestProd = m
print greatestProd

좌측 상단에서 부터 한 숫자를 기준으로 가로, 세로, 대각선 방향으로 4개의 숫자를 가져와서 곱을 구하고 그 중 가장 큰 수를 greatestProd 변수에 저장했다. 이렇게 우측 하단의 마지막 숫자까지 검사하고 나면 greatestProd 변수에 가장 큰 곱이 저장되어 있어야 한다.
그래서 처음에 이 값을 Project Euler 11번 문제 정답에 입력했더니 정답이 아니라고 나왔다. 분명 알고리즘상 답이 틀릴 리가 없는데... 그래서 20 * 20 사각형을 눈으로 훑다가 큰 숫자가 ↙방향으로 줄지어 있는 것을 발견했다. 아뿔사, 나는 ↘방향의 대각선만 처리하고 있었던 것이다. ↙방향의 대각선까지 검사하는 함수를 추가하고나니 제대로 된 결과를 얻고 11번 문제를 해결할 수 있었다.

나름 깔끔하게 짠 것 같은데, 고수들의 코드는 뭔가 다를 것이라는 기대를 갖고 다른 사람들의 코드들을 찾아보았다. 그러다 아~주 간단하게 코드를 찾았다.


#Developed by hkapur97 on Project Euler

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

def problem11():

    a = [[int(y) for y in x.split(' ')] for x in g.strip().split('\n')]
    m1 = max([a[i][j] * a[i+0][j+1] * a[i+0][j+2] * a[i+0][j+3] for i in xrange(20) for j in xrange(17)])
    m2 = max([a[i][j] * a[i+1][j+0] * a[i+2][j+0] * a[i+3][j+0] for i in xrange(17) for j in xrange(20)])
    m3 = max([a[i][j] * a[i+1][j+1] * a[i+2][j+2] * a[i+3][j+3] for i in xrange(17) for j in xrange(17)])
    m4 = max([a[i][j] * a[i+1][j-1] * a[i+2][j-2] * a[i+3][j-3] for i in xrange(17) for j in xrange(20)])
    return max(m1, m2, m3, m4)

리스트 내장으로 가로방향의 네 숫자의 곱 중 가장 큰 수, 세로방향의 네 숫자의 곱 중 가장 큰 수, 양 대각선 방향으로 네 숫자의 곱 중 가장 큰 수를 찾아내고, 이 네 숫자 중에서 가장 큰 수를 마지막으로 리턴하는 함수다.

10개의 문제를 풀고 나서 11번제 문제로 들어오니, 지금까지와는 다른 방식의 독특한 문제가 나온 것 같다. 딱히 난이도가 있다기보다는 문제 제시 방법이 특이한 문제였는데, 이제 이런 문제 스타일에서 난이도가 올라가면 리스트 내장을 적극 활용해서 문제를 잘 풀어봐야겠다.