Solution #62082b2d-9da5-46b1-994d-9b75f5adee57

1def solve(input):
2    text = input.get("text", "")
3    n = len(text)
4    if not n:
5        return {"encoded_length": 0, "decoded": ""}
6
7    freq = {}
8    get = freq.get
9    for ch in text:
10        freq[ch] = get(ch, 0) + 1
11
12    m = len(freq)
13    if m == 1:
14        return {"encoded_length": n, "decoded": text}
15
16    class Node:
17        __slots__ = ("w", "left", "right", "ch")
18        def __init__(self, w, left=None, right=None, ch=None):
19            self.w = w
20            self.left = left
21            self.right = right
22            self.ch = ch
23
24    heap = [Node(f, None, None, ch) for ch, f in freq.items()]
25    size = len(heap)
26
27    def sift_down(i, size, heap):
28        item = heap[i]
29        iw = item.w
30        while True:
31            l = (i << 1) + 1
32            if l >= size:
33                break
34            r = l + 1
35            c = l
36            cw = heap[l].w
37            if r < size:
38                rw = heap[r].w
39                if rw < cw:
40                    c = r
41                    cw = rw
42            if cw >= iw:
43                break
44            heap[i] = heap[c]
45            i = c
46        heap[i] = item
47
48    def sift_up(i, heap):
49        item = heap[i]
50        iw = item.w
51        while i:
52            p = (i - 1) >> 1
53            pw = heap[p].w
54            if pw <= iw:
55                break
56            heap[i] = heap[p]
57            i = p
58        heap[i] = item
59
60    for i in range((size >> 1) - 1, -1, -1):
61        sift_down(i, size, heap)
62
63    while size > 1:
64        a = heap[0]
65        size -= 1
66        last = heap[size]
67        if size:
68            heap[0] = last
69            sift_down(0, size, heap)
70
71        b = heap[0]
72        size -= 1
73        if size:
74            last = heap[size]
75            heap[0] = last
76            sift_down(0, size, heap)
77
78        parent = Node(a.w + b.w, a, b, None)
79        if size < len(heap):
80            heap[size] = parent
81        else:
82            heap.append(parent)
83        sift_up(size, heap)
84        size += 1
85
86    root = heap[0]
87    encoded_length = 0
88    stack = [(root, 0)]
89    append = stack.append
90    pop = stack.pop
91
92    while stack:
93        node, depth = pop()
94        ch = node.ch
95        if ch is not None:
96            encoded_length += node.w * depth
97        else:
98            nd = depth + 1
99            append((node.left, nd))
100            append((node.right, nd))
101
102    return {"encoded_length": encoded_length, "decoded": text}

1def solve(input):
2    text = input.get("text", "")
3    n = len(text)
4    if n == 0:
5        return {"encoded_length": 0, "decoded": ""}
6
7    counts = {}
8    get = counts.get
9    for ch in text:
10        counts[ch] = get(ch, 0) + 1
11
12    freqs = list(counts.values())
13    m = len(freqs)
14
15    if m == 1:
16        return {"encoded_length": n, "decoded": text}
17
18    freqs.sort()
19
20    # Bottom-up two-queue Huffman merge:
21    # use freqs as first queue and merged as second queue.
22    merged = [0] * (m - 1)
23    i = j = k = 0
24    total = 0
25
26    while k < m - 1:
27        if i < m and (j >= k or freqs[i] <= merged[j]):
28            a = freqs[i]
29            i += 1
30        else:
31            a = merged[j]
32            j += 1
33
34        if i < m and (j >= k or freqs[i] <= merged[j]):
35            b = freqs[i]
36            i += 1
37        else:
38            b = merged[j]
39            j += 1
40
41        s = a + b
42        merged[k] = s
43        total += s
44        k += 1
45
46    return {"encoded_length": total, "decoded": text}