CODEWITHSUNDEEP
javaarrays
cashmoneytf
cashmoneytf

Reputation: 1

Checking to see if two 2D boolean arrays are equal at a given interval: Java

I have two 2d boolean arrays, the smaller array (shape) is going over the larger array (world).

I am having trouble to find a method to find out when the smaller array can "fit" into the larger one.

When I run the code it either just goes through the larger array, never stopping, or stops after one step (incorrectly). 

public void solve() {
    ArrayList<Boolean> worldList=new ArrayList<>();
    ArrayList<Boolean> shapeList=new ArrayList<>();

    for (int i = 0; i < world.length; i++) {
        for (int k = 0; k < world[i].length; k++) {
            worldList.add(world[i][k]);
            display(i, k, Orientation.ROTATE_NONE);
            for (int j = 0; j < shape.length; j++) {
                for (int l = 0; l < shape[j].length; l++) {
                    shapeList.add(shape[j][l]);
                    if(shapeList.equals(worldList)) {
                        return;
                    }
                }
            }
        }
    }
}

Upvotes: 0

Views: 78

Answers (2)

b.GHILAS
b.GHILAS

Reputation: 2313

You can find the row and column of fitting like this

public void fit() {
    int h = world.length - shape.length;
    int w = world[0].length - shape[0].length;

    for (int i = 0; i <= h; i++) {
        for (int k = 0; k <= w; k++) {
            boolean found = true;
            for (int j = 0; j < shape.length && found; j++) {
                for (int l = 0; l < shape[j].length && found; l++) {
                    if (shape[j][l] != world[i + j][k + l]) 
                        found = false;
                }
            }

            if (found) {
                //Your shape list fit the world list at starting index (i, k)
                //You can for example save the i, k variable in instance variable
                //Or return then as an object for further use
                return;
            }
        }
    }

Upvotes: 1

sleepToken
sleepToken

Reputation: 1847

A good place to start with a problem like this is brute force for the simplest case. So, for each index in the world list, just check to see if every following index of world and shapes match.

Notice we only iterate to world.size()-shapes.size(), because naturally if shapes is longer than the portion of world we haven't checked, it won't fit.

import java.util.ArrayList;

public class Test {
    ArrayList<Boolean> world = new ArrayList<>();
    ArrayList<Boolean> shapes = new ArrayList<>();

    public static void main(String[] args) {
        new Work();
    }

    public Test() {
        world.add(true);
        world.add(false);
        world.add(false);
        world.add(true);

        shapes.add(false);
        shapes.add(true);

        // Arraylists initialized to these values:
        //   world:     T F F T
        //   shapes:    F T

        System.out.println(getFitIndex());
    }

    /**
     * Get the index of the fit, -1 if it won't fit.
     * @return
     */
    public int getFitIndex() {
        for (int w = 0; w <= world.size()-shapes.size(); w++) {
            boolean fits = true;

            for (int s = 0; s < shapes.size(); s++) {
                System.out.println("Compare shapes[" + s + "] and world["+ (w+s) + "]: " +
                        shapes.get(s).equals(world.get(w+s)));

                if (!shapes.get(s).equals(world.get(w+s))) fits = false;
            }

            System.out.println();

            if (fits) return w;
        }

        return -1;
    }
}

When we run this code, we get a value of 2 printed to the console, since shapes does indeed fit inside world, starting at world[2].

Upvotes: 1

Related Questions