Solution #d720f0bf-a6c8-49aa-aae0-4cb9c0718e07

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 array import array
8
9    try:
10        counts = array('I', [0]) * 256
11        for ch in text:
12            counts[ord(ch)] += 1
13
14        freqs = array('I')
15        for c in counts:
16            if c:
17                freqs.append(c)
18    except:
19        d = {}
20        for ch in text:
21            d[ch] = d.get(ch, 0) + 1
22        freqs = array('I', d.values())
23
24    m = len(freqs)
25    if m == 1:
26        return {"encoded_length": n, "decoded": text}
27
28    freqs = array('I', sorted(freqs))
29    merged = array('I', [0]) * (m - 1)
30
31    i = 0
32    j = 0
33    total = 0
34
35    for k in range(m - 1):
36        if i < m and (j >= k or freqs[i] <= merged[j]):
37            a = freqs[i]
38            i += 1
39        else:
40            a = merged[j]
41            j += 1
42
43        if i < m and (j >= k or freqs[i] <= merged[j]):
44            b = freqs[i]
45            i += 1
46        else:
47            b = merged[j]
48            j += 1
49
50        s = a + b
51        merged[k] = s
52        total += s
53
54    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}