Python Calculation in Euler Project problem

  • Ahoi,

    since i am learning python i am trying to work myself through the "Euler Project" questions.

    Currently i am stuck because i can't find WHY my solution produces the wrong answer.

    Obviously there are other solutions and implementations out there but i do not understand why mine does not output the correct solution although it looks to me (according to my print statements) like it does the correct thing.

    Anyone idea where MY mistake is?

    I am trying to create a version that allows to input the number N, to define the number of diagonals which should be considdered.

    And please this is for understanding so don't just post some other complete different solutions that produces the correct answer because i can google that myself.

    https://projecteuler.net/problem=11

    import numpy
    matrix = numpy.array([
    [8 ,2 ,22 ,97 ,38 ,15 ,0 ,40 ,0 ,75 ,4 ,5 ,7 ,78 ,52 ,12 ,50 ,77 ,91 ,8 ]
    ,[49 ,49 ,99 ,40 ,17 ,81 ,18 ,57 ,60 ,87 ,17 ,40 ,98 ,43 ,69 ,48 ,4 ,56 ,62 ,0 ]
    ,[81 ,49 ,31 ,73 ,55 ,79 ,14 ,29 ,93 ,71 ,40 ,67 ,53 ,88 ,30 ,3 ,49 ,13 ,36 ,65 ]
    ,[52 ,70 ,95 ,23 ,4 ,60 ,11 ,42 ,69 ,24 ,68 ,56 ,1 ,32 ,56 ,71 ,37 ,2 ,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 ,3 ,45 ,2 ,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 ,2 ,62 ,12 ,20 ,95 ,63 ,94 ,39 ,63 ,8 ,40 ,91 ,66 ,49 ,94 ,21 ]
    ,[24 ,55 ,58 ,5 ,66 ,73 ,99 ,26 ,97 ,17 ,78 ,78 ,96 ,83 ,14 ,88 ,34 ,89 ,63 ,72 ]
    ,[21 ,36 ,23 ,9 ,75 ,0 ,76 ,44 ,20 ,45 ,35 ,14 ,0 ,61 ,33 ,97 ,34 ,31 ,33 ,95 ]
    ,[78 ,17 ,53 ,28 ,22 ,75 ,31 ,67 ,15 ,94 ,3 ,80 ,4 ,62 ,16 ,14 ,9 ,53 ,56 ,92 ]
    ,[16 ,39 ,5 ,42 ,96 ,35 ,31 ,47 ,55 ,58 ,88 ,24 ,0 ,17 ,54 ,24 ,36 ,29 ,85 ,57 ]
    ,[86 ,56 ,0 ,48 ,35 ,71 ,89 ,7 ,5 ,44 ,44 ,37 ,44 ,60 ,21 ,58 ,51 ,54 ,17 ,58 ]
    ,[19 ,80 ,81 ,68 ,5 ,94 ,47 ,69 ,28 ,73 ,92 ,13 ,86 ,52 ,17 ,77 ,4 ,89 ,55 ,40 ]
    ,[4 ,52 ,8 ,83 ,97 ,35 ,99 ,16 ,7 ,97 ,57 ,32 ,16 ,26 ,26 ,79 ,33 ,27 ,98 ,66 ]
    ,[88 ,36 ,68 ,87 ,57 ,62 ,20 ,72 ,3 ,46 ,33 ,67 ,46 ,55 ,12 ,32 ,63 ,93 ,53 ,69 ]
    ,[4 ,42 ,16 ,73 ,38 ,25 ,39 ,11 ,24 ,94 ,72 ,18 ,8 ,46 ,29 ,32 ,40 ,62 ,76 ,36 ]
    ,[20 ,69 ,36 ,41 ,72 ,30 ,23 ,88 ,34 ,62 ,99 ,69 ,82 ,67 ,59 ,85 ,74 ,4 ,36 ,16 ]
    ,[20 ,73 ,35 ,29 ,78 ,31 ,90 ,1 ,74 ,31 ,49 ,71 ,48 ,86 ,81 ,16 ,23 ,57 ,5 ,54 ]
    ,[1 ,70 ,54 ,71 ,83 ,51 ,54 ,69 ,16 ,92 ,33 ,48 ,61 ,43 ,52 ,1 ,89 ,19 ,67 ,48 ]])


    #Test N for now since i the solution for N-Diagonal Values, and n2 for prevention to reach out of bounds
    n=4
    n2 = n-1

    #Matrix Shape
    number_of_lists = len(matrix)
    length_one_List = len(matrix[0])

    #Variables for total and current Max
    total = 0
    current = 0

    #Iteration through whole matrix without reaching bottom or right out of index
    #For each Element take the N diagonals and multiply them with the original one
    #Keep the global max in the variable total
    for x in range(number_of_lists-n2):
    for y in range(length_one_List-n2):
    #Save global Max
    if current > total:
    total = current
    #Reset for calc of next current Max
    current = matrix[x][y]
    for z in range(1,n):
    #current=matrix[x][y]*matrix[x+1][y+1]*matrix[x+2][y+1]*matrix[x+3][y+3]
    current*=matrix[x+z][y+z]
    #Debug help showing what he does
    #print(current,z,matrix[x+z][y+z])

    #Correct:70600674
    #Mine:40304286
    print(total)

    Would appreciate some help

    I want to be the very best
    Like no one ever was

  • Thanks for posting your issue and hopefully someone will answer soon.

    This is an automated bump to increase visibility of your question.

  • It looks like you are only calculating the product in a diagonal the extends down and to the right from each position. You will also need to calculate a product along the row, down the column, and on a diagonal up and to the right of each starting position.

    This will require a change in your "for x" and "for y" ranges. You have to go across every column and row for those products, not just stopping short at the (number_of_lists-n2) position. Also will need to add some criteria to ensure matrix indices stay in bounds. For each pass through the loops, you will get four "current" products: current_row, current_column, current_diagonal_down, current_diagonal_up.

    I'm not a Python coder, but ran through it in R to see if my hunch had validity before googling answers. I used brute force of the double loops to walk through each combination and add it to a dataframe of all possible totals.  Here are a few of the top combinations with their starting element:

    Row   Column   Total              Orientation

    7      13              70600674    diagonal up

    16      7              51267216       row

    11      9              48477312       column

    13     2               41076896     diagonal up

    10    17              40304286   diagonal down

    It was a fun exercise. There are some elegant solutions out there.

  • I've done a few Project Euler items. It's a good test for learning Python.

    I think you are also looking only along the upper left to lower right diagonal. The problem says any diagonal, as well as L, R, U, D. Meaning, that for this grid:

    1   2  3  4
    5 6 7 8
    9 10 11 12
    12 13 14 15
    16 17 18 19

    I need to calculate 1 * 6 * 11 * 15, but also 4 * 7 * 10 * 12, and also 12 * 13 * 14 * 15, and 18 * 14 * 11 * 7 * 3

    What I usually do with these is a test set. I like what the Advent of Code does, with a 3-4 example test set to work out an algorithm. From there, then try the whole set.

  • Steve Jones - SSC Editor wrote:

    I've done a few Project Euler items. It's a good test for learning Python.

    I think you are also looking only along the upper left to lower right diagonal. The problem says any diagonal, as well as L, R, U, D. Meaning, that for this grid:

    1   2  3  4
    5 6 7 8
    9 10 11 12
    12 13 14 15
    16 17 18 19

    I need to calculate 1 * 6 * 11 * 15, but also 4 * 7 * 10 * 12, and also 12 * 13 * 14 * 15, and 18 * 14 * 11 * 7 * 3

    What I usually do with these is a test set. I like what the Advent of Code does, with a 3-4 example test set to work out an algorithm. From there, then try the whole set.

     

    Thats it! Guess my mindset was set too much on the one diagonal so i forgot the other one.

    I want to be the very best
    Like no one ever was

Viewing 5 posts - 1 through 5 (of 5 total)

You must be logged in to reply to this topic. Login to reply