Solution #96012705-a644-4e7e-b0e0-3d2f937dd240

1def solve(input):
2    text = input.get("text", "")
3    n = len(text)
4    if n == 0:
5        return {"encoded_length": 0, "decoded": ""}
6
7    try:
8        b = text.encode("latin1")
9        counts = [0] * 256
10        for x in b:
11            counts[x] += 1
12
13        vals = [c for c in counts if c]
14    except:
15        cps = [ord(ch) for ch in text]
16        cps.sort()
17        vals = []
18        prev = cps[0]
19        cnt = 1
20        for x in cps[1:]:
21            if x == prev:
22                cnt += 1
23            else:
24                vals.append(cnt)
25                prev = x
26                cnt = 1
27        vals.append(cnt)
28
29    m = len(vals)
30    if m == 1:
31        return {"encoded_length": n, "decoded": text}
32
33    vals.sort()
34    q = [0] * (m - 1)
35    i = j = k = total = 0
36
37    while k < m - 1:
38        if i < m and (j >= k or vals[i] <= q[j]):
39            a = vals[i]
40            i += 1
41        else:
42            a = q[j]
43            j += 1
44
45        if i < m and (j >= k or vals[i] <= q[j]):
46            b = vals[i]
47            i += 1
48        else:
49            b = q[j]
50            j += 1
51
52        s = a + b
53        total += s
54        q[k] = s
55        k += 1
56
57    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}