파이썬_실전 프로젝트

프로젝트 오일러 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. 루프문을 돌면서, 가로,세로,대각선(↘),대각선 (↙) 을 따로 체크해야겠네요.

 

Code

데이터 불러오기
#웹상에서 파일을 다운받을때
from urllib.request import urlretrieve
urlretrieve("https://raw.githubusercontent.com/nomadlife/project-euler/master/q011_data.txt", "q011_data.txt")

#파일불러오기
filename = 'q011_data.txt'
with open(filename) as file_object:
    lines = file_object.readlines()
m=len(lines)

#리스트로 할당하기 
numbers=[]
for line in lines:
    print(line.split())
    numbers.append(line.split())
print(numbers)
max_product=0
print("max_product is ",max_product)
['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']
[['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']]
max_product is  0

화면이 좁아서 좀 어지러워 보이는데, 불러온 리스트 내용을 출력한겁니다.

 

리스트 호출하기
max_product=0

#리스트 호출하기
for i in range(20):
    for j in range(20):
        print(i,j,numbers[i][j])
        
print("max_product is ",max_product)

 

가로 숫자 4개의 곱

max_product=0
for i in range(20):
    for j in range(20):
        
        #가로숫자 4개 곱
        if j+4 < 20:
            product =1
            print(i,j,end=':')
            for k in range(0,4):
                print(numbers[i][j+k],end='*')
                product *= int(numbers[i][j+k])
            print("=",product,end=' ')
            if product >max_product:
                max_product = product
                print("max_product :",max_product)
            print()

print("max_product is ",max_product)

 

세로숫자 4개의 곱
max_product=0
for i in range(20):
    for j in range(20):
        
        #가로숫자 4개 곱
        if j+4 < 20:
            product =1
            for k in range(0,4):
                product *= int(numbers[i][j+k])
            if product >max_product:
                max_product = product
                print("max_product :",max_product)
        
        #세로숫자 4개 곱
        if i+4 < 20:
            product =1
            print(i,j,end=':')
            for k in range(0,4):
                print(numbers[i+k][j],end='*')
                product *= int(numbers[i+k][j])
            print("=",product,end=' ')
            if product >max_product:
                max_product = product
                print("max_product :",max_product)
            print()        

print("max_product is ",max_product)

 

대각선(↘) 숫자 4개 곱
max_product=0
for i in range(20):
    for j in range(20):

        #가로숫자 4개 곱
        if j+4 < 20:
            product =1
            for k in range(0,4):
                product *= int(numbers[i][j+k])
            if product >max_product:
                max_product = product
                print("max_product :",max_product)

        #세로숫자 4개 곱
        if i+4 < 20:
            product =1
            for k in range(0,4):
                product *= int(numbers[i+k][j])
            if product >max_product:
                max_product = product
                print("max_product :",max_product)

        #대각선(↘)숫자 4개 곱
        if i+4 < 20 and j+4 < 20:
            product =1
            print(i,j,end=':')
            for k in range(0,4):
                print(numbers[i+k][j+k],end='*')
                product *= int(numbers[i+k][j+k])
            print("=",product,end=' ')
            if product >max_product:
                max_product = product
                print("max_product :",max_product)
            print()
            
print("max_product is ",max_product)

 

대각선(↙) 숫자 4개 곱
max_product=0
for i in range(20):
    for j in range(20):
        
        #가로숫자 4개 곱
        if j+4 < 20:
            product =1
            for k in range(0,4):
                product *= int(numbers[i][j+k])
            if product >max_product:
                max_product = product
                print("max_product :",max_product)

        #세로숫자 4개 곱
        if i+4 < 20:
            product =1
            for k in range(0,4):
                product *= int(numbers[i+k][j])
            if product >max_product:
                max_product = product
                print("max_product :",max_product)
        
        #대각선(↘)숫자 4개 곱
        if i+4 < 20 and j+4 < 20:
            product =1
            for k in range(0,4):
                product *= int(numbers[i+k][j+k])
            if product >max_product:
                max_product = product
                print("max_product :",max_product)

        #대각선(↙)숫자 4개 곱
        if i+4 < 20 and j+4 < 20 and j >= 3:
            product =1
            print(i,j,end=':')
            for k in range(0,4):
                print(numbers[i+k][j-k],end='*')
                product *= int(numbers[i+k][j-k])
            print("=",product,end=' ')
            if product >max_product:
                max_product = product
                print("max_product :",max_product)
            print()
            
print("max_product is ",max_product)

 

정리
max_product=0
for i in range(20):
    for j in range(20):
        
        #가로숫자 4개 곱
        product =1
        if j+4 < 20:
            for k in range(0,4):
                product *= int(numbers[i][j+k])
            if product >max_product:
                max_product = product

        #세로숫자 4개 곱
        product =1
        if i+4 < 20:
            for k in range(0,4):
                product *= int(numbers[i+k][j])
            if product >max_product:
                max_product = product
        
        #대각선(↘)숫자 4개 곱
        product =1
        if i+4 < 20 and j+4 < 20:
            for k in range(0,4):
                product *= int(numbers[i+k][j+k])
            if product >max_product:
                max_product = product
        
        #대각선(↙)숫자 4개 곱
        product =1
        if i+4 < 20 and j+4 < 20 and j >= 3:
            for k in range(0,4):
                product *= int(numbers[i+k][j-k])
            if product >max_product:
                max_product = product

            
print("max_product is ",max_product)

 

댓글

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