[Tutor] Mutable data type in python

[Oscar Benjamin]

On 4 October 2015 at 00:13, Alan Gauld <alan.gauld at btinternet.com> wrote:
> On 03/10/15 23:20, C Smith wrote:
>>
>> On Sat, Oct 3, 2015 at 11:55 AM, Alan Gauld <alan.gauld at btinternet.com>
>> wrote:
>>>
>>> On 03/10/15 19:10, C Smith wrote:
>>>>>
>>>>> Here is my modified version which I think works as you want:
>>>>>
>>>>> def findMinDepthPath(n):
>>>>>       if n <= 0: raise ValueError
>>>>>       elif n==1:
>>>>>           return 0
>>>>>       elif n==2 or n==3:
>>>>>           return 1
>>>>>       else:
>>>>>           d1 = findMinDepthPath(n-1)+1
>>>>>           d2 = d3 = (d1+1) # initialize to higher than d1
>>>>>
>>>>>       if n%3 == 0:
>>>>>           d3 = findMinDepthPath(n/3)+1
>>>>>       if n%2 == 0:
>>>>>           d2 = findMinDepthPath(n/2)+1
>>>>>
>>>>>       return min(d1,d2,d3)
>>
>> What I meant was that the algorithm assumes that the lowest value from
>> one "action" (minus one, divide by 2, divide by 3) is the best
>> possible branch in the tree. That seems intuitively correct, but is it
>> necessarily so?
>
> I see. The answer is I don't know mathematically speaking.
> But I figured that the minimum path for (n-1|n/2|n/3)  plus 1
> must be the minimum path for n. But that was an entirely
> inuitive assumption.
>
> Also because the minimum path is being figured from the
> bottom to the top - ie it finds the minimum path for 1..3
> first, then for 4 via n/2 then 5 via n-1 and so on. It *feels* like
> that it should always select the minimum path. But I have learnt
> that in math intuitive is not always right :-)
>
> So if anyone can mathematically  prove my hunch right
> or wrong that would be interesting...

Your intuition is fine Alan. Of course it's correct!

Starting from a number n there are three possibilities for the first
step -1, /2, and /3 each of which counts as one action. Each of those
gives a new starting point n1, n2 or n3. Whichever of the ni has the
shortest path will also be the shortest path for n except that for n
you also need to include the action that gets from n to ni increasing
the count by 1.

A side point is that the algorithm is incredibly inefficient because
the 3 way branching will traverse the same routes many times over. It
is analogous to the dumb recursive Fibonacci sequence calculator:

    def fib(n):
        if n in (0, 1):
            return n
        else:
            return fib(n-1) + fib(n-2)

A typical solution for the inefficiency is to either use a memoisation
decorator or to roll it out into an explicit loop instead of a
recursive call:

    def fib(n):
       n1, n2 = 0, 1
       if n in (n1, n2):
            return n
        else:
            for _ in range(1, n):
                n1, n2 = n2, n1 + n2
            return n2

To do the same for this problem you would have something like:

    def shortest_path(n):
        paths = [None, 0]
        for i in range(2, n+1):
            d1 = paths[i-1] + 1
            d2 = paths[i // 2] + 1 if i % 2 == 0 else float('inf')
            d3 = paths[i // 3] + 1 if i % 3 == 0 else float('inf')
            paths.append(min(d1, d2, d3))
        return paths[n]

This way the algorithm is O(n) instead of O(3**n). Also if you
actually just want a list of all of the shortest paths you can adjust
this to simply return the full list at no extra cost. OTOH if you want
to be able to call this function repeatedly with random input values a
memoisation decorator may be preferable.

--
Oscar