Python recipes

### OrderedDict

The collections module provides many useful data structures. One of them is OrderedDict:

``````
from collections import OrderedDict
import sys

d = OrderedDict()
for _ in range(n):
if word in d:
d[word] += 1
else:
d[word] = 1

print(len(d))
print(*d.values())
``````

Breadth-First Search (BFS) framework uses a queue data structure to reach nodes that are the closest to the root node first

``````
from collections import defaultdict, deque

def bfs(n, m, edges, s):
graph = defaultdict(list)
for node1, node2 in edges:
graph[node1].append(node2)
graph[node2].append(node1)

dists = defaultdict(lambda: -1)
dists[s] = 0
queue = deque([s])
while queue:
v = queue.popleft()
for neighbor in graph[v]:
if dists[neighbor] < 0:
queue.append(neighbor)
dists[neighbor] = dists[v] + 6
return [dists[i] for i in range(1, n+1) if i != s]
``````

### MapReduce

MapReduce is a framework that allows for parallel computation of summary statistics.

``````
from functools import reduce
def getMinimumCost(k, c):
reduce(lambda acc, val: acc + val, map(lambda x: (x * (1 + x//k)), enumerate(sorted(c, reverse = True))))
``````