Problem 018

[jaap]

Have you read the rest of this thread, in particular this post? The simple greedy algorithm is not good enough.

[martix]

Ever played any games?
Ever wondered how units know how to get to the destination you ordered them to?
Just a couple of questions to ponder.

[gbutzi]

I'm having a curious error with my algorithm for this problem.

I'm stuffing the number triangle into an array. The array is being populated without any errors; I can print it with no problems and reproduce the triangle exactly.

However, when the elements are being looked at in the function, the array is improperly populated. Specifically, every value is zero EXCEPTING those values for which the horizontal index and the vertical index is identical ( (0,0), (1,1) ... (14,14).) So the right most values are all accessible, but everything else is zero. Naturally, my program will thus only give me the sum of the elements along the right hand side, which is clearly incorrect.

I can't figure out the inconsistency, why the array is populated when it's being called to print in nested for loops, but vacant in a function. I'm coding in Java using Eclipse. If anybody has thoughts or wants to examine the code, I'm happy to send it to you.

Edit: Never mind, figured it out. The indexes were reversed, so it was only looking at the unpopulated top-right half of the array, plus the line where the two parts overlap.

[pimspelier]

I think I know the right algorithm, but I have no idea how to read the triangle: the only method I can think of, is manually...
I use C.

Could anyone help me?

[thundre]

I think I know the right algorithm, but I have no idea how to read the triangle: the only method I can think of, is manually...
I use C.

Could anyone help me?

I copied from my web browser and pasted into my code editing window, then turned it into a 2-D array. Here it is in Java:

Code: Select all

    public static final int TRIANGLE15[][] = {
        {75},
        {95,64},
        {17,47,82},
        {18,35,87,10},
        {20,04,82,47,65},
        {19,01,23,75,03,34},
        {88,02,77,73,07,63,67},
        {99,65,04,28,06,16,70,92},
        {41,41,26,56,83,40,80,70,33},
        {41,48,72,33,47,32,37,16,94,29},
        {53,71,44,65,25,43,91,52,97,51,14},
        {70,11,33,28,77,73,17,78,39,68,17,57},
        {91,71,52,38,17,14,91,43,58,50,27,29,48},
        {63,66,04,68,89,53,67,30,73,16,69,87,40,31},
        {04,62,98,27,23, 9,70,98,73,93,38,53,60,04,23}
    };

[pimspelier]

Thanks!

[casperyc]

I have to say that the example given in this question is a bit miss leading. But to be fair, the question is CLEAR enough.

[HappyS5]

Hello,

I am confused. Can we only go to the largest number out of the two below the apex or can we go to the side as well?

[vamsikal3]

<deleted post>

[HappyS5]

Hello,

I am new to C++ and let's say I am ignorant of all programming but I like coming here for the problem solving practice.

if I have:
77
69 78
56 89 90
45 34 79 70

I would pick 77, 78, 90, 79. Could I have gone. 77, 78,90, 89, 79?

[hk]

No, 89 and 90 are on the same row.

[Ashkaji_tg]

I thin'k I've found the solution of the 18th problem but verifying the result, my solution is in harmony with the given example, it is thought that I'm wrong. Finally, I think the problem came from my conception of adjacent numbers.
I would be grateful if someone can explain me what is called adjacent numbers.

[hk]

Please don't start a new topic for a problem it there exists already one.

[DJohn]

I thin'k I've found the solution of the 18th problem but verifying the result, my solution is in harmony with the given example, it is thought that I'm wrong. Finally, I think the problem came from my conception of adjacent numbers.
I would be grateful if someone can explain me what is called adjacent numbers.

"Adjacent" just means "next to each other".

From any number in the triangle you can move to one of two others: the one immediately to the left on the next row, or the one immediately to the right on the next row. So if you're on the 47 in the third row, you could go to the 35 or 87 in the fourth row, but not to the 18 or 10, and not to any of the numbers on the fifth row.