Solution #52d74aac-4748-47c9-ba8b-8f14a1a3c301

1def solve(input):
2    text = input.get("text", "")
3    n = len(text)
4    if n == 0:
5        return {"encoded_length": 0, "decoded": ""}
6
7    def build_counts(i, counts):
8        if i == n:
9            return counts
10        ch = text[i]
11        counts[ch] = counts.get(ch, 0) + 1
12        return build_counts(i + 1, counts)
13
14    counts = build_counts(0, {})
15    freqs = list(counts.values())
16    m = len(freqs)
17
18    if m == 1:
19        return {"encoded_length": n, "decoded": text}
20
21    def heapify_down(heap, size, i):
22        l = (i << 1) + 1
23        if l >= size:
24            return
25        r = l + 1
26        c = r if r < size and heap[r] < heap[l] else l
27        if heap[c] < heap[i]:
28            heap[i], heap[c] = heap[c], heap[i]
29            heapify_down(heap, size, c)
30
31    def heapify_build(heap, i):
32        if i < 0:
33            return
34        heapify_down(heap, len(heap), i)
35        heapify_build(heap, i - 1)
36
37    heap = freqs[:]
38    heapify_build(heap, (len(heap) >> 1) - 1)
39
40    def sift_up(heap, i):
41        if i == 0:
42            return
43        p = (i - 1) >> 1
44        if heap[i] < heap[p]:
45            heap[i], heap[p] = heap[p], heap[i]
46            sift_up(heap, p)
47
48    def heappush(heap, x):
49        heap.append(x)
50        sift_up(heap, len(heap) - 1)
51
52    def heappop(heap):
53        root = heap[0]
54        last = heap.pop()
55        if heap:
56            heap[0] = last
57            heapify_down(heap, len(heap), 0)
58        return root
59
60    def merge_all(heap, total):
61        if len(heap) == 1:
62            return total
63        a = heappop(heap)
64        b = heappop(heap)
65        s = a + b
66        heappush(heap, s)
67        return merge_all(heap, total + s)
68
69    total = merge_all(heap, 0)
70    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}