Solution #c128503d-9482-42b1-a23f-65990022ac9e

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
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

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

    from array import array

    freqs = array('Q', counts.values())
    freqs = array('Q', sorted(freqs))
    m = len(freqs)

    merged = array('Q', [0]) * (m - 1)

    i = 0
    j = 0
    out = 0
    total = 0

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

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

        s = a + b
        merged[out] = s
        out += 1
        total += s

    return {"encoded_length": int(total), "decoded": text}

Compare with Champion

Score Difference

Tied

Runtime Advantage

27μs slower

Code Size

48 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 k = len(counts)11
12 if k == 1:12 freqs = list(counts.values())
13 return {"encoded_length": n, "decoded": text}13 m = len(freqs)
1414
15 from array import array15 if m == 1:
1616 return {"encoded_length": n, "decoded": text}
17 freqs = array('Q', counts.values())17
18 freqs = array('Q', sorted(freqs))18 freqs.sort()
19 m = len(freqs)19
2020 # Bottom-up two-queue Huffman merge:
21 merged = array('Q', [0]) * (m - 1)21 # use freqs as first queue and merged as second queue.
2222 merged = [0] * (m - 1)
23 i = 023 i = j = k = 0
24 j = 024 total = 0
25 out = 025
26 total = 026 while k < m - 1:
2727 if i < m and (j >= k or freqs[i] <= merged[j]):
28 while out < m - 1:28 a = freqs[i]
29 if i < m and (j >= out or freqs[i] <= merged[j]):29 i += 1
30 a = freqs[i]30 else:
31 i += 131 a = merged[j]
32 else:32 j += 1
33 a = merged[j]33
34 j += 134 if i < m and (j >= k or freqs[i] <= merged[j]):
3535 b = freqs[i]
36 if i < m and (j >= out or freqs[i] <= merged[j]):36 i += 1
37 b = freqs[i]37 else:
38 i += 138 b = merged[j]
39 else:39 j += 1
40 b = merged[j]40
41 j += 141 s = a + b
4242 merged[k] = s
43 s = a + b43 total += s
44 merged[out] = s44 k += 1
45 out += 145
46 total += s46 return {"encoded_length": total, "decoded": text}
4747
48 return {"encoded_length": int(total), "decoded": text}48
Your Solution
100% (5/5)51μ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    k = len(counts)
12    if k == 1:
13        return {"encoded_length": n, "decoded": text}
14
15    from array import array
16
17    freqs = array('Q', counts.values())
18    freqs = array('Q', sorted(freqs))
19    m = len(freqs)
20
21    merged = array('Q', [0]) * (m - 1)
22
23    i = 0
24    j = 0
25    out = 0
26    total = 0
27
28    while out < m - 1:
29        if i < m and (j >= out or freqs[i] <= merged[j]):
30            a = freqs[i]
31            i += 1
32        else:
33            a = merged[j]
34            j += 1
35
36        if i < m and (j >= out or freqs[i] <= merged[j]):
37            b = freqs[i]
38            i += 1
39        else:
40            b = merged[j]
41            j += 1
42
43        s = a + b
44        merged[out] = s
45        out += 1
46        total += s
47
48    return {"encoded_length": int(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}