## Thursday, April 28, 2016

### 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 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++) {
}

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 < a ? 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)```