Pr. Euler 18, recursion problem

[process]

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.

[Aidan]

Re: Pr. Euler 18, recursion problem

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.

[process]

Re: Pr. Euler 18, recursion problem

On Oct 6, 8:13 am, Aidan <awe...@gmail.c omwrote:

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?se...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?

[Aidan]

Re: Pr. Euler 18, recursion problem

process wrote:

On Oct 6, 8:13 am, Aidan <awe...@gmail.c omwrote:

>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?se...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.

[Lie Ryan]

Re: Pr. Euler 18, recursion problem

On Mon, 06 Oct 2008 00:14:37 -0700, process wrote:

On Oct 6, 8:13 am, Aidan <awe...@gmail.c omwrote:

>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?se...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?

A Wise Man once says: "When you're hopelessly stuck with a problem,
reverse the problem"