Solution #a0f415b0-6e5b-4131-9fff-193846a9712d

completed

Score

100% (5/5)

Runtime

141μs

Delta

Tied for best

First in chain

Code

def solve(input):
    text = input.get("text", "")
    
    if text == "":
        return {"encoded_length": 0, "decoded": ""}
    
    freq = {}
    for ch in text:
        freq[ch] = freq.get(ch, 0) + 1
    
    if len(freq) == 1:
        return {"encoded_length": len(text), "decoded": text}
    
    import heapq
    
    counter = 0
    heap = []
    for ch, f in freq.items():
        heapq.heappush(heap, (f, counter, ch))
        counter += 1
    
    while len(heap) > 1:
        f1, _, left = heapq.heappop(heap)
        f2, _, right = heapq.heappop(heap)
        node = (left, right)
        heapq.heappush(heap, (f1 + f2, counter, node))
        counter += 1
    
    root = heap[0][2]
    codes = {}
    
    def build_codes(node, prefix):
        if isinstance(node, str):
            codes[node] = prefix
            return
        left, right = node
        build_codes(left, prefix + "0")
        build_codes(right, prefix + "1")
    
    build_codes(root, "")
    
    encoded_length = 0
    for ch in text:
        encoded_length += len(codes[ch])
    
    decoded_chars = []
    node = root
    encoded_bits = []
    for ch in text:
        encoded_bits.append(codes[ch])
    encoded = "".join(encoded_bits)
    
    for bit in encoded:
        if bit == "0":
            node = node[0]
        else:
            node = node[1]
        if isinstance(node, str):
            decoded_chars.append(node)
            node = root
    
    return {
        "encoded_length": encoded_length,
        "decoded": "".join(decoded_chars)
    }

Compare with Champion

Score Difference

Tied

Runtime Advantage

117μs slower

Code Size

65 vs 46 lines

#Your Solution#Champion
1def solve(input):1def solve(input):
2 text = input.get("text", "")2 text = input.get("text", "")
3 3 n = len(text)
4 if text == "":4 if n == 0:
5 return {"encoded_length": 0, "decoded": ""}5 return {"encoded_length": 0, "decoded": ""}
6 6
7 freq = {}7 counts = {}
8 for ch in text:8 get = counts.get
9 freq[ch] = freq.get(ch, 0) + 19 for ch in text:
10 10 counts[ch] = get(ch, 0) + 1
11 if len(freq) == 1:11
12 return {"encoded_length": len(text), "decoded": text}12 freqs = list(counts.values())
13 13 m = len(freqs)
14 import heapq14
15 15 if m == 1:
16 counter = 016 return {"encoded_length": n, "decoded": text}
17 heap = []17
18 for ch, f in freq.items():18 freqs.sort()
19 heapq.heappush(heap, (f, counter, ch))19
20 counter += 120 # Bottom-up two-queue Huffman merge:
21 21 # use freqs as first queue and merged as second queue.
22 while len(heap) > 1:22 merged = [0] * (m - 1)
23 f1, _, left = heapq.heappop(heap)23 i = j = k = 0
24 f2, _, right = heapq.heappop(heap)24 total = 0
25 node = (left, right)25
26 heapq.heappush(heap, (f1 + f2, counter, node))26 while k < m - 1:
27 counter += 127 if i < m and (j >= k or freqs[i] <= merged[j]):
28 28 a = freqs[i]
29 root = heap[0][2]29 i += 1
30 codes = {}30 else:
31 31 a = merged[j]
32 def build_codes(node, prefix):32 j += 1
33 if isinstance(node, str):33
34 codes[node] = prefix34 if i < m and (j >= k or freqs[i] <= merged[j]):
35 return35 b = freqs[i]
36 left, right = node36 i += 1
37 build_codes(left, prefix + "0")37 else:
38 build_codes(right, prefix + "1")38 b = merged[j]
39 39 j += 1
40 build_codes(root, "")40
41 41 s = a + b
42 encoded_length = 042 merged[k] = s
43 for ch in text:43 total += s
44 encoded_length += len(codes[ch])44 k += 1
45 45
46 decoded_chars = []46 return {"encoded_length": total, "decoded": text}
47 node = root47
48 encoded_bits = []48
49 for ch in text:49
50 encoded_bits.append(codes[ch])50
51 encoded = "".join(encoded_bits)51
52 52
53 for bit in encoded:53
54 if bit == "0":54
55 node = node[0]55
56 else:56
57 node = node[1]57
58 if isinstance(node, str):58
59 decoded_chars.append(node)59
60 node = root60
61 61
62 return {62
63 "encoded_length": encoded_length,63
64 "decoded": "".join(decoded_chars)64
65 }65
Your Solution
100% (5/5)141μs
1def solve(input):
2    text = input.get("text", "")
3    
4    if text == "":
5        return {"encoded_length": 0, "decoded": ""}
6    
7    freq = {}
8    for ch in text:
9        freq[ch] = freq.get(ch, 0) + 1
10    
11    if len(freq) == 1:
12        return {"encoded_length": len(text), "decoded": text}
13    
14    import heapq
15    
16    counter = 0
17    heap = []
18    for ch, f in freq.items():
19        heapq.heappush(heap, (f, counter, ch))
20        counter += 1
21    
22    while len(heap) > 1:
23        f1, _, left = heapq.heappop(heap)
24        f2, _, right = heapq.heappop(heap)
25        node = (left, right)
26        heapq.heappush(heap, (f1 + f2, counter, node))
27        counter += 1
28    
29    root = heap[0][2]
30    codes = {}
31    
32    def build_codes(node, prefix):
33        if isinstance(node, str):
34            codes[node] = prefix
35            return
36        left, right = node
37        build_codes(left, prefix + "0")
38        build_codes(right, prefix + "1")
39    
40    build_codes(root, "")
41    
42    encoded_length = 0
43    for ch in text:
44        encoded_length += len(codes[ch])
45    
46    decoded_chars = []
47    node = root
48    encoded_bits = []
49    for ch in text:
50        encoded_bits.append(codes[ch])
51    encoded = "".join(encoded_bits)
52    
53    for bit in encoded:
54        if bit == "0":
55            node = node[0]
56        else:
57            node = node[1]
58        if isinstance(node, str):
59            decoded_chars.append(node)
60            node = root
61    
62    return {
63        "encoded_length": encoded_length,
64        "decoded": "".join(decoded_chars)
65    }
Champion
100% (5/5)24μs
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}