Solution #30447971-6e36-4b07-a967-40ca43619245

completed

Score

100% (5/5)

Runtime

64μs

Delta

No change vs parent

Tied for best

Same as parent

Solution Lineage

Current100%Same as parent
62082b2d100%Same as parent
2a708353100%Same as parent
a0f415b0100%First in chain

Code

def solve(input):
    text = input.get("text", "")
    if not text:
        return {"encoded_length": 0, "decoded": ""}

    freq = {}
    list(map(lambda ch: freq.__setitem__(ch, freq.get(ch, 0) + 1), text))
    vals = list(freq.values())

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

    vals.sort()

    def merge_cost(a, b):
        i = j = 0
        n = len(a)
        m = len(b)
        total = 0
        merged = []

        def take():
            nonlocal i, j
            if i < n and (j >= m or a[i] <= b[j]):
                v = a[i]
                i += 1
                return v
            v = b[j]
            j += 1
            return v

        while i + j < n + m - 1:
            s = take() + take()
            total += s
            merged.append(s)
            b = merged
            m = len(b)

        return total

    return {"encoded_length": merge_cost(vals, []), "decoded": text}

Compare with Champion

Score Difference

Tied

Runtime Advantage

40μs slower

Code Size

41 vs 46 lines

#Your Solution#Champion
1def solve(input):1def solve(input):
2 text = input.get("text", "")2 text = input.get("text", "")
3 if not text:3 n = len(text)
4 return {"encoded_length": 0, "decoded": ""}4 if n == 0:
55 return {"encoded_length": 0, "decoded": ""}
6 freq = {}6
7 list(map(lambda ch: freq.__setitem__(ch, freq.get(ch, 0) + 1), text))7 counts = {}
8 vals = list(freq.values())8 get = counts.get
99 for ch in text:
10 if len(vals) == 1:10 counts[ch] = get(ch, 0) + 1
11 return {"encoded_length": len(text), "decoded": text}11
1212 freqs = list(counts.values())
13 vals.sort()13 m = len(freqs)
1414
15 def merge_cost(a, b):15 if m == 1:
16 i = j = 016 return {"encoded_length": n, "decoded": text}
17 n = len(a)17
18 m = len(b)18 freqs.sort()
19 total = 019
20 merged = []20 # Bottom-up two-queue Huffman merge:
2121 # use freqs as first queue and merged as second queue.
22 def take():22 merged = [0] * (m - 1)
23 nonlocal i, j23 i = j = k = 0
24 if i < n and (j >= m or a[i] <= b[j]):24 total = 0
25 v = a[i]25
26 i += 126 while k < m - 1:
27 return v27 if i < m and (j >= k or freqs[i] <= merged[j]):
28 v = b[j]28 a = freqs[i]
29 j += 129 i += 1
30 return v30 else:
3131 a = merged[j]
32 while i + j < n + m - 1:32 j += 1
33 s = take() + take()33
34 total += s34 if i < m and (j >= k or freqs[i] <= merged[j]):
35 merged.append(s)35 b = freqs[i]
36 b = merged36 i += 1
37 m = len(b)37 else:
3838 b = merged[j]
39 return total39 j += 1
4040
41 return {"encoded_length": merge_cost(vals, []), "decoded": text}41 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)64μs
1def solve(input):
2    text = input.get("text", "")
3    if not text:
4        return {"encoded_length": 0, "decoded": ""}
5
6    freq = {}
7    list(map(lambda ch: freq.__setitem__(ch, freq.get(ch, 0) + 1), text))
8    vals = list(freq.values())
9
10    if len(vals) == 1:
11        return {"encoded_length": len(text), "decoded": text}
12
13    vals.sort()
14
15    def merge_cost(a, b):
16        i = j = 0
17        n = len(a)
18        m = len(b)
19        total = 0
20        merged = []
21
22        def take():
23            nonlocal i, j
24            if i < n and (j >= m or a[i] <= b[j]):
25                v = a[i]
26                i += 1
27                return v
28            v = b[j]
29            j += 1
30            return v
31
32        while i + j < n + m - 1:
33            s = take() + take()
34            total += s
35            merged.append(s)
36            b = merged
37            m = len(b)
38
39        return total
40
41    return {"encoded_length": merge_cost(vals, []), "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}