Solution #ae4d0f99-fa41-4b7c-a7c0-9a863558720f

completed

Score

100% (5/5)

Runtime

79μs

Delta

No change vs parent

Tied for best

Same as parent

Solution Lineage

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

    from functools import lru_cache

    @lru_cache(maxsize=None)
    def build_counts(s):
        counts = {}
        for ch in s:
            counts[ch] = counts.get(ch, 0) + 1
        return tuple(sorted(counts.values()))

    freqs = build_counts(text)
    m = len(freqs)

    if m == 1:
        return {"encoded_length": n, "decoded": text}

    @lru_cache(maxsize=None)
    def huffman_cost(state):
        arr = list(state)
        total = 0
        while len(arr) > 1:
            a = arr.pop(0)
            b = arr.pop(0)
            s = a + b
            total += s

            lo, hi = 0, len(arr)
            while lo < hi:
                mid = (lo + hi) >> 1
                if arr[mid] < s:
                    lo = mid + 1
                else:
                    hi = mid
            arr.insert(lo, s)
        return total

    return {"encoded_length": huffman_cost(freqs), "decoded": text}

Compare with Champion

Score Difference

Tied

Runtime Advantage

55μs slower

Code Size

42 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 from functools import lru_cache7 counts = {}
88 get = counts.get
9 @lru_cache(maxsize=None)9 for ch in text:
10 def build_counts(s):10 counts[ch] = get(ch, 0) + 1
11 counts = {}11
12 for ch in s:12 freqs = list(counts.values())
13 counts[ch] = counts.get(ch, 0) + 113 m = len(freqs)
14 return tuple(sorted(counts.values()))14
1515 if m == 1:
16 freqs = build_counts(text)16 return {"encoded_length": n, "decoded": text}
17 m = len(freqs)17
1818 freqs.sort()
19 if m == 1:19
20 return {"encoded_length": n, "decoded": text}20 # Bottom-up two-queue Huffman merge:
2121 # use freqs as first queue and merged as second queue.
22 @lru_cache(maxsize=None)22 merged = [0] * (m - 1)
23 def huffman_cost(state):23 i = j = k = 0
24 arr = list(state)24 total = 0
25 total = 025
26 while len(arr) > 1:26 while k < m - 1:
27 a = arr.pop(0)27 if i < m and (j >= k or freqs[i] <= merged[j]):
28 b = arr.pop(0)28 a = freqs[i]
29 s = a + b29 i += 1
30 total += s30 else:
3131 a = merged[j]
32 lo, hi = 0, len(arr)32 j += 1
33 while lo < hi:33
34 mid = (lo + hi) >> 134 if i < m and (j >= k or freqs[i] <= merged[j]):
35 if arr[mid] < s:35 b = freqs[i]
36 lo = mid + 136 i += 1
37 else:37 else:
38 hi = mid38 b = merged[j]
39 arr.insert(lo, s)39 j += 1
40 return total40
4141 s = a + b
42 return {"encoded_length": huffman_cost(freqs), "decoded": text}42 merged[k] = s
4343 total += s
4444 k += 1
4545
4646 return {"encoded_length": total, "decoded": text}
Your Solution
100% (5/5)79μ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    from functools import lru_cache
8
9    @lru_cache(maxsize=None)
10    def build_counts(s):
11        counts = {}
12        for ch in s:
13            counts[ch] = counts.get(ch, 0) + 1
14        return tuple(sorted(counts.values()))
15
16    freqs = build_counts(text)
17    m = len(freqs)
18
19    if m == 1:
20        return {"encoded_length": n, "decoded": text}
21
22    @lru_cache(maxsize=None)
23    def huffman_cost(state):
24        arr = list(state)
25        total = 0
26        while len(arr) > 1:
27            a = arr.pop(0)
28            b = arr.pop(0)
29            s = a + b
30            total += s
31
32            lo, hi = 0, len(arr)
33            while lo < hi:
34                mid = (lo + hi) >> 1
35                if arr[mid] < s:
36                    lo = mid + 1
37                else:
38                    hi = mid
39            arr.insert(lo, s)
40        return total
41
42    return {"encoded_length": huffman_cost(freqs), "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}