Solution #7e637902-b4f9-4e94-89d7-63eff3e8cec6

completed

Score

100% (5/5)

Runtime

59μs

Delta

No change vs parent

Tied for best

Same as parent

Solution Lineage

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

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

        freqs = []
        for c in counts:
            if c:
                freqs.append(c)
    except:
        d = {}
        for ch in text:
            d[ch] = d.get(ch, 0) + 1
        freqs = list(d.values())

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

    freqs.sort()

    i = 0
    j = 0
    q = [0] * (m - 1)
    qn = 0
    total = 0

    def take():
        nonlocal i, j
        if i < m and (j >= qn or freqs[i] <= q[j]):
            v = freqs[i]
            i += 1
            return v
        v = q[j]
        j += 1
        return v

    for k in range(m - 1):
        s = take() + take()
        q[k] = s
        qn += 1
        total += s

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

Compare with Champion

Score Difference

Tied

Runtime Advantage

35μ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 counts = [0] * 2568 get = counts.get
9 for ch in text:9 for ch in text:
10 counts[ord(ch)] += 110 counts[ch] = get(ch, 0) + 1
1111
12 freqs = []12 freqs = list(counts.values())
13 for c in counts:13 m = len(freqs)
14 if c:14
15 freqs.append(c)15 if m == 1:
16 except:16 return {"encoded_length": n, "decoded": text}
17 d = {}17
18 for ch in text:18 freqs.sort()
19 d[ch] = d.get(ch, 0) + 119
20 freqs = list(d.values())20 # Bottom-up two-queue Huffman merge:
2121 # use freqs as first queue and merged as second queue.
22 m = len(freqs)22 merged = [0] * (m - 1)
23 if m == 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 q = [0] * (m - 1)30 else:
31 qn = 031 a = merged[j]
32 total = 032 j += 1
3333
34 def take():34 if i < m and (j >= k or freqs[i] <= merged[j]):
35 nonlocal i, j35 b = freqs[i]
36 if i < m and (j >= qn or freqs[i] <= q[j]):36 i += 1
37 v = freqs[i]37 else:
38 i += 138 b = merged[j]
39 return v39 j += 1
40 v = q[j]40
41 j += 141 s = a + b
42 return v42 merged[k] = s
4343 total += s
44 for k in range(m - 1):44 k += 1
45 s = take() + take()45
46 q[k] = s46 return {"encoded_length": total, "decoded": text}
47 qn += 147
48 total += s48
4949
50 return {"encoded_length": total, "decoded": text}50
Your Solution
100% (5/5)59μ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        counts = [0] * 256
9        for ch in text:
10            counts[ord(ch)] += 1
11
12        freqs = []
13        for c in counts:
14            if c:
15                freqs.append(c)
16    except:
17        d = {}
18        for ch in text:
19            d[ch] = d.get(ch, 0) + 1
20        freqs = list(d.values())
21
22    m = len(freqs)
23    if m == 1:
24        return {"encoded_length": n, "decoded": text}
25
26    freqs.sort()
27
28    i = 0
29    j = 0
30    q = [0] * (m - 1)
31    qn = 0
32    total = 0
33
34    def take():
35        nonlocal i, j
36        if i < m and (j >= qn or freqs[i] <= q[j]):
37            v = freqs[i]
38            i += 1
39            return v
40        v = q[j]
41        j += 1
42        return v
43
44    for k in range(m - 1):
45        s = take() + take()
46        q[k] = s
47        qn += 1
48        total += 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}