算法、正则表达式知识

#The Word Ladder Problem
from pythonds.graphs import Graph
from pythonds.basic import Queue

def traverse(y):
    path=''
    x = y
    while (x.getPred()):
        path+=x.getId()+'->'
        x = x.getPred()
    path+=x.getId()
    print path
    
def bfs(g, start):
    start.setDistance(0)
    start.setPred(None)
    vertQueue = Queue()
    vertQueue.enqueue(start)
    while (vertQueue.size() > 0):
        currentVert = vertQueue.dequeue()
        for nbr in currentVert.getConnections():
            if (nbr.getColor() == 'white'):
                nbr.setColor('gray')
                nbr.setDistance(currentVert.getDistance() + 1)
                nbr.setPred(currentVert)
                vertQueue.enqueue(nbr)
        currentVert.setColor('black')

def buildGraph(wordFile):
    d = {}
    g = Graph()
    wfile = open(wordFile,'r')
    # create buckets of words that differ by one letter
    for line in wfile:
        word = line[:-1]
        for i in range(len(word)):
            bucket = word[:i] + '_' + word[i+1:]
            if bucket in d:
                d[bucket].append(word)
            else:
                d[bucket] = [word]
    # add vertices and edges for words in the same bucket
    for bucket in d.keys():
        for word1 in d[bucket]:
            for word2 in d[bucket]:
                if word1 != word2:
                    g.addEdge(word1,word2)
    return g

g=buildGraph('wordfile.txt')
start=g.getVertex('fool')
bfs(g,start)
traverse(g.getVertex('sage'))  #sage->sale->pale->pall->poll->pool->fool

#原文链接www.redblobgames.com/pathfinding/a-star/implementation.html
import collections
class Graph:
    def __init__(self):
        self.edges = {}
    def neighbors(self, id):
        return self.edges[id]
example_graph = Graph()
example_graph.edges = {
    'A': ['B'],
    'B': ['A', 'C', 'D'],
    'C': ['A'],
    'D': ['E', 'A'],
    'E': ['B']
}
class Queue:
    def __init__(self):
        self.elements = collections.deque() 
    def empty(self):
        return len(self.elements) == 0  
    def put(self, x):
        self.elements.append(x)
    def get(self):
        return self.elements.popleft()
def breadth_first_search(graph, start):
    frontier = Queue()
    frontier.put(start)
    visited = {}
    visited[start] = True
    while not frontier.empty():
        current = frontier.get()
        print("Visiting %r" % current)
        for next_ in graph.neighbors(current):
            if next_ not in visited:
                frontier.put(next_)
                visited[next_] = True
breadth_first_search(example_graph, 'A')
# Visiting 'A'
# Visiting 'B'
# Visiting 'C'
# Visiting 'D'
# Visiting 'E'

#数学迷宫
# coding: utf-8
P=[]
dirs=[[0,1,'D'],[1,0,'R'],[0,-1,'U'],[-1,0,'L']] 
D={'D':(0,1),'R':(1,0),'U':(0,-1),'L':(-1,0)}

data=[[0,0,0,0,0],
      [0,0,0,0,0],
      [0,0,0,0,0],
      [0,0,0,0,0],
      [0,0,0,0,0]]
v = [[9,3,5,8,4],
    [1,6,9,3,2],
    [7,4,5,4,1],
    [5,3,6,8,9],
    [4,2,8,3,0]]

def move(path,x,y,field):
    field[y][x]=1 
    if x==4 and y==4: 
        P.append(path)
    else:            
        for d in dirs:
            y1=y+d[1]
            x1=x+d[0]
            if y1<5 and y1>-1 and x1<5 and x1>-1:
                if field[y1][x1]==0: 
                    move(path+d[2],x+d[0],y+d[1],field)           
    field[y][x]=0       
                       
move('',0,0,data)
count=0
for s in P:
    sum_=v[0][0]
    (x,y)=(0,0)
    e=str(sum_)
    for c in s:
        t=D[c] 
        (x,y)=(x+t[0],y+t[1])
        if c in ['L','R']:
            sum_+=v[y][x]
            e+='+'+str(v[y][x])
        else:
            sum_-=v[y][x]
            e+='-'+str(v[y][x])
    if sum_==0:
        count+=1
        print '走法 \''+s+'\' 求和 ='+e
print '只有'+str(count)+'种情况满足题目要求'
#print len(P)
#走法 'RRDLLDRRDLDRRUUURDDD' 求和 =9+3+5-9+6+1-7+4+5-6+3-2+8+3-8-4-3+2-1-9-0
#只有171种情况满足题目要求  8512种走法

#http://hujiaweibujidao.github.io/blog/2014/07/01/python-algorithms-induction/
#拓扑排序
def topsort(G):
    count = dict((u, 0) for u in G)  # The in-degree for each node
    for u in G:
        for v in G[u]:
            count[v] += 1  # Count every in-edge
    Q = [u for u in G if count[u] == 0]  # Valid initial nodes
    S = []  # The result
    while Q:  # While we have start nodes...
        u = Q.pop()  # Pick one
        S.append(u)  # Use it as first of the rest
        for v in G[u]:
            count[v] -= 1  # "Uncount" its out-edges
            if count[v] == 0:  # New valid start nodes?
                Q.append(v)  # Deal with them next
    return S

G = {'a': set('bf'), 'b': set('cdf'),'c': set('d'), 'd': set('ef'), 'e': set('f'), 'f': set()}
print topsort(G) # ['a', 'b', 'c', 'd', 'e', 'f']