Solution #8cb031c4-b03a-4baf-8b27-800b528a2979

1def solve(input):
2    text = input.get("text", "")
3    n = len(text)
4    if n == 0:
5        return {"encoded_length": 0, "decoded": ""}
6
7    class Node:
8        __slots__ = ("freq", "ch", "left", "right")
9        def __init__(self, freq, ch=None, left=None, right=None):
10            self.freq = freq
11            self.ch = ch
12            self.left = left
13            self.right = right
14
15    counts = {}
16    get = counts.get
17    for ch in text:
18        counts[ch] = get(ch, 0) + 1
19
20    if len(counts) == 1:
21        return {"encoded_length": n, "decoded": text}
22
23    heap = []
24    push = heap.append
25    seq = 0
26    for ch, freq in counts.items():
27        push([freq, seq, Node(freq, ch=ch)])
28        seq += 1
29
30    heap.sort()
31
32    def siftdown(h, startpos, pos):
33        newitem = h[pos]
34        while pos > startpos:
35            parentpos = (pos - 1) >> 1
36            parent = h[parentpos]
37            if newitem < parent:
38                h[pos] = parent
39                pos = parentpos
40                continue
41            break
42        h[pos] = newitem
43
44    def siftup(h, pos):
45        endpos = len(h)
46        startpos = pos
47        newitem = h[pos]
48        childpos = 2 * pos + 1
49        while childpos < endpos:
50            rightpos = childpos + 1
51            if rightpos < endpos and not h[childpos] < h[rightpos]:
52                childpos = rightpos
53            h[pos] = h[childpos]
54            pos = childpos
55            childpos = 2 * pos + 1
56        h[pos] = newitem
57        siftdown(h, startpos, pos)
58
59    def heappop(h):
60        lastelt = h.pop()
61        if h:
62            returnitem = h[0]
63            h[0] = lastelt
64            siftup(h, 0)
65            return returnitem
66        return lastelt
67
68    def heappush(h, item):
69        h.append(item)
70        siftdown(h, 0, len(h) - 1)
71
72    while len(heap) > 1:
73        f1, _, n1 = heappop(heap)
74        f2, _, n2 = heappop(heap)
75        parent = Node(f1 + f2, left=n1, right=n2)
76        heappush(heap, [parent.freq, seq, parent])
77        seq += 1
78
79    root = heap[0][2]
80
81    codes = {}
82    stack = [(root, 0)]
83    cset = codes.__setitem__
84    while stack:
85        node, depth = stack.pop()
86        ch = node.ch
87        if ch is not None:
88            cset(ch, depth)
89        else:
90            stack.append((node.left, depth + 1))
91            stack.append((node.right, depth + 1))
92
93    total = 0
94    for ch, freq in counts.items():
95        total += freq * codes[ch]
96
97    out = []
98    append = out.append
99    node = root
100    idx = 0
101    while idx < n:
102        ch = text[idx]
103        if ch == node.left.ch if node.left and node.left.ch is not None and node.right and node.right.ch is not None else False:
104            pass
105        idx += 1
106
107    # Build encoded bitstream as bytes of 0/1 integers for decoding verification
108    bits = []
109    bappend = bits.append
110
111    paths = {}
112    stack = [(root, "")]
113    pset = paths.__setitem__
114    while stack:
115        node, code = stack.pop()
116        ch = node.ch
117        if ch is not None:
118            pset(ch, code if code else "0")
119        else:
120            stack.append((node.right, code + "1"))
121            stack.append((node.left, code + "0"))
122
123    for ch in text:
124        code = paths[ch]
125        for bit in code:
126            bappend(bit)
127
128    if root.ch is not None:
129        decoded = root.ch * len(bits)
130    else:
131        decoded_chars = []
132        dappend = decoded_chars.append
133        node = root
134        for bit in bits:
135            node = node.left if bit == "0" else node.right
136            if node.ch is not None:
137                dappend(node.ch)
138                node = root
139        decoded = "".join(decoded_chars)
140
141    return {"encoded_length": total, "decoded": decoded}

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}