Matrix Search – find group of connected-1s/sectors in a matrix

find length of connected cells of 1s(sector) in an matrix of 0s and 1s?
find number of islands in a matrix?
find connected sectors of a matric?
implementation of flood fill algorithm?
All these questions are same, below are the implementation details

Full source code can be downloaded from here

Consider a two-dimensional grid of cells, each of which may be empty or filled. The filled cells that are connected form a sector. Two cells are said to be connected if they are adjacent to each other horizontally, vertically or diagonally. There may be several sectors on the grid. Your job is to find the largest sector (in terms of number of cells) on the grid.

The following figure illustrates a grid with 3 sectors (the largest contains 5 cells).
grid

Problem
Write a program that determines the size of the largest sector for a given grid.

Input
The input begins with a single positive integer on a line by itself indicating the number of the cases
following, each of them as described below. This line is followed by a blank line, and there is also a blank
line between two consecutive inputs. The grid is given as a set of string, each composed of 0s and 1s.
The 1 indicates that the cell is filled and 0 indicates an empty cell. The strings should be converted into
the grid format. The largest grid that should be considered is a 25×25 grid.

Attached is the input file:
input.txt

Output
For each test case, the output must follow the description below. The outputs of two consecutive cases
will be separated by a blank line. The output is the size of the largest sector found on the grid.

Sample Input
2

11000
01100
00101
10001
01011

1011
1010

Sample Output
5
3

This solution is a recursion of depth of 8 levels :

int findMaxDepth(int[][] n, boolean[][] bool, int i, int j) {
	// Check if i, j (indexes) are within the size of array
	// Check if the cell is already traversed or not using bool array
	// Check if the cell value is 1 before counting it as part of a sector
	if(i >= 0 && i < n.length &&  				j >=0 && j < n[0].length
				&& bool[i][j] != true && n[i][j] != 0) {
		currentDepth++;

		// Mark the status of the cell for backtracking purpose
		bool[j] = true;

		// left traversal
		findMaxDepth(n, bool, i-1, j);
		// right traversal
		findMaxDepth(n, bool, i+1, j);

		// top traversal
		findMaxDepth(n, bool, i, j-1);
		// bottom traversal
		findMaxDepth(n, bool, i, j+1);

		// Top-Bottom diagnol
		// diagnol-down traversal
		findMaxDepth(n, bool, i+1, j+1);
		// diagnol-up traversal
		findMaxDepth(n, bool, i-1, j-1);

		// Bottom-Top diagnol
		// diagnol-down traversal
		findMaxDepth(n, bool, i+1, j-1);
		// diagnol-up traversal
		findMaxDepth(n, bool, i-1, j+1);
	}
	return currentDepth;
}

Full source code can be downloaded from here

Attaching the problem statement, input.txt.
counting_cell
 

Java Naming and Directory Interface (JNDI), JNDI Architecture

 

Naming Service? Is a service which allows us to store and retrieve simple objects with a unique name. It is just like one of the storage unit.

Directory Service? Is an added service on top of naming service which allows us to store and retrieve objects with some directory names (i.e, maintained into groups)

These services are implemented by different vendors where each vendor provides their own APIs and protocols to interact with theirs naming and directory services.
If any java application wants to use these services, it has to plugin to any of the vendor provided implementation, then

  • Application becomes vendor specific
  • While deploying we need to know about the vendor and its service API
  • While migrating the application from one vendor to another we need to change the code base of the application

To avoid these problems we want a standard abstraction through which a java application can interact with any vendor implemented Naming and Directory Service. To meet the above requirement SUN has released standard API providing solution to the above mentioned problems. These standards have been released under JNDI (Java Naming and Directory Service)

JNDI is an standard abstraction which allows any java application to interact with any vendor implemented naming and Directory Service.

In this case if java application wants to interact with any naming registry it just requires to prepare a request in JNDI format using JNDI API i.e, request is explained and submitted to JNDI API classes where JNDI API uses the information given by the java application and locates the SPI implementation and initializes it.
JNDI API dispatches the request to the SPI implementation through JNDI SPI.

SPI implementation converts the request and interact with the respective registry to process the request, collects the response convert it into the JNDI format and return it.
JNDI API returns response to the java application.

JNDI API
javax.naming.Context
Is an interface given under JNDI specification. Declared with methods required to read, insert, update and remove the objects like lookup, bind, rebind, unbind, list

This interface should be implemented by the vendors as part of SPI implementation.

javax.naming.InitialContext
Is a non-abstract class implementing Context interface given under JNDI specification. It implements wrapper pattern, it wraps one context implementation instance (i.e, instance of context interface implementation class given by third party vendor)
This is given to simplify the process of locating and initializing SPI implementation objects. i.e, it separates logic required to locate and initiaze SPI implementation objects from java objects.

Using JNDI API to connect to the naming registry

  • Set the required properties like
    a. Name: Context.INITIAL_CONTEXT_FACTORY
    Value: should be the qualified class name of the implementation class of javax.naming.spi.InitialContextFactory interface
    Example: weblogic.jndi.WLInitialContextFactory is the implementation class name of javax.naming.spi.InitialContextFactory. This allows us to interact with weblogic naming registry
    b. Name: Context.PROVIDER_URL
    Value: should be the url pointing to the naming registry
    Example: t3:\\localhost:7001 : points to weblogic naming registry running on the local machine on 7001 port.
    These properties can be set into the system properties into hashtable
  • Create an instance of InitialContext (IC) where it has following constructors
    a. IC as no arguments: In this case it gets the properties from the system props object
    b. IC(Hashtable ht): It gets the properties from hashtable
    Note: The first property given under the step1 is mandatory and if it is not found, IC object will not be created and it throws NamingException describing NoInitialContextFoundException

Step 1:

Hastable ht = new Hashtable();
ht.put(Context.INITIAL_CONTEXT_FACTORY,  “weblogic.jndi.WLInitialContextFactory”);
ht.put(Context.PROVIDER_URL, “t3:\\localhost:7001”);

//Here t3 is weblogic specific protocol
InitialContext ic = new InitialContext(ht);

Step 2:

System.setProperty(Context. INITIAL_CONTEXT_FACTORY,  “weblogic.jndi.WLInitialContextFactory”);
System.setProperty(Context.PROVIDER_URL, “t3:\\localhost:7001”);
InitialContext ic = new InitialContext(ht);

The above steps connects to the naming registry, now we can use IC object reference and interact with the naming registry to get the object and store the object.

 

Mawazo

Mostly technology with occasional sprinkling of other random thoughts

amintabar

Amir Amintabar's personal page

101 Books

Reading my way through Time Magazine's 100 Greatest Novels since 1923 (plus Ulysses)

Seek, Plunnge and more...

My words, my world...

ARRM Foundation

Do not wait for leaders; do it alone, person to person - Mother Teresa

Executive Management

An unexamined life is not worth living – Socrates

javaproffesionals

A topnotch WordPress.com site

thehandwritinganalyst

Just another WordPress.com site

coding algorithms

"An approximate answer to the right problem is worth a good deal more than an exact answer to an approximate problem." -- John Tukey