Re: [Tutor] Mutable data type in python
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
so i wrote a simple program like this
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)
def getMinDepthPathLength(n):
global depth
depth = float('inf')
findMinDepthPath(n,0)
return depth
it works fine with global variable or a list type parameter for depth but i
am looking for a way where i would be able to use a parameter which will be
shared across all invocation and it should certainly not be a list coz i
don't need a list
Thanks and appreciate your help,
Anshu
On Sat, Oct 3, 2015 at 5:05 AM, Alan Gauld
wrote:
> On 02/10/15 17:52, Anshu Kumar wrote:
>
> When we invoke the same function inside a function (recursive function), i
>> want to keep track of some data across all function invocation so i should
>> have shareable type but built in data types string, int are not helping as
>> they are immutable they are changed while next invocation.
>>
>
> Show us some code and we will understand exactly what you are struggling
> with. I think I know, but it would be easier if
> you give a specific short example.
>
> I could use lists which are mutable but sometimes i find it not suitable
>> for example when i need only single number or string.
>>
>
> You can create a closure using a list, or you could use a global
> or you could just use a lot of parameters/return values. But
> without seeing exactly what you are trying to do its difficult
> to know which options suit you best.
>
>
> --
> 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
Re: [Tutor] Mutable data type in python
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
Re: [Tutor] Mutable data type in python
>it works fine with global variable or a list type parameter for depth but i >am looking for a way where i would be able to use a parameter which will be >shared across all invocation and it should certainly not be a list coz i >don't need a list > >Thanks and appreciate your help, >Anshu I am not sure what you mean 'shared across all invocation'. You have a room of computers, and they all are going to use this program to find solutions, and you don't want them to duplicate work? This thing runs for a very long time and I want to be able to stop running this program .. have my laptop crash, even ... and start it up and have it pick up where it left off the last time? If this is your problem, then even lists and global variables will not help you, and you really need to save the data you need out on disk someplace. This leads me to believe that I just don't understand you properly yet. Laura ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Mutable data type in python
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
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
Re: [Tutor] Mutable data type in python
On 03/10/15 09:23, Anshu Kumar wrote:
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
Ah, OK I see.
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)
n = int(raw_input('N? '))
print "Minimum depth = ", findMinDepthPath(n),'\n'
>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?
You could use a dictionary but that is also a type of sequence...
So a class is the obvious non-sequential candidate.
class Store:
def __init__(self, value = 0):
self.value = value
You can then pass an instance of the class and modify its value.
--
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
Re: [Tutor] Mutable data type in python
One thing you can do is to make your variable live in another module. This is a common way to make config files, for instance. say you have a file called config.py which contains the single line my_int = 0 then in your main program you can do: import config and start using config.my_int wherever you would like to. of course, you can also do from config import my_int and start using my_int At this point, you aren't any better off that just using a global, though. Note that if you do: config.my_int = 1 or my_int = 1 the file config.py is not changed. The next time anybody imports it, they will get the 0 value for my_int. Laura ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Mutable data type in python
> 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)
>
>
> n = int(raw_input('N? '))
> print "Minimum depth = ", findMinDepthPath(n),'\n'
Doesn't this only look one level deep? Is the poster asking for
something that would traverse all possible paths and then check for
the shortest?
___
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Mutable data type in python
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)
n = int(raw_input('N? '))
print "Minimum depth = ", findMinDepthPath(n),'\n'
Doesn't this only look one level deep? Is the poster asking for
something that would traverse all possible paths and then check for
the shortest?
No, this is a recursive function which keeps calling itself with smaller
values of n until it reaches 1-3, at which point it returns a known result.
Here is an example of the factorial() function written recursively in a
similar style, it might be easier to see how it works:
def square(n):
print n # show the recursion
if n <= 1: return 1
else: return n * factorial(n-1)
print factorial(5)
HTH
--
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
Re: [Tutor] Exception Handling
Thank you (Cameron and Alan) for your review and feedback. This solved the
issue perfectly!
Thank you.
On Friday, October 2, 2015 11:49 PM, Cameron Simpson
wrote:
On 03Oct2015 00:51, ALAN GAULD wrote:
>On 02/10/15 23:57, Nym City via Tutor wrote:
>>socket.gaierror: [Errno 11004] getaddrinfo failed
>...
>>for name in ListOfHostNames:
>> try:
>> ResolveHostname = socket.gethostbyname(name)
>> print(ResolveHostname)
>> newFile.write(ResolveHostname + "\n")
>> print(ResolveHostname)
>> except socket.herror as e:
>> newFile.write("No resolution available for %s" % (name) + "\n")
>
>You are catching herror but your code is resulting in gaierror.
>
>Add socket.gaierror to your except line.
>
> except (socket.herror, socket.gaierror):
> newFile.write("No resolution available for %s" % (name) + "\n")
>
>see if that works
Just a followon remark: always try to print the exception when you're not
certain of what it will be or what to do with it. So I'd augument Alan's code
like this:
except (socket.herror, socket.gaierror) as e:
newFile.write("No resolution available for %s: %s" % (name, e) + "\n")
Cheers,
Cameron Simpson
___
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
Re: [Tutor] Mutable data type in python
On Sat, Oct 3, 2015 at 11:55 AM, Alan Gauld 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? ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Mutable data type in python
On 03/10/15 23:20, C Smith wrote: On Sat, Oct 3, 2015 at 11:55 AM, Alan Gauld 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... -- 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
