Skip to main content

Posts

Showing posts from April, 2016

Topcoder SRM 689 NonDeterministicSubstring

this problem is about


Problem Statement You are given two Strings: A and B. Each character in A is either '0' or '1'. Each character in B is '0', '1', or '?'.


A string C matches B if we can change B into C by changing each '?' in B either to '0' or to '1'. Different occurrences of '?' may be changed to different digits. For example, C = "0101" matches B = "01??". Note that each character in C must be either '0' or '1', there cannot be any '?' remaining.


Consider all possible strings that match B. How many of these strings occur as a (contiguous) substring in A? Compute and return their number. Note that we only count each good string once, even if it has multiple occurrences in A. Definition …

huffman coding ( encoding and decoding) algorithm in python

this is short code written by python.
Huffmanencoding and decoding

I studied using this site and write code  http://www.geeksforgeeks.org/greedy-algorithms-set-3-huffman-coding/




import random dic = {} class MinHeapNode: def setNode(self, left, right, freq, char): self.left = left self.right = right self.freq = freq self.char = char return selfdef huffmanCoding(arr, freq): heapArr = [] for i in range(len(arr)): heapArr.append(MinHeapNode().setNode(None, None , freq[i], arr[i])) print(heapArr[i].freq, heapArr[i].char) while(len(heapArr)>1): left = heapArr.pop(0) right = heapArr.pop(0) insertionSort(heapArr, MinHeapNode().setNode(left, right, left.freq+right.freq, left.char + right.char)) rootheap= heapArr.pop() return rootheap def printHeap(heap, str): if heap.left != None: printHeap(heap.left, str + '0') if heap.right !=None: printHeap(heap.right,…