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))

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.)

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()