Pr. Euler 18, recursion problem

[Aidan]

process wrote:
> On Oct 6, 8:13 am, Aidan <awe... at gmail.com> wrote:
>> process wrote:
>>> I am trying to solve project euler problem 18 with brute force(I will
>>> move on to a better solution after I have done that for problem 67).
>>> http://projecteuler.net/index.php?section=problems&id=18
>>> However I can't get the recursive function right.
>>> I always have to use return right? Unless I am printing? So I canät
>>> stack to diffferent recursive calls after each other like so:
>>> recur_left(t, p)
>>> recur_right(t,p+1)
>>> Some stuff I have tried:
>>> def recur(tree, pos):
>>>     if not tree:
>>>         return []
>>>     else:
>>>         return [[tree[0][pos]] + recur(tree[1:], pos)] + \
>>>                [[tree[0][pos]] + recur(tree[1:], pos+1)]
>>>>>> recur([[1],[2,3],[4,5,6]],0)
>>> [[1, [2, [4], [4]], [2, [5], [5]]], [1, [3, [5], [5]], [3, [6], [6]]]]
>>> SO it is kind of working, just not exactly like I want.
>>> A more easily parseable/readable result would be nice, I want to be
>>> able to sum() over each path preferrably.
>>> So the result should be:
>>> [[1,2,4],[1,2,5],[1,3,5],[1,3,6]]
>>> I know conceptually what has to be done.
>>> Base case: empty tree, return []
>>> Else: recur to the left and to the right.
>> This is just my opinion, but I felt the non-brute force solution to this
>> problem was actually simpler than trying to define a brute force
>> recursive solution.... I tried to implement a brute force algorithm at
>> first, until I had an epiphany with regard to how simple the problem
>> actually was.  Then I faced palmed.
> 
> 
> 
> But let's say you have [[1],[1,10],[1,2,300],[100000,1,1,1]].
> 
> you must check all solutions right? there is no pattern. if you start
> from the bottom and eliminate paths that seem to be losing can you
> regain that later up in the pyramid if it turns out one side gets bigg
> again?

It's difficult to say much here without giving the answer away... but, 
yes, you need to check all solutions - it's just that there's a very 
easy way to do that without having to recurse from the top of the tree 
to the bottom.

Hope that gives you a clue while not fully revealing the answer.