Game of life

Game of life :
Game Rules :
* 1. Any live cell with fewer than two live neighbors dies, as if caused by under-population.
* 2. Any live cell with two or three live neighbors lives on to the next generation.
* 3. Any live cell with more than three live neighbors dies, as if by overcrowding.
* 4. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.
*     5. In any other state cell dies or remains quiescent/dead.

package com.gol;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

import sun.util.locale.StringTokenIterator;

public class GameOfLife {

/*
* There are 8 immediate neighbors of any given location in board, if all boundary conditions met
* given location : [row, col]
*
*
* [r-1, c-1]  [r-1, c]    [r-1, c+1]
*                    |
* [r, c-1] <---[r,c]--->  [r, c+1]
*                    |
* [r+1, c-1] [r+1, c]    [r+1, c+1]
*
* We can count neighbor either using 8 if else or using loops as well.
* I think loop is better option, it will take care of boundary condition as well, otherwise in
* case of if-else we have to go through all 8 if-else irrespective of the given loc.
* eg : [0,0]
* Assuming row and col cannot be -ve i.e less then zero(<0)
* @return the numbers of live cell in the neighbor of given cell
* Time : both loops executes 9 times if row and col both are  >0    
*/
public int getNeighbourCount(boolean board[][], int rc, int cc, int row, int col){
int r = rc==0 ? 0 : rc-1; // to check boundary condition
int c = cc==0 ? 0 : cc-1;
int i, j, liveCount=0;
for (i=r; i<=r+1 && i<row; i++) {
for (j=c; j<=c+1 && j<col; j++) {
if (i==row && j==col) {
continue; // no need to count for the given location on the board
}
if (board[i][j]){ //counting live neighbors only
liveCount++;
}
}
}
return liveCount;
}

/*
* Game Rules :
* 1. Any live cell with fewer than two live neighbors dies, as if caused by under-population.
* 2. Any live cell with two or three live neighbors lives on to the next generation.
* 3. Any live cell with more than three live neighbors dies, as if by overcrowding.
* 4. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.
*  5. In any other state cell dies or remains quiescent/dead.
* @return the state of the given cell on the basis of rules
*/

public boolean getState(boolean cellState, int liveCount){

if (cellState) {//live cell rules-1,2,3
if (liveCount<2)return false;
if (liveCount==2 || liveCount==3)return true;
if (liveCount>3)return false;
}else{ // dead cell rules-4
if (liveCount==3)return true;
}
return false; //otherwise return the existing state, means state will not change or if there is rule 5 return false
}

/*
* Input 1 : Board row and col
* Input 2 : Live cell location in board
*/
public Board getInput() throws IOException{
System.out.println("Input 1 : Board row and col");
System.out.println("Input 2 : Live cell location in board, comma seprated list");

InputStreamReader in = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(in);
String rowStr = br.readLine();
int row = Integer.parseInt(rowStr);
String colStr = br.readLine();
int col = Integer.parseInt(colStr);
String liveCellLoc = br.readLine(); // comma separated list


StringTokenizer st = new StringTokenizer(liveCellLoc, ",");
int size = st.countTokens();
int liveCell[] = new int[size];
int i=0;
while(st.hasMoreElements()) {
liveCell[i] = Integer.parseInt((String)st.nextElement());
i++;
}
Board board = new Board(row, col);
board.constructBoard(liveCell);
return board;
}

public void start(Board board){
int i, j, liveCount;
int count=0;
while(true){
for (i=0; i<board.row; i++) {
for (j=0; j<board.col; j++) {
liveCount = getNeighbourCount(board.board, i, j, board.row, board.col);
board.board[i][j] = getState(board.board[i][j], liveCount);
}
}
//System.out.println("\r");
System.out.print(boardToString(board.board, board.row, board.col));
//System.out.flush();
//count++;
}
}


private String boardToString(boolean[][] board, int row, int col) {
StringBuffer sb = new StringBuffer();
int i,j;
for (i=0; i<row; i++) {
for (j=0; j<col; j++) {
if (board[i][j]){
sb.append("*"); //append * for live state
}else{
sb.append("-"); // append space for dead state;
}
}
sb.append("\n");
}
//System.out.println(sb.toString());
return sb.toString();
}

class Board{
private int row;
private int col;
private boolean[][]board;

public Board(int row, int col){
this.row = row;
this.col = col;
board =  new boolean[row][col];
}

public void constructBoard(int []liveCell){
int i,r,c,loc;
for (i=0; i<liveCell.length; i++) {
loc = liveCell[i];
r = loc/col;
c = loc%col;
board[r][c]=true;
}
}
}

public static void main(String[] args) throws IOException {
GameOfLife gol = new GameOfLife();
Board board = gol.getInput();
gol.start(board);
}

}

Eclipse console Input/ Output :
Input 1 : Board row and col
Input 2 : Live cell location in board, comma seprated list
6
6
1,2,6,7,32,22

------
------
------
------
***---
-**---
------
------
------
------
**----
*-*---
------
------
------
------
**----
***---
------
------
------
------
-**---
**----
------
------
------
------
*-*---
**----
------
------
------
------
***---
-**---
------
------
------
------
**----
*-*---
------
------
------
------
**----
***---
------
------
------
------
-**---
**----
------
------
------
------
*-*---
**----
------
------
------
------
***---
-**---
------
------
------
------

Given a dictionary of words and an input string, find the longest prefix of the string which is also a word in dictionary.

Problem : Given a dictionary of words and an input string, find the longest prefix of the string which is also a word in dictionary.

Examples:

Let the dictionary contains the following words:
{are, area, base, cat, cater, children, basement}

Below are some input/output examples:
--------------------------------------
Input String            Output
--------------------------------------
caterer                 cater
basemexy                base
child                   < Empty >
Solution
We build a Trie of all dictionary words. Once the Trie is built, traverse through it using characters of input string. If prefix matches a dictionary word, store current length and look for a longer match. Finally, return the longest match.
Following is Java implementation of the above solution.

public String getLongestMatchingPrex(String input){
String result="";
int inputLen = input.length();
int index=0, prevMatch=0;
TrieNode current = root, childNode = null;
char ch;
while (index < inputLen) {
ch = input.charAt(index);
childNode = current.subNode(ch);
if (childNode != null) {
result += ch;
current = childNode;
// If this is end of a word, then update prevMatch
if (current.isEndOfString){
prevMatch = index + 1;
}
}else{
break;
}
index++;
}

if (!current.isEndOfString){
return result.substring(0, prevMatch);
}

return result;
}

Implementation of auto-complete functionality using Tries data structure. Tries Insert, search, location of string in tries and autocomplete

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collection;
import java.util.LinkedList;

/*
 * Auto-complete using tries in java
 */
public class Trie {

public TrieNode root;
public Trie(){
root = new TrieNode(' ');
}

public void insertInTrie(String str){
int strLen = str.length();
if (strLen == 0) {
root.isEndOfString = true;
} else {
int i=0;
TrieNode current = root, child=null;
while (i<strLen){
child = current.subNode(str.toLowerCase().charAt(i));
if (child != null) {
current = child;
}else {
child = new TrieNode(str.charAt(i));
current.child.add(child);
current = child;
}
i++;
}
current.isEndOfString  = true;
current.leafNodeStr = str.toLowerCase();
}
}

public TrieNode getLocationOfStringInTrie(String str){
TrieNode current = this.root, child;
int strLen = str.length();
int i=0;
while(i<strLen){
child = current.subNode(str.toLowerCase().charAt(i));
if (child != null) {
current = child;
} else {
return null;
}
i++;
}
if ( i == strLen){
return current;
}
return null;
}

public void autocomplete(TrieNode node){

if (node.isEndOfString) {
System.out.println("-"+node.leafNodeStr);
}
for (TrieNode childNode : node.child){
autocomplete(childNode);
}

}

public boolean searchInTrie(String str){
int strLen = str.length();
if (strLen == 0){
return true;
}else {
int i=0;
TrieNode current = root, child =  null;
while (i<strLen) {
child = current.subNode(str.charAt(i));
if (child != null) {
current = child;
}else {
return false;
}
i++;
}
if (i == strLen) {
return true;
}
}
return false;
}

public class TrieNode {
public char data;
public boolean isEndOfString;
public Collection<TrieNode> child;
public String leafNodeStr;

public TrieNode(char data){
this.data = data;
child = new LinkedList<TrieNode>();
this.isEndOfString = false;
}

public TrieNode subNode(char data){
if (child != null) {
for (TrieNode childNode : child) {
if (childNode.data == data){
return childNode;
}
}
}
return null;
}
}

public static void main(String[] args) throws IOException {
Trie trie = new Trie();
trie.insertInTrie("analyse");
trie.insertInTrie("boondock");
trie.insertInTrie("extend");
trie.insertInTrie("append");
trie.insertInTrie("insert");
trie.insertInTrie("remove");
trie.insertInTrie("free");
trie.insertInTrie("Free weblog publishing tool from Google, for sharing text, photos and vide");
trie.insertInTrie("clear");
trie.insertInTrie("blog");
trie.insertInTrie("what is autocomplete");
trie.insertInTrie("blog is your best bet for a voice among the online crowd");
trie.insertInTrie("start a WordPress blog or create a free website in seconds");
trie.insertInTrie("start");
trie.insertInTrie("While we hope these tips are informative, we are unable to answer individua");
trie.insertInTrie("while");      
trie.insertInTrie("basement");
             
                System.out.println("Enter your keywords::");
                InputStreamReader in = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(in);
String line;
TrieNode location = null;
while (true) {
line = br.readLine();
if (line.equals("Y")){
break;
}
location = trie.getLocationOfStringInTrie(line);
if (location != null){
trie.autocomplete(location);
}else {
System.out.println("No Match found for [ "+line+" ] in our data base");
}

}
       }
}

Input and Output in Eclipse console :
Enter your keywords::
bl
-blog
-blog is your best bet for a voice among the online crowd
s
-start
-start a wordpress blog or create a free website in seconds
wh
-what is autocomplete
-while
-while we hope these tips are informative, we are unable to answer individua
whi
-while
-while we hope these tips are informative, we are unable to answer individua
re
-remove
for
No Match found for [ for ] in our data base
f
-free
-free weblog publishing tool from google, for sharing text, photos and vide