Searching through arrays

Question

Suppose I have a 6 by 6 int array randomly filled with 1s and 2s. I want to print the number of 1s appearing near at a specific point (x,y).

I know how to do it by writing 8 if loops and for each if loop i need to make sure it is not out of bound. I feel this method is extremely inefficient and inferior. Can anyone enlighten me a creative approach?

Answer 1

Here is an approach utilizing Java8 Streams/Predicates.

• Start with the X,Y Point
• Generate the List of points surrounding the center to test -- using the predefined BOX
• Apply a predicate function to validate that the point you want to test is within the bounds of your grid.
• If so, get the value at that location and test if it is 1 [or apply any predicate here].

By defining the static logic upfront the code really just boils down to

Stream<Point> results=
         BOX.stream()
            .map(p -> Point.of(p.X + centerPoint.X, p.Y + centerPoint.Y))
            .filter(p -> inBounds.test(p) && a6x6.get(p.X).get(p.Y) == 1);

I am sure the same logic could be applied with a few more functions in Java7 and you could use this for any grid size.

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.function.Predicate;
import java.util.stream.Stream;

public class Main {

    public static class Point {
        public final Integer X;
        public final Integer Y;
        public Point(Integer X, Integer Y){
            this.X = X;
            this.Y = Y;
        }
        public static Point of(Integer x, Integer y){
            return new Point(x,y);
        }

        @Override
        public String toString() {
            return String.format("[%s,%s]", X, Y);
        }
    }

    //Bounds of grid
    private static final Point MIN = Point.of(0,0);
    private static final Point MAX = Point.of(5,5);

    /**
     *  [-1,-1][-1,0][-1,1]
     *  [ 0,-1][ _,_][ 0,1]
     *  [ 1,-1][ 1,0][ 1,1]
     **/
    private static final List<Point> BOX = new ArrayList<Point>(){{
        add(Point.of(-1,-1));
        add(Point.of(-1,0));
        add(Point.of(-1,1));
        add(Point.of(0,-1));
        add(Point.of(0,1));
        add(Point.of(1,-1));
        add(Point.of(1,0));
        add(Point.of(1,1));
    }};

    public static final Predicate<Point> inBounds =
            p -> {
                if (p.X < MIN.X || p.Y < MIN.Y) return false;
                if (p.X > MAX.X || p.Y > MAX.Y) return false;
                return true;
    };

    public static void main(String[] args) {
        final Random rand = new Random();
        final List<List<Integer>> a6x6 = new ArrayList<List<Integer>>(){{
            for(int i=0;i<6;i++)
                add(new ArrayList<Integer>(){{
                    for(int i=0;i<6;i++)
                        add(rand.nextInt(2) + 1);
                }});
        }};

        final Point centerPoint = Point.of(2,2);

        System.out.println("Grid = ");
        a6x6.forEach(System.out::println);
        System.out.println("Point = " + centerPoint.toString());

        Stream<Point> results=
                BOX.stream()
                        .map(p -> Point.of(p.X + centerPoint.X, p.Y + centerPoint.Y))
                        .filter(p -> inBounds.test(p) && a6x6.get(p.X).get(p.Y) == 1);

        System.out.println("Results = ");
        results.forEach(System.out::println);
    }

}

results:

Grid =
[2, 2, 1, 2, 1, 1]
[1, 1, 1, 1, 1, 2]
[1, 2, 1, 1, 2, 1]
[2, 1, 1, 2, 1, 2]
[1, 1, 1, 1, 1, 1]
[1, 2, 2, 2, 1, 2]
Point = [2,2]
Results =
[1,1]
[1,2]
[1,3]
[2,3]
[3,1]
[3,2]

Answer 2

Here is my "creative approach" :-)

public class CountOnes {

int[][] space = new int[8][8]; //Notice this is 8x8 instead of 6x6

public CountOnes() {

    //Adding value 100 all around the 6x6 array
    for (int i = 0; i < 8; i++) {
        space[0][i] = 100;
        space[i][0] = 100;
        space[i][7] = 100;
        space[7][i] = 100;
    }
}

/**
 * Just print out the matrix
 */
public void showSpace() {
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            System.out.print("[" + space[i][j] + "]");
        }
        System.out.println();
    }
}

/**
 * 
 * @param x horizontal position in range [0-5]
 * @param y vertical position in range [0-5]
 * @param val 1 or 2
 */
public void insertValueAt(int x, int y, int val) {
    //Should throw an exception if val != 1 and val != 2 or x and y are out of bounds [0 - 5]
    space[x + 1][y + 1] = val; //Convert coordinates before inserting in 8x8 matrix
}

public int numberOfOnesAroundPosition(int x, int y) {
    //Should throw exception if x and y are out of bounds [0 - 5]
    int tot = 0;

    //add up all values around (x,y)
    for (int i = -1; i < 2; i++) {
        for (int j = -1; j < 2; j++) {
            tot += space[x + 1 + i][y + 1 + j];//convert coordinates adding 1 because we are in 8x8
        }
    }
    tot -= space[x + 1][y + 1];//remove value of (x,y) because it was added in previous loop

    return 2 * (8 - (tot / 100)) - (tot % 100); //the formula
}

/**
 * @param args
 */
public static void main(String[] args) {
    //simple test case
    CountOnes count = new CountOnes();

    for (int i = 0; i < 6; i++) {
        for (int j = 0; j < 6; j++) {
            count.insertValueAt(i, j, 1);
        }
    }

    count.insertValueAt(2, 2, 2);

    count.showSpace();
    for (int i = 0; i < 6; i++) {
        for (int j = 0; j < 6; j++) {
            System.out.println("[" + i + "," + j + "] => "
                    + count.numberOfOnesAroundPosition(i, j));
        }
    }

}

}

Answer 3

The two loop solution suggested by Jigar Joshi is probably optimal. You simply have one loop start at max(0, x-bound) and end at min(5, x+bound) and the other one start at max(0, y-bound) and end at min(5, y+bound).

EDIT: Some code to aid in comprehension

for(int i = Math.max(0, x-bound); i<Math.min(5, x+bound); i++){
    for(int j = Math.max(0, y-bound); j<Math.min(5, y+bound); j++){
        //Your check/counter here
    }
}

The max and min functions are being used to check the bounds. Simply, no matter how small x-bound is, the max will make it at minimum 0. (The same applies for the upper bound but in reverse)