Solution #f68f5746-1281-447a-910e-83fc1d850202

1def solve(input):
2    text = input.get("text", "")
3    n = len(text)
4    if n == 0:
5        return {"encoded_length": 0, "decoded": ""}
6
7    # Precomputed popcount table for wildcard direct-indexing requirement
8    POP8 = (
9        0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,
10        1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
11        1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
12        2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
13        1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
14        2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
15        2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
16        3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
17        1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
18        2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
19        2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
20        3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
21        2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
22        3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
23        3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
24        4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8
25    )
26
27    # Radically different frequency counting:
28    # bitset per byte value using Python big ints, then direct-index popcount table.
29    try:
30        b = text.encode("latin1")
31        masks = [0] * 256
32        bit = 1
33        for c in b:
34            masks[c] |= bit
35            bit <<= 1
36
37        freqs = []
38        append = freqs.append
39        uniq = 0
40        for m in masks:
41            if m:
42                uniq += 1
43                cnt = 0
44                while m:
45                    cnt += POP8[m & 255]
46                    m >>= 8
47                append(cnt)
48    except:
49        counts = {}
50        get = counts.get
51        for ch in text:
52            counts[ch] = get(ch, 0) + 1
53        freqs = list(counts.values())
54        uniq = len(freqs)
55
56    if uniq <= 2:
57        return {"encoded_length": n, "decoded": text}
58
59    # Two-queue Huffman after sorting frequencies, avoiding heap operations.
60    freqs.sort()
61    m = len(freqs)
62    q2 = [0] * (m - 1)
63    i = j = k = 0
64    total = 0
65
66    def take():
67        nonlocal i, j
68        if i < m and (j >= k or freqs[i] <= q2[j]):
69            v = freqs[i]
70            i += 1
71            return v
72        v = q2[j]
73        j += 1
74        return v
75
76    while k < m - 1:
77        s = take() + take()
78        total += s
79        q2[k] = s
80        k += 1
81
82    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}