Archive

Archive for July, 2010

Euler 11

2010/07/08 1 comment

After packing yesterday I thought I’d spend the last half an hour to solve the Euler 11 problem. I had used pen and paper in the car on the way home (I don’t drive myself 😉 to come up with a nice enough algorithm. However no matter how I twist and turn the problem I realized that I still need to check every possible solution. The first naive way on paper was to check every direction.

This is an example; assume we have a (zero indexed) 10×10 grid. and that our position is say at 4,4 (in blue) then the initial idea was to check all possible directions (below in red)


x x x x x x x x x x
x x x x x x x x x x
x x x x x x x x x x
x x x x x x x x x x
x x x x x x x x x x
x x x x x x x x x x
x x x x x x x x x x
x x x x x x x x x x
x x x x x x x x x x
x x x x x x x x x x

I soon realized that the opposite of each direction is just a reiteration of something that was already calculated. E.g. 4,4 -> 7,1 is the same as 7,1 -> 4,4 . This means that it is enough to just test half of these.


x x x x x x x x x x
x x x x x x x x x x
x x x x x x x x x x
x x x x x x x x x x
x x x x x x x x x x
x x x x x x x x x x
x x x x x x x x x x
x x x x x x x x x x
x x x x x x x x x x
x x x x x x x x x x

Now I only have to make sure I don’t get out of bounds. Since I’m traversing the grid from top right to bottom left i want to do as few checks as possible. First thing is that 3 out of 4 checks are made on the left side of the position, this means that I need to check that the position is x >= 3 and y > 3 and y < height – 3.  The last one only needs to be checked when the position is y >= 3 only. After that I simply take the max of those values.

This yields the following in python 3:

def local_max(y, x):
    llarge = drdlarge = ularge = dlularge = 0
    if x <= 16:
        # Check from position to right
        llarge = grid[y][x]*grid[y][x+1]*grid[y][x+2]*grid[y][x+3]
        if y >= 3:
            # Check from position diagonally right up
            dlularge = grid[y][x]*grid[y-1][x+1]*grid[y-2][x+2]*grid[y-3][x+3]
        if y <= 16:
            # Check from position diagonally right down
            drdlarge = grid[y][x]*grid[y+1][x+1]*grid[y+2][x+2]*grid[y+3][x+3]
    if y >= 3:
        # Check from position up
        ularge = grid[y][x]*grid[y-1][x]*grid[y-2][x]*grid[y-3][x]
    tmax = max(llarge, drdlarge, ularge, dlularge)
    # print("Local max:", tmax)
    return tmax

Then it is just a matter of iterating across the grid and get the largest value:

def traverse_grid():
    largest = 0
    for y in range(0, 20):
        for x in range(0, 20):
            candidate = local_max(y, x)
            if candidate > largest:
                largest = candidate
    return largest

if __name__ == '__main__':
    start = time.time()
    print("Answer:", traverse_grid())
    print("Completed in", str(time.time()-start), "seconds")

Two important lessons followed (This is the biggest reason to learn a language by actually USING it):

  1. On line 12 in the local_max() function I put x >= 3 by mistake. I thought everything was ok when I ran the code because I did get the right answer. However after look at the code when writing this blog entry (I wrote most of this yesterday evening and revised it today) I noticed that x >= is wrong! Python has a “feature” which is pretty dangerous if you don’t know about it. If you have a tuple e.g. grid = ((1,2,3),(4,5,6)) and then do grid[-1][0] the result is not a crash, it is simply 4. This is because in python you can slice a tuple as well! Very important detail!
  2. Because I usually program Erlang I sometimes put a comma at the end of a line by mistake. On line 5 in the traverse_grid() function I put a comma by mistake after the function call. This is another “feature” in python which means that I’m creating a one-value tuple. I was banging my head senseless trying to understand this late at night and simply extracted the first element but I couldn’t understand why. Today I asked my friend to be my Rubber duck and while explaining the code I realized what I was doing. This is also important to know because it “fails” silently if you don’t realize what is going on as an Erlang programmer

That’s all…

I’m off to Turkey! See you at the end of the month!

Advertisements
Categories: Python, Software Tags:

Project euler and Python3

I’m back. A lot of things happening right now… I’m getting married (is one of them) so I haven’t gotten around to update this page. Anyway I’ll start now again.

So I’ve decided to start learning a new programming language just to learn and get different perspectives of things (keep my brain fit :P). Erlang remains my number 1 language but I decided to learn python3. The reason is not important but I just wanted to know if python was any good.

I choose python3 over python2 because I didn’t like the fact that python2 was not going to be updated after 2.7 (which recently actually got released if I remember correctly). I am aware of the fact that much legacy code is written in python2.x but since I’m not using it commercially I don’t really care, it is for my own sake anyway.

To learn python I searched for a page with problems to solve (best way to learn a language is to use it) and I found projecteuler.net, I suggest that anyone who wants a challenge (in various levels) to go there. The page will explain more what it is but basically it presents a bunch of problems that you solve and you can solve them however you like (pen and paper even if you like that sort of things).

currently I’m at problem 11 which reads as follows:

In the 20×20 grid below, four numbers along a diagonal line have been marked in red.

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

The product of these numbers is 26 × 63 × 78 × 14 = 1788696.

What is the greatest product of four adjacent numbers in any direction (up, down, left, right, or diagonally) in the 20×20 grid?

I guess I could just brute force it but I’m trying to come up with a good solution in python, we’ll see how it works out.

All problems [that I manage to solve] in projecteuler I’m hoping to write solutions for in Erlang, Python, C and Javascript just to see how they are solved in different languages. The other day I saw a solution in Haskell (for problem 10) which very elegant which made me open my eyes for Haskell but I’ll see about that (Ocaml has been proposed as well and I really would love to have the time to look at Lisp or Scheme), I simply don’t have time for everything.

Oh… and I’m getting married so I guess that will put me off for a month or two 😛

Categories: Python Tags: