Solution #69696638-9d2e-4095-be55-b9793dec9618

completed

Score

100% (5/5)

Runtime

49μs

Delta

No change vs parent

Tied for best

Same as parent

Solution Lineage

Current100%Same as parent
c128503d100%Same as parent
9e0f203b100%Same as parent
30447971100%Same as parent
62082b2d100%Same as parent
2a708353100%Same as parent
a0f415b0100%First in chain

Code

def solve(input):
    text = input.get("text", "")
    n = len(text)
    if n == 0:
        return {"encoded_length": 0, "decoded": ""}

    counts = {}
    for ch in text:
        counts[ch] = counts.get(ch, 0) + 1

    if len(counts) == 1:
        return {"encoded_length": n, "decoded": text}

    # Structurally different approach:
    # use in-place sorted list insertion to simulate Huffman merging,
    # avoiding heap imports and the two-queue array merge strategy.
    freqs = []
    for v in counts.values():
        freqs.append(v)
    freqs.sort()

    total = 0
    while len(freqs) > 1:
        a = freqs[0]
        b = freqs[1]
        s = a + b
        total += s
        del freqs[0:2]

        lo = 0
        hi = len(freqs)
        while lo < hi:
            mid = (lo + hi) >> 1
            if freqs[mid] < s:
                lo = mid + 1
            else:
                hi = mid
        freqs[lo:lo] = [s]

    return {"encoded_length": total, "decoded": text}

Compare with Champion

Score Difference

Tied

Runtime Advantage

25μs slower

Code Size

40 vs 46 lines

#Your Solution#Champion
1def solve(input):1def solve(input):
2 text = input.get("text", "")2 text = input.get("text", "")
3 n = len(text)3 n = len(text)
4 if n == 0:4 if n == 0:
5 return {"encoded_length": 0, "decoded": ""}5 return {"encoded_length": 0, "decoded": ""}
66
7 counts = {}7 counts = {}
8 for ch in text:8 get = counts.get
9 counts[ch] = counts.get(ch, 0) + 19 for ch in text:
1010 counts[ch] = get(ch, 0) + 1
11 if len(counts) == 1:11
12 return {"encoded_length": n, "decoded": text}12 freqs = list(counts.values())
1313 m = len(freqs)
14 # Structurally different approach:14
15 # use in-place sorted list insertion to simulate Huffman merging,15 if m == 1:
16 # avoiding heap imports and the two-queue array merge strategy.16 return {"encoded_length": n, "decoded": text}
17 freqs = []17
18 for v in counts.values():18 freqs.sort()
19 freqs.append(v)19
20 freqs.sort()20 # Bottom-up two-queue Huffman merge:
2121 # use freqs as first queue and merged as second queue.
22 total = 022 merged = [0] * (m - 1)
23 while len(freqs) > 1:23 i = j = k = 0
24 a = freqs[0]24 total = 0
25 b = freqs[1]25
26 s = a + b26 while k < m - 1:
27 total += s27 if i < m and (j >= k or freqs[i] <= merged[j]):
28 del freqs[0:2]28 a = freqs[i]
2929 i += 1
30 lo = 030 else:
31 hi = len(freqs)31 a = merged[j]
32 while lo < hi:32 j += 1
33 mid = (lo + hi) >> 133
34 if freqs[mid] < s:34 if i < m and (j >= k or freqs[i] <= merged[j]):
35 lo = mid + 135 b = freqs[i]
36 else:36 i += 1
37 hi = mid37 else:
38 freqs[lo:lo] = [s]38 b = merged[j]
3939 j += 1
40 return {"encoded_length": total, "decoded": text}40
4141 s = a + b
4242 merged[k] = s
4343 total += s
4444 k += 1
4545
4646 return {"encoded_length": total, "decoded": text}
Your Solution
100% (5/5)49μ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    for ch in text:
9        counts[ch] = counts.get(ch, 0) + 1
10
11    if len(counts) == 1:
12        return {"encoded_length": n, "decoded": text}
13
14    # Structurally different approach:
15    # use in-place sorted list insertion to simulate Huffman merging,
16    # avoiding heap imports and the two-queue array merge strategy.
17    freqs = []
18    for v in counts.values():
19        freqs.append(v)
20    freqs.sort()
21
22    total = 0
23    while len(freqs) > 1:
24        a = freqs[0]
25        b = freqs[1]
26        s = a + b
27        total += s
28        del freqs[0:2]
29
30        lo = 0
31        hi = len(freqs)
32        while lo < hi:
33            mid = (lo + hi) >> 1
34            if freqs[mid] < s:
35                lo = mid + 1
36            else:
37                hi = mid
38        freqs[lo:lo] = [s]
39
40    return {"encoded_length": total, "decoded": text}
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}