In this task you have to code process planner.

You will be given initial thing, target thing and a set of processes to turn one thing into another (in the form of _[process\_name, start\_thing, end\_thing]_). You must return  names of shortest sequence of processes to turn initial thing into target thing, or empty sequence if it's impossible.

If start already equals end, return [], since no path is required.

Example: 

```python
test_processes = [
        ['gather', 'field', 'wheat'],
        ['bake', 'flour', 'bread'],
        ['mill', 'wheat', 'flour']
];

processes('field', 'bread', test_processes) # should return ['gather', 'mill', 'bake']
processes('field', 'ferrari', test_processes) # should return []
processes('field', 'field', test_processes) # should return [], since no processes are needed
```

Good luck!

Difficulty: introductory

Starter code:

def processes(start, end, processes):
	

Solutions:
def processes(start, end, processes):
  '''Dijkstra's shortest path algorithm'''
  q = [(start,[])]
  visited = set()
  
  while q:
      s, path = q.pop(0)
      if s == end: return path
      visited.add(s)
      for p in [x for x in processes if x[1] == s]:
          if not p[2] in visited:
              q.append((p[2], path + [p[0]]))
  return []


from collections import deque
def processes(start, end, graph):
    Q = deque([[i,[]] for i in graph if i[1]==start])
    visited = set()
    while Q:
        (p, s, e), path = Q.popleft()
        path.append(p)
        visited.add((s, e))
        if e == end : return path
        for k in graph:
            if k[1] == e and tuple(k[1:]) not in visited : Q.append([k, path[:]])
    return []

from collections import defaultdict, deque

def processes(start, end, processes):
    D, L, S = defaultdict(dict), deque([(start, [])]), set()
    for a, b, c in processes: D[b][a] = c
    while L:
        current, path = L.pop()
        if current == end: return path
        if current not in S:
            S.add(current)
            for k,v in D[current].items():
                L.appendleft((v, path+[k]))
    return []

def processes(start, end, processes):
    if start == end: return []
    result = check(start, end, processes, [])
    if result == None: return []
    return result
    
def check(start, end, processes, result):
    if start == end: return result
    results = []
    for i in processes:
        if i[1] == start:
            try:
                tmp = result.copy()
                tmp.append(i[0])
                tmp2 = check(i[2], end, processes, tmp)
                if tmp2 != None:
                    results.append(tmp2)
            except: return None
    if len(results) > 0: return min(results, key=len)
    else: return None

from collections import defaultdict, namedtuple

Edge = namedtuple('Edge', ['process_name', 'to'])
State = namedtuple('State', ['stack', 'visited', 'min_stack'])

def dfs(graph, cur_node, end_node, state):
    if cur_node in state.visited:
        return
    if len(state.min_stack) and len(state.stack) >= len(state.min_stack):
        return
    if cur_node == end_node:
        state.min_stack.clear()
        state.min_stack.extend(state.stack)
        return

    state.visited.add(cur_node)
    for process, node in graph[cur_node]:
        state.stack.append(process)
        dfs(graph, node, end_node, state)
        state.stack.pop()
    state.visited.remove(cur_node)

def processes(start, end, processes):
  if start == end:
      return []
  graph = defaultdict(list)
  
  for process_name, start_node, end_node in processes:
      graph[start_node].append(Edge(process_name, end_node))
  
  state = State([], set(), [])
  dfs(graph, start, end, state)
  
  return state.min_stack

def processes(start, end, procs):
    def _p(start, end, procs, re_):
        for step in procs:
            res = re_[:]
            if step[1] == start:
                res.append(step[0])

                _p(step[2], end, [x for x in procs if x != step], res)

                if step[2] == end:
                    _p.gres.append(res);


    _p.gres = []
    _p(start, end, procs, [])
    return min(_p.gres, key=lambda x: len(x)) if _p.gres else []


def processes(start, end, processes):
  sequences=[[start,[]]]
  while len(sequences) > 0:
      k = sequences[0]
      del sequences[0]
      node=k[0]
      path=k[1]
      if node == end: return path
      for n in processes:
          if n[1] == node and n[0] not in path:
              sequences.append([n[2],path+[n[0]]])
  return []

def processes(start, end, processes):
    pss = []
    def proc(start, end, ps, l=[]): [pss.append(l + [ps[i][0]]) if ps[i][-1] == end else proc(ps[i][-1], end,  ps[:i] + ps[i+1:], l + [ps[i][0]]) for i in range(len(ps)) if ps[i][1] == start]    
    return proc(start, end, processes) or (min(pss, key=len) if pss else [])

from collections import defaultdict

def processes(start, end, processes):
    d = defaultdict(list)
    for process, x, y in processes:
        d[x].append((y, process))
    visited, nodes = set(), [(start, [])]
    while nodes:
        next = []
        for node, path in nodes:
            if node in visited: 
                continue
            if node == end:
                return path
            visited.add(node)
            for y, process in d[node]:
                next.append((y, path + [process]))
        nodes = next
    return []

from collections import defaultdict

def prcs(start, end, procs, path):
    if start == end:
        return path

    paths = []
    try:
        for p in procs[start]:
            if p in path:
                continue
            paths.append(prcs(p[1], end, procs, path + [p]))
        return min([a for a in paths if a and a[-1][1] == end], key=len)
    except (KeyError, ValueError):
        return []
    


def processes(start, end, procs):
    dd = defaultdict(list)
    for n, s, e in procs:
        dd[s].append((n, e))

    return [n for n, _ in prcs(start, end, dd, [])]