Problem 018

[hk]

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.

[DaveRich]

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.

[hk]

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.

[matthewden]

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

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?

[TripleM]

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

[matthewden]

OK, I think I get it. Thanks!!

[TyrReich]

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.

[hk]

* replaced by *

[Metalith]

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.

[jaap]

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

[kevinsogo]

* replaced by *

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

[Metalith]

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

[jaap]

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.

[stijn263]

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

[Susanne]

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.

[Metalith]

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.

[GenePeer]

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.

[grodrigues3]

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?

[Lord_Farin]

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

[SimonO1992]

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