{"id":156,"date":"2022-03-05T19:48:52","date_gmt":"2022-03-06T00:48:52","guid":{"rendered":"https:\/\/sites.temple.edu\/vahid\/?p=156"},"modified":"2022-03-05T19:48:53","modified_gmt":"2022-03-06T00:48:53","slug":"hackerrank-solutions-tree-huffman-decoding","status":"publish","type":"post","link":"https:\/\/sites.temple.edu\/vahid\/2022\/03\/05\/hackerrank-solutions-tree-huffman-decoding\/","title":{"rendered":"HackerRank Solutions: Tree: Huffman Decoding"},"content":{"rendered":"\n<p class=\"has-text-align-center\"><strong>Problem<\/strong><\/p>\n\n\n\n<p><a href=\"https:\/\/en.wikipedia.org\/wiki\/Huffman_coding\">Huffman coding<\/a>\u00a0assigns variable length codewords to fixed length input characters based on their frequencies. More frequent characters are assigned shorter codewords and less frequent characters are assigned longer codewords. All edges along the path to a character contain a code digit. If they are on the left side of the tree, they will be a\u00a0<em>0<\/em>\u00a0(zero). If on the right, they&#8217;ll be a\u00a0<em>1<\/em>\u00a0(one). Only the leaves will contain a letter and its frequency count. All other nodes will contain a null instead of a character, and the count of the frequency of all of it and its descendant characters.<\/p>\n\n\n\n<p>For instance, consider the string&nbsp;<em>ABRACADABRA<\/em>. There are a total of&nbsp;&nbsp;characters in the string. This number should match the count in the ultimately determined root of the tree. Our frequencies are&nbsp;&nbsp;and&nbsp;. The two smallest frequencies are for&nbsp;&nbsp;and&nbsp;, both equal to&nbsp;, so we&#8217;ll create a tree with them. The root node will contain the sum of the counts of its descendants, in this case&nbsp;. The left node will be the first character encountered,&nbsp;, and the right will contain&nbsp;. Next we have&nbsp;&nbsp;items with a character count of&nbsp;: the tree we just created, the character&nbsp;&nbsp;and the character&nbsp;. The tree came first, so it will go on the left of our new root node.&nbsp;&nbsp;will go on the right. Repeat until the tree is complete, then fill in the&nbsp;&#8216;s and&nbsp;&#8216;s for the edges. The finished graph looks like:<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/s3.amazonaws.com\/hr-assets\/0\/1528128577-d4e3a24f3e-huffmanExample.png\" alt=\"image\" title=\"\" \/><\/figure>\n\n\n\n<p>Input characters are only present in the leaves. Internal nodes have a character value of \u03d5 (NULL). We can determine that our values for characters are:<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>A - 0\nB - 111\nC - 1100\nD - 1101\nR - 10\n<\/code><\/pre>\n\n\n\n<p>Our Huffman encoded string is:<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>A B    R  A C     A D     A B    R  A\n0 111 10 0 1100 0 1101 0 111 10 0\nor\n01111001100011010111100\n<\/code><\/pre>\n\n\n\n<p>To avoid ambiguity, Huffman encoding is a prefix free encoding technique. No codeword appears as a prefix of any other codeword.<\/p>\n\n\n\n<p>To decode the encoded string, follow the zeros and ones to a leaf and return the character there.<\/p>\n\n\n\n<p>You are given pointer to the root of the Huffman tree and a binary coded string to decode. You need to print the decoded string.<\/p>\n\n\n\n<p><strong>Function Description<\/strong><\/p>\n\n\n\n<p>Complete the function decode_huff in the editor below. It must return the decoded string.<\/p>\n\n\n\n<p>decode_huff has the following parameters:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><em>root<\/em>: a reference to the root node of the Huffman tree<\/li><li><em>s<\/em>: a Huffman encoded string<\/li><\/ul>\n\n\n\n<p><strong>Input Format<\/strong><\/p>\n\n\n\n<p>There is one line of input containing the plain string,&nbsp;. Background code creates the Huffman tree then passes the head node and the encoded string to the function.<\/p>\n\n\n\n<p><strong>Constraints<\/strong><\/p>\n\n\n\n<p><strong>Output Format<\/strong><\/p>\n\n\n\n<p>Output the decoded string on a single line.<\/p>\n\n\n\n<p><strong>Sample Input<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/s3.amazonaws.com\/hr-assets\/0\/1528126193-578de92bdb-huffmanSample.png\" alt=\"image\" title=\"\" \/><\/figure>\n\n\n\n<pre class=\"wp-block-code\"><code>s=\"1001011\"\n<\/code><\/pre>\n\n\n\n<p><strong>Sample Output<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>ABACA\n<\/code><\/pre>\n\n\n\n<p><strong>Explanation<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>S=\"1001011\"\nProcessing the string from left to right.\nS&#091;0]='1' : we move to the right child of the root. We encounter a leaf node with value 'A'. We add 'A' to the decoded string.\nWe move back to the root.\n\nS&#091;1]='0' : we move to the left child. \nS&#091;2]='0' : we move to the left child. We encounter a leaf node with value 'B'. We add 'B' to the decoded string.\nWe move back to the root.\n\nS&#091;3] = '1' : we move to the right child of the root. We encounter a leaf node with value 'A'. We add 'A' to the decoded string.\nWe move back to the root.\n\nS&#091;4]='0' : we move to the left child. \nS&#091;5]='1' : we move to the right child. We encounter a leaf node with value C'. We add 'C' to the decoded string.\nWe move back to the root.\n\n S&#091;6] = '1' : we move to the right child of the root. We encounter a leaf node with value 'A'. We add 'A' to the decoded string.\nWe move back to the root.\n\nDecoded String = \"ABACA\"<\/code><\/pre>\n\n\n\n<p class=\"has-text-align-center\"><strong>Solution<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>import queue as Queue\r\n\r\ncntr = 0\r\n\r\nclass Node:\r\n    def __init__(self, freq, data):\r\n        self.freq = freq\r\n        self.data = data\r\n        self.left = None\r\n        self.right = None\r\n        global cntr\r\n        self._count = cntr\r\n        cntr = cntr + 1\r\n        \r\n    def __lt__(self, other):\r\n        if self.freq != other.freq:\r\n            return self.freq &lt; other.freq\r\n        return self._count &lt; other._count\r\n\r\ndef huffman_hidden():#builds the tree and returns root\r\n    q = Queue.PriorityQueue()\r\n\r\n    \r\n    for key in freq:\r\n        q.put((freq&#091;key], key, Node(freq&#091;key], key) ))\r\n    \r\n    while q.qsize() != 1:\r\n        a = q.get()\r\n        b = q.get()\r\n        obj = Node(a&#091;0] + b&#091;0], '\\0' )\r\n        obj.left = a&#091;2]\r\n        obj.right = b&#091;2]\r\n        q.put((obj.freq, obj.data, obj ))\r\n        \r\n    root = q.get()\r\n    root = root&#091;2]#contains root object\r\n    return root\r\n\r\ndef dfs_hidden(obj, already):\r\n    if(obj == None):\r\n        return\r\n    elif(obj.data != '\\0'):\r\n        code_hidden&#091;obj.data] = already\r\n        \r\n    dfs_hidden(obj.right, already + \"1\")\r\n    dfs_hidden(obj.left, already + \"0\")\r\n\r\n\"\"\"class Node:\r\n    def __init__(self, freq,data):\r\n        self.freq= freq\r\n        self.data=data\r\n        self.left = None\r\n        self.right = None\r\n\"\"\"        \r\n\r\n# Enter your code here. Read input from STDIN. Print output to STDOUT\r\ndef decodeHuff(root, s):\r\n    #Enter Your Code Here\r\n    \r\n    # encoding\r\n    msg = ''\r\n    c = 0\r\n    node = root\r\n    while(c &lt; len(s)):\r\n        d = s&#091;c]\r\n        if (node.data == '\\0'):\r\n            node = node.left if d == '0' else node.right\r\n            c += 1\r\n        else:\r\n            msg += node.data\r\n            node = root\r\n    msg += node.data\r\n    print(msg)\r\n    \r\n    \r\n    \r\n\r\nip = input()\r\nfreq = {}#maps each character to its frequency\r\n\r\ncntr = 0\r\n\r\nfor ch in ip:\r\n    if(freq.get(ch) == None):\r\n        freq&#091;ch] = 1\r\n    else:\r\n        freq&#091;ch]+=1\r\n\r\nroot = huffman_hidden()#contains root of huffman tree\r\n\r\ncode_hidden = {}#contains code for each object\r\n\r\ndfs_hidden(root, \"\")\r\n\r\nif len(code_hidden) == 1:#if there is only one character in the i\/p\r\n    for key in code_hidden:\r\n        code_hidden&#091;key] = \"0\"\r\n\r\ntoBeDecoded = \"\"\r\n\r\nfor ch in ip:\r\n   toBeDecoded += code_hidden&#091;ch]\r\n\r\ndecodeHuff(root, toBeDecoded)\r<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Problem Huffman coding\u00a0assigns variable length codewords to fixed length input characters based on their frequencies. More frequent characters are assigned shorter codewords and less frequent&#8230;<\/p>\n<div class=\"more-link-wrapper\"><a class=\"more-link\" href=\"https:\/\/sites.temple.edu\/vahid\/2022\/03\/05\/hackerrank-solutions-tree-huffman-decoding\/\">Continue reading<span class=\"screen-reader-text\">HackerRank Solutions: Tree: Huffman Decoding<\/span><\/a><\/div>\n","protected":false},"author":18759,"featured_media":157,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[101],"tags":[102,4,103],"class_list":["post-156","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-programming","tag-hackerrank","tag-python","tag-solution","entry"],"_links":{"self":[{"href":"https:\/\/sites.temple.edu\/vahid\/wp-json\/wp\/v2\/posts\/156","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/sites.temple.edu\/vahid\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/sites.temple.edu\/vahid\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/sites.temple.edu\/vahid\/wp-json\/wp\/v2\/users\/18759"}],"replies":[{"embeddable":true,"href":"https:\/\/sites.temple.edu\/vahid\/wp-json\/wp\/v2\/comments?post=156"}],"version-history":[{"count":0,"href":"https:\/\/sites.temple.edu\/vahid\/wp-json\/wp\/v2\/posts\/156\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/sites.temple.edu\/vahid\/wp-json\/wp\/v2\/media\/157"}],"wp:attachment":[{"href":"https:\/\/sites.temple.edu\/vahid\/wp-json\/wp\/v2\/media?parent=156"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/sites.temple.edu\/vahid\/wp-json\/wp\/v2\/categories?post=156"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/sites.temple.edu\/vahid\/wp-json\/wp\/v2\/tags?post=156"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}