Pr. Euler 18, recursion problem

process circularfunc at gmail.com
Mon Oct 6 09:14:37 CEST 2008


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?



More information about the Python-list mailing list