Mailman 3 May 2001 - Edu-sig

shortest path algorithm based on guido's essay and a post by June Kim
by Christian Jeitler May 9, 2001

May 9, 2001

hello! this code shows how to calculate the shortest path between two cities on a map based on: http://www.python.org/doc/essays/graphs.html i have changed the code with the hlp of a news article by June Kim. For small graphs it works better than the Dijkstra algorithm. If anybody has an idea how to speed up this algorithm ? By the way I am looking forward to the second part of the essay. def weight(path): weight_of_path= 0 for node in path: weight_of_path = weight_of_path + node[1] return weight_of_path def find_shortest_path(graph, start, end, path=[]): path = path + [start] path_hlp=[] for node_hlp in path: path_hlp = path_hlp + [node_hlp[0]] if start[0] == end: return path shortest_path = None for node in graph[start[0]]: if node[0] not in path_hlp: new_path = find_shortest_path(graph, node, end, path) if new_path: if not shortest_path or weight(new_path) < weight(shortest_path): shortest_path = new_path return shortest_path # real geographic area in vienna graph = {'A':[('B',513)], 'B':[('A',513),('C',1513),('J',1684),('K',1107)], 'C':[('B',1513),('D',406),('K',654)], 'D':[('C',406),('E',834),('L',860)], 'E':[('D',834),('L',889),('F',2472)], 'F':[('E',2472),('Z',170),('M',765),('G',2796)], 'G':[('F',2796),('N',1317),('H',737)], 'H':[('G',737),('P',1181),('I',1072)], 'I':[('H',1072),('Q',1020),('J',467)], 'J':[('I',467),('Q',565),('B',1684)], 'K':[('B',1107),('C',654),('P',1340),('Q',719)], 'Q':[('K',719),('I',1020),('J',565)], 'L':[('D',860),('E',889),('M',729),('O',648)], 'O':[('L',648),('N',709),('P',153)], 'M':[('L',729),('F',765),('N',444)], 'N':[('M',444),('G',1317),('O',709)], 'P':[('O',153),('H',1181),('K',1340)], 'Z':[('F',170)]} pathfinder = find_shortest_path(graph,('A',0),'Z')

1 0

Intro and question: assignments/projects for year end
by Sheila King May 8, 2001

May 8, 2001

Hello, My name is Sheila King. I'm a high school AP Computer Science teacher. Heh. AP Exam is tomorrow! I've been learning Python for myself since January. If you read comp.lang.python or the Python Tutor List, you've seen my posts there, probably. Anyway, for the last two or so weeks of the school year, what I'm going to have my AP Comp Sci students do is this: They get a choice of two possible types of projects: (1) CMU graphics. (this is what all of my students did last year.) (2) Learn Python. I must've given a pretty convincing speech about Python, because 10 of my 17 students picked to do Python. I was surprised. I thought most of them would want to do a graphics project. (Last year's class wrote a number of different games.) Anyhow...here's my question: I'm looking for suggested projects or programming problems for my students. They have had a year of C++, and some of them are excellent. Some are only barely proficient. I know the good ones will pick up Python easily. I hope the others will be able to do so, as well. It's going to be sort of independent study. (I'm putting several HTML tutorials on their desktops...) If they only have about two weeks to "learn" Python, and write a small program or two, what types of things could I have them do? We won't have time to get into GUIs. These can't be very ambitious projects, due to the limited amount of time. -- Sheila King http://www.thinkspot.net/sheila/ http://www.k12groups.org/

7 6

Turtle Draw program
by Dethe Elza May 8, 2001

May 8, 2001

Hi folks, This is just an announcement for my own bit of "throwaway" code: a primitive turtle-drawing program called Kutia. I wanted a logo-like environment for introducing my daughter Mina (age 4) to programming. The idea was that you could move the turtle with buttons, or click the field to have it chase the mouse-clicks, or enter text commands. Each control method should be interlinked, so when the turtle chases the mouse, the commands it uses are entered in the command window, which would be editable. I have not implemented the command window yet, and the buttons don't seem very useful when you have direct manipulation of the turtle. In fact I think I can get rid of the penup/pendown buttons once I allow the turtle to be dragged directly. Anyway, it's pretty fun and ready for some comments. http://delza.alliances.org/archive/ Two classes in one file, notes and demo data at the top. It's more complicated right now than it needs to be, I'm still cleaning up the code which is there while I add additional functionality. There are a lot of methods which don't get used: I tried animating the rotation of the turtle but it was too slow, there is support for buttons to move forward, turn right/left, but I've removed the buttons based on usability testing. This is different from "adaptable interfaces" because the interface is not designed to change: direct manipulation is always available, as is the command window (when implemented). This allows the learner to switch back and forth at will between the two methods for ease of exploration. Also, when I say Logo-like, I'm using the term pretty loosly. I've never really used Logo, just read about it. Caveat emptor or something. And despite my .sig, this isn't a BT product, just a personal project. --Dethe Dethe Elza Chief Mad Scientist Burning Tiger Technologies

1 0

RE: [Edu-sig] Algebra + Python
by Daniel Ajoy May 8, 2001

May 8, 2001

On 7 May 01, at 12:01, edu-sig-request(a)python.org wrote: > A simple way to compute the determinant is to add the signed > products of all permutations of matrix elements, choosing one > from each row (a total of row! possibilities). ciphers.py is > in charge of returning a list of all those possibilities Does that work for matrices 4x4 ? I ask because it didn't work for me. I have an algorithm that gives me the permutation in this order for a 3 row matrix: [[0 1 2] [0 2 1] [1 2 0] [1 0 2] [2 0 1] [2 1 0]] and this for a 4 row matrix: [[0 1 2 3] [0 1 3 2] [0 2 3 1] [0 2 1 3] [0 3 1 2] [0 3 2 1] [1 2 3 0] [1 2 0 3] [1 3 0 2] [1 3 2 0] [1 0 2 3] [1 0 3 2] [2 3 0 1] [2 3 1 0] [2 0 1 3] [2 0 3 1] [2 1 3 0] [2 1 0 3] [3 0 1 2] [3 0 2 1] [3 1 2 0] [3 1 0 2] [3 2 0 1] [3 2 1 0]] Is that the same order you get with your algorithm. For the 3 row matrix I change signs like this (using the same order as above): [1 -1 1 -1 1 -1] and for the 4 row matrix something very similar: [1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1] Am I wrong in this step? using this this sequence of signs? The funny thing is that it works nicely for matrices (2x2) and (3x3). Daniel

2 1

RE: [Edu-sig] Algebra + Python
by Kirby Urner May 7, 2001

May 7, 2001

Getting Poly, Fraction and Matrix to interoperate has been fun. I get into these operator precedence situations where two objects have different implementations of __mul__, so the __rmul__ of one triggers where what I want is the __mul__ of the other. So I end up doing type checking to force the result I want. For example, Poly knows how to coerce a Fraction into becoming a polynomial of degree 0, but Fraction shouldn't ever try to change a polynomial into a Fraction. So when it comes to a Fraction * a Poly, it's the Poly version of * that takes precedence over the Fraction version -- but only because I type check, e.g. def __mul__(self,n): if type(n).__name__=='instance': if n.__class__.__name__ == "Poly": print "Fraction -> Poly" return n.__mul__(self) if n.__class__.__name__ == "Matrix": print "Fraction -> Fraction" return n.__mul__(self) f = self.mkfract(n) return Fraction(self.numer*f.numer, self.denom*f.denom) Anyway, below is an example of a session at the command line: >>> C = Matrix([map(Fraction,[1,1,1]), map(Fraction,[2,3,4]), map(Fraction,[5,8,9])]) >>> C [1, 1, 1] [2, 3, 4] [5, 8, 9] >>> C.inverse() [(5.0/2), (1.0/2), (-1.0/2)] [-1.0, -2.0, 1.0] [(-1.0/2), (3.0/2), (-1.0/2)] >>> A = Matrix([[Poly([1,-3],'t'),2], [Fraction(1,2),Poly([1,-4],'t')]]) >>> A [t - 3, 2] [(1/2), t - 4] >>> A.det() # determinant of A x**2 - 7*x + 11 >>> I = Matrix([[1,0,0],[0,1,0],[0,0,1]]) # identity matrix >>> t = Poly([1,0],'t') # t >>> t*I [t, 0, 0] [0, t, 0] [0, 0, t] >>> A = Matrix([[1,1,2],[0,3,2],[1,3,9]]) >>> A [1, 1, 2] [0, 3, 2] [1, 3, 9] >>> (t*I-A).det() # characteristic polynomial of A t**3 - 13*t**2 + 31*t - 17 >>> p=(t*I-A).det() # t = 10 >>> p(10) -7 Note that polynomials now optionally permit some variable other than x. However, you can't multiply two polynomials with differing variables and expect their identities to stay separate. Getting evaluation to work no matter the letter required a small modification to __call__ in polynomial.py. I've stowed polynomial,pyfraction and simplematrix as a package called mathobjects. simplematrix is dependent on ciphers.py however, which was my last project, and which has to do with permutations in the context of group theory and cryptography. A simple way to compute the determinant is to add the signed products of all permutations of matrix elements, choosing one from each row (a total of row! possibilities). ciphers.py is in charge of returning a list of all those possibilities (breaks down when n is double-digit or higher -- but that's OK, as this is throwaway code)). Kirby

2 2

Setup python path on Windows 98
by dcraig May 5, 2001

May 5, 2001

Help! I have been learning python using idle as the editor and it's great. My new problem is setting up the environmental variables (path) necessary to run it from the command line in MS-DOS. I am using WIN 98 and the Python files are located at C:\Python20. Thanks for any help. Dave Craig dcraig(a)cris.com

2 1

Is it alive?
by Roman Suzi May 4, 2001

May 4, 2001

Hello! I've just subscribed to this list and there is only silence here. Probably, edu-sig needs more publicity? Sorry for this test message. Sincerely yours, Roman A.Suzi -- - Petrozavodsk - Karelia - Russia - mailto:rnd@onego.ru -

3 2

Wanted: a new edu-sig owner!
by Guido van Rossum May 3, 2001

May 3, 2001

I'm looking for someone to take ownership of the edu-sig. You don't have to do much, except occasionally approve or reject posts that are caught by the spam filter. You also receive mail sent to the SIG owner; very rare. Anyone interested? While it's not much work, I just don't get to the requests in time myself. --Guido van Rossum (home page: http://www.python.org/~guido/)

2 3

Re: [Edu-sig] Algebra + Python
by Brent Burley May 2, 2001

May 2, 2001

Kirby wrote: > There may be a better way to write the factory function than > I've shown below. I'd like to see other solutions: > > >>> def makepoly(A,B,C): > """ > Build a polynomial function from coefficients > """ > return eval("lambda x: %s*x**2 + %s*x + %s" % (A,B,C)) How about this? class poly: def __init__(self, A, B, C): self.A, self.B, self.C = A, B, C def __call__(self, x): return self.A * x**2 + self.B * x + self.C >>> f = poly(2,3,4) >>> f(10) 234 Having to know about classes pushes you more into learning Python as a programming language rather than just using Python as a math exploration tool, but that could be a good thing. You could even expand on the idea by adding additional methods that relate to polynomials (deriv, integral, roots, etc.): class poly: ... def deriv(self, x): return 2*self.A*x + self.B >>> f.deriv(2) 11 Brent

3 10

Useless Python
by rob＠jam.rr.com May 2, 2001

May 2, 2001

I hope I'm not posting off-topic, but I'm new to the list. I maintain a small website dedicated to Python, featuring a section called Useless Python, which is the star of our little show. It consists of two things which I hope may be of potential value in the arena of Python and education. Each came about as a good idea set in motion on the Python Tutor email list. We allow people to provide solutions to ACM Programming Contest problems, which must be submitted in other languages such as Perl and C when submitting to the contest judges. We do not judge the submissions, but post them for the world to see. When I contacted the people behind the ACM site, I was told that they were delighted to hear about it and if we could provide a Python judge (which I took to mean software similar to that which they already use), they would be willing to add Python to the list of possible submission languages. Useless Python itself is a collection of scripts and similar selections sent in by anyone who cares to submit code. The general purpose is dual: to reduce the need to send long snips of source in emails to the tutor list, and to allow people to share scripts for beginners to look at. Novice and Intermediate level concepts are expressed in the code here. If there is any way that this resource could be made more useful for educational purposes, or improved in any way, we would welcome any requests or criticism. Oh, and if you have any odd programs you would share with people learning the language, please do. Please forgive my verbosity, Rob Andrews -- Useless Python! If your Python is this useless, we need you. http://www.lowerstandard.com/python/pythonsource.html

2 1