[Leetcode][DP][Backtracking] Word Break II [Snapchat]

1. What
Break a word with space to form a sentence with each word in the dictionary
s= "catsanddog"
dict = ["cat", "cats", "and", "sand","dog"]
A solution is ["cats and dog", "cat sand dog"]
Record all solutions => use DFS
2. How
2-1 can split like this
c
ca
cat
cats
catsa
catsan
....
2-1 need a dict
hashset<String> contain() to check if word exist or not
2-2 solve
Thought 1. split a string and hashset each substring(word), too much possibilities
Thought 2. start from the first letter to see any match in Dict (hashSet contain)
2-3 Solution
Thought 2. would be more doable, start from the first letter and check
2-4 Algorithm
so start from index 0 (int start)
and the length of extension (int ext)
E.g., s = "catsanddog"
start = 0 and ext =0 => "c",  NOT FOUND
start = 0 and ext =1 =>"ca", NOT FOUND
start = 0 and ext =2 => "cat",        FOUND (reset start =0+2+1= 3)
"cat sanddog"
start = 3 and ext = 0=>"s", NOT FOUND
start =3 and ext =1=>"sa", NOT FOUND
start = 3 and ext =2 =>"san", NOT FOUND
start =3 and ext =3=> "sand",          FOUND(reset start  = 3+3+1 = 7)
"cat sand dog"
start = 7 and ext =0 => "d", NOT FOND
start = 7 and ext =1=>"do",NOT FOUND
start= 7 and ext =2=> "dog",       FOUND (reset start = 7+2+1 = 10 > length)

start > length => return to start =3 and ext =3 "sand"
start = 3 and  ext = 4 "sandd", NOT FOUND

start =3 and ext =5 (total > length) return to start =0 and ext =2 "cat"
start = 0 and ext =3 =>"cats", FOUND (reset start = 0+3+1 =4)
"cats anddog"
start =4 and ext =0=>"a" X
start =4 and ext =1=> "an" X
start=4 and ext =2 => "and" O (reset start = 4+2+1 =7)
"cats and dog"
start =7 and ext = 0 =>..
start = 7 and ext =2=>"dog", FOUND(reset start = 7+2+1 > length)
 return
..

public class Solution
{
    public List wordBreak(String s, Set wordDict)
    {
         List res = new ArrayList();
        // valid the input
        if ( s== null || s.length() == 0)
        {
            return res;
        }
         
        if ( check(s,dict) )
        {
            helper(s,dict,0,"",res);
        }
        return res;
    }
    // get part of string 
    private void helper(String s, Set dict, int start, String item, List res)
    {
        if ( start >= s.length )
        {
              res.add(item);
              return;
        }
        // the length of extension from the start 
        StringBuilder str = new StringBuilder();
        for ( int i = start ; i < s.length() ;i++)
        {
            str.append(s.charAt(i));
            // FOUND
            if (  dict.contains( str.toString(str) )  )
            {
                 String newItem = new String();
                 if (item.length() > 0)
                 { 
                      newItem = item+ " "+ str.toString();
                 } 
                 else 
                 {
                      newItem = str.toString();
                 }
                 // reset start and recurse
                 helper(s, dict, i+1, newItem, res);
            }
        }
    }

    //check s if in the dict 
    private boolean check(String s , Set dict)
    {
        // validate the input
        if ( s== null || s.length() == 0)
        {
            return true;
        }
        boolean[] res = new boolean[s.length()+1];
        res[0] = true;
        for (int i = 0 ; i < s.length();i++)
        {       
               StringBuilder str = new StringBuilder(  s.substring(0,i+!)  );
               for (int j = 0; j<= i; j++)
               {
                    if (res[j] && dict.contains(str.toString()))
                    {
                         res[i+1] = true;
                         break;
                    }
                    str.deleteCharAt(0);
               }
        }
        return res[s.length()];
    }
}

[Leetcode][Backtracking] N-Queens II [Sanpchat]

1. What
http://codingweihung.blogspot.com/2015/08/leetcodebacktracking-n-queens-sanpchat.html
2. How
http://codingweihung.blogspot.com/2015/08/leetcodebacktracking-n-queens-sanpchat.html

NOTE: return total number of distinct solution 

What is distinct solution? 

how to represent a solution?  a String[], so distinct means different String[]

hashSet to store string array ?  to much hassle

hashSet to store int array which is columnWithQueenForRow

public class Solution
{
   // NOTE: can also declare a global variable int res, initialize in totalNQueens() and increment in helper()
   public int totalNQueens(int n)
   {
         int[] res = {0};
        /*validate the input */
        if ( n <= 0)
        {
            return res[0];
        }
        int[] columnWithQueenForRow = new int[n];
        helper(n, 0, columnWithQueenForRow, res);
   }
   
   /*recursive function to go over column by column*/
   private void helper (int size, int row , int[] ColumnWithQueenForRow, int[] res)
   {
       if ( row == n )
       {  
           /*NOTE: won;t have duplicate solution since start from different column*/
           res[0]+=1;
           return;
       }
       for (int j = 0 ; j < n ;j++)
       {
             columnWithQueenForRow[row] = j;
             if ( check(row, columnWithQueenForRow) )
             {
                   helper( n, row+1, columnWithQueenForRow, );
             }
       }
   }
   
   /* check valid move*/
   private boolean check (int row, int[] columnWithQueenForRow)
   {
       for ( int i = 0 ; i < row; i++)
       {
              if ( columnWithQueenForRow[row] == columnWithQueenForRow[i] || Math.abs( columnWithQueenForRow[row] - columnWithQueenForRow[i] ) == (row - i) ) 
              {
                    return false;
              }
       }
       return true;
   }
}

[Leetcode][Backtracking] N-Queens [Sanpchat]

1. What
-NxN board
- Queen is expressed as 'Q' on the board and Empty is expressed as '.'
Play Rules:
-Rule1: Cannot place in the same row
-Rule2: Cannot place in the same column
-Rule3: Cannot place in diagonal

2. How
   2-1. So every time you place an Queen(called a move), you need a function to check if it is complied with all the rules.
   2-2. Then how to start the first move?
NOTE: start from row 0
   2-3 Space:O(NxN) to store all the characters in the board
   Improve?
   Space:O(N) since what we care is that for each column or row, does it have any Queen in there.     Thus,  we can just use an array called columnWithQueenForRow to record which column have Queen, e.g., columnWithQueenForRow[0] = 5 means in row 0, column 5 has a queen
   2-4. Time:O(n^n) Exponential ?
every row has N options N*N*N..*N = N^N
   2.5 return a List<String[]>, to make String[], we can use StringBuilder to append empty or Queen and then add each String[] into List for each row iteration
NOTE: when it's at the end of the row, create a String array to record current solution and put onto List

/*
Parameter: n, the size of board 
Return: List, whole board character 
*/
public class Solution
{
    public List solveNQueens(int n)
    {
         List res = new ArrayList();
         /*validate the input */
         if ( n == 0 )
         {
              return res;
         }
         helper(n, 0, new int[n], res);
         return res;
    }
    /* recursive function to keep placing move by going over column by column*/
    private void helper(int n, int row, int[] columnWithQueenForRow, List res )
    {
           // NOTE: return whole board String 
           if ( row == n )
           { 
                // NOTE: String[] to store current solution of all rows
                String[] item = new String[n]; 
                for (int i = 0 ; i < n; i++)
                {   
                    StringBuilder sb =new StringBuilder();
                    for (int j = 0; j < n ; j++ )
                    {
                         if ( columnWithQueenForRow[i] == j )
                         {
                              sb.append('Q');
                         }
                         else 
                         {
                              sb.append('.');
                         }
                    }
                    item[i] = sb.toString();
                }
                res.add(item);
                return;
           }
           for ( int j = 0 ; j  < n; j++ )
           {
                // NOTE: no need to clean value since if false, it goes to next iteration and will assign a new value to override it
                columnWithQueenForRow[row] = j;
                if ( check(row, columnWithQueenForRow) )
                {
                      helper(n, row+1, columnWithQueenForRow, res);
                }

           }

    }
    /* check legal move or not by checking if there any queen along that column */
    private boolean check (int row, int[] columnWithQueenForRow)
    {    

         // NOTE: avoid default column index 0 check, only compare with previous rows which are already being marked
         for (int i = 0 ; i < row;i++)
         {
             if ( columnWithQueenForRow[row] ==  columnWithQueenFor[i] || Math.abs( columnWithQueenForRow[row] - columnWithQueenForRow[i]) == Math.abs(row - i) )
             {
                   return false;
             }
         }
         return true;
    }
}

[Algorithm][Math] calculate the angle between hour and minute hand

// calculate the angle between hour and minute hand
public int calcAngle( double h, double m)
{
      // validate the input 
      if ( h < 0 || h >12 || m < 0 || m > 60 )
      {
              throw IllegalArgumentInput(“Wrong Input”);
       }
       if ( h==12  ) h = 0;
       if ( m == 60 ) m = 0;
       
       int hour_angle = 30*h + 0.5*m; // 30 degree per hour =  a circle 360 degree / 12 and 1 minute affects 0.5 degree to hour hand
       int minute_angle = 6 * m ;            // 6 degree per minute = a circle 360 degree / 60 

       int angle = abs(hour_angle - minute_angle);
       angle = Math.min(360 -angle, angle);
       return angle;
}

[Algorithm] Algorithm Interview Questions

Algorithm Basics

BFS Iterative

BFS recursive

DFS Iterative

DFS recursive

Bubble Sort

Count Sort

Selection Sort

MergeSort

QuickSort

HeapSort

Topological Sort

Binary Search

HashTable and Binary Search Tree Time and Space Complexity

Two Sum

Top10

Algorithm Advanced

Trie

LRU

*Quick select (Quick Sort)

*Binary Indexed Tree

*Line Sweep

*DHT

*B-Tree

Map<K,V>

[DP] Find first non repeated character in a string [Rubicon]

1. Problem
Given a string, find the first non repeated character ?

2. Example
s= "hello", except 'l' all are non-repeated, but 'h' is the first non-repeated character.
s= "swiss", 'w' is the first non-repeated character.
One way to solve this problem is creating a table to store count of each character, and then picking the first entry which is not repeated. key thing to remember is order.

3. Implementation in Java

// Time:O(2n) two for loops not nested, Space:O(n) LinkedHashMap

// LinkedHashMap to store character count, since LinkedHashMap maintains // insertion order and we are inserting character in the order they 
// appear in the string.
// We just need to iterate through LinkedHashMap and choose the entry with value 1


public static char findFirstNonRepeatedCharacter( String s)
{
     Map map = new LinkedHashMap<>(str.length());
     for (char c: s.toCharArray())
     {
         map.put(c, map.containsKey(c)? map.get(c)+1 :1   );
     }
    
     for ( Entry entry:map.entrySet() )
     {
         if (entry.getValue() ==1)
         {
              return entry.getKey();
         }
     }
     throw new RuntimeException("cannot find any non repeated character");
}

4.Implementation in Java

// Time:O(n) one for loop, Space:O(n) set 

// one set and one list to repeating and non-repeating character separately
// Once we finish scanning through string, which is O(n), we can get the magic character by accessing List in O(1) time.

public static char findFirstNonRepeatedCharacter (String s)
{
    Set repeated = new HashSet<>();
    List nonRepeated = new ArrayList<>();
    for ( int i = 0 ; i < s.length() ; i++ )
    {
         char letter = s.charAt(i);
         if ( repeated.contains(letter)  ) 
         {
             continue;
         }
         if ( nonRepeated.contains( letter  )) 
         {
              nonRepeated.remove((Character) letter ));
              repeated.add( letter );
         }
         else
         {
              nonRepeated.add( letter );
         }
    }
    return nonRepeated.get(0);
}

5.Implementation in Java

// Time:O(2n) two for loops not nested, Space:O(n) 


// HashMap 

public static char findFirstNonRepeatedCharacter(String s)
{
    HashMap score = new HahMap<>();
    for ( int i = 0 ; i < s.length() ; i++)
    {
       char letter = s.charAt(i);
       score.put(letter, score.containsKey(letter)? score.get(letter)+1:1);  
    }

    for (int i = 0; i < s.length();i++)
    {
        char letter = s.charAt(i);
        if (score.get(letter) == 1)
        {
           return letter;
        }
    }
    throw new RuntimeException("Undefined Behavior");
}



import static org.junit.Assert.*;
import org.junit.Test;

public class findFirstNonRepeatedCharacterTest {

    @Test
    public void testFirstNonRepeatedCharacter() {
        assertEquals('b', Solution.firstNonRepeatedCharacter("abcdefghija"));
        assertEquals('h', Solution.findFirstNonRepeatedCharacter("hello"));
        assertEquals('J', Solution.findFirstNonRepeatedCharacter("Java"));
        assertEquals('i', Solution.findFirstNonRepeatedCharacter("simplest"));
    }

    @Test
    public void testFirstNonRepeatingChar() {
        assertEquals('b', Solution.firstNonRepeatingChar("abcdefghija"));
        assertEquals('h', Solution.findFirstNonRepeatedCharacter("hello"));
        assertEquals('J', Solution.findFirstNonRepeatedCharacter("Java"));
        assertEquals('i', Solution.findFirstNonRepeatedCharacter("simplest"));
    }

    @Test
    public void testGetFirstNonRepeatedChar() {
        assertEquals('b', Solution.getFirstNonRepeatedChar("abcdefghija"));
        assertEquals('h', Solution.findFirstNonRepeatedCharacter("hello"));
        assertEquals('J', Solution.findFirstNonRepeatedCharacter("Java"));
        assertEquals('i', Solution.findFirstNonRepeatedCharacter("simplest"));
    }
}

6. References:
http://javarevisited.blogspot.com/2014/03/3-ways-to-find-first-non-repeated-character-String-programming-problem.html

[DP]Longest Increasing Subsequence in Java O(n logn) [Rubicon]

1. Problem

Given a integer array with no duplicate integer, find the longest increasing subsequence?

2. Example

 int[] num = [1,6,2,4,5,0]
subsequence = [1],[6],[2],[4],[5],[0], [1,6], [1,5], [1,6,2,5], [1,2,4,5]..etc.
increasing subsequence = [1],[6],[2],[4],[5],[0], [1,6], [1,2], [1,2,4], [1,2,4,5]..etc.

1	6	2	4	5	0
1 LIS = 1	6 1,6 LIS =2	2 1,2 LIS = 2	4 1,2,4 LIS =3	5 1,2,4,5 LIS = 4	0 LIS=1
LIS[0]=LIS[0]=1	LIS[1]=LIS[0]+1=2 since 6 > 1	LIS[2]=LIS[0]+1 = 2 since 2 !> 6 but 2 > 1	LIS[3]=LIS[2]+1=3 since 4 > 2	LIS[4] = LIS[3]+1 =4 since 5 >4	LIS[5] = LIS[5] since 0 !> 5,4,2,6,2

Formula: if ( num[i] > num[j] ) LIS[i] = LIS[j] +1 

3. Implementation in Java

// Time:O(n^2) two for loop, Space:O(n) an array
// For each element in an array, compare it with the elements before it and computer the length of LIS(longest increasing subsequence)

public static int LongestIncreasingSubsequence(int[] num)
{
    int[] L = new int[num.length];
    L[0] = 1;
    //  j  i
    //  1  6
    for (int i = 1 ; i < L.length; i++)
    {
        // for every index, they have their own max
        int max = 0;
        for ( int j = 0; j< i ; j++)
        {
            if( num[i] > num[j] && L[j] > max )
            {
                 max = L[j];
            }  
        }
        L[i] = max +1; // 1. L[1] = 0+1= 1 or 2. no greater than any element or 3. anyway add current element
    }

    int max = 0;
    for (int i = 0 ; i < L.length ; i++)
    {
       if ( L[i] > max )
       {
          max = L[i];
       }
    }
    
    return max;
}

4. Example :

	1	6	2	4	5	0
s={} - initialize s to the empty set	s={1} New largest LIS	s={1,6} - New Largest LIS	s= {1,2} New largest LIS	s={1,2,4} New largest LIS	s={1,2,4,5} New largest LIS	s={0,,2,4,5} New largest LIS
		if num[i] > last element in S, then append X to the end of S	otherwise, find the smaller greater than element in num, change it to num[i] ex. change 6 to 2 Because S is sorted at any time, the element can be found using binary search in log(N).	if num[i] > last element in S, then append X to the end of S	if num[i] > last element in S, then append X to the end of S	otherwise, find the smaller greater than element in num, change it to num[i] ex. change 1 to 0 Because S is sorted at any time, the element can be found using binary search in log(N).

5. Implementation in Java

// Time:O(n logn ) , Space:O(n) an array
// Binary search a sorted array to replace element


        if ( num == null || num.length == 0) {
            return 0;
        }
        if ( num.length == 1){
            return 1;
        }
    
        int[] sortedTable = new int[num.length];
        int len = 0;
        sortedTable[0] = num[0];
        len =1;
        for ( int i = 1 ; i < num.length ; i ++)
        {
            if ( num[i] < sortedTable[0] )
            {
                sortedTable[0] = num[i]; // change it to current value
            }
            else if ( num[i] > sortedTable[len-1] )
            {
                sortedTable[len++] = num[i]; // append 
            }
            else
            {
              // num[i] wants to be current end candidate of an existing subsequence, it will replace ceil value in sortedTable
                sortedTable[ serachInsertPosition(sortedTable,0,len-1,num[i])  ] = num[i];
            }
        }
        return len;
    }
    // 1,2,4,5, Target = 0
    // 0 1 2 3
    private int serachInsertPosition(int[] sortedTable, int l, int r, int target){

        while ( l <= r){
            int m = (l+r)/2;
            if ( sortedTable[m] == target ){
                return m;
            }
            if ( sortedTable[m] > target ){
                r= m-1;
            } else {
                l = m+1;
            }
        }
        return l;
    }

6. References:
http://professorjava.weebly.com/longest-increasing-subsequence.html
http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/

[Java] Difference between System.arraycopy() vs. Arrays.copyOf()

1. The Major Difference
Arrays.copyOf() will create a new array and return it and it use System.arraycopy() to copy elements
System.arraycopy() just copy elements

2. Example:



System.arraycopy()

int[] arr = {1,2,3,4,7};
 
int[] copy = new int[10];
System.arraycopy(arr, 0, copy, 1, 5);//5 is the length to copy
 
System.out.println(Arrays.toString(copied));

Output

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 2, 3, 4, 7, 0, 0, 0, 0]

Arrays.copyOf()

int[] arr = {1,2,3,4,7};
int[] copy = Arrays.copyOf(arr, 10); //10 the the length of the new array
System.out.println(Arrays.toString(copy));
copy = Arrays.copyOf(arr, 3);
System.out.println(Arrays.toString(copy));

Output

[1, 2, 3, 4, 7, 0, 0, 0, 0, 0]
[1, 2, 3]

References:
http://www.programcreek.com/2015/03/system-arraycopy-vs-arrays-copyof-in-java/

[Leetcode] [DFS]Path Sum II

For example:
Given the below binary tree and sum = 22,
              5
             / \
            4   8
           /   / \
          11  13  4
         /  \        / \
        7    2    5   1
return
[
   [5,4,11,2],
   [5,8,4,5]
]
/*

Time:O(n), Space:O(k*logn), where k means total k paths

*/
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List> pathSum(TreeNode root, int sum) {
        List> res = new ArrayList>();
        // special case
        if ( root == null )
        {
            return res;
        }
        List item = new ArrayList();
        item.add(root.val);
        helper(root, sum - root.val, item, res);
        return res;
    }
    
    private void helper(TreeNode root, int sum, List item, List> res)
    {
        // leaf.left
        if (root == null )
        {
            return;
        }
        if ( root.left == null && root.right == null && sum == 0 ) // base case
        {
            //**** need a new one
            //res.add(item);
            res.add( new ArrayList(item) );
            return;
        }
        //  1
        // 2 3
        if ( root.left != null )
        {
            // 1 +2 
            item.add(root.left.val);
            helper(root.left, sum - root.left.val, item, res);
            // **** become 1 for 1+3
            item.remove(item.size()-1);
        }
        if ( root.right != null )
        {
            // 1+3
            item.add(root.right.val);
            helper(root.right, sum - root.right.val, item, res);
            // 1
            item.remove(item.size() -1);
        }
        return;
    }
}

[Leetcode] Populating Next Right Pointers in Each Node II

For example,

Given the following binary tree,

         1

       /  \

      2    3

     / \      \

    4   5     7

After calling your function, the tree should look like:

         1 -> NULL

       /  \

      2 -> 3 -> NULL

     / \       \

    4-> 5 -> 7 -> NULL

/** Definition for binary tree with next pointer.
 * public class TreeLinkNode {
 *     int val;
 *     TreeLinkNode left, right, next;
 *     TreeLinkNode(int x) { val = x; }
 * }
 */
/*
Binary Tree Level Order Traversal Extension

*** only use constant extra space
so precious BFS with queue not working here

M1: BFS
Time:O(n) Space:O(1)


Runtime Error Message:
Line 54: java.lang.NullPointerException
Last executed input:
{7,-10,2,-4,3,-8,#,#,#,#,-1,11}
      7
  -10      2
-4  3   -8  #
## #-1  11
 */
public class Solution {
    public void connect(TreeLinkNode root) {

        /*BFS*/
        if (root == null)
        {
            return;
        }
        TreeLinkNode head = root; // use TreeLinkNode next feature as a queue
        TreeLinkNode newHead = null;
        TreeLinkNode iterating = null;
        int lastNum = 1;
        int curNum = 0;
        while ( head != null )
        {
            TreeLinkNode cur = head;
            lastNum--;
            if (cur.left != null)
            {
                if (curNum == 0)
                {
                    newHead = cur.left;
                    iterating = newHead;
                }
                else
                {
                    iterating.next = cur.left;
                    iterating = iterating.next;
                }
                curNum++;
            }
            if ( cur.right != null )
            {
                if ( curNum != 0 )
                {
                    iterating.next = cur.right;
                    iterating = iterating.next;
                }
                // major difference from Populating Next Right Pointers in Each Node I
                if(curNum == 0)
                {
                  newHead = cur.right; 
                  iterating = newHead;
                }
                curNum++;
            }

            if ( lastNum == 0 )
            {

                head = newHead;
                lastNum = curNum;
                curNum = 0;
                newHead = null;
                iterating = null;
            }
            else
            {
                head = head.next;
            }
        }
    }
}

[Leetcode] Populating Next Right Pointers in Each Node I

For example,

Given the following perfect binary tree,

         1

       /  \

      2    3

     / \  / \

    4  5  6  7

After calling your function, the tree should look like:

         1 -> NULL

       /  \

      2 -> 3 -> NULL

     / \  / \

    4->5->6->7 -> NULL

/**
 * Definition for binary tree with next pointer.
 * public class TreeLinkNode {
 *     int val;
 *     TreeLinkNode left, right, next;
 *     TreeLinkNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void connect(TreeLinkNode root) {
        
        
        /*BFS*/
        if (root == null)
        {
            return;
        }
        TreeLinkNode head = root; // use TreeLinkNode next feature as a queue
        TreeLinkNode newHead = null;
        TreeLinkNode iterating = null;
        int lastNum = 1;
        int curNum = 0;
        while ( head != null )
        {
            TreeLinkNode cur = head;
            lastNum--;
            if (cur.left != null)
            {
                if (curNum == 0)
                {
                    newHead = cur.left;
                    iterating = newHead;
                }
                else
                {
                    iterating.next = cur.left;
                    iterating = iterating.next;
                }
                curNum++;
            }
            if ( cur.right != null )
            {
                if ( curNum != 0 )
                {
                    iterating.next = cur.right;
                    iterating = iterating.next;
                }
                //if(curNum == 0)
                //{
                // newHead = cur.right;  
                //}
                curNum++;
            }
            if ( lastNum == 0 )
            {
                head = newHead;
                lastNum = curNum;
                curNum = 0;
                newHead = null;
                iterating = null;
            }
            else
            {
                head = head.next;
            }
        }
    }
}

A Scrabble game

0. What is Scrabble game
For example, if you had the letter tiles "P", "A", "L", "P", and "O" (note that you can possess repeated letters), and the board looked like this:

_	_	_	_	_	_
_	_	_	_	_	_
_	_	T	_	_	_
_	_	E	_	_	_
G	R	A	P	E	_
_	_	R	_	_	_

There would be a large number of possible moves, or words to place. Here are a few of the possibilities (indicated by bold letters) :

_ _ _ _ _ _ _ _ _ _ _ _ _ _ T A P _ _ _ E _ _ _ G R A P E _ _ _ R _ _ _

_ _ _ _ _ _ _ _ _ _ _ _ L O T _ _ _ _ _ E _ _ _ G R A P E _ _ _ R _ _ _

_ _ _ _ _ _ _ _ _ _ _ _ L _ T _ _ _ A _ E _ _ _ G R A P E _ _ _ R _ _ _

_ _ _ _ _ _ _ _ _ _ _ _ _ _ T _ _ _ _ _ E _ _ _ G R A P E _ O _ R _ _ _

_ _ _ _ A _ _ _ _ _ P _ _ _ T _ P _ _ _ E _ L _ G R A P E _ _ _ R _ _ _

As you can summarize from the above, rules are as follows: 

1. More than one letter

2. Placing position is valid

3. word exists in the dictionary

4. Crossword-style

5. No additional new word is created

0.5 Logic

1. A dictionary to store all the valid word
-Constructor: init in Game class to load all words into dictionary
-Function: allow add word
-Function: allow search a word exist or not in  the dictionary, including pattern matching
- Leetcode: add and search word


2. A board to hold all the characters or tiles
-Constructor: a DS to store all the characters, A-Z (Upper case), '_'(Empty character)
ScrabbleBoard(int numrows, int numcols, ScrabbleMove move) 
the board is initialized with the word represented by move (unless it is null)
-Function: update the new move on the board, which means place legal word onto the board
-Function: isLegal(ScrabbleMove, Trie) 


3. Move
-Constructor: a move contains start location, direction,
ScrabbleMove(int row, int column, boolean direction, String word) intended word 
-Function: search a move, find all available characters on the board and choose the one with no character on the column or row where it locate(could be vertical or horizontal) and make sure only one character next to it
-Function:search a word and form a move ("T." and length >=4, ".T" and length <=3, ".G" and length 5, "G." and  length 2) 
-Function: calculate score for a legal move


4. Game
-Constructor:
- init board(int rows, int columns), init dictionary(filename)
- distribute letter tiles (String letterBag)
- whose turn (double[] players)
- scores, points(int[] letterValues)
- (int rows, int columns, String filename, double[] players, String letterBag, int numTiles, int[] letterValues, int seed)
-filename: the filename of a file containing the vocabulary of the game
-letterBag: a String representing all of available letter tiles for the game. There is one character for each available tile - thus, characters may be repeated.
-numTiles: the maximum number of letter tiles available to a player at any time
-letterValues: a 26-element int array indicating the points value of every letter
-seed: used to seed a single number generator
-Function: run game to make turns and no any move=> Game Over
-Function: currentLetters(): returns a string, representing the letter tiles available to current human player


5. AI 
-Constructor
-bestMove( ScrabbleBoard board, Trie vocabulary, int[] points, String letters)
static method which returns the highest-scoring legal move
-Move: search a best move
-Function: allMoves(ScrabbleBoard board, Trie vocabulary, String letters)
static method which returns all legal moves (as an array of ScrabbleMoves), given the parameters(same as bestMove). Return null if no moves are available

1. Trie.java
The vocabulary of all allowable words in your game will be represented by a trie.

Trie(String filename)
void addWord(String)
String[] getAllWords(String)
String[] getMatches(String)
"TR.E" => "TRIE" and "TREE"
Not "TRE" or "STREET"
boolean hasWord(String)
int size()

Method	Description
Trie(String filename)	The constructor, which reads a word list from the filename provided as a parameter, and builds a trie containing those words.
addWord(String)	Store the specified word in the trie. If the word exists in the trie already, then do nothing.
getAllWords()	Returns an array of Strings, containing all the words in the trie in sorted order.
getMatches(String)	Returns an array of Strings, containing all the words in the trie which match the given pattern, in sorted order.
hasWord(String)	Returns a boolean indicating whether the given word is contained within the trie.
size()	Returns an int count of the number of words in the trie.

2. ScrabbleMove.java
A move consists of a large amount of information: where the word is placed, the direction that it's placed in, and the actual word to be placed.

ScrabbleMove(int row, int column, boolean direction, String word)
direction = true when horizontal and direction = false when vertical
word means intended word
int getRow()
int getColumn()
boolean getDirection()
String getWord()

Method	Description
ScrabbleMove(int row, int column, boolean direction, String word)	Constructor, with parameters indicating the move's row, column, direction ( true = horizontal, false = vertical), and intended word.
getRow(), getColumn(), getDirection(), getWord()	These methods return (respectively) the move's row, column, direction, and intended word.

3. ScrabbleBoard.java
you must implement the rules of the game, so that only legal moves are permitted. Exactly how you implement theScrabbleBoard is up to you, including how you represent the board. You should decide which data structures or classes are most appropriate in order to implement the class according to the specifications.

ScrabbleBoard(int numrows, int numcols, ScrabbleMove move)
int numRows()
int numColumns()
charAt(int row, int column)
'_' if unoccupied
toString()
" " first row (each column start)
"\n" first column (each row start)
makeMove(ScrabbleMove, Trie)
update the board
isLegal(ScrabbleMove, Trie)

Method	Description
ScrabbleBoard(int numrows, int numcols, ScrabbleMove move)	The constructor, which creates a Scrabble board with numrows rows and numcols columns. The board is initialized with the word represented bymove (unless it is null). Precondition: move only occupies valid board locations. (Modified July 22)
numRows(), numColumns()	Return an int representation of the board's number of rows and columns, respectively.
charAt(int row, int column)	Returns the character (as a char) at positions (row, column), or an underscore ('_') if the position is unoccupied.
toString()	Return a String representation of the board, with each column preceded by a blank space (" ") and each row followed by a newline ("\n"). Empty positions are represented by an underscore ("_").
makeMove(ScrabbleMove, Trie)	Make the specified move and update the board as appropriate. Throws an IllegalMoveException if the move is illegal. Precondition: any words already on the board are in the given vocabulary.
isLegal(ScrabbleMove, Trie)	Returns a boolean indicating whether the specified move is legal, given a vocabulary in trie form. Precondition: any words already on the board are in the given vocabulary.

4. ScrabbleAI.java
bestMove(ScrabbleBoard board, Trie vocab, int[] points, string letters)
allMoves(ScrabbleBoard board, Trie vocab, String letters)

Method	Description
bestMove(ScrabbleBoard board, Trie vocab, int[] points, String letters)	static method which returns the highest-scoring legal move given: board: the current board state. vocab: a vocabulary in trie form. points: a 26-item array of ints, indicating the point value of each letter in the alphabet. letters: the letter tiles available to the AI to place. This may be the empty string, and it may contain repeated characters. However, the order of the characters should not matter. Returns null if no moves are available.
allMoves(ScrabbleBoard board, Trie vocab, String letters)	static method which returns all legal moves (as an array of ScrabbleMoves), given the parameters (same as bestMove). Returns null if no moves are available.

5.ScrabbleGame.java
Everything is tied together by the "front end" class, ScrabbleGame. This class is created with all of the parameters of the game, manages the AI players, keeps score, and distributes letter tiles.

Method	Constructor
ScrabbleGame(int rows, int columns, String filename, double[] players, String letterBag, int numTiles, int[] letterValues, int seed)	Constructor, which creates a Scrabble game with the following parameters: rows: the number of rows on the board. columns: the number of columns on the board. filename: the filename of a file containing the vocabulary of the game. players: an array of doubles, with one entry for each player, in order. The entries are either -1 (indicating a human player) or a value between 0 and 1 (indicating the skill of an AI player). letterBag: a String representing all of the available letter tiles for the game. There is one character for each available tile - thus, characters may be repeated. numTiles: the maximum number of letter tiles available to a player at any time. letterValues: a 26-element int array indicating the points value of every letter. seed: used to seed a single random number generator.
isOver()	Returns a boolean, indicating whether the game is finished or not.
getScores()	Returns an array of ints, representing the current score of each player.
currentPlayer()	Returns an int, representing the player # of the human player whose move is required.
currentLetters()	Returns a String, representing the letter tiles available to the current human player.
makeMove(ScrabbleMove)	Makes the specified move, for the current human player. A null parameter indicates a "pass". If the move is illegal, throws an IllegalMoveException and play does not advance to the next player.
getBoard()	Returns a String representation of the current board.

6. Order of play
when the game is started, the following occurs:

1. The game vocabulary is loaded.
2. Each player is given random letter tiles from the bag, one player at a time. for example, Player 0 gets a tile, then Player 1 , and so on. This continues until all players have the maximum number of tiles, or there is only one letter tile remaining in the bag.
3. One of the remaining letter tiles is selected, and is placed at a random position - that is, a random row and a random column. If only one tiles remains, it is chosen automatically without a random number being generated.
4. Play begins with Player 0, and continues with each player in order , repeating in order once the last player's turn is over. Players may either make a legal move, or pass. Players with no remaining letter tiles automatically pass.
       - when a player makes a legal move by placing n letter tiles, they are given n randomly-selected tiles from the bag to maintain same number of letter tiles. If fewer than n tiles remain, then the palyer is given all remaining tiles (which may be none) without a random number being generated.
      - when a player make a legal move, their score is modified by the total points value of every letter in the word that was created.
Note: this means that points are awarded for letters which the player did not place, but are part of the word they created.
      - if current turn is an AI player, their move is determined according to their skill level (see below), and play continues to the next player.

5. If all players has passed in a row (for example, Player 1 passed, Player 2 passed, ....and then Player ) passed), then the game is over.

6. AI
Each AI player is represented by a "skill value" between 0 and 1. On its turn, an AI player with a skill value of s will determine its action according to the following algorithm:

 1. A random number r, between 0 and 1, is generated.
 2. If r < s, the AI player makes the best legal move, or passes if no moves are available.
 3. Otherwise, the AI player randomly makes one of all the available moves, or passes if no moves are available.

7. Move Legally

     1. More than one letter

     2. Placing position is valid

     3. word exists in the dictionary

     4. Crossword-style

     5. No additional new word




_
_
_
_
_
_
E
_
_
_
A
_
_
_
T
_

After placing "CAR" horizontally at (2, 1):

_
_
_
_
_
_
E
_
_
C
A
R
_
_
T
_




While the following move is illegal because "RC" and "ER" were created. Even if these words were in the game's vocabulary, this move would still be illegal.


_
_
_
_
T
R
E
E
_
_
A
_
_
_
T
_

After placing "CAR" horizontally at (2, 1):

_
_
_
_
T
R
E
E
_
C
A
R
_
_
T
_




This move would also be illegal, because "BEAT" was created, even though it may be in the game's vocabulary:


_
_
_
_
_
_
E
_
_
_
A
_
_
_
T
_

After placing "CAB" horizontally at (0, 0):

C
A
B
_
_
_
E
_
_
_
A
_
_
_
T
_




(Added July 22) At least one of the move's letters corresponds to a board position already occupied for that letter. This means that new words must be placed "crossword-style" (attached to each other) and not just anywhere on the board. For example, the following is illegal:


_
_
_
_
_
_
_
_
_
_
_
_
R
A
T
_

After placing "CAR" horizontally at (1, 0):

_
_
_
_
C
A
R
_
_
_
_
_
R
A
T
_



However, the word could be placed legally this way:


_
_
_
_
_
_
_
_
_
_
_
_
R
A
T
_

After placing "CAR" vertically at (1, 0):

_
_
_
_
C
_
_
_
A
_
_
_
R
A
T
_










Random Numbers

Like in Assignment 3, your ScrabbleGame should use a single object of class Random to generate all of its random numbers, and the Random should be seeded with the value provided to theScrabbleGame constructor. When generating a random number between 0 and 1, use the nextDouble method as in Assignment 3. However, in many cases you have to make a random selection from a particular number of elements. In these situations, use the nextInt(int n) method, which generates a random int between 0 (inclusive) and n (exclusive).

Simplifying Assumptions

Because this assignment involves a substantial amount of design, both for classes and algorithms, you may assume "resonable" input for each method described here. This means that you may make the following assumptions:

All Strings provided as parameter, consist only of upper-case letters, or the empty string. The only exception to this is Trie.getMatches, whose input String may also contain periods (".").
All filenames will be valid.
No null values will be provided as parameters. The only exception to this is ScrabbleGame.makeMove.
The board will have at least two rows and two columns. Otherwise, that would be silly.
There will be at least one player.







References:

http://www.dgp.toronto.edu/~karan/courses/148/148/assignments/a4/a4handout.html


https://github.com/marineb/scrabble/blob/master/src/Gameplay.java


http://www.java-forums.org/new-java/29100-scrabble-like-game.html

http://cs.stanford.edu/people/eroberts/courses/cs106a/handouts/32a-section-4-solutions.pdf

Distributed Hash Table(DHT)

0. Why:
In network scenario, the data is distributedly stored among a collection of machines.
Distributed Lookup Services deal with the problem of locating data that
is distributed among a collection of machines.

There are three basic approaches we can take to locate such data:
1. centralized server
2. flooding
3. distributed hash tables

For centralized server approach, a central server holds the entire database to serve the action of lookup
which server contain the data being looked up. However, it can be a problem
if a central server is not reliable or dead.

For flooding approach,  via peer to peer forwarding the loop-up, the peer who has the data can respond whoever sent the look-up request. However, the problem is that peers were not always
reliable up or fast (especially those connected to slow modems).

1. What:
In a distributed implementation, known as a distributed hash table, or DHT,
the hash table is distributed among a set of nodes. Nodes all use the same hash function.

The entire goal of a DHT is to allow anyone to find the node that corresponds to a given key.
that node will be responsible for holding the information associated with that key. So looking up a key gives you a node ID that holds the data.

A key difference between the DHT approach and the centralized or flooding approaches is that
a specific node is responsible for holding information relating to the key (even if it just sends a link to the content). However, in DHT, any node can hold the information relating which node ID holds the data.

2. How
For the implementation of DHT, there are two approaches to do it
1. chord
2. CAN, a Content-Addressable Network

Chord
Hash Function = hash(IP)%(n) = position index = 0,1,2,...n
IP is IP address and n refers to the number of node in a ring, thinking of a sequence of numbers in a logical ring, 0,1,2,.....n, and looping back to 0. Each node occupies a position this ring.

A (key,value) would be stored at a node that matches hash(key).
If there is no node at that position, the next node ahead of that number is responsible for storing the data. This is the next node you hit if you traverse the ring clockwise starting from that hash(key) position. This node (the next node of hash(key) ) is called the successor node. => Look up

When a node "joins" a network at some position j, where j = hash(node's IP), some (key,value) data has to migrate from successor's node to this new node. => Insert

For routing queries, a node only needs to know of its successor node. Queries can be forwarded through successors until a node that holds the value is found.

However, the problem would arise if it traverse the entire circle. To avoid this worst case and increase performance, nodes may maintain a table containing additional routing information about other nearby nodes. The reason is when a node needs to locate one that is farther away, it contacts the furthest node that knows about which node is nearby node of wanted located node. It means contacting the node whose ID is less than the hash(key) and asking it to locate the node for hash(key). The process can be repeated recursively to locate the node.


CAN, Content-Addressable Network
CAN use 2D hash function to locate the node that holds the key and value pair. It means thinking of a grid and two seperate hash function hash_x(key) and hash_y(key). The key is hashed with both of them and produce x = hash_x(key) and y = hash_y(key) coordiante value. The node responsible for the location (x,y) stores (key,value).

A node only knows about its immediate nodes. For looking up and routing messages to the node that holds the data it needs, it will use neighbors that minimize the distance to the destination.

A new node is inserted is inserted by the following process:
1. pick up a random pair of values in the grid (i,j)
2. cotact some node in the grid and ask it look up the node that is responsible for location (i,j)
3. Negotiate with that node to split its zone in half. The new node will own half of this area (i,j)
=> Insert

3. Implementation
Some essential elements to do the implementation:

1. Network overlay : it is very simple to simulate overlay, you can use a simple Circular Linked List, where each node points to a successor node forming the circular list.

2. Choosing Node ID: by hashing the Nodes IP, using a consistent hash function like SHA-1, a m bit identifier is generated which is set as the Node Id. Similarly, the value is hashed to generate a m bit identifier to be used as the key. Any key has to be of the same range of the Node Id so that they can be compared.

3. Store (insert)

# This is a clockwise ring distance function.
# It depends on a globally defined k, the key size
# The largest possible node id is 2**k
# Returns the node which is closest to the key
public Node closest_node(Node node, Node successor, int key)
{
if ( node.id > successor.id ) // 2^4 - 2(successor.id) - 6 > 6 - 4(node.id)
{
if ( (pow(2,k) - successor.id - key) > (key-node.id) )
return node;
else
return successor;
} 
}
else
{ 
if ( ( key - node.id) > ( successor.id - key )  )
{
return successor;
 }
else
{
 return node;
 }

}
}

# Find the responsible node and get the value for the key
public int lookup(Node start, int key)

    Node node = find_node(start, key);
    return node.value// node.data[key];
}

5. Analysis