Solution #6126deee-8594-4f76-8ce0-72d8845a7ba5

completed

Score

100% (5/5)

Runtime

51μs

Delta

No change vs parent

Tied for best

Same as parent

Solution Lineage

Current100%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 not n:
        return {"encoded_length": 0, "decoded": ""}

    counts = {}
    [counts.__setitem__(ch, counts.get(ch, 0) + 1) for ch in text]
    vals = list(counts.values())

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

    vals.sort()
    q = vals
    m = len(q)
    head1 = 0
    head2 = m
    q.extend([0] * (m - 1))
    tail = m
    total = 0

    def popmin():
        nonlocal head1, head2
        if head1 < m and (head2 >= tail or q[head1] <= q[head2]):
            v = q[head1]
            head1 += 1
            return v
        v = q[head2]
        head2 += 1
        return v

    while tail < 2 * m - 1:
        s = popmin() + popmin()
        q[tail] = s
        tail += 1
        total += s

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

Compare with Champion

Score Difference

Tied

Runtime Advantage

27μs slower

Code Size

39 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 not n:4 if n == 0:
5 return {"encoded_length": 0, "decoded": ""}5 return {"encoded_length": 0, "decoded": ""}
66
7 counts = {}7 counts = {}
8 [counts.__setitem__(ch, counts.get(ch, 0) + 1) for ch in text]8 get = counts.get
9 vals = list(counts.values())9 for ch in text:
1010 counts[ch] = get(ch, 0) + 1
11 if len(vals) == 1:11
12 return {"encoded_length": n, "decoded": text}12 freqs = list(counts.values())
1313 m = len(freqs)
14 vals.sort()14
15 q = vals15 if m == 1:
16 m = len(q)16 return {"encoded_length": n, "decoded": text}
17 head1 = 017
18 head2 = m18 freqs.sort()
19 q.extend([0] * (m - 1))19
20 tail = m20 # Bottom-up two-queue Huffman merge:
21 total = 021 # use freqs as first queue and merged as second queue.
2222 merged = [0] * (m - 1)
23 def popmin():23 i = j = k = 0
24 nonlocal head1, head224 total = 0
25 if head1 < m and (head2 >= tail or q[head1] <= q[head2]):25
26 v = q[head1]26 while k < m - 1:
27 head1 += 127 if i < m and (j >= k or freqs[i] <= merged[j]):
28 return v28 a = freqs[i]
29 v = q[head2]29 i += 1
30 head2 += 130 else:
31 return v31 a = merged[j]
3232 j += 1
33 while tail < 2 * m - 1:33
34 s = popmin() + popmin()34 if i < m and (j >= k or freqs[i] <= merged[j]):
35 q[tail] = s35 b = freqs[i]
36 tail += 136 i += 1
37 total += s37 else:
3838 b = merged[j]
39 return {"encoded_length": total, "decoded": text}39 j += 1
4040
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)51μs
1def solve(input):
2    text = input.get("text", "")
3    n = len(text)
4    if not n:
5        return {"encoded_length": 0, "decoded": ""}
6
7    counts = {}
8    [counts.__setitem__(ch, counts.get(ch, 0) + 1) for ch in text]
9    vals = list(counts.values())
10
11    if len(vals) == 1:
12        return {"encoded_length": n, "decoded": text}
13
14    vals.sort()
15    q = vals
16    m = len(q)
17    head1 = 0
18    head2 = m
19    q.extend([0] * (m - 1))
20    tail = m
21    total = 0
22
23    def popmin():
24        nonlocal head1, head2
25        if head1 < m and (head2 >= tail or q[head1] <= q[head2]):
26            v = q[head1]
27            head1 += 1
28            return v
29        v = q[head2]
30        head2 += 1
31        return v
32
33    while tail < 2 * m - 1:
34        s = popmin() + popmin()
35        q[tail] = s
36        tail += 1
37        total += s
38
39    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}