My solution for project euler #11 in python. Possibly it can be improved. But other than improvements, I have 2 extra questions, more likely confessions, mostly because 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 2, I feel like I had cheated. Shall I worry about them or just ignore them?

Thanks

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))
share|improve this question

1 Answer

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)
share|improve this answer
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). – Konrad Rudolph Aug 8 '12 at 14:26
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 :) – cat_baxter Aug 8 '12 at 16:05

Your Answer

 
or
required, but never shown
discard

By posting your answer, you agree to the privacy policy and terms of service.

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