Hi Alan,
I have given a wrong example of 16 . I am sorry for it. You are correct it
will take only 4 turns.
If i consider your solution for number 10
it will go like this 10-->10/2 =5 --> 5-1=4--> 4/2 =2-->2/2 =1 which gives
4 as output but answer would be in 3 steps 10-->10-1=9-->9/3=3-->3/3=1
So we must consider every path /3, /2 and -1 and try to find out shortest
one which i tested with my logic it works because I have put multiple
recursive calls to span multiple branches. I am certain with my logic as it
passes most of test cases. Due to multiple branches it takes more time for
large numbers but returns correct result.
I have used global variable called depth but was wondering if we can have
something being passed as function parametedata structurr which could have
been shared across all invocations. I know list and sets can be used do we
have any other data structure in python which would be mutable and not a
sequence?
Thanks and appreciate your generous help,
Anshu
On Sat, Oct 3, 2015 at 1:32 PM, Alan Gauld <alan.ga...@btinternet.com>
wrote:
> 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
>
>
> _______________________________________________
> Tutor maillist - Tutor@python.org
> To unsubscribe or change subscription options:
> https://mail.python.org/mailman/listinfo/tutor
>
_______________________________________________
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor
