Solution #15ec7bd1-f974-4ad2-b7cb-c562c061bacf

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        freqs = []
14        for c in counts:
15            if c:
16                freqs.append(c)
17    except:
18        counts = {}
19        get = counts.get
20        for ch in text:
21            counts[ch] = get(ch, 0) + 1
22        freqs = list(counts.values())
23
24    m = len(freqs)
25    if m == 1:
26        return {"encoded_length": n, "decoded": text}
27
28    freqs.sort()
29
30    if m == 2:
31        return {"encoded_length": freqs[0] + freqs[1], "decoded": text}
32
33    merged = [0] * (m - 1)
34    i = j = k = 0
35    total = 0
36
37    while k < m - 1:
38        fi = freqs
39        mg = merged
40
41        if j >= k or (i < m and fi[i] <= mg[j]):
42            a = fi[i]
43            i += 1
44        else:
45            a = mg[j]
46            j += 1
47
48        if j >= k or (i < m and fi[i] <= mg[j]):
49            b2 = fi[i]
50            i += 1
51        else:
52            b2 = mg[j]
53            j += 1
54
55        s = a + b2
56        mg[k] = s
57        total += s
58        k += 1
59
60    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}