Solution #ffe6e932-1a78-4af2-bd47-94048be8e1ca

completed

Score

100% (5/5)

Runtime

54μs

Delta

No change vs parent

Tied for best

Same as parent

Solution Lineage

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

    try:
        from bisect import insort
    except:
        def insort(a, x):
            lo, hi = 0, len(a)
            while lo < hi:
                mid = (lo + hi) >> 1
                if a[mid] <= x:
                    lo = mid + 1
                else:
                    hi = mid
            a.insert(lo, x)

    try:
        counts = [0] * 256
        for ch in text:
            counts[ord(ch)] += 1
        freqs = []
        for c in counts:
            if c:
                freqs.append(c)
        if len(freqs) == 0 or sum(freqs) != n:
            raise ValueError
    except:
        freq = {}
        get = freq.get
        for ch in text:
            freq[ch] = get(ch, 0) + 1
        freqs = list(freq.values())

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

    freqs.sort()
    total = 0

    while len(freqs) > 1:
        a = freqs.pop(0)
        b = freqs.pop(0)
        s = a + b
        total += s
        insort(freqs, s)

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

Compare with Champion

Score Difference

Tied

Runtime Advantage

30μs slower

Code Size

50 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 try:7 counts = {}
8 from bisect import insort8 get = counts.get
9 except:9 for ch in text:
10 def insort(a, x):10 counts[ch] = get(ch, 0) + 1
11 lo, hi = 0, len(a)11
12 while lo < hi:12 freqs = list(counts.values())
13 mid = (lo + hi) >> 113 m = len(freqs)
14 if a[mid] <= x:14
15 lo = mid + 115 if m == 1:
16 else:16 return {"encoded_length": n, "decoded": text}
17 hi = mid17
18 a.insert(lo, x)18 freqs.sort()
1919
20 try:20 # Bottom-up two-queue Huffman merge:
21 counts = [0] * 25621 # use freqs as first queue and merged as second queue.
22 for ch in text:22 merged = [0] * (m - 1)
23 counts[ord(ch)] += 123 i = j = k = 0
24 freqs = []24 total = 0
25 for c in counts:25
26 if c:26 while k < m - 1:
27 freqs.append(c)27 if i < m and (j >= k or freqs[i] <= merged[j]):
28 if len(freqs) == 0 or sum(freqs) != n:28 a = freqs[i]
29 raise ValueError29 i += 1
30 except:30 else:
31 freq = {}31 a = merged[j]
32 get = freq.get32 j += 1
33 for ch in text:33
34 freq[ch] = get(ch, 0) + 134 if i < m and (j >= k or freqs[i] <= merged[j]):
35 freqs = list(freq.values())35 b = freqs[i]
3636 i += 1
37 if len(freqs) == 1:37 else:
38 return {"encoded_length": n, "decoded": text}38 b = merged[j]
3939 j += 1
40 freqs.sort()40
41 total = 041 s = a + b
4242 merged[k] = s
43 while len(freqs) > 1:43 total += s
44 a = freqs.pop(0)44 k += 1
45 b = freqs.pop(0)45
46 s = a + b46 return {"encoded_length": total, "decoded": text}
47 total += s47
48 insort(freqs, s)48
4949
50 return {"encoded_length": total, "decoded": text}50
Your Solution
100% (5/5)54μ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    try:
8        from bisect import insort
9    except:
10        def insort(a, x):
11            lo, hi = 0, len(a)
12            while lo < hi:
13                mid = (lo + hi) >> 1
14                if a[mid] <= x:
15                    lo = mid + 1
16                else:
17                    hi = mid
18            a.insert(lo, x)
19
20    try:
21        counts = [0] * 256
22        for ch in text:
23            counts[ord(ch)] += 1
24        freqs = []
25        for c in counts:
26            if c:
27                freqs.append(c)
28        if len(freqs) == 0 or sum(freqs) != n:
29            raise ValueError
30    except:
31        freq = {}
32        get = freq.get
33        for ch in text:
34            freq[ch] = get(ch, 0) + 1
35        freqs = list(freq.values())
36
37    if len(freqs) == 1:
38        return {"encoded_length": n, "decoded": text}
39
40    freqs.sort()
41    total = 0
42
43    while len(freqs) > 1:
44        a = freqs.pop(0)
45        b = freqs.pop(0)
46        s = a + b
47        total += s
48        insort(freqs, s)
49
50    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}