quinta-feira, julho 14, 2011

def __init__(self, name): "The Art of Computer Programming" by Donald E. Knuth



(Original Review, 2011)


Here's my code and a sample run attempting to find the shortest path from "Home" to "School":

class Location:
    def __init__(self, name):
        self.name = name
        self.connections = []

    def set_connections(self, connections):
        self.connections = connections

    def __str__(self):
        return self.name

home = Location("Home")
storeA = Location("StoreA")
storeB = Location("StoreB")
school = Location("School")
intersection = Location("Intersection")

home.set_connections([storeA, storeB, intersection])
storeA.set_connections([home, storeB])
storeB.set_connections([school])
school.set_connections([storeB, intersection])
intersection.set_connections([school])

visited = []
paths = []

def find_path(start, dest):
    visited.append(start)
    if start.connections.count(dest) == 1:
        print("From ", start, " to ", dest)
        print("Found", dest)
        visited.append(dest)
        paths.append(list(visited))
        visited.clear()
    else:
        for location in start.connections:
            if visited.count(location) != 1:
                #visited.append(location)
                print("From ", start, " to ", location)
                find_path(location, dest)

find_path(home, school)

minn = len(paths[0])
index = 0
for i in range(len(paths)):
    #print(paths[i])
    if minn > len(paths[i]):
        minn = len(paths[i])
        index = i

print("The shortest path is:")
for j in range(len(paths[index])):
    print("From ", paths[index][j], " to ")

#Output:
From  Home  to  StoreA
From  StoreA  to  StoreB
From  StoreB  to  School
Found School
From  Home  to  StoreB
From  StoreB  to  School
Found School
From  Home  to  Intersection
From  Intersection  to  School
Found School
The shortest path is:
From  StoreB  to
From  School  to

Question: What Knuth algorithm did I use here? 

Bottom-line: Knuth once said something that I still remember to this day (and I follow this dictum to the letter): "Do your own thing and know what you are talking about."