## 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

Don't post any spoilers
Raman
Posts: 15
Joined: Sun Nov 28, 2010 1:40 pm
Location: Chennai, India

### Problem 082

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.

Raman2.png (6.36 KiB) Viewed 7210 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.

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

### Re: Problem 082

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

Hello,

Since you are still level 3, i guess you haven't found your error yet.

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.
Joined PE in May 2011

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

### Re: Problem 082

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 (6.25 KiB) Viewed 6968 times

hk
Posts: 10678
Joined: Sun Mar 26, 2006 9:34 am
Location: Haren, Netherlands

### Re: Problem 082

Raman,

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

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

### Re: Problem 082

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

fabas indulcet fames

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

### Re: Problem 082

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

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

### Re: Problem 082

994
1309
1420
2376
2222

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

fabas indulcet fames

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

### Re: Problem 082

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

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

### Re: Problem 082

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

fabas indulcet fames

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

### Re: Problem 082

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

Hibernatus34 wrote:Hello,

Since you are still level 3, i guess you haven't found your error yet.

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!

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

### Problem 82

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
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

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

sjhillier
Posts: 511
Joined: Sun Aug 17, 2014 3:59 pm
Location: Birmingham, UK
Contact:

### Re: Confusing Wording in Problem 82

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

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: 27
Joined: Fri Sep 20, 2019 12:25 pm

### Re: Problem 082

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: 65
Joined: Thu Nov 03, 2016 4:32 pm

### Re: Problem 082

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

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

### Re: Problem 082

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: 65
Joined: Thu Nov 03, 2016 4:32 pm

### Re: Problem 082

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