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


See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
Post Reply
ParadiceCity9
Posts: 15
Joined: Sat Dec 17, 2011 7:15 pm
Location: Charlottesville, Virginia

Problem 081

Post by ParadiceCity9 »

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

Post by thundre »

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

Re: Problem 081

Post by ParadiceCity9 »

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

Post by thundre »

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.
Image
jlillest
Posts: 1
Joined: Sat Jun 22, 2013 10:06 pm

Problem 81

Post by jlillest »

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
User avatar
RishadanPort
Posts: 78
Joined: Mon Jun 10, 2013 7:31 am

Re: Problem 81

Post by RishadanPort »

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

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

Re: Problem 081

Post by rayfil »

@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.
User avatar
solarmew
Posts: 42
Joined: Thu Jan 01, 2015 3:52 pm

Re: Problem 081

Post by solarmew »

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
failwhale.jpg (465.26 KiB) Viewed 4304 times
Image
366541_5799d51e95657e1a227f2cb86bd181de
User avatar
angzhiping
Posts: 32
Joined: Sat Aug 09, 2014 3:51 pm
Location: Jurong East, Singapore
Contact:

Re: Problem 081

Post by angzhiping »

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?
Image
170825_b3d528c2bf87aaeff2a0ff93382fba94
User avatar
solarmew
Posts: 42
Joined: Thu Jan 01, 2015 3:52 pm

Re: Problem 081

Post by solarmew »

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...
Image
366541_5799d51e95657e1a227f2cb86bd181de
srinathmkce
Posts: 5
Joined: Fri Jun 19, 2015 2:50 pm

Re: Problem 081

Post by srinathmkce »

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 ?
User avatar
jaap
Posts: 554
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: Problem 081

Post by jaap »

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