[gbertoli3]

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

[Skaggles]

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.

[gbertoli3]

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.

[Karel-Lodewijk]

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

They come into 2 flavors, top-down and bottom-up. Both can be applied.

The top-down method is easiest to add to the naive method which tries all possible paths. So let's take a look at a possible implementation in pseudo-code. I'm assuming you have read the input as a binary tree.

def maxsum(treeNode)
    if treeNode.nil? 
        return 0
    else 
        return treeNode.value + max(maxsum(treeNode.left), maxsum(treeNode.right))
    end
end

This is the core of the algorithm. The maximal sum of all paths in a node is the value in that node + the maximum of the maximal sum in the left subtree and the maximal sum in the right subtree. Now the problem is maxsum will be called many times on identical overlapping subtrees, if we were somehow to remember this information, then we would save a lot of work the second time it is called on the same subtree.

The other option is bottom up. Basically you will take the maxsums of all elements 2by2 from the bottom and break down the tree from there. Peeling away one layer at a time.

A top-down implementation

Spoiler

class Node
   def initialize(value)
      @value = value
   end
   attr_accessor :left, :right, :maxsum
   attr_reader :value
end

root = gets.chomp.to_i
rootNode = Node.new(root)
lastRow = [rootNode]

#read this somewhat perculiar tree
while (line = gets) != nil 
    line = line.chomp.split(" ").map{|x| x.to_i}
    newRow = []

    node = Node.new(line[0])
    lastRow[0].left = node;
    newRow.push(node);
    
    line[1..-2].each_with_index {|x,i|
        node = Node.new(x)
        newRow.push(node)
        lastRow[i].right = node
        lastRow[i+1].left = node
    }

    node = Node.new(line[-1])
    lastRow[-1].right = node;
    newRow.push(node);
   
    lastRow = newRow
end

#top-down dynamic programming solution
def maxsum(node)
    if node.nil?
        return 0
    elsif node.maxsum.nil?
        #it really is that simple instead of immediately
        #returning it, which would give a correct result.
        #Store it in the node so this only needs to be 
        #done once for every subtree
        node.maxsum = node.value + [maxsum(node.left), maxsum(node.right)].max
    end
    return node.maxsum
end

puts maxsum(rootNode)

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

[Skaggles]

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.

[Karel-Lodewijk]

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