Problem 082

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.

This forum is NOT meant to discuss solution methods for a problem.

In particular don't post any code fragments or results.

Don't start begging others to give partial answers to problems

Don't ask for hints how to solve a problem

Don't start a new topic for a problem if there already exists one


See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
User avatar
Raman
Posts: 15
Joined: Sun Nov 28, 2010 1:40 pm
Location: Chennai, India

Problem 082

Post by Raman » Sat Dec 18, 2010 11:15 am

Finding out error in any part of code is major headache, very boring than writing that piece of code itself
for solving any of that given problems.
One more to go for Level 4, but

I have been struggling with that Problem 82, after solving up with that Problem 81,
82 is lowest unsolved problem for me. I have been constantly getting answer as xxxx,
which I believe is correct. My algorithm properly works out for that 5x5 matrix, that
is being mentioned within that problem, which gives away with the answer as that xxx.

Breaking my head...
Raman2.png
Raman2.png (6.36 KiB) Viewed 6344 times
Edit by hk:
Please don't post any code or results.
Finding errors in your code is one of the major activities you should perform when solving PE problems.
Results and attachment with results snipped.
Image

kaerus01
Posts: 1
Joined: Mon Nov 08, 2010 9:42 pm

Re: Problem 082

Post by kaerus01 » Sun Dec 26, 2010 1:03 am

The answer is in the form of xxxxxx if that helps.

Have you considered how your looking at your results? Could you be focused in on one calculated result rather than seeking for the lowest value after completing all calculations? How are you trying to compute your result, what method are you using?

Hibernatus34
Posts: 31
Joined: Mon May 16, 2011 6:03 am

Re: Problem 082

Post by Hibernatus34 » Tue May 31, 2011 7:36 am

Hello,

Since you are still level 3, i guess you haven't found your error yet.
I think this grid should help you :

Code: Select all

21 10 61  2 10
42  8 51  7 35
63 11 45  9 38
81  5 11  1 22
99 10  2 10 90
If not, try to make other examples with different best paths. For example you can try to flip the grid and see if you get the same answer.
Image Joined PE in May 2011

User avatar
Raman
Posts: 15
Joined: Sun Nov 28, 2010 1:40 pm
Location: Chennai, India

Re: Problem 082

Post by Raman » Thu Jun 23, 2011 4:29 am

Somehow I got with a value of 2392 extra at that particular time period of course
That way, it is thus going to be a bit more than the threshold limit
value, but curiously enough that this number is probably not
present anywhere within that matrix grid at all
that is being available for this specific problem itself
according to this current scale forever
Raman.png
Raman.png (6.25 KiB) Viewed 6102 times
Image

User avatar
hk
Administrator
Posts: 10564
Joined: Sun Mar 26, 2006 9:34 am
Location: Haren, Netherlands

Re: Problem 082

Post by hk » Thu Jun 23, 2011 9:48 am

Raman,
you can make a link to your profile image, by inserting its hyperlink between Image

Better still is to do this in your signature (like I did).
Image

User avatar
thedoctar
Posts: 74
Joined: Fri Apr 15, 2011 10:57 am
Location: Sydney, Australia

Re: Problem 082

Post by thedoctar » Wed Jul 20, 2011 2:06 pm

Can someone please check my code?? I use python.

I used a similar implementation from problem 81. I didn't solve 81 recursively, so I think I should be use the same idea to apply it to 82, but i keep getting the wrong answer.

HOWEVER i do get the correct answer for the SMALL grid. 994.

Can someone confirm that for the small grid, the sums of the shortest paths for all paths that end at the last columns are
994 (shortest path that ends at 18)
1754 (shortest path that ends at 150)
2387 (shortest path that ends at 111)
2810 (shortest path that ends at 956)
2222 (shortest path that ends at 331)

The answer I get is 27xxxx for the large grid.
Last edited by thedoctar on Wed Jul 20, 2011 2:41 pm, edited 1 time in total.
4x Intel(R) Core(TM) i3-2330M CPU @ 2.20GHz
Image
fabas indulcet fames

User avatar
Francky
Posts: 90
Joined: Sat May 07, 2011 2:49 pm
Location: South of France

Re: Problem 082

Post by Francky » Wed Jul 20, 2011 2:36 pm

Only two of the five are correct for the small grid.
Sorry.
ImageEntia non sunt multiplicanda praeter necessitatem

User avatar
thedoctar
Posts: 74
Joined: Fri Apr 15, 2011 10:57 am
Location: Sydney, Australia

Re: Problem 082

Post by thedoctar » Wed Jul 20, 2011 2:47 pm

994
1309
1420
2376
2222

I believe these are correct?
4x Intel(R) Core(TM) i3-2330M CPU @ 2.20GHz
Image
fabas indulcet fames

Hibernatus34
Posts: 31
Joined: Mon May 16, 2011 6:03 am

Re: Problem 082

Post by Hibernatus34 » Wed Jul 20, 2011 3:56 pm

Why don't you verify it by hand ? The grid is small enough.
Image Joined PE in May 2011

User avatar
thedoctar
Posts: 74
Joined: Fri Apr 15, 2011 10:57 am
Location: Sydney, Australia

Re: Problem 082

Post by thedoctar » Wed Jul 20, 2011 6:21 pm

Don't worry, I solved it
4x Intel(R) Core(TM) i3-2330M CPU @ 2.20GHz
Image
fabas indulcet fames

kamy
Posts: 2
Joined: Wed Aug 31, 2011 3:36 am

Re: Problem 082

Post by kamy » Thu Sep 15, 2011 10:08 pm

For the small example (5 x 5):
994
1144
1255
2211
2222

are this correct?
For the big input I get something like 26****. How far am I from the right solution?

kamy
Posts: 2
Joined: Wed Aug 31, 2011 3:36 am

Re: Problem 082

Post by kamy » Thu Sep 15, 2011 10:20 pm

Hibernatus34 wrote:Hello,

Since you are still level 3, i guess you haven't found your error yet.
I think this grid should help you :

Code: Select all

21 10 61  2 10
42  8 51  7 35
63 11 45  9 38
81  5 11  1 22
99 10  2 10 90
If not, try to make other examples with different best paths. For example you can try to flip the grid and see if you get the same answer.
Hi!
Is 89 the answer?

Panphobia
Posts: 2
Joined: Fri Dec 06, 2013 8:24 am

Problem 82

Post by Panphobia » Fri Dec 06, 2013 8:41 am

For problem 81, I just used the <snip> solution. But for 82 I tried using <snip> to solve it, but I always get 0 as the answer. Is <snip> right for this problem? Or can I use a simpler algorithm? What I basically do is alter the starting position of <snip> to be every left most edge of the matrix, and then<snip>

Edit
All possible spoilers snipped by hk

Edit by mpiotte
I merged your topic with an already existing one.
Please check in the future if there already exists a topic for a problem.

CtChocula
Posts: 1
Joined: Sun Apr 02, 2017 1:54 am

Confusing Wording in Problem 82

Post by CtChocula » Sun Apr 02, 2017 2:05 am

I am a newbie here, so apologies if this goes in the wrong forum. I've finished Problem 82, but I found the description extremely confusing that led me to wasting several hours debugging my code for this problem even though my code was bug-free. My issue is with the following:

"Find the minimal path sum, in matrix.txt (right click and "Save Link/Target As..."), a 31K text file containing a 80 by 80 matrix, from the left column to the right column."

The phrase "from from the left column to the right column" seems to suggest that the matrix is stored in column-major order, but it is actually in row-major. To save time and make this problem more enjoyable for other people, I strongly recommend changing it to something like:

"Find the minimal path sum, in matrix.txt (right click and "Save Link/Target As..."), a 31K text file containing a 80 by 80 matrix stored in row major order [1], from the left column to the right column."

If the admins don't want to introduce a new definition like that, perhaps you could include at the very least a test.txt that matches the small 5x5 matrix in the example. This would achieve the same purpose.

edit: To clarify by row-major order, I mean that I assumed the CSV was expressed in transposed fashion i.e. for the 5x5 matrix

Code: Select all

131 673 234 103 18
201  96 342 965 150
630 803 746 422 111
537 699 497 121 956
805 732 524  37 331
I assumed that the first line of CSV would have 131,201,630,537,805 since that's what "left column" implied to me.

[1] https://en.wikipedia.org/wiki/Row-_and_ ... ajor_order

User avatar
sjhillier
Administrator
Posts: 507
Joined: Sun Aug 17, 2014 3:59 pm
Location: Birmingham, UK
Contact:

Re: Confusing Wording in Problem 82

Post by sjhillier » Sun Apr 02, 2017 12:25 pm

CtChocula wrote:
Sun Apr 02, 2017 2:05 am
I am a newbie here, so apologies if this goes in the wrong forum.
I moved the question into the Clarifications for Problem 82 forum, as I think it's more appropriate here. It's always a good idea to see if there's a forum dedicated to a problem first before starting a new topic.

As for the question, I haven't thought very hard about it, but I'm personally reluctant to change much in the early problems, since they have been established for a long time and solved by many people.

Alobar
Posts: 4
Joined: Mon Apr 17, 2017 12:57 am

Problem 082

Post by Alobar » Mon Apr 17, 2017 1:13 am

CtChocula wrote:
Sun Apr 02, 2017 2:05 am

The phrase "from from the left column to the right column" seems to suggest that the matrix is stored in column-major order, but it is actually in row-major. To save time and make this problem more enjoyable for other people, I strongly recommend changing it to something like:

"Find the minimal path sum, in matrix.txt (right click and "Save Link/Target As..."), a 31K text file containing a 80 by 80 matrix stored in row major order [1], from the left column to the right column."
omg, sooooo much this. I spent at least 6 hours frustratingly trying to debug this. I went over my algorithm a dozen times, and was convinced there weren't any bugs. I created test matrix by hand with any possible scenario I could think of that might somehow be an issue. Worked every time. Thank god I finally broke down and googled for help and found this. As this was the issue. I can't fathom how this hasn't happened to more people, as the wording of the problem seems pretty clear and that each line of the text file represents the elements of a column, from left to right.

Even if you don't want to change the wording, just adding a link to the test text file would make it clear.

lol, I'm equal parts relieved I can finally let this go, and annoyed at all that time I wasted.

I suppose a learned a lesson at least, even when I'm 100% positive the input isnt the issue, change it anyway!

Junglemath
Posts: 14
Joined: Fri Sep 20, 2019 12:25 pm

Re: Problem 082

Post by Junglemath » Sun Nov 03, 2019 2:02 pm

In the given text file that contains the matrix, are the entries given as columns or as rows? That is, are the first 80 numbers the first row, the second 80 numbers the second row, ..., or are the first 80 numbers the first column, the second 80 numbers the second column, ...?

LilStalker
Posts: 64
Joined: Thu Nov 03, 2016 4:32 pm

Re: Problem 082

Post by LilStalker » Tue Nov 05, 2019 12:53 pm

They are given as rows. So the first row in the text file is the first row of the matrix and so on.
Image

Junglemath
Posts: 14
Joined: Fri Sep 20, 2019 12:25 pm

Re: Problem 082

Post by Junglemath » Thu Nov 07, 2019 3:08 pm

Finally got this one after trying to figure out what was wrong when I knew my code was correct. Admins, please add a line of clarification in the problem statement, namely one that specifies that the entries in the attached matrix are given as rows and not columns. This might save many people from frustration and despair in the future.

LilStalker
Posts: 64
Joined: Thu Nov 03, 2016 4:32 pm

Re: Problem 082

Post by LilStalker » Sat Nov 09, 2019 10:17 am

Doesn't it make the most sense that the row in a file corresponds to a row in a matrix?
Image

Post Reply