Solution #0826d84e-9385-48cb-80d5-c5e8fffc4e74

completed

Score

100% (5/5)

Runtime

45μs

Delta

No change vs parent

Tied for best

Same as parent

Solution Lineage

Current100%Same as parent
2da814bd100%Same as parent
e227904f100%Same as parent
69696638100%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 = [0] * 256
    non_ascii = None

    for ch in text:
        o = ord(ch)
        if o < 256:
            counts[o] += 1
        else:
            if non_ascii is None:
                non_ascii = {}
            non_ascii[ch] = non_ascii.get(ch, 0) + 1

    freqs = [c for c in counts if c]
    if non_ascii:
        freqs.extend(non_ascii.values())

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

    freqs.sort()

    i = 0
    j = 0
    merged = [0] * (m - 1)
    k = 0
    total = 0

    if m >= 2:
        a = freqs[0]
        b = freqs[1]
        s = a + b
        total = s
        merged[0] = s
        i = 2
        k = 1

    while k < m - 1:
        if i < m and (j >= k or freqs[i] <= merged[j]):
            x = freqs[i]
            i += 1
        else:
            x = merged[j]
            j += 1

        if i < m and (j >= k or freqs[i] <= merged[j]):
            y = freqs[i]
            i += 1
        else:
            y = merged[j]
            j += 1

        s = x + y
        merged[k] = s
        total += s
        k += 1

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

Compare with Champion

Score Difference

Tied

Runtime Advantage

21μs slower

Code Size

64 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 = [0] * 2567 counts = {}
8 non_ascii = None8 get = counts.get
99 for ch in text:
10 for ch in text:10 counts[ch] = get(ch, 0) + 1
11 o = ord(ch)11
12 if o < 256:12 freqs = list(counts.values())
13 counts[o] += 113 m = len(freqs)
14 else:14
15 if non_ascii is None:15 if m == 1:
16 non_ascii = {}16 return {"encoded_length": n, "decoded": text}
17 non_ascii[ch] = non_ascii.get(ch, 0) + 117
1818 freqs.sort()
19 freqs = [c for c in counts if c]19
20 if non_ascii:20 # Bottom-up two-queue Huffman merge:
21 freqs.extend(non_ascii.values())21 # use freqs as first queue and merged as second queue.
2222 merged = [0] * (m - 1)
23 m = len(freqs)23 i = j = k = 0
24 if m == 1:24 total = 0
25 return {"encoded_length": n, "decoded": text}25
2626 while k < m - 1:
27 freqs.sort()27 if i < m and (j >= k or freqs[i] <= merged[j]):
2828 a = freqs[i]
29 i = 029 i += 1
30 j = 030 else:
31 merged = [0] * (m - 1)31 a = merged[j]
32 k = 032 j += 1
33 total = 033
3434 if i < m and (j >= k or freqs[i] <= merged[j]):
35 if m >= 2:35 b = freqs[i]
36 a = freqs[0]36 i += 1
37 b = freqs[1]37 else:
38 s = a + b38 b = merged[j]
39 total = s39 j += 1
40 merged[0] = s40
41 i = 241 s = a + b
42 k = 142 merged[k] = s
4343 total += s
44 while k < m - 1:44 k += 1
45 if i < m and (j >= k or freqs[i] <= merged[j]):45
46 x = freqs[i]46 return {"encoded_length": total, "decoded": text}
47 i += 147
48 else:48
49 x = merged[j]49
50 j += 150
5151
52 if i < m and (j >= k or freqs[i] <= merged[j]):52
53 y = freqs[i]53
54 i += 154
55 else:55
56 y = merged[j]56
57 j += 157
5858
59 s = x + y59
60 merged[k] = s60
61 total += s61
62 k += 162
6363
64 return {"encoded_length": total, "decoded": text}64
Your Solution
100% (5/5)45μ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 = [0] * 256
8    non_ascii = None
9
10    for ch in text:
11        o = ord(ch)
12        if o < 256:
13            counts[o] += 1
14        else:
15            if non_ascii is None:
16                non_ascii = {}
17            non_ascii[ch] = non_ascii.get(ch, 0) + 1
18
19    freqs = [c for c in counts if c]
20    if non_ascii:
21        freqs.extend(non_ascii.values())
22
23    m = len(freqs)
24    if m == 1:
25        return {"encoded_length": n, "decoded": text}
26
27    freqs.sort()
28
29    i = 0
30    j = 0
31    merged = [0] * (m - 1)
32    k = 0
33    total = 0
34
35    if m >= 2:
36        a = freqs[0]
37        b = freqs[1]
38        s = a + b
39        total = s
40        merged[0] = s
41        i = 2
42        k = 1
43
44    while k < m - 1:
45        if i < m and (j >= k or freqs[i] <= merged[j]):
46            x = freqs[i]
47            i += 1
48        else:
49            x = merged[j]
50            j += 1
51
52        if i < m and (j >= k or freqs[i] <= merged[j]):
53            y = freqs[i]
54            i += 1
55        else:
56            y = merged[j]
57            j += 1
58
59        s = x + y
60        merged[k] = s
61        total += s
62        k += 1
63
64    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}