Solution #9a277008-c346-4594-9672-f7a508ee9a95

completed

Score

100% (5/5)

Runtime

29μs

Delta

+400.0% vs parent

Tied for best

Improved from parent

Solution Lineage

Current100%Improved from parent
1b2fa39920%Regression from parent
98fd02a3100%Same as parent
ae4d0f99100%Same as parent
6126deee100%Same as parent
d720f0bf100%Same as parent
7e637902100%Same as parent
29bbc470100%Same as parent
268b5b53100%Same as parent
ffe6e932100%Same as parent
bb8a4da9100%Same as parent
0d32fca6100%Same as parent
195f1ac7100%Same as parent
96773990100%Same as parent
d7adae63100%Same as parent
8cb031c4100%Same as parent
0826d84e100%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 = {}
    for ch in text:
        counts[ch] = counts.get(ch, 0) + 1

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

    freqs.sort()
    m = len(freqs)

    q = [0] * (m - 1)
    i = 0
    j = 0
    qn = 0
    total = 0

    remaining = m + qn
    while remaining > 1:
        if i < m and (j >= qn or freqs[i] <= q[j]):
            a = freqs[i]
            i += 1
        else:
            a = q[j]
            j += 1

        if i < m and (j >= qn or freqs[i] <= q[j]):
            b = freqs[i]
            i += 1
        else:
            b = q[j]
            j += 1

        s = a + b
        total += s
        q[qn] = s
        qn += 1

        remaining -= 1

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

Compare with Champion

Score Difference

Tied

Runtime Advantage

5μs slower

Code Size

47 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 freqs = list(counts.values())11
12 if len(freqs) == 1:12 freqs = list(counts.values())
13 return {"encoded_length": n, "decoded": text}13 m = len(freqs)
1414
15 freqs.sort()15 if m == 1:
16 m = len(freqs)16 return {"encoded_length": n, "decoded": text}
1717
18 q = [0] * (m - 1)18 freqs.sort()
19 i = 019
20 j = 020 # Bottom-up two-queue Huffman merge:
21 qn = 021 # use freqs as first queue and merged as second queue.
22 total = 022 merged = [0] * (m - 1)
2323 i = j = k = 0
24 remaining = m + qn24 total = 0
25 while remaining > 1:25
26 if i < m and (j >= qn or freqs[i] <= q[j]):26 while k < m - 1:
27 a = freqs[i]27 if i < m and (j >= k or freqs[i] <= merged[j]):
28 i += 128 a = freqs[i]
29 else:29 i += 1
30 a = q[j]30 else:
31 j += 131 a = merged[j]
3232 j += 1
33 if i < m and (j >= qn or freqs[i] <= q[j]):33
34 b = freqs[i]34 if i < m and (j >= k or freqs[i] <= merged[j]):
35 i += 135 b = freqs[i]
36 else:36 i += 1
37 b = q[j]37 else:
38 j += 138 b = merged[j]
3939 j += 1
40 s = a + b40
41 total += s41 s = a + b
42 q[qn] = s42 merged[k] = s
43 qn += 143 total += s
4444 k += 1
45 remaining -= 145
4646 return {"encoded_length": total, "decoded": text}
47 return {"encoded_length": total, "decoded": text}47
Your Solution
100% (5/5)29μ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    freqs = list(counts.values())
12    if len(freqs) == 1:
13        return {"encoded_length": n, "decoded": text}
14
15    freqs.sort()
16    m = len(freqs)
17
18    q = [0] * (m - 1)
19    i = 0
20    j = 0
21    qn = 0
22    total = 0
23
24    remaining = m + qn
25    while remaining > 1:
26        if i < m and (j >= qn or freqs[i] <= q[j]):
27            a = freqs[i]
28            i += 1
29        else:
30            a = q[j]
31            j += 1
32
33        if i < m and (j >= qn or freqs[i] <= q[j]):
34            b = freqs[i]
35            i += 1
36        else:
37            b = q[j]
38            j += 1
39
40        s = a + b
41        total += s
42        q[qn] = s
43        qn += 1
44
45        remaining -= 1
46
47    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}