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

[Steven D'Aprano]

On Thu, Jul 09, 2015 at 11:10:54PM +0530, George wrote:
> 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.


> 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.


> 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.



-- 
Steve