Solution #195f1ac7-f7ec-44cc-a52b-40995e0968f1

completed

Score

100% (5/5)

Runtime

82μs

Delta

No change vs parent

Tied for best

Same as parent

Solution Lineage

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

    counts = [0] * 256
    ascii_only = True
    unique = 0

    for ch in text:
        o = ord(ch)
        if o < 256:
            if counts[o] == 0:
                unique += 1
            counts[o] += 1
        else:
            ascii_only = False
            break

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

        heap = [0] * unique
        idx = 0
        for c in counts:
            if c:
                heap[idx] = c
                idx += 1
    else:
        d = {}
        get = d.get
        for ch in text:
            d[ch] = get(ch, 0) + 1
        if len(d) == 1:
            return {"encoded_length": n, "decoded": text}
        heap = [0] * len(d)
        idx = 0
        for c in d.values():
            heap[idx] = c
            idx += 1

    size = len(heap)

    i = (size >> 1) - 1
    while i >= 0:
        j = i
        x = heap[j]
        while True:
            l = (j << 1) + 1
            if l >= size:
                break
            r = l + 1
            c = l
            if r < size and heap[r] < heap[l]:
                c = r
            if heap[c] >= x:
                break
            heap[j] = heap[c]
            j = c
        heap[j] = x
        i -= 1

    total = 0

    while size > 1:
        a = heap[0]
        size -= 1
        x = heap[size]
        j = 0
        while True:
            l = (j << 1) + 1
            if l >= size:
                break
            r = l + 1
            c = l
            if r < size and heap[r] < heap[l]:
                c = r
            if heap[c] >= x:
                break
            heap[j] = heap[c]
            j = c
        if size:
            heap[j] = x

        b = heap[0]
        size -= 1
        x = heap[size] if size else 0
        j = 0
        while True:
            l = (j << 1) + 1
            if l >= size:
                break
            r = l + 1
            c = l
            if r < size and heap[r] < heap[l]:
                c = r
            if heap[c] >= x:
                break
            heap[j] = heap[c]
            j = c
        if size:
            heap[j] = x

        s = a + b
        total += s

        j = size
        size += 1
        while j:
            p = (j - 1) >> 1
            if heap[p] <= s:
                break
            heap[j] = heap[p]
            j = p
        if j < len(heap):
            heap[j] = s
        else:
            heap.append(s)

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

Compare with Champion

Score Difference

Tied

Runtime Advantage

58μs slower

Code Size

122 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 counts = [0] * 2567 counts = {}
8 ascii_only = True8 get = counts.get
9 unique = 09 for ch in text:
1010 counts[ch] = get(ch, 0) + 1
11 for ch in text:11
12 o = ord(ch)12 freqs = list(counts.values())
13 if o < 256:13 m = len(freqs)
14 if counts[o] == 0:14
15 unique += 115 if m == 1:
16 counts[o] += 116 return {"encoded_length": n, "decoded": text}
17 else:17
18 ascii_only = False18 freqs.sort()
19 break19
2020 # Bottom-up two-queue Huffman merge:
21 if ascii_only:21 # use freqs as first queue and merged as second queue.
22 if unique == 1:22 merged = [0] * (m - 1)
23 return {"encoded_length": n, "decoded": text}23 i = j = k = 0
2424 total = 0
25 heap = [0] * unique25
26 idx = 026 while k < m - 1:
27 for c in counts:27 if i < m and (j >= k or freqs[i] <= merged[j]):
28 if c:28 a = freqs[i]
29 heap[idx] = c29 i += 1
30 idx += 130 else:
31 else:31 a = merged[j]
32 d = {}32 j += 1
33 get = d.get33
34 for ch in text:34 if i < m and (j >= k or freqs[i] <= merged[j]):
35 d[ch] = get(ch, 0) + 135 b = freqs[i]
36 if len(d) == 1:36 i += 1
37 return {"encoded_length": n, "decoded": text}37 else:
38 heap = [0] * len(d)38 b = merged[j]
39 idx = 039 j += 1
40 for c in d.values():40
41 heap[idx] = c41 s = a + b
42 idx += 142 merged[k] = s
4343 total += s
44 size = len(heap)44 k += 1
4545
46 i = (size >> 1) - 146 return {"encoded_length": total, "decoded": text}
47 while i >= 0:47
48 j = i48
49 x = heap[j]49
50 while True:50
51 l = (j << 1) + 151
52 if l >= size:52
53 break53
54 r = l + 154
55 c = l55
56 if r < size and heap[r] < heap[l]:56
57 c = r57
58 if heap[c] >= x:58
59 break59
60 heap[j] = heap[c]60
61 j = c61
62 heap[j] = x62
63 i -= 163
6464
65 total = 065
6666
67 while size > 1:67
68 a = heap[0]68
69 size -= 169
70 x = heap[size]70
71 j = 071
72 while True:72
73 l = (j << 1) + 173
74 if l >= size:74
75 break75
76 r = l + 176
77 c = l77
78 if r < size and heap[r] < heap[l]:78
79 c = r79
80 if heap[c] >= x:80
81 break81
82 heap[j] = heap[c]82
83 j = c83
84 if size:84
85 heap[j] = x85
8686
87 b = heap[0]87
88 size -= 188
89 x = heap[size] if size else 089
90 j = 090
91 while True:91
92 l = (j << 1) + 192
93 if l >= size:93
94 break94
95 r = l + 195
96 c = l96
97 if r < size and heap[r] < heap[l]:97
98 c = r98
99 if heap[c] >= x:99
100 break100
101 heap[j] = heap[c]101
102 j = c102
103 if size:103
104 heap[j] = x104
105105
106 s = a + b106
107 total += s107
108108
109 j = size109
110 size += 1110
111 while j:111
112 p = (j - 1) >> 1112
113 if heap[p] <= s:113
114 break114
115 heap[j] = heap[p]115
116 j = p116
117 if j < len(heap):117
118 heap[j] = s118
119 else:119
120 heap.append(s)120
121121
122 return {"encoded_length": total, "decoded": text}122
Your Solution
100% (5/5)82μ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 = [0] * 256
8    ascii_only = True
9    unique = 0
10
11    for ch in text:
12        o = ord(ch)
13        if o < 256:
14            if counts[o] == 0:
15                unique += 1
16            counts[o] += 1
17        else:
18            ascii_only = False
19            break
20
21    if ascii_only:
22        if unique == 1:
23            return {"encoded_length": n, "decoded": text}
24
25        heap = [0] * unique
26        idx = 0
27        for c in counts:
28            if c:
29                heap[idx] = c
30                idx += 1
31    else:
32        d = {}
33        get = d.get
34        for ch in text:
35            d[ch] = get(ch, 0) + 1
36        if len(d) == 1:
37            return {"encoded_length": n, "decoded": text}
38        heap = [0] * len(d)
39        idx = 0
40        for c in d.values():
41            heap[idx] = c
42            idx += 1
43
44    size = len(heap)
45
46    i = (size >> 1) - 1
47    while i >= 0:
48        j = i
49        x = heap[j]
50        while True:
51            l = (j << 1) + 1
52            if l >= size:
53                break
54            r = l + 1
55            c = l
56            if r < size and heap[r] < heap[l]:
57                c = r
58            if heap[c] >= x:
59                break
60            heap[j] = heap[c]
61            j = c
62        heap[j] = x
63        i -= 1
64
65    total = 0
66
67    while size > 1:
68        a = heap[0]
69        size -= 1
70        x = heap[size]
71        j = 0
72        while True:
73            l = (j << 1) + 1
74            if l >= size:
75                break
76            r = l + 1
77            c = l
78            if r < size and heap[r] < heap[l]:
79                c = r
80            if heap[c] >= x:
81                break
82            heap[j] = heap[c]
83            j = c
84        if size:
85            heap[j] = x
86
87        b = heap[0]
88        size -= 1
89        x = heap[size] if size else 0
90        j = 0
91        while True:
92            l = (j << 1) + 1
93            if l >= size:
94                break
95            r = l + 1
96            c = l
97            if r < size and heap[r] < heap[l]:
98                c = r
99            if heap[c] >= x:
100                break
101            heap[j] = heap[c]
102            j = c
103        if size:
104            heap[j] = x
105
106        s = a + b
107        total += s
108
109        j = size
110        size += 1
111        while j:
112            p = (j - 1) >> 1
113            if heap[p] <= s:
114                break
115            heap[j] = heap[p]
116            j = p
117        if j < len(heap):
118            heap[j] = s
119        else:
120            heap.append(s)
121
122    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}