My Blog List

Thursday, April 28, 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

    
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;
 }

Tuesday, April 26, 2016

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


Tuesday, April 19, 2016

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. 

Thursday, April 7, 2016

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)