Page 1 of 3
Problem 018
Posted: Mon Jan 14, 2008 8:24 pm
by babel-17
Hello all!
I'm having problems with understanding problems 18 and 67 (calculating maximum totals in given triangles). I tried submitting solutions during several days to eliminate server problems from the last few days, but they are rejected, so my reasoning is probably wrong.
My reasoning was: put top number to the list we sum later, start at the top, take two numbers below the top one and return the greater one. Store the greater to the list. On the next loop iteration, start with last number taken, examine two numbers below that one, take greater one, and store it to the list. Repeat for all rows. At the end sum all numbers stored in the list. I checked the list of numbers I got from the program manually verifying that the problem is doing the right thing. And it works as I expect it to work: it extracts the same numbers which I extracted manually. And it works on small test triangle. But, still solutions are not accepted.
So, what to do next? Should I post my solution here for review, or is there another triangle with given solution that I can test my program with? Or my reasoning is dead wrong?
Thanx for help!
Re: Clarification on problems 18 and 67
Posted: Mon Jan 14, 2008 8:27 pm
by daniel.is.fischer
I have a few triangles (and a triangle maker) somewhere, have to look for it and then will post an example with solution.
Re: Clarification on problems 18 and 67
Posted: Mon Jan 14, 2008 8:32 pm
by babel-17
I hope it will be helpfull.. Thanx!
Re: Clarification on problems 18 and 67
Posted: Mon Jan 14, 2008 8:44 pm
by daniel.is.fischer
Here goes:
77
37 90
03 69 81
95 64 43 18
05 78 38 91 43
16 75 38 63 20 98
58 39 54 28 30 43 42
79 36 54 63 41 94 21 80
65 14 18 18 52 07 68 95 11
38 23 25 22 62 07 30 78 82 10
66 85 99 33 71 11 71 31 45 91 08
45 73 30 20 20 18 41 78 53 44 82 39
73 48 11 37 64 50 31 35 71 01 73 62 71
31 93 84 63 54 38 78 90 30 61 16 61 04 96
60 98 79 66 12 74 04 18 03 36 12 32 35 40 65
Best path has value 1048.
Re: Clarification on problems 18 and 67
Posted: Thu Jan 17, 2008 8:26 am
by babel-17
Thank you for help!
Now I see that I was completely wrong. I will work on new solution.
Problem 18
Posted: Sat Nov 08, 2008 12:09 am
by MaJJ
Hi,
I tried to solve problem 18 - I did my program, it threw a result, and I am pretty sure it's correct (tried to solve it on paper and result was the same), but that "problem page" says it's wrong. Isn't something with it?
http://projecteuler.net/index.php?secti ... lems&id=18
EDIT: Maybe I just misunderstood the problem. For example, look at this:
Right now, my program is looking just for max(6,8) - that's 8 ... and then it's looking for max(1,2) - that's 2 ... and the sum is 11.
But if the problem wants me to look for a "maximal route" ? Like 1 + 6 + 9 (the 6 is smaller than 8, but it's compensated becouse of that 9) ... and the sum is 16.
So, what should I look for? "Maximal route" (uh-oh 
) or maximal of two adjacent numbers?
Re: Problem #18
Posted: Sat Nov 08, 2008 1:12 am
by btilly
Maximal route.
A greedy algorithm will not find it.
Re: Problem #18
Posted: Sun Nov 09, 2008 10:59 pm
by uws8505
btilly wrote:A greedy algorithm will not find it.
But I used some variation of greedy algorithm to get to the solution and solved it.
Re: Problem 018
Posted: Tue May 05, 2009 2:27 pm
by giampiz
I am having problem too with problem 018.
The solution I put is 1020, but it seems to be wrong.
I tried the triangle example proposed in this thread and the solution is 1048 as expected.
Is the problem mine or of the interface checking for answer?
Thanks
Giampiero from Florence (Italy)
Re: Problem 018
Posted: Tue May 05, 2009 2:38 pm
by Tommy137
giampiz wrote:Is the problem mine or of the interface checking for answer?
1020 isn't the maximum sum.
Re: Problem 018
Posted: Tue May 05, 2009 2:47 pm
by giampiz
1020 isn't the maximum sum
thanks for your kind reply
mmm, so my program is falling in a "special case" error, going right on the triangle in this thread and going wrong on problem 018
ciao
Problem fixed; algorithm was ok, but there was a "dirty" variable
Problem 018 Sample
Posted: Sun Jun 28, 2009 3:22 am
by r-dog
Since Problem 018 is still active ( new solvers continue to accumulate ),
you might consider minor rewrite:
Problem 018 implies a single answer in the sample: "That is, 3 + 7 + 4 + 9 = 23."
An alternate valid answer is: "( or 3 + 5 + 6 + 9 = 23 )."
Might be easier to change sample triangle slightly to validate single answer as stated currently !
Re: Problem 018 Sample
Posted: Sun Jun 28, 2009 12:39 pm
by yashkochar
Since the final answer only asks for the maximum total and not the number of paths to get it, I don't think it is necessary to change the example.
Re: Problem 018
Posted: Tue Feb 02, 2010 1:48 am
by Jae
HI Guys !
I am new to project euler and i am now going thru some of the problems and developing my algorithms. I looked at the example for problem 18 and the max is 3+7+4+9 but should it not be 3+7+6+9 or is it that i do not understand the problem. let me know if the example is indeed correct, and if it is in that case i will have to rewrite my algorithm .
Jae
Re: Problem 018
Posted: Tue Feb 02, 2010 3:09 am
by rayfil
If you read the problem carefully, you will notice as part of the description:
and moving to adjacent numbers on the row below
And then, looking at the example, you should realize that the 6 in the 3rd row is NOT adjacent to the 7 in the 2nd row.
Re: Problem 018
Posted: Tue Aug 31, 2010 11:15 am
by Mantithetical
Hello Everyone,
My method is similar to babel17's:
put top number to the list we sum later, start at the top, take two numbers below the top one and return the greater one. Store the greater to the list. On the next loop iteration, start with last number taken, examine two numbers below that one, take greater one, and store it to the list. Repeat for all rows. At the end sum all numbers stored in the list. I checked the list of numbers I got from the program manually verifying that the problem is doing the right thing. And it works as I expect it to work: it extracts the same numbers which I extracted manually. And it works on small test triangle. But, still solutions are not accepted.
Needless to say, it doesn't seem to be working. Could someone tell please me what is wrong with my reasoning?
Edit by hk (1 sep 13:00): code snipped.
Re: Problem 018
Posted: Tue Aug 31, 2010 11:28 am
by hk
Mantithetical,
did you read this sticky topic:
viewtopic.php?f=50&t=1356#p12839
Re: Problem 018
Posted: Tue Aug 31, 2010 11:35 am
by Lord_Farin
Besides the fact that this forum is not for posting code (it's a public forum, please remove your code), your code is failing because it's built on a greedy algorithm. It fails for the following triangle:
01
02 01
01 01 09
01 01 01 09
Where it returns 5 instead of 20 as the optimal result. Consider another algorithm please
Problem 018
Posted: Thu Sep 16, 2010 8:29 am
by DaveRich
Here goes my first forum post on projecteuler.net
I am under the impression that I can not post any code, but that posting the output of my program is alright.
The program was done in java, and it "compiles" and runs fine, the problem is the answer it spits out is wrong, and I can see where the program errs, I just can't for the life of me figure out why. I've run through my loops on pen and paper, and don't know what to do.
The output of my program is:
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 Back: 77 Last Position: 2
Moved Down: 73 Last Position: 2
Moved Back: 65 Last Position: 1
Moved Forward: 28 Last Position: 2
Moved Forward: 56 Last Position: 3
Moved Back: 72 Last Position: 2
Moved Forward: 47 Last Position: 3
Moved Down: 65 Last Position: 3
Moved Forward: 77 Last Position: 4
Moved Back: 38 Last Position: 3
Moved Down: 17 Last Position: 3
Moved Forward: 89 Last Position: 4
Moved Back: 27 Last Position: 3
Moved Down: 23 Last Position: 3
The largest sum using adjacent squares is: 1215
Press any key to continue . . .
Move Down => Indicates no change in the index value of the greatest available number in the line.
Move Forward => Index number increments so largest available value on the previous line was in position 2, now it's in position 3 on the current line, etc.
Move Backward => Opposite of moves forward.
As you can see with the output of each step my program takes sometimes it's okay, and sometimes it spits out random values.
Code: Select all
Move Forward: 75 //VALID MOVE
Move Down: 77 //VALID MOVE
Move Down: 73 //73 Falls on the same line as 77? What's going on!?
The basic premise of my code for solving the largest sum is
Go through each line of the triangle,
On each line, check the number in the same position as the previous highest value, the position before it, and the position after it.
Take the highest of these three values and add it to the sum.
Increase/Decrease/Leave the position of the previous highest value accordingly.
Re: Problem 18 - Wrong Solution...
Posted: Thu Sep 16, 2010 8:38 am
by Lord_Farin
First of all, Move Backward is not allowed. It would require a knight's move to do that in the setting of
Problem 18 (
View Problem)
Second, what does your program do with
?
And last, a thread for problem 18 already exists. For other problems, please search first if there already exists a thread (usually it does)
I request the moderators to move this to the appropriate forum.