Project Euler Forum

Posted: **Thu Sep 16, 2010 11:43 am**

Lord_Farin wrote:I request the moderators to move this to the appropriate forum.

Done.
@Dave Rich: you can sort the topics by subject. That's why you should name a new topic here: Problem xxx.
In this case that would have been: Problem 018. But please lookup if there exists such a topic before creating one.

Posted: **Thu Sep 16, 2010 3:37 pm**

Thanks for the help

I Will post in the correct forum from now on

.

I thought "Move Backward" was allowed.

But I realized because the triangle is getting wide, and position 0 becomes farther left each line, you can never decrement your position index.

However, when I remove the MoveBackward functionality in my program, my answer is off by * in the solution.

My output is now as follows:

Code: Select all

  75   0   0   0   0   0   0   0   0   0   0   0   0   0   0
  95  64   0   0   0   0   0   0   0   0   0   0   0   0   0
  17  47  82   0   0   0   0   0   0   0   0   0   0   0   0
  18  35  87  10   0   0   0   0   0   0   0   0   0   0   0
  20   4  82  47  65   0   0   0   0   0   0   0   0   0   0
  19   1  23  75   3  34   0   0   0   0   0   0   0   0   0
  88   2  77  73   7  63  67   0   0   0   0   0   0   0   0
  99  65   4  28   6  16  70  92   0   0   0   0   0   0   0
  41  41  26  56  83  40  80  70  33   0   0   0   0   0   0
  41  48  72  33  47  32  37  16  94  29   0   0   0   0   0
  53  71  44  65  25  43  91  52  97  51  14   0   0   0   0
  70  11  33  28  77  73  17  78  39  68  17  57   0   0   0
  91  71  52  38  17  14  91  43  58  50  27  29  48   0   0
  63  66   4  68  89  53  67  30  73  16  69  87  40  31   0
   4  62  98  27  23   9  70  98  73  93  38  53  60   4  23


Moved Down:     75              Last Position: 0
Moved Down:     95              Last Position: 0
Moved Forward:  47              Last Position: 1
Moved Forward:  87              Last Position: 2
Moved Down:     82              Last Position: 2
Moved Forward:  75              Last Position: 3
Moved Down:     73              Last Position: 3
Moved Down:     28              Last Position: 3
Moved Forward:  83              Last Position: 4
Moved Down:     47              Last Position: 4
Moved Forward:  43              Last Position: 5
Moved Down:     73              Last Position: 5
Moved Forward:  91              Last Position: 6
Moved Down:     67              Last Position: 6
Moved Forward:  98              Last Position: 7

The largest sum using adjacent squares is: {skipped by hk]
Press any key to continue . . .

And with the small sample triangle I get the output:

Code: Select all

   1   0   0   0
   2   1   0   0
   1   1   9   0
   1   1   1   9


Moved Down:     1               Last Position: 0
Moved Down:     2               Last Position: 0

The largest sum using adjacent squares is: 3
Press any key to continue . . .

I have found out my main problem (among other things), is that I am only looking at the next row, and picking the best available value, when in fact, there is one row in the triangle where you have to choose the lower immediate value, in order to reach the maximum sum overall in the triangle. Have to rethink my approach here.

Posted: **Thu Sep 16, 2010 7:34 pm**

I skipped the final answer from your results.
If you post results and say that the final answer is off by *, that seems to me like shouting what the answer is.

As long as the example you are trying gives obvious wrong results, please refrain from posting other results.

Posted: **Mon Oct 04, 2010 10:57 pm**

I am have my program pick the bigger number in the "number triangle", and am getting the same maximums that DaveRich is getting.

DaveRich wrote:I have found out my main problem (among other things), is that I am only looking at the next row, and picking the best available value, when in fact, there is one row in the triangle where you have to choose the lower immediate value, in order to reach the maximum sum overall in the triangle. Have to rethink my approach here.

I don't understand that (the part in red). If you pick a lower number over a greater number, and you don't check every path, then how would you know if you got the maximum path?

Should I be looking two steps ahead?

Posted: **Mon Oct 04, 2010 11:11 pm**

Even two steps ahead won't be enough. Imagine a very large grid where every number is 1 except for a 100 somewhere a long way down.

You need to come up with an algorithm that guarantees you find the best path regardless of how many 'steps ahead' you look. There is a way of doing that without checking every single path by itself; and coming up with that idea is the whole point here so I can't really give you too many hints

Posted: **Wed Oct 06, 2010 1:04 pm**

OK, I think I get it. Thanks!!

Posted: **Mon Jan 24, 2011 4:24 pm**

hk wrote:I skipped the final answer from your results.
If you post results and say that the final answer is off by *, that seems to me like shouting what the answer is.

As long as the example you are trying gives obvious wrong results, please refrain from posting other results.

HK, you're doing the same. I solved it with your inadvertent hint. I'm going to keep tweaking my program until I get it correct though.

Posted: **Mon Jan 24, 2011 7:39 pm**

* replaced by *

Posted: **Mon Jan 31, 2011 8:47 pm**

This is probably gonna seem really stupid, but I have no clue where to go with this problem if greedy algorithms dont work. If someone could provide me with a little enlightenment it would be great.

Posted: **Tue Feb 01, 2011 9:14 am**

Metalith wrote:This is probably gonna seem really stupid, but I have no clue where to go with this problem if greedy algorithms dont work. If someone could provide me with a little enlightenment it would be great.

Have you done Problem 15 (View Problem)?

Posted: **Tue Feb 01, 2011 12:47 pm**

hk wrote:* replaced by *

the "off by *" text is still referenced in DaveRich's post.

Posted: **Wed Feb 02, 2011 8:41 am**

I have done problem 15, but thats just finding the number of routes though.

Posted: **Wed Feb 02, 2011 9:17 am**

Metalith wrote:I have done problem 15, but thats just finding the number of routes though.

And this is just finding the max value of the routes.

Posted: **Wed Feb 02, 2011 10:08 am**

It's an excellent problem to learn the first basics of Dynamic Programming, a technique that'll help you solve quite a few PE problems

Posted: **Wed Feb 02, 2011 9:14 pm**

Perhaps it also can be helpful for you to look what would be the maximal possible sum if the triangle just had 1, 2, 3, 4, ... rows.

Posted: **Thu Feb 03, 2011 10:51 pm**

Im afraid I still dont see the relation between 15 and 18. sorry I dont mean to seem hard headed

. However Im looking up dynamic programming right now.

Posted: **Thu Feb 03, 2011 11:24 pm**

Metalith wrote:Im afraid I still dont see the relation between 15 and 18. sorry I dont mean to seem hard headed . However Im looking up dynamic programming right now.

If you used brute-force to find the number of paths in 15, then a similar brute-force could go through all the paths in the triangle. For each path, calculate the sum of its numbers, etc. This is a poor solution though, you're better off with dynamic programming which is more powerful and can work on bigger triangles.

Posted: **Thu Jun 16, 2011 4:15 pm**

I think I have an understanding of how to approach the optimization/summation problem, but I'm having some difficulty with the coding.
It seems intuitive to build a tree for this problem, and I can't figure out how to do it using the list that I read in. I read the data in as a list of lists [ [row1], [row2],...[row15]]. My initial approach was to make a node with the value, a left child (another node) and a right child (another node). The left child simply takes in the same list but starting at the next row. The right child takes in the same list but with the first element of each row removed. It's an ugly loop. Can anyone suggest a better approach?

Posted: **Thu Jun 16, 2011 4:44 pm**

grodrigues3 wrote:... The left child simply takes in the same list but starting at the next row. The right child takes in the same list but with the first element of each row removed. It's an ugly loop. Can anyone suggest a better approach?

I read this as if you are duplicating elements since they mostly occur both as left, and as right node. This will eventually vastly increase the necessary memory. You might want to consider hard-coding the list indices you use, instead of using a data type (the tree) that is not really suited for the allowed operations. That's about all I can say before I feel like spoiling...

Posted: **Wed Jul 27, 2011 3:31 pm**

Hi,

I'm certain I have figured the algorithm out for this question, yet I am getting an incorrect answer from it.

If I am to do this in my head I would do the following: (Sorry if I can't show this calculation, but this is annoying me)

75+95+47+87+82+75+73+28+83+47+43+73+91+67+98 = 1064

This answer is incorrect(for the problem) but in my head is the way in which this problem is completed.

Can somebody please give me a hint or tip as to what may be going wrong?

Thanks
Simon

Project Euler Forum

Problem 018

Re: Problem 18 - Wrong Solution...

Re: Problem 018

Re: Problem 018

Re: Problem 018

Re: Problem 018

Re: Problem 018

Re: Problem 018

Re: Problem 018

Re: Problem 018

Re: Problem 018

Re: Problem 018

Re: Problem 018

Re: Problem 018

Re: Problem 018

Re: Problem 018

Re: Problem 018

Re: Problem 018

Re: Problem 018

Re: Problem 018

Problem 018