Pr. Euler 18, recursion problem

Discussion in 'Python' started by process, Oct 6, 2008.

  1. process

    process Guest

    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.
    process, Oct 6, 2008
    #1
    1. Advertising

  2. process

    Aidan Guest

    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.
    Aidan, Oct 6, 2008
    #2
    1. Advertising

  3. process

    process Guest

    On Oct 6, 8:13 am, Aidan <> 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?
    process, Oct 6, 2008
    #3
  4. process

    Aidan Guest

    process wrote:
    > On Oct 6, 8:13 am, Aidan <> 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.
    Aidan, Oct 6, 2008
    #4
  5. process

    Lie Ryan Guest

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

    > On Oct 6, 8:13 am, Aidan <> 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?


    A Wise Man once says: "When you're hopelessly stuck with a problem,
    reverse the problem"
    Lie Ryan, Oct 9, 2008
    #5
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Piet den Dulk

    Euler tour problem

    Piet den Dulk, Oct 24, 2003, in forum: Java
    Replies:
    6
    Views:
    1,156
    Piet den Dulk
    Oct 27, 2003
  2. Protoman
    Replies:
    10
    Views:
    6,197
  3. euler circuit

    , Mar 19, 2007, in forum: C++
    Replies:
    7
    Views:
    2,530
    Reporter
    Mar 20, 2007
  4. Bruno Desthuilliers
    Replies:
    30
    Views:
    1,064
    paulhankin
    Sep 19, 2007
  5. vsoler
    Replies:
    24
    Views:
    836
    Steven D'Aprano
    Nov 11, 2009
Loading...

Share This Page