Nov
26
Project Euler: Largest product of consecutive digits in grid
Filed Under hisabati, project euler by Mucheru
Problem 11 from Project Euler is a fun one:
In the 20 by 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 48The product of these numbers is
What is the greatest product of four adjacent numbers in any direction (up, down, left, right, or diagonally) in the 20 by 20 grid?
I came up with two solutions: a naive exhaustive search (which still runs remarkably fast in python) and a slightly more efficient one in the spirit of my solution to problem 8. The naive version proceeds as follows:
1: def max_prod_in_grid_basic(gridString, windowSize): 2: gridNums = [int(x) for x in gridString.split()] 3: gridLen = int(sqrt(len(gridNums))) 4: maxProduct = 0 5: # get horizontal products 6: lastColumn = gridLen - windowSize + 1 7: for rootRow in range(0, gridLen): 8: for rootColumn in range(0, lastColumn): 9: startIndex = (rootRow * gridLen) + rootColumn 10: endIndex = startIndex + windowSize 11: windowItems = gridNums[startIndex:endIndex] 12: currProduct = prod(windowItems) 13: if(currProduct > maxProduct): 14: maxProduct = currProduct 15: # get vertical products 16: lastRow = gridLen - windowSize + 1 17: for rootColumn in range(0, gridLen): 18: for rootRow in range(0, lastRow): 19: startIndex = (rootRow * gridLen) + rootColumn 20: endIndex = startIndex + (gridLen * windowSize) 21: windowItems = gridNums[startIndex: endIndex: gridLen] 22: currProduct = prod(windowItems) 23: if(currProduct > maxProduct): 24: maxProduct = currProduct 25: # get down-diagonal products 26: lastRow = gridLen - windowSize + 1 27: lastColumn = gridLen - windowSize + 1 28: for rootRow in range(0, lastRow): 29: for rootColumn in range(0, lastColumn): 30: startIndex = (rootRow * gridLen) + rootColumn 31: endIndex = startIndex + (gridLen * windowSize) + windowSize 32: windowItems = gridNums[startIndex: endIndex: gridLen+1] 33: currProduct = prod(windowItems) 34: if(currProduct > maxProduct): 35: maxProduct = currProduct 36: # get up-diagonal products 37: lastRow = gridLen - windowSize + 1 38: lastColumn = gridLen 39: firstColumn = windowSize - 1 40: for rootRow in range(0, lastRow): 41: for rootColumn in range(firstColumn, lastColumn): 42: startIndex = (rootRow * gridLen) + rootColumn 43: endIndex = startIndex + (gridLen * windowSize) - windowSize 44: windowItems = gridNums[startIndex: endIndex: gridLen-1] 45: currProduct = prod(windowItems) 46: if(currProduct > maxProduct): 47: maxProduct = currProduct 48: return maxProduct
The primary weakness with this approach is that it does not take advantage of the fact that there is a simple relationship between the products of two adjacent sets of consecutive numbers. From the solution to problem 8:
We achieve some performance gain by taking advantage of the overlap between adjacent windows. If the window has length 5, then adjacent windows have 3 elements in common. The overlap elements contribute the same value to the product computed for the two adjacent windows. Therefore, the difference between the product computed for a window starting at index i and one starting at i+1 is due to elements at the end of the windows. Specifically, the product of the window rooted at i+1 is given by the dividing the value of the product of the window rooted at i by the value of the ith element (undoing the effect of the element we’re removing) multiplied by the value of the element at position i+(windowSize – 1) (adding the effect of the new element)
The second algorithm takes advantage of this information. The solution is in two functions. First, we extract the list of valid sequences (all the rows, columns and up and down diagonals), taking the maximum length of each sequence.
1: def get_sequences_in_grid(gridString, minLength): 2: gridNums = [int(x) for x in gridString.split()] 3: gridLen = int(sqrt(len(gridNums))) 4: digitSequences = [] 5: # get horizontal sequences 6: rootColumn = 0 7: for rootRow in range(0, gridLen): 8: startIndex = (rootRow * gridLen) + rootColumn 9: endIndex = startIndex + gridLen 10: listItems = gridNums[startIndex:endIndex] 11: digitSequences.append(listItems) 12: # get vertical sequences 13: rootRow = 0 14: for rootColumn in range(0, gridLen): 15: startIndex = (rootRow * gridLen) + rootColumn 16: endIndex = int(len(gridNums)) 17: listItems = gridNums[startIndex: endIndex: gridLen] 18: digitSequences.append(listItems) 19: # get down-diagonal sequences 20: # upper triangle 21: lastRow = gridLen - minLength + 1 22: lastColumn = gridLen - minLength + 1 23: rootRow = 0 24: for rootColumn in range(0, lastColumn): 25: startIndex = (rootRow * gridLen) + rootColumn 26: endIndex = (rootRow + 1 +(gridLen - (rootColumn + 1))) * gridLen 27: listItems = gridNums[startIndex: endIndex: gridLen+1] 28: digitSequences.append(listItems) 29: # lower triangle 30: rootColumn = 0 31: for rootRow in range(1, lastRow): 32: startIndex = (rootRow * gridLen) + rootColumn 33: endIndex = (rootRow + 1 + (gridLen - (rootRow + 1))) * gridLen 34: listItems = gridNums[startIndex: endIndex: gridLen+1] 35: digitSequences.append(listItems) 36: # get up-diagonal sequences 37: # upper triangle 38: rootRow = 0 39: firstColumn = minLength - 1 40: for rootColumn in range(firstColumn, gridLen): 41: startIndex = (rootRow * gridLen) + rootColumn 42: endIndex = startIndex + (rootColumn * gridLen) 43: listItems = gridNums[startIndex: endIndex: gridLen - 1] 44: digitSequences.append(listItems) 45: # lower triangle 46: rootColumn = gridLen - 1 47: for rootRow in range(1, lastRow): 48: startIndex = (rootRow * gridLen) + rootColumn 49: endIndex = (rootRow + 1 + (gridLen - (rootRow + 1))) * gridLen 50: listItems = gridNums[startIndex: endIndex: gridLen - 1] 51: digitSequences.append(listItems) 52: return digitSequences 53:
The second step takes the list of sequences and iterates through them, computing the max product for each list using a modified version of the “slice product” function from problem 8.
1: def max_prod_in_grid(gridString, minLength): 2: sequences = get_sequences_in_grid(gridString, minLength) 3: max_product = 0 4: for currList in sequences: 5: listLength = len(currList) 6: if(listLength < minLength): 7: continue 8: curr_product = prod(currList[:minLength]) 9: if(curr_product > max_product): 10: max_product = curr_product 11: for i in range(1, listLength - minLength + 1): 12: stopPosition = i + (minLength - 1) 13: outItem = currList[i - 1] 14: inItem = currList[stopPosition] 15: if(outItem == 0): 16: curr_product = prod(currList[i:stopPosition + 1]) 17: else: 18: curr_product = (curr_product / outItem) * inItem 19: if(curr_product > max_product): 20: max_product = curr_product 21: return max_product