Solution #5a4f6922-a0e9-4208-8265-cc218390e25b

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        b = text.encode("latin1")
11        cnt = array('I', [0]) * 256
12        for x in b:
13            cnt[x] += 1
14
15        freqs = array('I')
16        for c in cnt:
17            if c:
18                freqs.append(c)
19    except:
20        counts = {}
21        get = counts.get
22        for ch in text:
23            counts[ch] = get(ch, 0) + 1
24        vals = counts.values()
25        freqs = array('I', vals)
26
27    m = len(freqs)
28    if m == 1:
29        return {"encoded_length": n, "decoded": text}
30    if m == 2:
31        return {"encoded_length": freqs[0] + freqs[1], "decoded": text}
32
33    freqs = array('I', sorted(freqs))
34    merged = array('I', [0]) * (m - 1)
35
36    i = j = k = 0
37    total = 0
38
39    while k < m - 1:
40        if j >= k:
41            a = freqs[i]
42            i += 1
43        elif i >= m:
44            a = merged[j]
45            j += 1
46        elif freqs[i] <= merged[j]:
47            a = freqs[i]
48            i += 1
49        else:
50            a = merged[j]
51            j += 1
52
53        if j >= k:
54            b2 = freqs[i]
55            i += 1
56        elif i >= m:
57            b2 = merged[j]
58            j += 1
59        elif freqs[i] <= merged[j]:
60            b2 = freqs[i]
61            i += 1
62        else:
63            b2 = merged[j]
64            j += 1
65
66        s = a + b2
67        merged[k] = s
68        total += s
69        k += 1
70
71    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}