[Tutor] Mutable data type in python

[Anshu Kumar]

Hi Everyone,

I have been facing this problem from a while in python could I please be
helped?

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.

I could use lists which are mutable but sometimes i find it not suitable
for example when i need only single number or string.

Thanks and Regards,
Anshu
_______________________________________________
Tutor maillist - ***@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor

[Alan Gauld]

Post by Anshu Kumar
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.

Post by Anshu Kumar
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 - ***@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor

[Anshu Kumar]

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

Post by Anshu Kumar
When we invoke the same function inside a function (recursive function), i

Post by Anshu Kumar
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

Post by Anshu Kumar
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
http://www.flickr.com/photos/alangauldphotos
_______________________________________________
https://mail.python.org/mailman/listinfo/tutor

_______________________________________________
Tutor maillist - ***@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor

[Alan Gauld]

Post by Anshu Kumar
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.

Post by Anshu Kumar
depth = float('inf')
global depth
depth = counter
depth = counter + 1
findMinDepthPath(n/3,counter + 1)
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 - ***@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor

[Anshu Kumar]

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

Post by Alan Gauld

Post by Anshu Kumar
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')

Post by Anshu Kumar
global depth
depth = counter
depth = counter + 1
findMinDepthPath(n/3,counter + 1)
findMinDepthPath(n/2,counter + 1)
findMinDepthPath(n-1,counter +1)

return 0
return 1
return findMinDepthPath(n/3)+1
return findMinDepthPath(n/2)+1
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
http://www.flickr.com/photos/alangauldphotos
_______________________________________________
https://mail.python.org/mailman/listinfo/tutor

_______________________________________________
Tutor maillist - ***@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor

[Alan Gauld]

Post by Anshu Kumar
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'

Post by Anshu Kumar
I know list and sets can be used do we have any other data structure

in python

Post by Anshu Kumar
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 - ***@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor

[C Smith]

Post by Alan Gauld
if n <= 0: raise ValueError
return 0
return 1
d1 = findMinDepthPath(n-1)+1
d2 = d3 = (d1+1) # initialize to higher than d1
d3 = findMinDepthPath(n/3)+1
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 - ***@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor

[Alan Gauld]

Post by C Smith

Post by Alan Gauld
if n <= 0: raise ValueError
return 0
return 1
d1 = findMinDepthPath(n-1)+1
d2 = d3 = (d1+1) # initialize to higher than d1
d3 = findMinDepthPath(n/3)+1
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 - ***@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor

[C Smith]

Post by Alan Gauld
if n <= 0: raise ValueError
return 0
return 1
d1 = findMinDepthPath(n-1)+1
d2 = d3 = (d1+1) # initialize to higher than d1
d3 = findMinDepthPath(n/3)+1
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 - ***@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor

[Alan Gauld]

Post by C Smith

Post by Alan Gauld
if n <= 0: raise ValueError
return 0
return 1
d1 = findMinDepthPath(n-1)+1
d2 = d3 = (d1+1) # initialize to higher than d1
d3 = findMinDepthPath(n/3)+1
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 - ***@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor

[Oscar Benjamin]

Post by Alan Gauld

Post by C Smith

Post by Alan Gauld
if n <= 0: raise ValueError
return 0
return 1
d1 = findMinDepthPath(n-1)+1
d2 = d3 = (d1+1) # initialize to higher than d1
d3 = findMinDepthPath(n/3)+1
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
_______________________________________________
Tutor maillist - ***@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor

[Laura Creighton]

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 - ***@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor

[Laura Creighton]

Post by Anshu Kumar
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 - ***@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor

[Cameron Simpson]

Post by Anshu Kumar
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.
I could use lists which are mutable but sometimes i find it not suitable
for example when i need only single number or string.

Please provide some more context, perhaps with an example of what you're trying
to do. What follows is general advice which may not be what you need. Anyway...

What you use depends very much on what you need (trite, but true). Numbers and
strings are not themselfs mutable.

I'm presuming you want some kind of shared state that continues over the
recursion, for example a record of what nodes have already been visiting while
traversing a graph with loops: if you follow a loop you want to stop instead of
circling/recursing forever.

When I do this I usually form the function somewhat like the below. Let's
suppose we're walking a graph whose nodes have a ".children" attribute which is
a list of child nodes. And that the graph might have loops (this node might be
a child or subchild of itself).

def traverse(node, seen=None):
''' Traverse the graph from `node`, printing each node's name.
`seen`: if not None, a set of nodes already visited.
'''
if seen is None:
seen = set()
seen.add(node)
print(node.name)
for child in node.children:
if child not in seen:
traverse(child, seen)

So the paramater "seen" is your mutable object keeping track of which nodes
have been visited. You add this node to "seen", then visit any children which
are not in "seen". You pass "seen" to the traverse() of each child, so all the
function calls share the same "seen" object.

So in this case we're using a set. There's any number of different things you
might use depending on what you need to keep track of.

Cheers,
Cameron Simpson <***@zip.com.au>
_______________________________________________
Tutor maillist - ***@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor