Home > Python, Software > Euler 11

Euler 11

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:
  1. 2010/08/09 at 17:49

    Mazen,

    We are an exciting startup that has recently raised Series A. Located in downtown San Mateo, CA the startup is founded by veterans from Yahoo, Netscape and Paypal. We are seeking a Sr.Erlang engineer either on a contract or fulltime basis. We are open to folks that are willing to work remotely if they have stellar qualifications. Interested in speaking to us?

    Loads of startup perks. We believe in pampering our employees.

    We are looking to hire a key senior engineer with these skills:

    – 2+ years of professional Erlang/OTP development, 5+ years of professional software engineering
    – Needs to have strong working knowledge of OTP and related design methodology
    – Expertise in Python, MySQL, possibly Java
    – Experience designing and building killer consumer web applications

    Pluses:
    – Production experience with high volume mnesia-backed databases
    – Web development in Erlang using Mochiweb and/or Webmachine
    – Natural Language Understanding

    Please email your cover letter and your resume.

    Cheers,
    Lakshmi Jonasson

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: