Finding destination using 2D matrix


package example;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class TruckProblem {

public static void main(String[] args) {

// input 1
List<List<Integer>> area = new ArrayList<>();
area.add(Arrays.asList(1, 0, 0));
area.add(Arrays.asList(1, 0, 0));
area.add(Arrays.asList(1, 9, 1));
Integer[][] areaArray = convertListToArray(area);
// List<List<Integer>> pathArray = getRegionSize(areaArray);
int size = getBiggestRegion(areaArray);
System.out.println("path array:" + size);

// input 2
area = new ArrayList<>();
area.add(Arrays.asList(1, 0, 1));
area.add(Arrays.asList(1, 0, 1));
area.add(Arrays.asList(1, 9, 1));
areaArray = convertListToArray(area);
// List<List<Integer>> pathArray = getRegionSize(areaArray);
size = getBiggestRegion(areaArray);
System.out.println("path array:" + size);
}

static Integer[][] convertListToArray(List<List<Integer>> area) {
Integer[][] areaArray = new Integer[area.size()][];
for (int i = 0; i < area.size(); i++) {
List<Integer> list = area.get(i);
System.out.println(list);
areaArray[i] = list.toArray(new Integer[list.size()]);
}
return areaArray;
}

public static int getRegionSize(Integer[][] matrix, int row, int column) {
if (row < 0 || column < 0 || row >= matrix.length || column >= matrix[row].length) {
return 0;
}
if (matrix[row][column] == 0 || matrix[row][column] == 9) {
return 0;
}
//System.out.println(row + " " + column);
matrix[row][column] = 0;
int size = 1;

for (int r = row - 1; r <= row + 1; r++) {
for (int c = column - 1; c <= column + 1; c++) {
if (r != row || c != column) {
// System.out.println(r +" "+ c);
size += getRegionSize(matrix, r, c);
}
}
//System.out.println("*** ");
}
return size;
}

public static int getBiggestRegion(Integer[][] matrix) {

int maxRegion = 0;

for (int row = 0; row < matrix.length; row++) {
for (int column = 0; column < matrix[row].length; column++) {
if (matrix[row][column] == 1) {
int size = getRegionSize(matrix, row, column);
maxRegion = Math.max(size, maxRegion);
}
if (matrix[row][column] == 9) {
break;
}
}
}
return maxRegion;
}
}

Output:

[1, 0, 0]

[1, 0, 0]

[1, 9, 1]

path array:3

[1, 0, 1]

[1, 0, 1]

[1, 9, 1]

path array:3

finding nearest veg restaurants


package example;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

public class amazon1 {

public static void main(String[] args) {
// TODO Auto-generated method stub

List<List<Integer>> allLocations = new ArrayList<>();
allLocations.add(Arrays.asList(1,2));
allLocations.add(Arrays.asList(3,4));
allLocations.add(Arrays.asList(1,-3));
nearestVegRest(3,allLocations, 1);

List<List<Integer>> allLocations1 = new ArrayList<>();
allLocations1.add(Arrays.asList(2,4));
allLocations1.add(Arrays.asList(3,6));
allLocations1.add(Arrays.asList(2,7));
allLocations1.add(Arrays.asList(5,3));
allLocations1.add(Arrays.asList(1,8));
allLocations1.add(Arrays.asList(7,9));
nearestVegRest(6,allLocations1, 3);

}

static List<List<Integer>> nearestVegRest(int totalRests, List<List<Integer>> allLocations, int numRest)
{
TreeMap<Double,List<Integer>> map = new TreeMap<>();
List<List<Integer>> nearest = new ArrayList<>();
if(numRest <= totalRests)
{

for(int i =0; i<allLocations.size(); i++)
{
List<Integer> inner = allLocations.get(i);
double sum = 0d;

sum = Math.pow(Math.abs(inner.get(0)), 2) +  Math.pow(Math.abs(inner.get(1)), 2);
map.put(Math.sqrt(sum), allLocations.get(i));

}
System.out.println("Map:"+map);
int j = 1;
for(Map.Entry<Double, List<Integer>> ele: map.entrySet())
{

if(j <= numRest )
{
nearest.add(ele.getValue());
++j;
}
}
System.out.println("nearest:"+nearest);
}

return nearest;

}

}

output:

Map:{2.23606797749979=[1, 2], 3.1622776601683795=[1, -3], 5.0=[3, 4]}
nearest:[[1, 2]]
Map:{4.47213595499958=[2, 4], 5.830951894845301=[5, 3], 6.708203932499369=[3, 6], 7.280109889280518=[2, 7], 8.06225774829855=[1, 8], 11.40175425099138=[7, 9]}
nearest:[[2, 4], [5, 3], [3, 6]]

Program to find biggest island

package example;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class IslandProblem1 {

public static void main(String[] args) {
// TODO Auto-generated method stub
   //int[][]  matrix = int[6][7];
 
   List<List<Integer>> area = new ArrayList<>();
area.add(Arrays.asList(0,0,0,1,1,0,0));
area.add(Arrays.asList(0,1, 0, 0,1,1,0));
area.add(Arrays.asList(1,1,0,1,0,0,1));
area.add(Arrays.asList(0,0,0,0,0,1,0));
area.add(Arrays.asList(1,1,0,0,0,0,0));
area.add(Arrays.asList(0,0,0,1,0,0,0));
Integer[][] areaArray = convertListToArray(area);
int size = getBiggestRegion(areaArray);
System.out.println("Biggest Island size:" +size);
}

public static int getRegionSize(Integer[][] matrix, int row, int column)
{
if(row < 0 || column < 0 || row >= matrix.length || column >= matrix[row].length)
{
return 0;
}
if(matrix[row][column] == 0)
{
return 0;
}
//System.out.println(row + " "+ column);
matrix[row][column] = 0;
int size = 1;

for(int r = row -1; r<= row+1; r++)
{
for (int c = column -1 ; c<= column+1; c++)
{
if(r != row || c!=column)
{
//System.out.println(r +" "+ c);
size += getRegionSize(matrix, r ,c);
}
}
//System.out.println("*** ");
}
return size;

}
public static int getBiggestRegion(Integer[][] matrix)
{

int maxRegion = 0;

for(int row=0; row< matrix.length; row++)
{
for(int column= 0; column <matrix[row].length; column ++)
if (matrix[row][column] == 1)
{
int size = getRegionSize(matrix, row, column);
maxRegion = Math.max(size, maxRegion);
}
}
return maxRegion;
}

static Integer[][] convertListToArray(List<List<Integer>> area) {
Integer[][] areaArray = new Integer[area.size()][];
for (int i = 0; i < area.size(); i++) {
List<Integer> list = area.get(i);
System.out.println(list);
areaArray[i] = list.toArray(new Integer[list.size()]);
}
return areaArray;
}

}

Output: 

[0, 0, 0, 1, 1, 0, 0]

[0, 1, 0, 0, 1, 1, 0]

[1, 1, 0, 1, 0, 0, 1]

[0, 0, 0, 0, 0, 1, 0]

[1, 1, 0, 0, 0, 0, 0]

[0, 0, 0, 1, 0, 0, 0]

Biggest Island size:7

Program to find no.of  connected islands


package example;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class IslandCount {

static int islandCount = 0;

public static void main(String[] args) {

Map<Integer, List<Integer>> map = new HashMap<>();


List<List<Integer>> area = new ArrayList<>();
area.add(Arrays.asList(0, 0, 0, 1, 1, 0, 0));
area.add(Arrays.asList(0, 1, 0, 0, 1, 1, 0));
area.add(Arrays.asList(1, 1, 0, 1, 0, 0, 1));
area.add(Arrays.asList(0, 0, 0, 0, 0, 1, 0));
area.add(Arrays.asList(1, 1, 0, 0, 0, 0, 0));
area.add(Arrays.asList(0, 0, 0, 0, 0, 1, 1));
Integer[][] areaArray = convertListToArray(area);

getBiggestRegion(areaArray);
System.out.println("islandCount :" + islandCount);
}

public static int getRegionSize(Integer[][] matrix, int row, int column) {
if (row < 0 || column < 0 || row >= matrix.length || column >= matrix[row].length) {
return 0;
}
if (matrix[row][column] == 0) {
return 0;
}
//System.out.println(row + " " + column);
matrix[row][column] = 0;
int size = 1;

for (int r = row - 1; r <= row + 1; r++) {
for (int c = column - 1; c <= column + 1; c++) {
if (r != row || c != column) {
// System.out.println(r +" "+ c);
size += getRegionSize(matrix, r, c);
}
}
//System.out.println("*** ");
}
return size;

}

public static int getBiggestRegion(Integer[][] matrix) {

int maxRegion = 0;

for (int row = 0; row < matrix.length; row++) {
for (int column = 0; column < matrix[row].length; column++) {
if (matrix[row][column] == 1) {
int size = getRegionSize(matrix, row, column);
maxRegion = Math.max(size, maxRegion);
islandCount++;
}
}
}
return maxRegion;
}

static Integer[][] convertListToArray(List<List<Integer>> area) {
Integer[][] areaArray = new Integer[area.size()][];
for (int i = 0; i < area.size(); i++) {
List<Integer> list = area.get(i);
System.out.println(list);
areaArray[i] = list.toArray(new Integer[list.size()]);
}
return areaArray;
}

}

output:

[0, 0, 0, 1, 1, 0, 0]
[0, 1, 0, 0, 1, 1, 0]
[1, 1, 0, 1, 0, 0, 1]
[0, 0, 0, 0, 0, 1, 0]
[1, 1, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 1]
islandCount :4