5 Replies - 2366 Views - Last Post: 25 November 2011 - 04:12 PM Rate Topic: -----

#1 gbertoli3  Icon User is offline

  • DIC at Heart + Code
  • member icon

Reputation: 40
  • View blog
  • Posts: 1,162
  • 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  Icon User is offline

  • THE PEN IS MIGHTIER
  • member icon





Reputation: 251
  • View blog
  • Posts: 640
  • 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.
Was This Post Helpful? 1
  • +
  • -

#3 gbertoli3  Icon User is offline

  • DIC at Heart + Code
  • member icon

Reputation: 40
  • View blog
  • Posts: 1,162
  • 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.
Was This Post Helpful? 0
  • +
  • -

#4 Karel-Lodewijk  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 451
  • View blog
  • Posts: 855
  • 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

Was This Post Helpful? 3
  • +
  • -

#5 Skaggles  Icon User is offline

  • THE PEN IS MIGHTIER
  • member icon





Reputation: 251
  • View blog
  • Posts: 640
  • 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.
Was This Post Helpful? 1
  • +
  • -

#6 Karel-Lodewijk  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 451
  • View blog
  • Posts: 855
  • 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

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1