Write a program in Java: Read in file containing a square matrix of N rows by N

Question

Write a program in Java:

Read in file containing a square matrix of N rows by N columns of integers as discussed in classThe first line of the file contains a single value specifying the "size" of N for the rest of the grid.

Eg., if the first line contains "10" then the remainder of the lines form a 10x10 matrix.

NOTE: The input size could be anything from 10x10 or larger. The "safe assumption" is that the data will fit in memory.

The remainder of the file contains rows and columns of ascending (in each direction) values.

The values are "space delimited".

There may be duplicate values in the grid.

A small sample is illustrated below.

The program should accept the following as "command line parameters"

The path/name of the input file.

The "target value" to search for in the matrix.

NOTE: There is no OUTPUT file in this case... just writing the screen (stdout) is sufficient.

To the screen, display the total number of comparisons needed to find (or not find) the given element:
Using a "brute force" linear technique

"Exhaustive Search": Row-By-Row, Column-by-Column

Using the "optimized" search technique as discussed in class.

As a reminder, this was achieved by starting in the lower-left (or even upper-right) corner.

Using a "Recursive divide an conquer technique".

The grid is recursively divided into 4 quadrants, where only one can be safely discarded. The remaining 3 quadrantsare recursively searched.

Sample c: empinput.txt:

Explanation / Answer

import java.util.*;
import java.lang.*;
import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;

public class Searching {
public static int[][] create2DIntMatrixFromFile(String filename) throws Exception {
int[][] matrix = null;

// If included in an Eclipse project.
// InputStream stream = ClassLoader.getSystemResourceAsStream(filename);
//BufferedReader buffer = new BufferedReader(new InputStreamReader(stream));

// If in the same directory - Probably in your case...
// Just comment out the 2 lines above this and uncomment the line
// that follows.
BufferedReader buffer = new BufferedReader(new FileReader(filename));

String line;
int size = buffer.readline();
int row=0;
while ((line = buffer.readLine()) != null) {
String[] vals = line.trim().split("\s+");

// Lazy instantiation.
if (matrix == null) {
matrix = new int[size][size];
}

for (int col = 0; col < size; col++) {
matrix[row][col] = Integer.parseInt(vals[col]);
}

row++;
}

return matrix;
}

void search1(int [][]matrix,int size,int x)

{

int count=0,comp=0;

for(int i=0;i<size;i++)

{ for(int j=0;j<=size;j++)

if(matrix[i][j]==x) count++;

comp++;

}

System.out.println(count+" found in" + comp + "comparisons using a linear search");

}

void search2(int [][]matrix,int size,int x)

{ //Assuming elements in each row and column are already sorted

int count=0,comp=0;

int i=size-1,j=0; //Starting from lower left
int j=0;
while(i>=0 && j<size-1)
if(matrix[i][j]>x)
i--;
else if (matrix[i][j]<x)
j++;
if(matrix[i][j]==x)
{ count++; j++; }
comp++;

}

System.out.println(count+" found in" + comp + "comparisons using a optimized search");

}

// A divide and conquer method to search a given key in mat[]
// in rows from fromRow to toRow and columns from fromCol to
// toCol assuming matrix is sorted rowwise and columnwise
public static void search(int[][] mat, int fromRow, int toRow,
int fromCol, int toCol, int key)
{
// Find middle and compare with middle
int i = fromRow + (toRow-fromRow )/2;
int j = fromCol + (toCol-fromCol )/2;
int count=0,comp=0;
if (mat[i][j] == key) // If key is present at middle
{ count++; comp++; System.out.println(count+" found in" + comp + "comparisons using a recursion search"); }
else
{
// right-up quarter of matrix is searched in all cases.
// Provided it is different from current call
if (i!=toRow || j!=fromCol)
search(mat,fromRow,i,j,toCol,key);

// Special case for iteration with 1*2 matrix
// mat[i][j] and mat[i][j+1] are only two elements.
// So just check second element
if (fromRow == toRow && fromCol + 1 == toCol)
if (mat[fromRow][toCol] == key)
count++;

// If middle key is lesser then search lower horizontal
// matrix and right hand side matrix
if (mat[i][j] < key)
{
// search lower horizontal if such matrix exists
if (i+1<=toRow)
search(mat, i+1, toRow, fromCol, toCol, key);
}

// If middle key is greater then search left vertical
// matrix and right hand side matrix
else
{
// search left vertical if such matrix exists
if (j-1>=fromCol)
search(mat, fromRow, toRow, fromCol, j-1, key);
} comp++;

}
}

public static void main(String[] args)

{

BufferedReader buffer = new BufferedReader(new FileReader(args[0]));
int size = buffer.readline();
int[] matrix = new int[100][100];
matrix = create2DIntMatrixFromFile(args[0]);

search1(matrix, size,args[1]);

search2(matrix,size,args[1]);

search3(matrix,0,size, 0,size,args[1]);

return 0;

}

}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.