파이썬_실전 프로젝트

프로젝트 오일러 11번문제 - 연속한 4개의 숫자의 곱

400개의 배열에서, 가로,세로,대각선 방향으로 연속해서 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?

 

1. 데이터를 배열또는 2차원 리스트로 읽어와서, (파일 읽어오기 참조)

2. 루프문을 돌면서, 가로,세로,대각선(↘),대각선 (↙) 을 각각 체크해야겠네요.

 

데이터 불러오기
filename = 'q011_data.txt'
with open(filename) as file_object:
    lines = file_object.readlines()

한줄의 data가 하나의 긴 문자열로 되어있습니다. 낱개로 분리하는게 계산하는데 더 편할거 같네요.

 

from urllib.request import urlretrieve
urlretrieve("https://raw.githubusercontent.com/nomadlife/project-euler/master/q011_data.txt", "q011_data.txt")

url에서 불러오려면, 코드 맨앞에 위의 코드 2줄을 추가해주면 됩니다. url주소와 파일이름을 정해주어야 합니다.

 

리스트로 할당하기
numbers=[]
for line in lines:
    numbers.append(line.split())

split을 해서 numbers라는 2차원 리스트로 할당했습니다. numbers[i][j] 형식으로 각 숫자를 불러서 쓸수 있습니다.

 

가로방향 숫자 4개
from functools import reduce

prodH = reduce(lambda x, y: x+y, numbers[0][0:4])
print("prodH:",prodH)
prodH: 08022297

리스트도 문자열의 slice 처럼 범위를 지정해서 뽑아서 쓸수있습니다. 5번문제에서 사용한 reduce를 활용해서, 가로숫자 4개 08, 02, 22, 97 이 문자열로 합해져서 08022297 로 출력이 되었습니다. 합산이나 곱셈을 하려면, x+y 를 int(x)+int(y) 나 int(x)*int(y) 로 바꾸어 주면 됩니다.

이제 이걸 반복문으로 만들어주면 되겠죠.

from functools import reduce

for i in range(17):
    for j in range(17):
        prodH = reduce(lambda x, y: x+y, numbers[i][j:j+4])
        print("prodH:",prodH)
prodH: 08022297
prodH: 02229738
prodH: 22973815
prodH: 97381500
prodH: 38150040
prodH: 15004000
prodH: 00400075
prodH: 40007504
prodH: 00750405
prodH: 75040507
prodH: 04050778
prodH: 05077852
...
..

전체 list에 대해서 가로 4개의 숫자가 출력되는걸 볼수있습니다.

 

세로방향

세로방향은 연속된 자료가 아니라서, 약간의 응용이 필요합니다. reduce의 범위부분에 1번문제에서 사용했던 list의 축약된 형태의 반복문을 넣어줘야 합니다.

prodV = reduce(lambda x, y: x+y, [numbers[0+k][0] for k in range(0,4)])
print("prodV:",prodV)
prodV: 08498152

08,49,81,52 의 세로방향 4개의 숫자가 출력되었습니다. 이것도 마찬가지로 가로방향과 함께 반복문에 넣어주고, numbers[0+k][0] 부분을 numbers[i+k][j] 로 바꿔주도록 하겠습니다.

from functools import reduce

for i in range(17):
    for j in range(17):
        prodH = reduce(lambda x, y: x+y, numbers[i][j:j+4])
        prodV = reduce(lambda x, y: x+y, [numbers[i+k][j] for k in range(0,4)])
        print("prodH:",prodH)
        print("prodV:",prodV)
prodH: 08022297
prodV: 08498152
prodH: 02229738
prodV: 02494970
prodH: 22973815
prodV: 22993195
prodH: 97381500
prodV: 97407323
...

 

대각선 방향
from functools import reduce

for i in range(17):
    for j in range(17):
        prodH = reduce(lambda x, y: x+y, numbers[i][j:j+4])
        prodV = reduce(lambda x, y: x+y, [numbers[i+k][j] for k in range(0,4)])
        prodD1 = reduce(lambda x, y: x+y, [numbers[i+k][j+k] for k in range(0,4)])
        prodD2 = reduce(lambda x, y: x+y, [numbers[i+k][j+3-k] for k in range(0,4)])
        print("prodH:",prodH)
        print("prodV:",prodV)
        print("prodD1:",prodD1)
        print("prodD2:",prodD2)

대각선은 / 방향과 ↘(역슬래시)방향 두가지가 있습니다. 세로방향의 식을 약간 변형해서 리스트를 출력해주면 되겠습니다.

 

리스트로 출력
from functools import reduce

for i in range(17):
    for j in range(17):
        prod=[]
        prod.append(reduce(lambda x, y: x+y, numbers[i][j:j+4]))
        prod.append(reduce(lambda x, y: x+y, [numbers[i+k][j] for k in range(0,4)]))
        prod.append(reduce(lambda x, y: x+y, [numbers[i+k][j+k] for k in range(0,4)]))
        prod.append(reduce(lambda x, y: x+y, [numbers[i+k][j+3-k] for k in range(0,4)]))
        print("prod:",prod)
prod: ['08022297', '08498152', '08493123', '97994952']
prod: ['02229738', '02494970', '02997304', '38403170']
prod: ['22973815', '22993195', '22405560', '15177395']

하나의 리스트 prod로 출력해줍니다.  list.append()는 list끝에 값을 하나씩 추가하라는 명령입니다.

 

계산
from functools import reduce

for i in range(17):
    for j in range(17):
        prod=[]
        prod.append(reduce(lambda x, y: int(x)*int(y), numbers[i][j:j+4]))
        prod.append(reduce(lambda x, y: int(x)*int(y), [numbers[i+k][j] for k in range(0,4)]))
        prod.append(reduce(lambda x, y: int(x)*int(y), [numbers[i+k][j+k] for k in range(0,4)]))
        prod.append(reduce(lambda x, y: int(x)*int(y), [numbers[i+k][j+3-k] for k in range(0,4)]))
        print("prod:",prod)

문자를 int(x)로 숫자로 바꿔서 계산.

 

최대값 판별
from functools import reduce

maxValue=0
for i in range(17):
    for j in range(17):
        prod=[]
        prod.append(reduce(lambda x, y: int(x)*int(y), numbers[i][j:j+4]))
        prod.append(reduce(lambda x, y: int(x)*int(y), [numbers[i+k][j] for k in range(0,4)]))
        prod.append(reduce(lambda x, y: int(x)*int(y), [numbers[i+k][j+k] for k in range(0,4)]))
        prod.append(reduce(lambda x, y: int(x)*int(y), [numbers[i+k][j+3-k] for k in range(0,4)]))
        if max(prod) > maxValue:
            maxValue = max(prod)
print(maxValue)
70600674

 최대값을 저장할 변수를 만들고, 매 루프마다 최대값인지 확인하는 조건문을 추가해줍니다.

댓글

댓글 본문
작성자
비밀번호
버전 관리
nomadlife
현재 버전
선택 버전
graphittie 자세히 보기