Solution #1b2fa399-a96c-4074-9155-1ea37fb663e2

completed

Score

20% (1/5)

Runtime

78μs

Delta

-80.0% vs parent

-80.0% vs best

Regression from parent

Solution Lineage

Current20%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": ""}

    m = 0
    for ch in text:
        o = ord(ch)
        if o > m:
            m = o

    counts = [0] * (m + 1)
    for ch in text:
        counts[ord(ch)] += 1

    freqs = []
    for c in counts:
        if c:
            freqs.append(c)

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

    freqs.sort()

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

    while True:
        if i < k and (j >= merged_len or freqs[i] <= merged[j]):
            a = freqs[i]
            i += 1
        else:
            a = merged[j]
            j += 1

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

        s = a + b
        total += s

        if merged_len < k - 1:
            merged[merged_len] = s
            merged_len += 1
        else:
            break

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

Compare with Champion

Score Difference

-80.0%

Runtime Advantage

54μs slower

Code Size

58 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 m = 07 counts = {}
8 for ch in text:8 get = counts.get
9 o = ord(ch)9 for ch in text:
10 if o > m:10 counts[ch] = get(ch, 0) + 1
11 m = o11
1212 freqs = list(counts.values())
13 counts = [0] * (m + 1)13 m = len(freqs)
14 for ch in text:14
15 counts[ord(ch)] += 115 if m == 1:
1616 return {"encoded_length": n, "decoded": text}
17 freqs = []17
18 for c in counts:18 freqs.sort()
19 if c:19
20 freqs.append(c)20 # Bottom-up two-queue Huffman merge:
2121 # use freqs as first queue and merged as second queue.
22 k = len(freqs)22 merged = [0] * (m - 1)
23 if k == 1:23 i = j = k = 0
24 return {"encoded_length": n, "decoded": text}24 total = 0
2525
26 freqs.sort()26 while k < m - 1:
2727 if i < m and (j >= k or freqs[i] <= merged[j]):
28 i = 028 a = freqs[i]
29 j = 029 i += 1
30 merged = [0] * (k - 1)30 else:
31 merged_len = 031 a = merged[j]
32 total = 032 j += 1
3333
34 while True:34 if i < m and (j >= k or freqs[i] <= merged[j]):
35 if i < k and (j >= merged_len or freqs[i] <= merged[j]):35 b = freqs[i]
36 a = freqs[i]36 i += 1
37 i += 137 else:
38 else:38 b = merged[j]
39 a = merged[j]39 j += 1
40 j += 140
4141 s = a + b
42 if i < k and (j >= merged_len or freqs[i] <= merged[j]):42 merged[k] = s
43 b = freqs[i]43 total += s
44 i += 144 k += 1
45 else:45
46 b = merged[j]46 return {"encoded_length": total, "decoded": text}
47 j += 147
4848
49 s = a + b49
50 total += s50
5151
52 if merged_len < k - 1:52
53 merged[merged_len] = s53
54 merged_len += 154
55 else:55
56 break56
5757
58 return {"encoded_length": total, "decoded": text}58
Your Solution
20% (1/5)78μ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    m = 0
8    for ch in text:
9        o = ord(ch)
10        if o > m:
11            m = o
12
13    counts = [0] * (m + 1)
14    for ch in text:
15        counts[ord(ch)] += 1
16
17    freqs = []
18    for c in counts:
19        if c:
20            freqs.append(c)
21
22    k = len(freqs)
23    if k == 1:
24        return {"encoded_length": n, "decoded": text}
25
26    freqs.sort()
27
28    i = 0
29    j = 0
30    merged = [0] * (k - 1)
31    merged_len = 0
32    total = 0
33
34    while True:
35        if i < k and (j >= merged_len or freqs[i] <= merged[j]):
36            a = freqs[i]
37            i += 1
38        else:
39            a = merged[j]
40            j += 1
41
42        if i < k and (j >= merged_len or freqs[i] <= merged[j]):
43            b = freqs[i]
44            i += 1
45        else:
46            b = merged[j]
47            j += 1
48
49        s = a + b
50        total += s
51
52        if merged_len < k - 1:
53            merged[merged_len] = s
54            merged_len += 1
55        else:
56            break
57
58    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}