Pr. Euler 18, recursion problem

P

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)]

[[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.
 
A

Aidan

process said:
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.
 
P

process

process said:
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?
 
A

Aidan

process said:
process said:
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.
 
L

Lie Ryan

process said:
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?

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

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,901
Latest member
Noble71S45

Latest Threads

Top