Conversation started Feb 24, 2017 at 15:19.
Feb 24, 2017 15:19
did you solve the triangle problem @Hemlata
user6857832
@motaa Yes
with the tree data structure?
user6857832
Nah lol
you went for the bruteforce method? :D
user6857832
Took the max of two till n and then which one was max added with the current number.
user6857832
Feb 24, 2017 15:21
And did till it reached the top of the node and took off that number of the node.
so you started at the bottom?
user6857832
I started at the top first, but again I was having the index problem. So I started at the bottom.
it is still this problem right? projecteuler.net/problem=18
user6857832
Yes
I think that might not work properly :)
user6857832
Feb 24, 2017 15:23
It is working
what happens if you got like 10 rows
user6857832
It will still do the same
3
7 4
2 4 6
8 5 9 3
5 5 5 5 5
6 6 6 6 6 6
will that triangle work aswell?
user6857832
Yes
user6857832
Start at line 5 5 5 5 5 5
user6857832
Feb 24, 2017 15:25
Check for max in last line
user6857832
And add up to the current no which is 5
user6857832
So 5th line will be 11 11 11 11 11
user6857832
Then do again, So 4th line will be 19 16 20 14
@Hemlata that's a crazy idea, but I'm glad it works. :)
I still don't think it will work properly :)
user6857832
Feb 24, 2017 15:28
Now 3rd line will be 21 24 26
user6857832
Now 2nd line will be 31 30
user6857832
And 1st line will be 34
user6857832
So 34 is a answer
take this triangle:
3
7 1
0 1 9
I edited the triangle
will this one work?
user6857832
Is that all or you gonna add more rows?
user6857832
Feb 24, 2017 15:30
Yes
nope thats all
result?
user6857832
2nd line will be 8 10
user6857832
13 is answer
so it does not work:P
the answer should be 11
user6857832
Did you ran it?
Feb 24, 2017 15:32
@motaa 3+1+9 != 11
then reread the problem again pls :)
user6857832
Did you ran it?@motaa
@Hemlata what do you get for this triangle?
what is your result on this:


3
7 4
2 4 6
8 5 9 3
user6857832
@JonahSloan I can't calculate it myself. I need to run it.
user6857832
Feb 24, 2017 15:34
@motaa Wait let me calculate
user6857832
10 13 15 -> 3rd line
user6857832
20 19 -> 2nd line
@JonahSloan the path is actually not 3+1+9 but 3+7+1
user6857832
23
user6857832
23 is answer
user6857832
Feb 24, 2017 15:36
@JonahSloan I will tell the answer in a bit when I will be using laptop
Why wouldn't the path be 3+1+9 on that? Doesn't the problem want the highest possible sum?
no
reread the problem pls:)
user6857832
@Leathe It is 3 + 1 + 9
user6857832
Let me run his code to make sure
By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.
user6857832
Feb 24, 2017 15:39
@motaa Yeah, that's what I said
user6857832
23 is the answer
that's the line from the example, right?
yes
that means you start at the top which is 3
user6857832
But you don't need to start at the top
user6857832
If you'll start at the bottom that is better approach
Feb 24, 2017 15:41
3
7 1
0 1 9

but how you get the wrong result on this triangle?
user6857832
Can you prove me my answer is wrong?
user6857832
Or give me the link where you see this example with the answer
let me explain it one more time given the above example:
you start at top -> 3
go straight dow one line and check the adjacent values which are 7 and 1
user6857832
No, it's wrong that's how I was doing earlier, but then I realized you're not supposed to do it like that.
Am I missing something here? 3+1+9 = 13, 3+7+1 = 11, 13 is higher, how is that not the right answer then?
Feb 24, 2017 15:42
there you take the max
now from 2 down 2 adjacent numbers are 0 and 1
so you add 1
ooh
1 and 9 are the adjacent numbers of 1 from line 2
But it's asking for the maximum total, not the maximum adjacent number, tho
0 and 1 are the adjacent numbers from 7 oout of line 2
user6857832
No, you're wrong @motaa
Feb 24, 2017 15:44
first line of the problem explains it
LOOK AT THE ADJACENT NUMBERS!
user6857832
I will ask you one question, wait.
user6857832
1
2 1
1 1 100
user6857832
@motaa
result 4
user6857832
What is the answer of it?
user6857832
Feb 24, 2017 15:46
Wrong
user6857832
102 is the answer.
says your script? :D
user6857832
Nah, I will show you wait.
user6857832
http://stackoverflow.com/a/4772620/6857832
Have a look at it
There's no limitation in the problem that says you have to take the highest adjacent number, unless I can't read
user6857832
Feb 24, 2017 15:47
It's correct
user6857832
@motaa
The problem says "Find the maximum total from top to bottom of the triangle"
user6857832
@JonahSloan You can start from the bottom to top, It doesn't matter.
user6857832
Plus I read a bit on it and it says bottom approach is more better.
user6857832
But it will work from top to bottom as well
user6857832
Feb 24, 2017 15:50
@motaa You are doing the same mistake which I was doing it eariler.
user6857832
We don't have to just check the adjacent number. We need to check for every number and take the maximum of them.
I guess it'd be easier to say the numbers from the current line + 2 rows aren't hidden, they're still known and a high number should be considered as a viable path.
In a triangle with 3-4 rows that is.
well at the first part of the problem description it says that one should look at the adjacent numbers on the row below
It says you should move to an adjacent number
Like checkers
user6857832
Feb 24, 2017 15:53
@motaa But it should look at all the numbers.
Meaning in @Hemlata's example with the 100 at the bottom, you can't go 1+2+100, because 2 and 100 aren't adjacent, but the 100 is the biggest number and has the highest impact on the total and should therefore be considered above the 2.
leaving
bye
o/
bye
user6857832
@Leathe Yes
Meaning the problem is much deeper than going 1 row down and checking the highest number, rinse and repeat.
Feb 24, 2017 15:56
yes @Leathe but still it strucks me that the problem states one should check the adjacent numbers which of course would not ask for the absolut maxsum path
 
Conversation ended Feb 24, 2017 at 15:56.