Constructing a 4×4 grid of words

Question

I have an ArrayList which contains Strings with a size of 1000. I am looping through that ArrayList and finding words and trying to form a square from them. For example as follows:

C A R D
A R E A
R E A R
D A R T

The square must match left to right and top to bottom. So first left to right word (card) must match first top to bottom (card) and so on. The list has [voes, rose, soon, odds] and so on, a 1000 of them all of length 4.

I am looping through them 1 by 1. So take 'voes' first, loop through remaining 999, find the first word starting with 'o', i store it as second word (example: odds) and move on to next loop.

This will give me for example:

voes
odds

loop 999 times again. first letter to start with 'e' and its 3rd letter is 'd' store that as 3rd name and move on to 4th loop.

This will give me for example:

voes
odds
eddo

loop 999 times again. Similar check for 4th word. And lets say I cant find any word that meets the condition. Break out of loop, go on top and replace the first word to the second word in the list and do it all over again.

I have managed to get it working but it involves a lot of nested looping. If I am reading this right, this is O(n^4). Is there a more efficient way to do this.

void makeWord(ArrayList<String> arr){

    String first, second, third, fourth;
    for (int i = 0; i < arr.size(); i++) {

        first = arr.get(i);

        for (int j = 0; j < arr.size(); j++) {
            if(first.substring(1,2).equals(arr.get(j).substring(0,1)) &&
                    (!first.equals(arr.get(j)))){
                second = arr.get(j);
            }
            else {
                second = "    ";
            }

            if (!second.trim().isEmpty()) {
                for (int k = 0; k < arr.size(); k++) {
                    if (first.substring(2, 3).equals(arr.get(k).substring(0, 1)) &&
                            second.substring(2, 3).equals(arr.get(k).substring(1, 2)) &&
                            (!first.equals(arr.get(k)) && (!second.equals(arr.get(k))))) {
                        third = arr.get(k);
                    } else {
                        third = "    ";
                    }

                    if (!third.trim().isEmpty()) {

                        for (int m = 0; m < arr.size(); m++) {
                            if(first.substring(3,4).equals(arr.get(m).substring(0,1)) &&
                                    second.substring(3,4).equals(arr.get(m).substring(1,2))&&
                                    third.substring(3,4).equals(arr.get(m).substring(2,3)) &&
                                    (!first.equals(arr.get(m)) && (!second.equals(arr.get(m))))){
                                fourth = arr.get(m);
                            }
                            else {
                                fourth = "    ";
                            }

                            if (!(fourth.trim().isEmpty())) {
                                System.out.println(first);
                                System.out.println(second);
                                System.out.println(third);
                                System.out.println(fourth);
                                System.out.println(" ");
                            }
                        }
                    }
                }
            }
        }
    }
}

Answer 1

I'm not sure if there's a faster way of doing it. However, your current code can be improved.

Enhanced for loop

Your loop are written using the traditional index:

String first;
for (int i = 0; i < arr.size(); i++) {
    first = arr.get(i);
    // ...

When you don't need the index, it is better to use the enhanced for loop. This has the advantage that it makes the code more compact and easier to read:

for (String first : arr) {
     // ...

You are also calling multiple times arr.get(j) with the index instead of storing the result in a local variable. Using the enhanced for loop solves that directly.

String comparisons

Right now, you are comparing each String together with

if(first.substring(1,2).equals(arr.get(j).substring(0,1)) &&
    (!first.equals(arr.get(j)))){

There are a couple of comments here:

• This is very hard to read: it is unclear what the code is doing ;
• This is split in two lines and has a lot of parentheses which doesn't help
• Each line is "compact" so it's hard to see what is actually happening.

To rewrite that, we should remember that what we're trying to do here: test whether the 2nd character of the 1st string is the same as the 1st character of the 2nd string. So, instead of using substring, let's use charAt which directly returns the character at the given index. The 2nd character of the first String is first.charAt(1); the 1st charcter of the second String is second.charAt(0). As such, we could have:

if (!first.equals(second) && first.charAt(1) == second.charAt(0)) {
    // ...
}

Note the added spaces before the curly braces, between the operators and after the if statement, it also contributes to clarity.

Bizarre default condition

When the word currently considered is not a property fit, you are dping

else {
    second = "    ";
}

if (!second.trim().isEmpty()) {
    // ...
}

You are explicitely setting the String to whitespaces, only to trim it afterwards. This is a bit awkward.

What you want to do here is to continue when you reach an unwanted word. So you could have instead:

for (String first : arr) {
    for (String second : arr) {
        if (second.equals(first) || second.charAt(0) != first.charAt(1)) {
            continue;
        }
        for (String third : arr) {
            if (third.equals(first) || third.equals(second) || 
                first.charAt(2) != third.charAt(0) || second.charAt(2) != third.charAt(1)) {
                continue;
            }
            for (String fourth : arr) {
                if (fourth.equals(first) || fourth.equals(second) || fourth.equals(third) ||
                    first.charAt(3) != fourth.charAt(0) || second.charAt(3) != fourth.charAt(1) || third.charAt(3) != fourth.charAt(2)) {
                    continue;
                }

but now we're back to a mess: this is hard to read. However, it gives us insight into how can we do it better.

What we want is the following: we have a list of already found words (first and second for example); with that, we want to continue when the third is incorrect. What makes it incorrect is:

• either it is equal to one of the previous found word
• its characters do not match with the previously found words

So we can make a method of that!

Factoring common logic

private static boolean isIncorrect(String word, String... others) {
    boolean alreadyFound = Arrays.stream(others).anyMatch(word::equals);
    boolean notMatchedChars = 
        IntStream.range(0, others.length)
                 .anyMatch(i -> word.charAt(i) != others[i].charAt(others.length));
    return alreadyFound || notMatchedChars;
}

This method is split in two (and uses Java 8 idioms but the logic would be the same without it). It takes as parameter a word to test and a vararg of the currently found words.

• The first test checks whether any of the currently found words others are equal to the tested word.
• The second test checks whether the characters are correct. If we have 3 currently found words then
  • the 1st character of the word must be equal to the 3rd character of the first word;
  • the 2nd character of the word must be equal to the 3rd character of the second word;
  • the 3rd character of the word must be equal to the 3rd character of the third word;

With that method, we can refactor our code to

void makeWord(List<String> arr) {
    for (String first : arr) {
        for (String second : arr) {
            if (isIncorrect(second, first)) {
                continue;
            }
            for (String third : arr) {
                if (isIncorrect(third, first, second)) {
                    continue;
                }
                for (String fourth : arr) {
                    if (isIncorrect(fourth, first, second, third)) {
                        continue;
                    }
                    System.out.println(first);
                    System.out.println(second);
                    System.out.println(third);
                    System.out.println(fourth);
                    System.out.println(" ");
                }
            }
        }
    }
}

which is very clean, although surely O(n⁴).

Answer 2

Minimum scope

    String first, second, third, fourth;
    for (int i = 0; i < arr.size(); i++) {

        first = arr.get(i);

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

In general in Java (and most programming languages), you want to declare your variables at the smallest scope possible.

    for (int i = 0; i < arr.size(); i++) {

        String first = arr.get(i);

        for (int j = 0; j < arr.size(); j++) {
            String second;

Note that I'm not arguing to retain this over the for each form. I'm just pointing out the advantages of minimal scope. In particular, it is easier to see where the variable is declared and used if those two things happen close together.

There is some overhead from declaring a variable, so you might think that you shouldn't do that in a loop. However, in most languages, the compiler will only declare the variable once per loop, not once per iteration.

Prefer interfaces as types

void makeWord(ArrayList<String> arr){

Here you have the type as an ArrayList, but you never use functionality specific to that implementation. So instead use the interface as the type.

void makeWordGrid(List<String> words) {

Now you can change from ArrayList to any other List implementation without changing this method at all.

I also changed the rather generic arr to words, as I find that more readable. And I changed MakeWord to MakeWordGrid as I find that more descriptive.

Improving the algorithm

Note that you know the first letter of the second, third, and fourth words once you know the first word. So your interior loops can start with more limited scope. Starting from @Tunaki's version:

    for (String first : words) {
        for (String second : limitByInitial(words, first.charAt(1), letterPositions)) {
            if (isIncorrect(second, first)) {
                continue;
            }

            for (String third : limitByInitial(words, first.charAt(2), letterPositions)) {
                if (isIncorrect(third, first, second)) {
                    continue;
                }

                for (String fourth : limitByInitial(words, first.charAt(3), letterPositions)) {

then define

List<String> limitByInitial(List<String> words, char initial, char[] letterPositions) {
    int index = initial - 'a';
    return words.subList(letterPositions[index], letterPositions[index + 1]);
}

This will still be \$O(n^4)\$ in theory, but it will be faster in practice if there are a significant number of words.

You might notice that once you know the second word, you know the first two letters. And with the third word, you know three. The thing is though that the added overhead costs more as you increase the number of letters. So it may not be worth implementing additional limits. Note that the first one reduces us from a thousand words to about forty on average. Reducing it to an average of about one and a half might be helpful? But would reducing it to almost zero help?