5
\$\begingroup\$

Project Euler #11 asks to find the largest product of four numbers of a grid, where the four numbers occur consecutive to each other vertically, horizontally, or diagonally.

Here is my solution in Python. In addition to the usual code review, I have 2 extra questions (actually confessions of my laziness):

  1. Would it be better if I compared products as in traditional way instead of using max(list)? Like:

    if (current > max_product):
        max_product = current
    
  2. Would it be better if I used proper for loops instead of relying on try? Because in certain cases it gives KeyError.

Because of these two shortcuts, I feel like I have cheated. Shall I worry about them or just ignore them?

yy = """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"""

rows = yy.splitlines()
d = {}
x = 0
for row in rows:
    row_cels = row.split()
    y = 0
    d[x] = {}
    for cell in row_cels:
        d[x].update({y: int(cell)})
        y+=1
    x+=1


def product(a, b, al="hori", r=4):
    try:
        res = 1
        for xx in xrange(r):
            if al == "hori": #        -
                res *= d[a][b+xx]
            elif al == "verti": #     |
                res *= d[b+xx][a]
            elif al == "dia": #       \
                res *= d[a+xx][b+xx]
            elif al == "diarev": #    /
                res *= d[a+xx][19-(b+xx)]
        return res
    except:
        return 0

hori = []
verti = []
dia = []
diarev = []

for x in xrange(0, 20):
    for y in xrange(0, 20):
        hori.append(product(x,y))
        verti.append(product(x, y, "verti"))
        dia.append(product(x, y, "dia"))
        diarev.append(product(x, y, "diarev"))

print max(max(hori), max(verti), max(dia), max(diarev))
\$\endgroup\$
2
\$\begingroup\$
  1. It's OK to use max(), reimplementing it yourself won't save time, especially since the Python version is possibly faster if it's written in C. It's possible to be more concise and clearer though: max(hori + verti + dia + diarev).
  2. You should use a list of list to represent a matrix, not a list of dictionaries. As cat_baxter points out, d = [map(int, row.split()) for row in open('20x20.txt').read().splitlines()] is enough to populate d. However if you're not familiar with list comprehensions and map, it's OK to use normal loops.
  3. Python doesn't really have constants, but a convention is to do VERTI = "verti" and then use VERTI everywher, denoting that it is a constant ("verti" is not a good name, by the way, "vertical" is better. Use code completion.)
  4. try: ... except: ... is bad practice, you need to catch specific exceptions (KeyError in this case). And you need to understand why those errors are thrown! This could be a bug in your code.
\$\endgroup\$
1
\$\begingroup\$

The problem is pretty trivial and you should only check the index ranges and don't use

for x in xrange(0, 20):
    for y in xrange(0, 20):

but

for x in xrange(16):
    for y in xrange(16):

My version:

d = [map(int, row.split()) for row in open('20x20.txt').read().splitlines()]
value = 0
for m in xrange(16):
    for n in xrange(16):
        value = max(value,
            # rows
            d[m][n] * d[m][n + 1] * d[m][n + 2] * d[m][n + 3],
            d[m + 1][n] * d[m + 1][n + 1] * d[m + 1][n + 2] * d[m + 1][n + 3],
            d[m + 2][n] * d[m + 2][n + 1] * d[m + 2][n + 2] * d[m + 2][n + 3],
            d[m + 3][n] * d[m + 3][n + 1] * d[m + 3][n + 2] * d[m + 3][n + 3],
            # cols
            d[m][n] * d[m + 1][n] * d[m + 2][n] * d[m + 3][n],
            d[m][n + 1] * d[m + 1][n + 1] * d[m + 2][n + 1] * d[m + 3][n + 1],
            d[m][n + 2] * d[m + 1][n + 2] * d[m + 2][n + 2] * d[m + 3][n + 2],
            d[m][n + 3] * d[m + 1][n + 3] * d[m + 2][n + 3] * d[m + 3][n + 3],
            # diag
            d[m][n] * d[m + 1][n + 1] * d[m + 2][n + 2] * d[m + 3][n + 3],
            d[m + 3][n] * d[m + 2][n + 1] * d[m + 1][n + 2] * d[m][n + 3])
print('Max value = %d' % value)
\$\endgroup\$
  • \$\begingroup\$ Hmm. Hardcoding all these calculations looks icky. I’d write a tiny helper functions do do the calculation given a 4-tuple of offsets in a 4x4 field (call as e.g. get(m, n, 1, 4, 9, 13) to get the second row in row-major layout). \$\endgroup\$ – Konrad Rudolph Aug 8 '12 at 14:26
  • \$\begingroup\$ May be your idea is correct for a huge code, but such hardcoding makes the code very fast (I would bet that a code optimizer just loves that :) \$\endgroup\$ – cat_baxter Aug 8 '12 at 16:05
  • \$\begingroup\$ Upvoted, it's a great answer, even though a version without the unrolled loops would have been nice. \$\endgroup\$ – Quentin Pradet May 3 '13 at 8:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.