Project Euler: Problem 18

Page 1 of 1

5 Replies - 3205 Views - Last Post: 25 November 2011 - 04:12 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=257104&amp;s=8f5fb3d6aeb67500464ee10a8f38795c&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

#1 gbertoli3

• DIC at Heart + Code

Reputation: 41
• Posts: 1,166
• Joined: 23-June 08

Project Euler: Problem 18

Posted 24 November 2011 - 11:19 PM

I recently stumbled upon ProjectEuler.net and started problem 18 today. I have spent many hours on this problem. I am very close to the answer. First I designed my algorithm and then I ran it tweaking it until it "should" be working. And as far as I can tell it "should" work, but it doesn't. Since this has frustrated me so much I looked up the answer to see how far off my algorithm is. **SPOILER START** The answer is 1074, my algorithm gives me 1064 **SPOILER END** I even went through the triangle line by line with my calculator and come up with the same number.

Here is my code, can anyone tell me where/why my algorithm is not accounting for the extra 10.
I do know that this code can be greatly shortened, but I'd rather keep it like this because I don't understand the other(much shorter) ways.
```def solve18
current_line = 0
current_index = 0

numbers_below(current_line, current_index)
end

def numbers_below(current_line, current_index)
total = 0
numsUsed = Array.new
new_index = current_index
while current_line < 15
next_line = current_line + 1
next_numbers = get_next_numbers(next_line, new_index)
a = next_numbers[0]
b = next_numbers[1]

# B will be nil when on the first line
# I put this here to make sure that A is greater than B
if a == nil
a = -1
elsif b == nil
b = -1
end

if a.to_i > b.to_i
total += a.to_i
numsUsed << a.to_i
new_index = next_numbers[2]
elsif b.to_i > a.to_i
total += b.to_i
numsUsed << b.to_i
new_index = next_numbers[3]
end
current_line = next_line
end
total
end

def get_next_numbers(next_line, current_index)
numbersArray = Array.new
# This file exists and contains all lines/numbers
triangle = File.open("triangle_problem18.txt", "r")
lines = triangle.gets.to_s.split('\n')
line = lines[next_line - 1]

numbers = line.to_s.split(' ')
for i in 0..numbers.length
if i == current_index
numbersArray << numbers[current_index]
numbersArray << numbers[current_index + 1]
numbersArray << current_index
numbersArray << (current_index + 1)
end
end
numbersArray
end

```

Any help would be greatly appreciated.

This post has been edited by gbertoli3: 25 November 2011 - 01:04 AM

Is This A Good Question/Topic? 0

Replies To: Project Euler: Problem 18

#2 Skaggles

• THE PEN IS MIGHTIER

Reputation: 255
• Posts: 641
• Joined: 01-March 09

Re: Project Euler: Problem 18

Posted 25 November 2011 - 12:30 AM

Are you just going down the triangle picking the largest adjacent number in the row below? Without giving you the solution, I would look at starting from the bottom and working your way up. In Ruby, using the max method helps when comparing integers and returning the greater value.

#3 gbertoli3

• DIC at Heart + Code

Reputation: 41
• Posts: 1,166
• Joined: 23-June 08

Re: Project Euler: Problem 18

Posted 25 November 2011 - 01:00 AM

Ah, I see what you are saying. As I look over the triangle again, I see that there are duplicates of some numbers in multiple rows. Now I realize why you have to flip the triangle upside down. Thanks, I really appreciate the help. I'll fix it in the morning.

#4 Karel-Lodewijk

Reputation: 454
• Posts: 864
• Joined: 17-March 11

Re: Project Euler: Problem 18

Posted 25 November 2011 - 06:37 AM

Both methods won't really work. Let me give an example

```     1
2   3
50  4   6

```

You're original algorithm will find 10 as the max sum while it is obviously 53. Starting from the bottom will work in this example but not in the following example.

```      1
50   3
2    4   6

```

The problem is that it can not be solved using a greedy algorithm as you've written. And the assignment says that trying all paths will become unfeasible, so what can we do ?

The important thing to notice is that all possible paths share common substructures. Let me give an example of 2 paths.

```      [b]1[/b]
[b]2[/b]   3
4   [b]5[/b]   6
7   [b]8[/b]   9   10

```

```      [b]1[/b]
2   [b]3[/b]
4   [b]5[/b]   6
7   [b]8[/b]   9   10

```

See how 5,8 is common to both paths. A naive algorithm will go over the sum of 5,8 twice. But we can design a much more efficient algorithm if we use the fact that a lot of the substructures are shared.

In fact there exist a class of algorithms called dynamic programming algorithms that can be used to solve problems that can broken down into overlapping subproblems efficiently. http://en.wikipedia....mic_programming

Here comes a short explanation about the top-down and bottom-up approach and how they can be applied to this problem.
Spoiler

A top-down implementation
Spoiler

This post has been edited by Karel-Lodewijk: 25 November 2011 - 07:33 AM

#5 Skaggles

• THE PEN IS MIGHTIER

Reputation: 255
• Posts: 641
• Joined: 01-March 09

Re: Project Euler: Problem 18

Posted 25 November 2011 - 01:22 PM

Very well written break-down, but let me explain how going from the bottom would work. I'll use the example that you said it wouldn't work with.

```3
50 3
2 4 6

```

I think you're assuming that I'm suggesting picking the largest number from each row, when I'm not. You compare integers with the adjacent integer above and replace the adjacent integer with the max sum.

```57
54 9
2 4 6

```

Since 4 + 50 > 2 + 50, 50 becomes 54. Same with 6 + 3 being > 4 + 3. Then moving to the next row we see that 54 + 3 > 9 + 3, so 3 becomes the max total of the triangle, 57.

#6 Karel-Lodewijk

Reputation: 454
• Posts: 864
• Joined: 17-March 11

Re: Project Euler: Problem 18

Posted 25 November 2011 - 04:12 PM

Yes I misunderstood. This is basically the bottom-up dynamic approach and will be at least just as and probably more efficient.

I like the top-down approach because it flows more naturally from the recursive solution which came very natural to me when I looked at the problem.

This post has been edited by Karel-Lodewijk: 25 November 2011 - 04:13 PM