Solution #96773990-608b-44da-a8ad-1e9df695bea7

1def solve(input):
2    text = input.get("text", "")
3    n = len(text)
4    if n == 0:
5        return {"encoded_length": 0, "decoded": ""}
6
7    from functools import lru_cache
8
9    @lru_cache(None)
10    def count_ascii(s):
11        arr = [0] * 256
12        all_ascii = True
13        for ch in s:
14            o = ord(ch)
15            if o < 256:
16                arr[o] += 1
17            else:
18                all_ascii = False
19                break
20        return all_ascii, tuple(arr)
21
22    all_ascii, arr = count_ascii(text)
23
24    if all_ascii:
25        freqs = [c for c in arr if c]
26    else:
27        counts = {}
28        get = counts.get
29        for ch in text:
30            counts[ch] = get(ch, 0) + 1
31        freqs = list(counts.values())
32
33    m = len(freqs)
34    if m == 1:
35        return {"encoded_length": n, "decoded": text}
36
37    freqs.sort()
38
39    @lru_cache(None)
40    def merged_sum(sorted_freqs):
41        vals = list(sorted_freqs)
42        m = len(vals)
43        if m <= 1:
44            return 0
45
46        q1 = 0
47        q2 = 0
48        made = 0
49        merged = [0] * (m - 1)
50        total = 0
51
52        while made < m - 1:
53            if q1 < m and (q2 >= made or vals[q1] <= merged[q2]):
54                a = vals[q1]
55                q1 += 1
56            else:
57                a = merged[q2]
58                q2 += 1
59
60            if q1 < m and (q2 >= made or vals[q1] <= merged[q2]):
61                b = vals[q1]
62                q1 += 1
63            else:
64                b = merged[q2]
65                q2 += 1
66
67            s = a + b
68            merged[made] = s
69            total += s
70            made += 1
71
72        return total
73
74    return {"encoded_length": merged_sum(tuple(freqs)), "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}