[Tutor] How to run same lines of code in different order at runtime

[George]

Hello,

I have done little piece of work for finding nearest shortest route from
one point on a graph to other with connected points(cities to be
precise). The way i achieved it is by getting the nearest neighbours in
(NE, NE, SE, SW) and then traversing them one by one until i reach my
destination in the first instance of recursion. this thing works for me
and i am not looking for route solving problems but rather a peculiar
problem of running different lines of code arbitarily.

The problem with my coding is that it follows a strict route search
algorithm that i hardcoded i.e.
it first searches NE, then NW, then SE, and finally SW. this code will
always find a route but will not be the shortest route which could
either start from any direction. So i have to devise a way by which i
can run all the posibilities to find the best route. so i have to run
4*3*3*3 runs to find out the shortest route. My code is as below, any
way i can achieve it in python without typing all the posibilites.


def GetShortestRoute(source:list,destination:City,recursion=0):
print("recursion",recursion)
#print(source)
assert type(source)==list,"Source must be a list of list"
assert len(source)>0,"Source must contain atleast 1 item"
assert type(source[0])==list,"Sub items of source must be a list"

#debug
for route in source:
print (route)
#end Debug

#found something
foundlist=[]
for miniroute in source:
if destination in miniroute:
print("found",destination," in ",miniroute,":", destination
in miniroute)
foundlist.append(miniroute)
else:
print("Not found",destination," in ",miniroute,":",
destination in miniroute)

#print ("length of found list",len(foundlist),foundlist)

#retun the shortest amongst the find
shortestRoute=[None,9999999.9]
if len(foundlist)>0:
for miniroute in foundlist:
#print("shortest distance",shortestRoute[1])
distance=calculateRouteDistantce(miniroute)
#print("distance calculated",distance)
if distance<shortestRoute[1]:
shortestRoute[1]=distance
shortestRoute[0]=miniroute
return shortestRoute


#not found
duplicatesource=source[:]
for route in source:
lastCity=route[len(route)-1]

#the part i do not want to recode everytime to find the shortest route
if lastCity.NE!=None and
isCityInRouteList(lastCity.NE,source)==False:
tmproute=route[:]
tmproute.append(lastCity.NE)
if tmproute not in duplicatesource:
duplicatesource.append(tmproute)

if lastCity.NW!=None and
isCityInRouteList(lastCity.NW,source)==False:
tmproute=route[:]
tmproute.append(lastCity.NW)
if tmproute not in duplicatesource:
duplicatesource.append(tmproute)

if lastCity.SE!=None and
isCityInRouteList(lastCity.SE,source)==False:
tmproute=route[:]
tmproute.append(lastCity.SE)
if tmproute not in duplicatesource:
duplicatesource.append(tmproute)

if lastCity.SW!=None and
isCityInRouteList(lastCity.SW,source)==False:
tmproute=route[:]
tmproute.append(lastCity.SW)
if tmproute not in duplicatesource:
duplicatesource.append(tmproute)
#end of the part

return GetShortestRoute(duplicatesource,destination,recursion+1)

Thanks

George

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

[Alan Gauld]

Post by George
and i am not looking for route solving problems but rather a peculiar
problem of running different lines of code arbitarily.

I'm not sure what you mean by that.
What is arbitrary? What determines which lines are run?

Post by George
either start from any direction. So i have to devise a way by which i
can run all the posibilities to find the best route. so i have to run
4*3*3*3 runs to find out the shortest route. My code is as below, any
way i can achieve it in python without typing all the posibilites.

The normal way to deal with this kind of thing is to a) create
a function that does the work and b) make it data driven so
you can code the choices as data.

But i don;t pretend to know what your algorithm would look like
so I'll somply make some suggestions to tidy the code below in
the hope that they might fire some ideas.

Post by George
print("recursion",recursion)

recursion may not be the best solution for this since Pythons
recursion limit is not huge (1000 last time I looked) and you
could easily hit that with this type of problem.

Post by George
#print(source)
assert type(source)==list,"Source must be a list of list"
assert len(source)>0,"Source must contain atleast 1 item"
assert type(source[0])==list,"Sub items of source must be a list"

Just an observation but you seem very concerned with typechecking. Thats
not usually necessary in Python since it will check for incompatible
types as you go and raise exceptions.

Post by George
#found something
foundlist=[]
print("found",destination," in ",miniroute,":", destination
in miniroute)
foundlist.append(miniroute)
print("Not found",destination," in ",miniroute,":",
destination in miniroute)
shortestRoute=[None,9999999.9]

This is more usually written as

Post by George
distance=calculateRouteDistantce(miniroute)
shortestRoute[1]=distance
shortestRoute[0]=miniroute
return shortestRoute
duplicatesource=source[:]
lastCity=route[len(route)-1]

It would be easierv to access the last element directly rather than looping:

lastCity = route[-1]

Post by George
#the part i do not want to recode everytime to find the shortest route
if lastCity.NE!=None and
tmproute=route[:]
tmproute.append(lastCity.NE)
duplicatesource.append(tmproute)

You repeat the if clause each time so put it in a function.
I'm not sure what you would call it but it will look like:

def add_route(direction,source):
node = getattr(lastCity,direction)
if node and not isCityInRouteList(node,source):
tmproute=route[:]
tmproute.append(lastCity.NE)
if tmproute not in duplicatesource:
duplicatesource.append(tmproute)

And you can apply it by iterating over a list of 'directions'.

for dir in ['NE','NW','SE','SW']:
add_route(dir,source)

Post by George
return GetShortestRoute(duplicatesource,destination,recursion+1)

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

[Alan Gauld]

Post by Alan Gauld
lastCity = route[-1]

Oops. looping -> calculating.
--
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

[George]

Post by Alan Gauld

Post by Alan Gauld
lastCity = route[-1]

Oops. looping -> calculating.

Thank u Steven and Alan,

I am sorry to reply late. Your replies were insightful and particularly
Steven's which was more specific to my problem, although i had a slight
difficulty in understanding them. I will get back to you with the
problem on graph with pylab. Although i am also looking into another
solutions to the same problem (me a Python newbie and programming
hobbyist). i will do some programming and will get back to you with my
results.

Thanks again.

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

[Steven D'Aprano]

Post by George
Hello,
I have done little piece of work for finding nearest shortest route from
one point on a graph to other with connected points(cities to be
precise). The way i achieved it is by getting the nearest neighbours in
(NE, NE, SE, SW) and then traversing them one by one until i reach my
destination in the first instance of recursion. this thing works for me
and i am not looking for route solving problems but rather a peculiar
problem of running different lines of code arbitarily.

Generally speaking, pathfinding algorithms that exhaustively check every
possible route should not depend on the order that you search. If you
don't perform an exhaustive search, then they may.

Post by George
The problem with my coding is that it follows a strict route search
algorithm that i hardcoded i.e.
it first searches NE, then NW, then SE, and finally SW. this code will
always find a route but will not be the shortest route which could
either start from any direction.

You don't have to stop at the first route found, you can keep going and
return the shortest route. If you do that, you don't need separate runs:

NE NW SE SW
NE NW SW SE
NE SW NW SE
NE SW SE NW
...

etc. Just run through them all once, in any direction, and when you find
a route, you compare it to any previous route you found, remembering
only the shortest. Or return all the routes.

Post by George
So i have to devise a way by which i
can run all the posibilities to find the best route. so i have to run
4*3*3*3 runs to find out the shortest route.

I think you mean 4*3*2*1.

I don't think you actually need to do that, but if you do, one approach
is to have a "master search" function that takes a set of directions,
then searches in those. Start off with four functions to do a partial
search in a particular direction:


def search_NE():
# Search in the NE direction
...

def search_NW(): ...
def search_SE(): ...
def search_SW(): ...


and a main search that calculates the overall route, if any. There are
two approaches, one uses strings (or integers, but I prefer strings) to
give the directions:

def search(a, b, c, d):
# Search in direction a, b, c then d, in that order:
directions = {
'SW': search_SW, # note carefully there are no parentheses
'SE': search_SE,
'NW': search_NW,
'NE': search_NE,
}
# Find the route
w = directions[a]() # Look up the function, then call it
x = directions[b]()
y = directions[c]()
z = directions[d]()
return route

(Obviously, I haven't looked at how you actually combine the functions
to give a route. That's up to you.)

Then, you can search in all 4! = 24 permutations:

import sys
from itertools import permutations
directions = 'NE SE NW SW'.split()
best = (None, sys.maxsize) # In Python 2, use sys.maxint
for dirs in permutations(directions, 4):
route = search(*dirs)
if distance(route) < best[1]:
best = (route, distance(route))

print(best)


The permutations function will iterate over all of the permutations:
('NE', 'SE', 'NW', 'SW')
('NE', 'SE', 'SW', 'NW')
('NE', 'NW', 'SE', 'SW')
('NE', 'NW', 'SW', 'SE')
etc.



The other approach is to eshew the intervening strings, and just use the
functions themselves:


def search(a, b, c, d):
# Search using functions a, b, c then d, in that order:
w = a()
x = b()
y = c()
z = d()
return route


# Make sure you *don't* call the functions here.
directions = [search_SW, search_NW, search_NE, search_SE]
best = (None, sys.maxsize)
for dirs in permutations(directions, 4):
route = search(*dirs)
if distance(route) < best[1]:
best = (route, distance(route))



Obviously the above is not a complete solution, but hopefully it will
point you in the right direction. Don't hesitate to ask if you have any
questions.