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
	Class: NonDeterministicSubstring Method: ways Parameters: String, String Returns: long Method signature: long ways(String A, String B) (be sure your method is public)
Limits
	Time limit (s): 2.000 Memory limit (MB): 256 Stack limit (MB): 256
Constraints
-	A will contain between 1 and 50 characters, inclusive.
-	B will contain between 1 and 50 characters, inclusive.
-	Each character in A will be '0' or '1'.
-	Each character in B will be '0', '1' or '?'.
Examples
0)
	"00010001" "??" Returns: 3 There are four strings that match B: the strings "00", "01", "10", and "11". Out of these, the string "11" does not occur in A as a substring. The other three do occur, hence the answer is 3.
1)
	"00000000" "??0??0" Returns: 1 There are 16 different strings that match B, but out of those only the string "000000" is a substring of A.
2)
	"001010101100010111010" "???" Returns: 8 Each of the 8 strings that match B occurs somewhere in A.
3)
	"00101" "??????" Returns: 0 Here, the length of B is greater than the length of A. Clearly, a string that matches this B cannot be a substring of this A.
4)
	"1101010101111010101011111111110001010101" "???????????????????????????????????" Returns: 6

=========================================================
My approach


1. A>B and
2. Find B length
3. Make all possible String with length of B and push HashSet
4. HashSet will filter duplication.
5. and finally only unique strings remain in hashset
6. compare all string with B if index of character is not ?
7. count all if it is match


my code is below

public long ways(String A, String B){
  HashSet<String> set = new HashSet<String>();
  
  int blen = B.length();
  for (int i = 0; i <= A.length()-blen; i++) {
   set.add(A.substring(i, i+blen));
  }
  
  Iterator<String> iter =  set.iterator();
  int count =0;
  while (iter.hasNext()) {
   String str = iter.next();
   boolean found = true;   
   for (int i = 0; i < blen; i++) {
    if(B.charAt(i)!= '?'){
     if(A.charAt(i) != B.charAt(i)){
      found =false;
      break;
     }
    }
   }
   if(found){
    count++;
   }
  }
  return count;
 }

how can we know this array is sorted in java

this is easy example

        int o = a[0] < a[1] ? 0 :1;
 for (int i = 1; i < a.length-1; i++) 
   if( 0!= (a[i] < a[i+1]?0:1) )   return "not sorted";
 return o ==0?"ascending" : "descending";

Project Euler problem 303

My effort to solve it

1. make 3digit generator and divide with n

2. 9999 is never solved in time.

3. find 9, 99, 999, 9999 in pattern.

4. finally solve it in 9s

find the ways to make specific number with dice

this problem is about hexanacci number

               long a = 0,b= 0,c= 0,d= 0,e= 0,f=1, t = 0;
  
  for (int i = 1; i <= n; i++) {
   t = a+b+c+d+e+f;   
   a=b;
   b=c;
   c=d;   
   d=e;
   e=f;
   f=t;
  }
  return t+"";

Hexanacci numbers: a(n+1) = a(n)+...+a(n-5) with a(0)=...=a(4)=0, a(5)=1. 

huffman coding ( encoding and decoding) algorithm in python

this is short code written by python.

Huffman encoding 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 self
def 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, str + '1' )

    if heap.left == None:
        print(heap.char, str)
        dic[heap.char] = str

def insertionSort(heapArr, heap):
    index = len(heapArr)
    for i in range(len(heapArr)):
        if heap.freq < heapArr[i].freq:
           index  = i
           break
    heapArr.insert(index, heap)

def makeNewString(arr, freq):

    freqcopy = freq[:]
    arrcopy = arr[:]
    strval = ''
    while len(freqcopy) >0:
        number = random.randrange(0,len(freqcopy))
        freqcopy[number] = freqcopy[number]-1        strval = strval + arrcopy[number]
        if freqcopy[number] == 0:
            freqcopy.pop(number)
            arrcopy.pop(number)

    return strval

def endcoding(str):
    strval = ''    for i in range(len(str)):
        strval = strval + dic[str[i]]

    return strval

def huffmandecode(rootheap, strvalencoded):

    index = 0;
    orgstr = '';

    while index < len(strvalencoded):
        str = getchar(rootheap, index, strvalencoded)
        index = index + len(dic[str])
        orgstr = orgstr + str
    return orgstr

def getchar(rootheap, index, strvalencoded):
    if rootheap.left == None:
        return rootheap.char

    number = int(strvalencoded[index])
    if number ==0:
        return getchar(rootheap.left, index+1, strvalencoded)

    if number ==1:
        return getchar(rootheap.right, index+1, strvalencoded)

arr = ['a', 'b', 'c', 'd', 'e', 'f']
freq = [5, 9, 12, 13, 16, 45]
rootheap = huffmanCoding(arr, freq)

printHeap(rootheap, '')

strval  = makeNewString(arr, freq)
print("org     ", strval)

strvalencoded = endcoding(strval)
print("encoded ",strvalencoded)

orgencoded = huffmandecode(rootheap, strvalencoded)
print("decoded ", orgencoded)