Problem_011_Largest product in a grid

[그림 01] Problem_011 문제

문제 설명

문제 이름 : 격자무늬의 근접한 숫자의 곱 중 가장 큰 값

문제 내용 : 20 x 20의 격자무늬로 이루어진 숫자열 중 빨간색으로 되어 있는 4개의 숫자의 곱은 26 x 63 x 78 x 14 = 1788696입니다. 그렇다면 근접한 4개의 숫자의 곱 중 가장 큰 값은 무엇입니까?(가로, 세로, 위, 아래, 대각선 모두 포함)

매우 힘들었습니다...

특히 대각선...

문제에서 필요한 내용은 일단 각설하고 소스코드로 넘어가도록 하겠습니다.

소스코드

#Problem 011 Largest product in a grid
#Python 3 version source

def getDiagonallyRight(List):
	DiagonallyRight = []
	num = 1
	
	for k in range(0,17):
		for j in range(0,17):
			for i in range(0,4):
				num *= int(List[k+i][j+i])
			DiagonallyRight.append(num)
			num = 1 
	
	return DiagonallyRight
	

def getDiagonallyLeft(List):
	DiagonallyLeft = []
	num = 1
	
	for k in range(0,17):
		for j in range(3,20):
			for i in range(0,4):
				num *= int(List[k+i][j-i])
			DiagonallyLeft.append(num)
			num = 1
			
	return DiagonallyLeft
	
def getRow(List):#Left to Right
	RowList = []
	num = 1
	
	for i in range(0, 17):
		for j in range(0, 17):
			for k in range(0, 4):
				num *= int(List[i][j+k])
			RowList.append(num)
			num = 1
	
	return RowList
	
def getCol(List):#Up to Down
	ColList = []
	num = 1
	
	for i in range(0, 17):
		for j in range(0, 17):
			for k in range(0, 4):
				num *= int(List[i+k][j])
			ColList.append(num)
			num = 1
			
	return ColList
			
if __name__ == "__main__":
	Main_grid = """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"""
	Main_gridsplit = Main_grid.split()
	Main_gridint	= []
	for i in Main_gridsplit:
		Main_gridint.append(int(i))
	
	Main_gridList = []
	for i in range(0, 400, 20):
		Main_gridList.append(Main_gridsplit[i:i+20])
		
	#Main_gridList ==> 2 degree Array~~!!
	
	Main_List = []
	
	Main_List += getRow(Main_gridList)
	Main_List += getCol(Main_gridList)
	Main_List += getDiagonallyLeft(Main_gridList)
	Main_List += getDiagonallyRight(Main_gridList)
	
	Main_sort = sorted(Main_List)
	print(Main_sort[-1])
	

Main_grid는 격자무늬 숫자열을 가져온 값입니다.

Main_gridsplit --> Main_gridint --> Main_gridList까지 해서 숫자 2차원 배열을 만들었습니다.

Main_List는 4개의 함수에서 구해진 곱을 모두 더할 리스트입니다.

getRow함수는 가로로 되어 있는 곱을 모두 구하는 함수입니다.

getCol함수는 세로로 되어 있는 곱을 모두 구하는 함수입니다.

getDiagonallyLeft함수는 오른쪽 위에서 왼쪽 아래로 향한 대각선으로 되어 있는 곱을 모두 구하는 함수입니다.

getDiagonallyRight함수는 왼쪽 위에서 오른쪽 아래로 향한 대각선으로 되어 있는 곱을 모두 구하는 함수입니다.

 소스코드가 매우매우 개판이지만, 먼저 나름의 자부심을 가지고 잘하는 분의 소스코드를 가져와 비교해보도록 하겠습니다.

nums = (
    ( 8, 2,22,97,38,15, 0,40, 0,75, 4, 5, 7,78,52,12,50,77,91, 8,),
    (49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48, 4,56,62, 0,),
    (81,49,31,73,55,79,14,29,93,71,40,67,53,88,30, 3,49,13,36,65,),
    (52,70,95,23, 4,60,11,42,69,24,68,56, 1,32,56,71,37, 2,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, 3,45, 2,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, 2,62,12,20,95,63,94,39,63, 8,40,91,66,49,94,21,),
    (24,55,58, 5,66,73,99,26,97,17,78,78,96,83,14,88,34,89,63,72,),
    (21,36,23, 9,75, 0,76,44,20,45,35,14, 0,61,33,97,34,31,33,95,),
    (78,17,53,28,22,75,31,67,15,94, 3,80, 4,62,16,14, 9,53,56,92,),
    (16,39, 5,42,96,35,31,47,55,58,88,24, 0,17,54,24,36,29,85,57,),
    (86,56, 0,48,35,71,89, 7, 5,44,44,37,44,60,21,58,51,54,17,58,),
    (19,80,81,68, 5,94,47,69,28,73,92,13,86,52,17,77, 4,89,55,40,),
    ( 4,52, 8,83,97,35,99,16, 7,97,57,32,16,26,26,79,33,27,98,66,),
    (88,36,68,87,57,62,20,72, 3,46,33,67,46,55,12,32,63,93,53,69,),
    ( 4,42,16,73,38,25,39,11,24,94,72,18, 8,46,29,32,40,62,76,36,),
    (20,69,36,41,72,30,23,88,34,62,99,69,82,67,59,85,74, 4,36,16,),
    (20,73,35,29,78,31,90, 1,74,31,49,71,48,86,81,16,23,57, 5,54,),
    ( 1,70,54,71,83,51,54,69,16,92,33,48,61,43,52, 1,89,19,67,48,),
)

def seqs(nums, row, col):
    if row + 4 <= len(nums):                                yield list(nums[i][col] for i in xrange(row, row+4))
    if col + 4 <= len(nums[row]):                           yield list(nums[row][i] for i in xrange(col, col+4))
    if row + 4 <= len(nums) and col + 4 <= len(nums[row]):  yield list(nums[row+i][col+i] for i in xrange(0,4))
    if row + 4 <= len(nums) and col >= 3:                   yield list(nums[row+i][col-i] for i in xrange(0,4))

def product(seq):
    n = 1
    for x in seq: n = n * x
    return n

def list_seqs(nums):
    for row in range(0, len(nums)):
        for col in range(0, len(nums[row])):
            for seq in seqs(nums, row, col):
                yield seq
				
print max(product(seq) for seq in list_seqs(nums))

아쉽게도 실행이 안 되네요.

위의 소스는 python2.7.x버전의 소스이기 때문에 2.7.13으로 실행해봤는데... 안 되네요.

일단 Yield라는 게 있네요. 파이썬을 공부하면서 필요한 요소가 하나하나 떠오릅니당 헤헤

이번에 Yield를 공부해서 업로드해야겠습니다.