Solution #b513de2d-45cb-4c37-a6f4-0777c70b7998

1def solve(input):
2    text = input.get("text", "")
3    n = len(text)
4    if not n:
5        return {"encoded_length": 0, "decoded": ""}
6
7    class Node:
8        __slots__ = ("w", "left", "right")
9        def __init__(self, w, left=None, right=None):
10            self.w = w
11            self.left = left
12            self.right = right
13
14    try:
15        b = text.encode("latin1")
16        counts = [0] * 256
17        for x in b:
18            counts[x] += 1
19        nodes = [Node(c) for c in counts if c]
20    except:
21        d = {}
22        get = d.get
23        for ch in text:
24            d[ch] = get(ch, 0) + 1
25        nodes = [Node(c) for c in d.values()]
26
27    m = len(nodes)
28    if m == 1:
29        return {"encoded_length": n, "decoded": text}
30
31    nodes.sort(key=lambda node: node.w)
32
33    i = 0
34    q = []
35    qi = 0
36    q_append = q.append
37    total = 0
38
39    def pop_smallest():
40        nonlocal i, qi
41        if i < m:
42            if qi < len(q):
43                if nodes[i].w <= q[qi].w:
44                    x = nodes[i]
45                    i += 1
46                    return x
47                x = q[qi]
48                qi += 1
49                return x
50            x = nodes[i]
51            i += 1
52            return x
53        x = q[qi]
54        qi += 1
55        return x
56
57    remaining = m
58    while remaining > 1:
59        a = pop_smallest()
60        b = pop_smallest()
61        s = a.w + b.w
62        total += s
63        q_append(Node(s, a, b))
64        remaining -= 1
65
66    root = q[-1]
67    decoded = []
68    stack = [(root, 0)]
69    dec_append = decoded.append
70    while stack:
71        node, depth = stack.pop()
72        left = node.left
73        if left is None:
74            dec_append(node.w << depth)
75        else:
76            stack.append((left, depth + 1))
77            stack.append((node.right, depth + 1))
78
79    return {"encoded_length": total, "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}