[Tutor] Mutable data type in python

[Alan Gauld]

On 03/10/15 03:46, Anshu Kumar wrote:
> Hi Alan,
>
> I was trying to solve a simple dynamic programming problem.
>
> It goes like this. I have an input integer and i can choose to divide it by
> two or three or subtract by one to reduce it to one. there is a condition
> the number has to be divisible by 2 or 3 if we are dividing by two or three
> respectively. I have to get shortest path to reduce input number to 1 by
> using combination of either divide by three or two or subtract one.
>
>
> so let suppose i have number 16 as input it will be reduced to 1 in 5
> number of minimal steps 16-->16-1 = 15 -->15/3 = 5-->5-1= 4--> 4/2=2-->2/2
> =1

I donm;t understand the logic.
I'd have expected 16/2->8 as the first step, then 8/2 etc. So the depth 
would be 4? Why would n-1 be the first step? And your code below 
certainly doesn't do that. In fact it calls n-1 on every iteration.


> depth = float('inf')
>
> def findMinDepthPath(n,counter):
>      global depth
>      if(n== 1 and counter < depth):
>          depth = counter
>      elif(( n==2 or n==3) and counter < depth):
>          depth = counter + 1
>      else:
>          if(counter < depth):
>              if(n%3 == 0):
>                findMinDepthPath(n/3,counter + 1)
>              if(n%2 == 0):
>                  findMinDepthPath(n/2,counter + 1)
>              findMinDepthPath(n-1,counter +1)

If I understand what I think you want I'd write this as:

def findMinDepthPath(n):
     if n== 1:
         return 0
     elif n==2 or n==3:
         return 1
     elif n%3 == 0:
         return findMinDepthPath(n/3)+1
     elif n%2 == 0:
         return findMinDepthPath(n/2)+1
     else:
         return findMinDepthPath(n-1)+1

The key difference being that I return a value rather
than try to set an external one. That removes the need
for the depth and counter values.

But it does give different results to your code because
the algorithm is slightly different for the n-1 cases,
so I may be oversimplifying. If so please explain the
logic again.

-- 
Alan G
Author of the Learn to Program web site
http://www.alan-g.me.uk/
http://www.amazon.com/author/alan_gauld
Follow my photo-blog on Flickr at:
http://www.flickr.com/photos/alangauldphotos