Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Based on the hints solution in Clear category for Huffman Encode by Patrick_vG
from collections import Counter
import heapq
def huffman_encode(s: str) -> str:
counter = Counter(s)
if len(counter) == 1:
return "0" * list(counter.values())[0]
# Initialize the heapq (freq first) and the translation dictionary
queue = [(freq, letter) for letter, freq in counter.items()]
heapq.heapify(queue)
letters = {letter: "" for letter in counter}
while len(queue) > 1:
# Get the first two nodes from the queue
freq1, let1 = heapq.heappop(queue)
freq2, let2 = heapq.heappop(queue)
# Update the dictionary: add a "0" for the letters of the first node
# and a "1" for the letters of the second node
for letter in let1:
letters[letter] = "0" + letters[letter]
for letter in let2:
letters[letter] = "1" + letters[letter]
# Merge the two nodes and push them back
heapq.heappush(queue, (freq1 + freq2, let1 + let2))
return "".join([letters[letter] for letter in s])
print("Example:")
print(huffman_encode("BADABUM"))
# These "asserts" are used for self-checking
assert huffman_encode("BADABUM") == "1001110011000111"
assert (
huffman_encode("A DEAD DAD CEDED A BAD BABE A BEADED ABACA BED")
== "1000011101001000110010011101100111001001000111110010011111011111100010001111110100111001001011111011101000111111001"
)
assert (
huffman_encode("no devil lived on")
== "100101111000001110010011111011010110001000111101100"
)
assert huffman_encode("an assassin sins") == "110111100110001100010111110001011110"
assert huffman_encode("aaaa") == "0000"
assert huffman_encode("") == ""
assert huffman_encode("T isnt t") == "01000011101100110011"
assert (
huffman_encode("how quickly daft jumping zebras vex")
== "00101011011011011001111101000111111110100101010111001100000011110000011001011001000101001011011100011011000010011011101000111111010000111101000111010011000110111"
)
assert (
huffman_encode("amazingly few discotheques provide jukeboxes")
== "1100100010110011100001110001111110100001011011101111100100010111101111010111101111100110100011111111010000101010010010111101001000011010100101001111110110011011111110100000001001110001010011001001011"
)
print("The mission is done! Click 'Check Solution' to earn rewards!")
Oct. 7, 2023
