## Problem 081

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
Posts: 15
Joined: Sat Dec 17, 2011 7:15 pm
Location: Charlottesville, Virginia

### Problem 081

Hello,

I'm having trouble with this problem. My algorithm works just fine for the small sample matrix and seems to be working how I think it should. Is it fair to say that once either the row number or the column number equals 0 (with the matrix going from 0 to 79), you add up the numbers going up the side that you have reached? That's the only problem I can think of with my code.

Thanks
thundre
Posts: 356
Joined: Sun Mar 27, 2011 10:01 am

### Re: Problem 081

ParadiceCity9 wrote:I'm having trouble with this problem. My algorithm works just fine for the small sample matrix and seems to be working how I think it should. Is it fair to say that once either the row number or the column number equals 0 (with the matrix going from 0 to 79), you add up the numbers going up the side that you have reached? That's the only problem I can think of with my code.
Yes, you must get to the bottom right corner using only right and down directions, so when you hit a side (right or bottom), you must add all of the numbers from there to the corner. For an 80x80 matrix, it will always be 159 numbers total.

I think most programmers use (0,0) for the top-left square.
Posts: 15
Joined: Sat Dec 17, 2011 7:15 pm
Location: Charlottesville, Virginia

### Re: Problem 081

I'm getting 159 numbers is the thing. Would you mind taking a look at my code? It's in Java so it should be fairly easy to read/understand.
thundre
Posts: 356
Joined: Sun Mar 27, 2011 10:01 am

### Re: Problem 081

I'll look at the code, if you include an explanation of your solution and I agree that the algorithm you explain will solve the problem.
jlillest
Posts: 1
Joined: Sat Jun 22, 2013 10:06 pm

### Problem 81

Does anybody have any suggestions for solving Problem 81?

I have set up a binary tree to traverse every possible path, but brute-forcing it like this looks like it will take a while. Would something like Dijkstra's algorithm be a good fit for this problem?

I've been running my code for a few hours now and it looks like I have a long time to go.

Thanks,
-Jon
Posts: 78
Joined: Mon Jun 10, 2013 7:31 am

### Re: Problem 81

Funny.

I just solved this one like 2 minutes ago. Not a very terribly difficult problem to do -- a very basic Dynamic Programming problem...

I suggest you to do a bit of research on DPs. -- Think about how you can break this problem down into sub problems.

Rishada is the gateway to free trade—but the key will cost you.
rayfil
Posts: 1406
Joined: Sun Mar 26, 2006 5:30 am
Contact:

### Re: Problem 081

@jlillest

FYI, problem numbers below 100 are padded with leading 0's to make then 3-digit numbers. You may then find that answer already exists to your question(s) in many cases by searching the proper topic.
When you assume something, you risk being wrong half the time.
solarmew
Posts: 42
Joined: Thu Jan 01, 2015 3:52 pm

### Re: Problem 081

Just wanted to share my failed attempt at solving this XD (one from top left corner down and one from bottom right corner up) ... cutting and patching the two "minimized" trails together didn't work either XD grrr ... couldn't make it an easy one, could you? XD
failwhale.jpg (465.26 KiB) Viewed 4304 times

366541_5799d51e95657e1a227f2cb86bd181de
angzhiping
Posts: 32
Joined: Sat Aug 09, 2014 3:51 pm
Location: Jurong East, Singapore
Contact:

### Re: Problem 081

solarmew wrote:Just wanted to share my failed attempt at solving this XD (one from top left corner down and one from bottom right corner up) ... cutting and patching the two "minimized" trails together didn't work either XD grrr ... couldn't make it an easy one, could you? XD
How do you come up with the "minimized" trail?
170825_b3d528c2bf87aaeff2a0ff93382fba94
solarmew
Posts: 42
Joined: Thu Jan 01, 2015 3:52 pm

### Re: Problem 081

Just a simple check if the number to the right(left) is smaller than the number above(below) the current position in the matrix, depending on which way you're going (staring on top or bottom). I didn't expect this to work because I figured that sometimes you would have to pick a higher number because the following sequence would contain smaller numbers, but just wanted to try the easy way first just in case...

366541_5799d51e95657e1a227f2cb86bd181de
srinathmkce
Posts: 5
Joined: Fri Jun 19, 2015 2:50 pm

### Re: Problem 081

i tried applying djikstra algorithm for this problem

in the 5x5 matrix till the index (3,2) algorithm is working fine .

However, wrong number is getting picked for the neighbor of (3,2)

i.e. (3,2) has two valid neighbor node.

Right (4,2) = 111
Down(3,3) = 121

When we calculate distance till (3,2) = 131 + 201 + 96 + 342 + 746 + 422 = 1938

Now, we need to select either right or down node. since right node has lesser weight(111) , my algorithm is selecting it .

and the answer is printing as 1938 + 111 + 956 + 331

However, the path that should be taken is 1938 + 121 + 37 + 331 and this is the minmal path.

Can someone correct my understanding ?
jaap
Posts: 554
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

### Re: Problem 081

srinathmkce wrote:Can someone correct my understanding ?
I sent a private message with some explanation.