Solution #2da814bd-4b7d-485b-b46a-4a1288e60fdf

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    m = len(counts)
13    if m == 1:
14        return {"encoded_length": n, "decoded": text}
15
16    class Node:
17        __slots__ = ("w", "left", "right")
18        def __init__(self, w, left=None, right=None):
19            self.w = w
20            self.left = left
21            self.right = right
22
23    heap = [None] * m
24    i = 0
25    for v in counts.values():
26        heap[i] = Node(v)
27        i += 1
28
29    size = m
30
31    def siftdown(heap, pos, size):
32        item = heap[pos]
33        w = item.w
34        child = (pos << 1) + 1
35        while child < size:
36            right = child + 1
37            if right < size and heap[right].w < heap[child].w:
38                child = right
39            if heap[child].w >= w:
40                break
41            heap[pos] = heap[child]
42            pos = child
43            child = (pos << 1) + 1
44        heap[pos] = item
45
46    def siftup(heap, pos):
47        item = heap[pos]
48        w = item.w
49        while pos:
50            parent = (pos - 1) >> 1
51            if heap[parent].w <= w:
52                break
53            heap[pos] = heap[parent]
54            pos = parent
55        heap[pos] = item
56
57    for i in range((size >> 1) - 1, -1, -1):
58        siftdown(heap, i, size)
59
60    total = 0
61    while size > 1:
62        a = heap[0]
63        size -= 1
64        last = heap[size]
65        if size:
66            heap[0] = last
67            siftdown(heap, 0, size)
68
69        b = heap[0]
70        size -= 1
71        if size:
72            last = heap[size]
73            heap[0] = last
74            siftdown(heap, 0, size)
75
76        s = a.w + b.w
77        total += s
78        node = Node(s, a, b)
79        heap[size] = node
80        size += 1
81        siftup(heap, size - 1)
82
83    root = heap[0]
84    stack = [(root, 0)]
85    encoded_length = 0
86    while stack:
87        node, depth = stack.pop()
88        left = node.left
89        if left is None:
90            encoded_length += node.w * depth
91        else:
92            d = depth + 1
93            stack.append((left, d))
94            stack.append((node.right, d))
95
96    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}