Project Euler Problem 11: largest product of 4 adjacent numbers

Question

I am a fairly beginner-level programmer, and I have been working through the Project Euler Puzzles. I am currently on Problem #11, which asks to find the largest product of four consecutive numbers (horizontally, vertically, or diagonally) in a grid.

I would like someone to look at my code and give me any tips, pointers, and better techniques and styles I could use. I think I have the grasp of functional programming fairly well, and am try to get better at OOP, so I am also wondering if there is any way to code this in an OOP manner.

# coding: utf-8
def stringToList(string):
 numberList = string.split()
 return numberList
numberSequence = ["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"]
numberList = []
for i in numberSequence:
 numberList.append(stringToList(i))
numberList = [[int(x) for x in y] for y in numberList]
def scanDown(numberList, x, y):
 try:
 product = 1
 for i in range(4):
 product*= numberList[x][y-i]
 return product
 except IndexError:
 return 0
def scanRight(numberList, x, y):
 try:
 product = 1
 for i in range(4):
 product*= numberList[x+i][y]
 return product
 except IndexError:
 return 0
def scanDownDiagonal(numberList, x, y):
 try:
 product = 1
 for i in range(4):
 product*= numberList[x+i][y-i]
 return product
 except IndexError:
 return 0
def scanUpDiagonal(numberList, x, y):
 try:
 product = 1 
 for i in range(4):
 product*= numberList[x+i][y+i]
 return product
 except IndexError:
 return 0
largestProduct = 0 
for x, item in enumerate(numberList):
 for y in range(len(item)):
 if scanDown(numberList, x, y) > largestProduct:
 largestProduct = scanDown(numberList, x, y)
 if scanRight(numberList, x, y) > largestProduct:
 largestProduct = scanDown(numberList, x, y)
 if scanDownDiagonal(numberList, x, y) > largestProduct:
 largestProduct = scanDownDiagonal(numberList, x, y)
 if scanUpDiagonal(numberList, x, y) > largestProduct:
 largestProduct = scanUpDiagonal(numberList, x, y) > largestProduct
print(largestProduct)

Answer 1

Avoid interleaving function definitions and free-floating code. If you put all the function definitions first, then it will be clear that the functions do not depend on any variables in the environment.

Consider what functions are worth defining. This function simply renames split() and is pointless:

def stringToList(string):
 numberList = string.split()
 return numberList

On the other hand, a product(seq) would be a useful function, since you have written four multiplication-performing loops. (Personally, I would implement it as functools.reduce(operator.mul, seq).)

So, how should you read in the input instead? Just a nested list comprehension would do the job:

number_sequence = [
 "08 02 ...",
 "49 49 ...",
 ...,
]
matrix = [
 [int(str) for str in line.split()] for line in number_sequence
]

---

You have a copy-and-paste bug here:

if scanRight(numberList, x, y) > largestProduct:
 largestProduct = scanDown(numberList, x, y)

You could use some objects to help reduce the repetitiveness of the four scanning functions.

class Scanner:
 def __init__(self, row_incr, col_incr):
 self.row_incr = row_incr
 self.col_incr = col_incr
 def scan(self, matrix, start_row, start_col, len):
 try:
 return [matrix[start_row + i * self.row_incr][start_col + i * self.col_incr] for i in range(len)]
 except IndexError:
 return None
def streaks(matrix, length):
 directions = [
 Scanner(0, 1),
 Scanner(1, 0),
 Scanner(1, 1),
 Scanner(1, -1),
 ]
 for r, row in enumerate(matrix):
 for c in range(len(row)):
 for scanner in directions:
 yield scanner.scan(matrix, r, c, length)
print(max(product(streak) for streak in streaks(matrix, 4) if streak))

• Jamerack: Thank you for answer the OOP part of my question! In the final line of the code, what does the {if streak} part do?
• 200_success: The scan() method returns None for streaks that go out of bounds. Putting the if streak condition on the generator expression in the last line ignores those None results.
• Jamerack: ah, I see. I completely missed that. Thanks!

Answer 2

Your stringToList function creates a variable, and does nothing but return it. Why create the variable? Why not just return string.split() in the first place? I actually don't see any use in creating the function. To me string.split() is more clear than stringToList(string). One could reasonably make a list of each character in a string and call the function stringToList. The method .split(), however, is built-in and well documented. Why complicate things?

---

I'm not sure that it is a good idea to put the grid directly into your code. The more magic values you have, the less reusable your code is. I would suggest that your program should take a filename as an argument and read the grid from there. Of course, you would make sure that the user actually gives a filename, the filename is valid, etc.

---

You use a list comprehension below, but you don't use one when you convert the list of strings to a list of lists of strings. In fact, I would merge the two:

numberList = [[int(x) for x in line.strip().split()] for line in numberSequence]

If you were reading from a file, you would switch numberSequence to the name chosen for your file object (numbersFile if you did something like numbersFile = open(filename))

On top of all that, I suggest that you move the definition of numberList lower down. Usually, code should go like this:

import module
#...
CONSTANT = value
#...
def function():
# ...
def function2():
# ...
#...
def main():
# ...
if __name__ == '__main__':
 main()

Therefore, I would move the definition of numberList to the main function. If you don't want a main function, it should go in the if __name__ == '__main__': block. If you don't want that, it should at least go after the function definitions. If you don't want that either, ... you're a hopeless case.

---

Your scanning functions are very similar. They are so similar, in fact, that I believe they can be merged:

def scan(numberList, x, y, nums=4):
 products = [1] * nums
 # Changes we will make to x and y to get the adjacent numbers.
 # (0, -1) means x will stay the same, but y will go down by one for
 # each adjacent number (down by index, but up visually).
 changes = [(0, -1), (0, 1), (1, 0), (-1, 0)]
 for i in range(nums):
 for p, (xChange, yChange) in enumerate(changes):
 try:
 products[p] *= numberList[x+(i*xChange)][y+(i*yChange)]
 except IndexError:
 products[p] = 0
 return max(products)

The above has not been tested, but the concept should be fairly clear.

---

Now that it is all in one function, your largestProduct definition is fairly simple:

largestProduct = max(
 scan(numberList, x, y)
 for x, item in enumerate(numberList)
 for y in range(len(item))
)

(Again, untested. If you could test it yourself and confirm that it works, I can remove this clutter.)

• Jamerack: Awesome! Thank you, this is very helpful. I honestly don't know why I wrote the stringToList function, it's dumb. I'll test this as soon as I get to my iPad.

Answer 3

Here's what I see:

• When doing Project Euler exercises I like to drop a link and a copy of the subject in the module docstring: it's nice when you share it and read it later.
• Your numberSequence big-array is breaking the 80th column, which I personally don't like.
• You do not need a stringToList function, just use .split(). It may look more readable as you're naming your intention, which is really nice, and you named it well, which is really nice. BUT we all know .split() and it's no surprise. So when we encounter stringToList we have to go read the code, which is slower and harder than just reading .split(). So naming intention is a nice idea, but don't over-do it, it costs you the time to write a single-line function and cost us the time to find it and read it for something commonly known (str.split(), please).
• Indentation in your numberSequence is messed up, I don't know why but remember that in Python you should not use tabs to indent your code, only blocks of 4 spaces (see the PEP8). It's nice when you share code with 4 spaces that it appears everywhere equals (and by not using tabs we're sure nobody mixes tabs and spaces ...).
• You're calling each scan* method twice if the product is greater than the previous, you're not nice with the CPU (think like you're doing it yourself)
• Your numberList variable means two different things in two different scopes: global and locals, which should probably be avoided to avoid bugs (like thinking you're hitting the global one, but modifying the local one ?)
• PEP8 tells us to put two newlines between functions.
• Your four scan methods are essentially the same, only the signs change. Maybe they can be combined?
• for i in numberSequence: numberList.append(stringToList(i)) should probably be more readable as a list comprehension.

I would go for something more like:

from contextlib import suppress
numberSequence = [
 "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"]
numberList = [line.split() for line in numberSequence]
numberList = [[int(x) for x in y] for y in numberList]
def multiply(iterable):
 result = 1
 for number in iterable:
 result *= number
 return result
def scan(x, y):
 with suppress(IndexError):
 yield multiply(numberList[x][y+i] for i in range(4))
 with suppress(IndexError):
 yield multiply(numberList[x+i][y] for i in range(4))
 with suppress(IndexError):
 yield multiply(numberList[x+i][y-i] for i in range(4))
 with suppress(IndexError):
 yield multiply(numberList[x+i][y+i] for i in range(4))
def main():
 all_products = []
 for x in range(len(numberList)):
 for y in range(len(numberList[0])):
 for product in scan(x, y):
 all_products.append(product)
 largestProduct = max(all_products)
 print(largestProduct)
 assert largestProduct == 70600674
main()

• Jamerack: Thank you very much for this! I don't know exactly what happened with the weird indentations on numberSequence, it's normal on my code. I have one questions about the suppress function you use, how exactly does that work? I'm guessing its name is pretty true to its function?
• Julien Palard: See docs.python.org/3/library/contextlib.html#contextlib.suppress it's just a short way to skip an ugly/empty try-except.
• Julien Palard: Oh you're completly right about my unnecessary conversion, I added it only to check if everything was right (added a print) ! And kept it by error. I fixed it in my answer, thanks! BTW I prefer my way which is far more readable than the reduce way. In fact, reduce has been dropped because for loops are more readable.