Tell me more ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 4 down vote favorite
1

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

2 Answers

up vote 1 down vote
  1. It's OK 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 clearar 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.
share|improve this answer
up vote 0 down vote

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
 
Upvoted, it's a great answer, even though a version without the unrolled loops would have been nice. –  Quentin Pradet May 3 at 8:53

Your Answer

 
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.