Pr. Euler 18, recursion problem
lie.1296 at gmail.com
Thu Oct 9 19:39:14 CEST 2008
On Mon, 06 Oct 2008 00:14:37 -0700, 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).
>> > 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[pos]] + recur(tree[1:], pos)] + \
>> > [[tree[pos]] + recur(tree[1:], pos+1)]
>> >>>> recur([,[2,3],[4,5,6]],0)
>> > [[1, [2, , ], [2, , ]], [1, [3, , ], [3, ,
>> > ]]]
>> > 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,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
A Wise Man once says: "When you're hopelessly stuck with a problem,
reverse the problem"
More information about the Python-list