11
\$\begingroup\$

I'm rather new to Java and to algorithms in general. I implemented the so called Two-pass algorithm, and want to know if there are improvements to my way of implementing it. What it does is it takes a matrix of ones and zeros and replaces all ones by labels. All ones that are connected should be labeled with the same label. Each such component should have a unique label. The end result can be visualized by replacing each label with a color, like this:

result

I followed as closely as I could the pseudo-code available in this section of the Wikipedia article. But are there improvements?

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;

public class MatrixComponents {

    public int[][] labeledMatrix;

    public MatrixComponents(int[][] matrix) {
        ArrayList<ArrayList<Integer>> linked = new ArrayList<ArrayList<Integer>>();
        int[][] labels = new int[matrix.length][matrix[0].length];

        int NextLabel = 0;

        //First pass
        for(int i=0; i<matrix.length; i++) {
            for( int j=0; j<matrix.length; j++) {
                labels[i][j] = 0;
            }
        }

        for(int i=0; i<matrix.length; i++) {
            for(int j=0; j<matrix[0].length; j++) {
                if(matrix[i][j] != 0) {

                    //Labels of neighbors
                    ArrayList<Integer> neighbors = new ArrayList<Integer>();
                    for(int ni=-1; ni<=1; ni++) {
                        for(int nj=-1; nj<=1; nj++) {
                            if(i+ni<0 || j+nj<0 || i+ni>labels.length-1 || j+nj>labels[0].length-1) {
                                continue;
                            }
                            else {
                                if(i+ni == 0 && i+nj == 0) continue;
                                if(labels[i+ni][j+nj] != 0) neighbors.add(labels[i+ni][j+nj]);
                            }
                        }
                    }

                    if(neighbors.size() == 0) {
                        ArrayList<Integer> tempArrayList = new ArrayList<Integer>();
                        tempArrayList.add(NextLabel);
                        linked.add(NextLabel, tempArrayList);
                        labels[i][j] = NextLabel;
                        NextLabel++;
                    }
                    else {

                        labels[i][j]=1000*1000;
                        for(int neighbor : neighbors) {
                            if(neighbor < labels[i][j]) labels[i][j] = neighbor;
                        }

                        for(int neighbor : neighbors) {
                            linked.set(neighbor,union(linked.get(neighbor),neighbors));
                        }
                    }
                }

            }
        }

        //Second pass
        for(int i=0; i<matrix.length; i++) {
            for(int j=0; j<matrix[0].length; j++) {
                ArrayList<Integer> EquivalentLabels = linked.get(labels[i][j]);
                labels[i][j]=1000*1000;
                for(int label : EquivalentLabels) {
                    if(label < labels[i][j]) labels[i][j]=label;
                }
            }
        }

        labeledMatrix = labels;
    }

    //union: http://stackoverflow.com/questions/5283047/intersection-and-union-of-arraylists-in-java
    public <T> ArrayList<T> union(ArrayList<T> list1, ArrayList<T> list2) {
        Set<T> set = new HashSet<T>();

        set.addAll(list1);
        set.addAll(list2);

        return new ArrayList<T>(set);
    }

    public int[][] getLabeledMatrix() {
        return labeledMatrix;
    }

    public static void main(String[] args) {
        int[][] matrix = {{0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1,
                0, 0, 0, 0, 0, 0, 0}, {1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0,
                1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1}, {0, 1, 0, 0, 0, 0, 0,
                1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                0}, {0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0,
                0, 1, 0, 0, 1, 0, 0, 1, 0}, {0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0,
                1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1}, {0, 0, 0, 0, 1,
                0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0,
                0, 0}, {0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0,
                0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0,
                0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1}, {0, 1, 0, 0,
                1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1,
                0, 0, 1, 0}, {0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0,
                0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0}, {1, 1, 1, 0, 1, 1, 0, 1, 1, 1,
                1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1}, {0, 0,
                0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0,
                1, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0,
                0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0}, {1, 1, 0, 0, 1, 1, 0, 1, 0,
                0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1}, {0,
                0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1,
                0, 0, 0, 0, 0, 1, 0}, {0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0,
                0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0}, {0, 1, 1, 1, 1, 0, 0,
                1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1,
                0}, {0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0,
                0, 1, 0, 0, 1, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0,
                1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0}, {0, 1, 1, 0, 1,
                1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1,
                1, 0}, {0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0,
                0, 0, 1, 0, 0, 1, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0,
                0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0}, {0, 1, 0, 1,
                1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1,
                1, 1, 1, 1}, {0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0,
                0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0}, {0, 0, 0, 0, 1, 0, 0, 1, 0, 0,
                1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 1,
                1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0,
                1, 1, 1, 1, 1}, {0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1,
                0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 0, 0, 0, 0,
                0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0}, {1,
                1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1,
                0, 1, 1, 0, 1, 1, 0}, {0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0,
                0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};

        MatrixComponents matrixComponents = new MatrixComponents(matrix);
        int[][] newMatrix = matrixComponents.getLabeledMatrix();

        System.out.println("{");
        for(int i=0; i<newMatrix.length; i++) {
            System.out.print("{");
            for(int j=0; j<newMatrix[0].length; j++) {
                if(j != newMatrix[0].length-1)
                    System.out.print(newMatrix[i][j]+", ");
                else
                    System.out.print(newMatrix[i][j]);
            }
            if(i != newMatrix.length-1)
                System.out.println("},");
            else
                System.out.println("}");
        }
        System.out.print("}");
    }
}

The test in the main method prints the array. I don't know of any quick way of visualizing it in Java, but if it would be visualized it would look like my image above.

\$\endgroup\$
1
  • \$\begingroup\$ Technically initialization of the matrix doesn't count as a pass, so I would move //First pass to the beginning of the following for loop. \$\endgroup\$
    – Neil
    Jun 26, 2014 at 8:50

4 Answers 4

Reset to default
15
\$\begingroup\$

Declare by interface and not implementation

Instead of

ArrayList<ArrayList<Integer>> linked = new ArrayList<ArrayList<Integer>>();

use:

List<List<Integer>> linked = new ArrayList<List<Integer>>();

Or, if you're using Java 7+:

List<List<Integer>> linked = new ArrayList<>();

Edit: When looking at your code a bit more, with all the union method and stuff going on, I wonder if it perhaps should be List<Set<Integer>> right from the start, so that you could use

linked.get(neighbor).addAll(neighbors);

instead of what you currently do:

linked.set(neighbor,union(linked.get(neighbor),neighbors));

Algorithmically speaking, this part:

//First pass
for(int i=0; i<matrix.length; i++) {
    for( int j=0; j<matrix.length; j++) {
        labels[i][j] = 0;
    }
}

Is a) Not part of the first pass. b) Totally unnecessary as the labels array is filled with zeros already. c) Buggy if matrix is not square.

int[][] matrix = {{0, 0, 0, 0, 1, ...

I'd highly recommend reading from a file instead of hardcoding into the code!

Your constructor and your main method is doing way too many things, break up the code into additional methods.

Some methods can include:

  • Read matrix from file / some input / code
  • One (or more) methods for doing the "first pass" (you can put the 2d outer loop in one method, which can call another method)
  • One method for the "second pass"
  • One method for the output
public int[][] labeledMatrix;

Don't use public fields like that, that one should be private. It's good to restrict the visibility as much as possible.

i and j vs. x and y

Sometimes 2d arrays are indexed as matrix[x][y] and sometimes as matrix[y][x], to make it clear which version you're using, don't use i and j. I really don't like those variable names when using 2d arrays.

It is a good practice to always use braces, even for one-liners: (Even I get told this from time to time!)

if(i+ni == 0 && i+nj == 0) continue;
if(labels[i+ni][j+nj] != 0) neighbors.add(labels[i+ni][j+nj]);

Is changed to:

if (i + ni == 0 && i + nj == 0) {
    continue;
}
if (labels[i + ni][j + nj] != 0) {
    neighbors.add(labels[i + ni][j + nj]);
}

Remember the comments about the naming though.

For your drawing an image plans, you should read up on Creating and Drawing to an Image and the chapter that follows it Writing/Saving an Image. You can use the Graphics2D object as shown in the first link to draw rectangles on the image.

if(neighbors.size() == 0) {

is the same as

if (neighbors.isEmpty()) {
\$\endgroup\$
0
11
\$\begingroup\$

White-Space

You really need some white-space in your code. This is the first thing that will help to read your code easily. I have not read a lot your since it's really to read those kind of exppresions : 

if(i+ni<0 || j+nj<0 || i+ni>labels.length-1 || j+nj>labels[0].length-1)

With some white-spaces, it will be easier to easily see what's going on.

if(i + ni < 0 || j + nj < 0 || i + ni > labels.length - 1 || j + nj > labels[0].length - 1)

It could look like it take a lot more of space, but it's worth it. Imagineiftosavespacewewouldallwritelikethis (This is just an exaggeration, this is not that much of a problem).

Variables names

I know i and j are common names for counter in a for loop, but you can give relevant names too. Why would you not follow the "suggestion" from the wiki and use row and column, this would be much more relevant to your context.

Reading i + ni < 0 versus row + neighborsPosition, I prefer the second option.

In Java, variable names are camelCase so EquivalentLabels and NextLabel should be equivalentLabels and nextLabel. (Hint look at the coloration syntax in your question, it identify those variables like a class).

Functions

You could separate your code in smaller functions. A good example would be : 

                ArrayList<Integer> neighbors = new ArrayList<Integer>();
                for(int ni=-1; ni<=1; ni++) {
                    for(int nj=-1; nj<=1; nj++) {
                        if(i+ni<0 || j+nj<0 || i+ni>labels.length-1 || j+nj>labels[0].length-1) {
                            continue;
                        }
                        else {
                            if(i+ni == 0 && i+nj == 0) continue;
                            if(labels[i+ni][j+nj] != 0) neighbors.add(labels[i+ni][j+nj]);
                        }
                    }
                }

This clearly could be a function constructNeighborsList. It would not change your code much but would help read your code.

\$\endgroup\$
3
  • \$\begingroup\$ I'm looking at your algo, I will edit if I find something to say about it. \$\endgroup\$
    – Marc-Andre
    Jun 25, 2014 at 18:37
  • 1
    \$\begingroup\$ I would go a bit further with the methods. For example, i+ni<0 || j+nj<0 || i+ni>labels.length-1 || j+nj>labels[0].length-1 could be extracted to method on its own, improving readability and promoting single purpose programming. \$\endgroup\$
    – Travis
    Jun 26, 2014 at 19:52
  • \$\begingroup\$ @Travis I almost suggest it, but I think he's not there yet. I agree with you though and I do it myself when the condition is complex. I might edit it when I'll be back home! \$\endgroup\$
    – Marc-Andre
    Jun 26, 2014 at 19:59
10
\$\begingroup\$

Just a small little comment about your array initializer:

int[][] matrix = {{0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1,
        0, 0, 0, 0, 0, 0, 0}, {1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0,
        1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1}, {0, 1, 0, 0, 0, 0, 0,
        1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0}, {0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0,
        0, 1, 0, 0, 1, 0, 0, 1, 0}, {0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0,
        1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1}, {0, 0, 0, 0, 1,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0,
        0, 0}, {0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0,
        0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1}, {0, 1, 0, 0,
        1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1,
        0, 0, 1, 0}, {0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0,
        0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0}, {1, 1, 1, 0, 1, 1, 0, 1, 1, 1,
        1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1}, {0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0,
        1, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0,
        0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0}, {1, 1, 0, 0, 1, 1, 0, 1, 0,
        0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1}, {0,
        0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1,
        0, 0, 0, 0, 0, 1, 0}, {0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0,
        0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0}, {0, 1, 1, 1, 1, 0, 0,
        1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1,
        0}, {0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0,
        0, 1, 0, 0, 1, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0,
        1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0}, {0, 1, 1, 0, 1,
        1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1,
        1, 0}, {0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0,
        0, 0, 1, 0, 0, 1, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0,
        0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0}, {0, 1, 0, 1,
        1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1,
        1, 1, 1, 1}, {0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0}, {0, 0, 0, 0, 1, 0, 0, 1, 0, 0,
        1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 1,
        1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0,
        1, 1, 1, 1, 1}, {0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1,
        0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0}, {1,
        1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1,
        0, 1, 1, 0, 1, 1, 0}, {0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};

Would be much easier to read parse, and to eventually maintain, if you put line breaks after each element, lining up each item:

int[][] matrix = {
       {0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0}, 
       {1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1}, 
       {0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
       {0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0}, 
       {0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1}, 
       {0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0}, 
       {0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
       {1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1}, 
       {0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0},
       {0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0}, 
       {1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1}, 
       {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0}, 
       {0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0}, 
       {1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1}, 
       {0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0}, 
       {0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0}, 
       {0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0}, 
       {0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0},
       {0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0}, 
       {0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0}, 
       {0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0}, 
       {0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0}, 
       {0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1}, 
       {0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0}, 
       {0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
       {0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1}, 
       {0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0}, 
       {0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0}, 
       {1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0}, 
       {0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
};

Now whether or not it's a good idea to put data in your code like this, ... there has to be a better way... I'll leave the actual review to the guys. Cheers!

\$\endgroup\$
5
  • \$\begingroup\$ Did you have to copy-paste that whole matrix into your answer? :) \$\endgroup\$
    – Simon Forsberg
    Jun 25, 2014 at 18:45
  • 8
    \$\begingroup\$ What a troll - "just a small comment"... proceeds to paste two gigantic matrices. \$\endgroup\$
    – corsiKa
    Jun 25, 2014 at 19:36
  • 3
    \$\begingroup\$ +1. "A picture tells more than thousand words." "Show, don't tell" etc. I think's a perfectly valid answer, thanks. \$\endgroup\$
    – user36070
    Jun 25, 2014 at 21:34
  • 2
    \$\begingroup\$ @Pickett awesome! thanks! Welcome to the CR voters' club :D (looks like there's heavy caching on these pages though), feel free to spend up to 40/day, this site needs more voters! :) \$\endgroup\$
    – Mathieu Guindon
    Jun 25, 2014 at 22:02
  • 1
    \$\begingroup\$ This was bugging me too. I checked all the answers first to see if anyone had mentioned it yet. And alas someone did. +1 \$\endgroup\$
    – Cruncher
    Jun 26, 2014 at 17:02
5
\$\begingroup\$

Some small tips:

  • Avoid calculations in a loop. Change 1000*1000 to a constant:

    public static final int MILLION = 1000 * 1000;

  • Integer arrays have default value of zero when created, so your "first pass" could be arrested.

\$\endgroup\$
6
  • 3
    \$\begingroup\$ Much like no one would write public static final int ONE = 1, perhaps a better name for MILLION would be the significance of what it represents. I would recommend Integer.Max_Value instead, as MILLION just seems arbitrary. \$\endgroup\$
    – Matthew
    Jun 25, 2014 at 18:46
  • \$\begingroup\$ Yeah, I agree with you. I did not understood the meaning by my self. \$\endgroup\$
    – Ilya Gazman
    Jun 25, 2014 at 20:13
  • 3
    \$\begingroup\$ "Avoid calculations in a loop" is good advice in general, but in this case 1000 * 1000 is a compile-time constant and there's no performance implication. It's still a good idea for readability. \$\endgroup\$
    – Chris Hayes
    Jun 26, 2014 at 3:31
  • \$\begingroup\$ @ChrisHayes I agree with you in general, how ever I think it works slightly different. It's not a compile constant but it will optimized with Java jet. Of curse it doesn't meter in this case. \$\endgroup\$
    – Ilya Gazman
    Jun 26, 2014 at 11:49
  • \$\begingroup\$ @Ilya_Gazman It absolutely is a compile-time constant, per your own link. In JLS terms, it's two primitive literals composed with the operator *, which is explicitly called out as a constant expression. \$\endgroup\$
    – Chris Hayes
    Jun 26, 2014 at 17:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.