February 20, 2021 at 11:24 am
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
February 21, 2021 at 12:10 pm
Thanks for posting your issue and hopefully someone will answer soon.
This is an automated bump to increase visibility of your question.
March 1, 2021 at 1:53 am
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.
March 1, 2021 at 5:59 pm
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.
March 2, 2021 at 5:10 am
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 19I 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 4 (of 4 total)
You must be logged in to reply to this topic. Login to reply