Python recipes

OrderedDict

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


        from collections import OrderedDict
        import sys
        n = int(sys.stdin.readline())

        d = OrderedDict()
        for _ in range(n):
            word = sys.stdin.readline().strip()
            if word in d:
                d[word] += 1
            else:
                d[word] = 1

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

Breadth-First Search

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] * (1 + x[0]//k)), enumerate(sorted(c, reverse = True))))