CodeGym/Help with Java Tasks/Why is it displaying all of the elements when I have inst...

Level 41

15.03.2021
509views
13comments

Why is it displaying all of the elements when I have instructed it to skip duplicates?

Question about the task

Under discussion

In line 41 I have added : if (wordsFound.contains(word)) continue; Even if I move this line after 38 it still prints the same result. I don't understand why. When I run the program, this is the result:

same - (1, 1) - (3, 4)
same - (1, 1) - (2, 4)
same - (1, 1) - (4, 1)
same - (1, 1) - (2, 0)
home - (5, 3) - (3, 4)
home - (5, 3) - (2, 4)
home - (5, 3) - (4, 1)
home - (5, 3) - (2, 0)

Process finished with exit code 0

1. We have a two-dimensional array that contains lowercase letters.
2. The detectAllWords method must find all the words in the wordSearch array.
3. The element(startX, startY) must correspond to the first letter of the word, while the element(endX, endY) corresponds to the last letter.
text is the word itself, located between the start and end elements
4. All the words are in the array.
5. The words can be arranged horizontally, vertically, and diagonally, both forward and backward.
6. The main method is not tested.

Requirements:

The Solution class must have a detectAllWords method.
The Solution class must contain a static Word class.
The Solution class must not have static fields.
The detectAllWords method must be static.
The detectAllWords method must be public.
The detectAllWords method should return the list of all words in the word search (according to the task conditions).

package com.codegym.task.task20.task2027; import java.util.ArrayList; import java.util.List; /* Word search */ public class Solution { public static void main(String[] args) { int[][] wordSearch = new int[][]{ {'f', 'd', 'e', 'r', 'l', 'k'}, {'u', 's', 'a', 'm', 'e', 'o'}, {'l', 'n', 'g', 'r', 'o', 'v'}, {'m', 'l', 'p', 'r', 'r', 'h'}, {'p', 'o', 'e', 'e', 'j', 'j'} }; //detectAllWords(wordSearch, "fuck", "ship"); for (Word word : detectAllWords(wordSearch, "home", "same")) { System.out.println(word.toString()); } /* Expected result home - (5, 3) - (2, 0) same - (1, 1) - (4, 1) */ } public static List<Word> detectAllWords(int[][] wordSearch, String... words) { List<Word> wordsFound = new ArrayList<>(); for (String word : words){ char[] wordLetters = word.toCharArray(); int firstLetter = wordLetters[0]; int lastLetter = wordLetters[wordLetters.length-1]; for (int i = 0; i < wordSearch.length; i++){ for (int j = 0; j < wordSearch[i].length; j++){ if (wordsFound.contains(word)) continue; if (wordSearch[i][j] == firstLetter) { for (int k = 0; k < wordSearch.length; k++){ for (int l = 0; l < wordSearch[k].length; l++) { if (wordSearch[k][l] == lastLetter){ wordsFound.add(0, new Word(word)); wordsFound.get(0).setStartPoint(j, i); wordsFound.get(0).setEndPoint(l, k); } } } } } } } return wordsFound; } public static class Word { private String text; private int startX; private int startY; private int endX; private int endY; public Word(String text) { this.text = text; } public void setStartPoint(int i, int j) { startX = i; startY = j; } public void setEndPoint(int i, int j) { endX = i; endY = j; } @Override public String toString() { return String.format("%s - (%d, %d) - (%d, %d)", text, startX, startY, endX, endY); } } }

Comments (13)

Popular
New
Old

You must be signed in to leave a comment

Nouser

Level 36 , Germany

15 March 2021, 10:09

useful

wordsFound is of type Word. If you compare that to a string (word) then that condition never will be true.

Andrei

Level 41

15 March 2021, 10:42

Nice catch, thanks! I added a getter for the name in the word class and modified line 41 to compare the texts. I also changed its position to after line 44 yet the results are not correct. I am wondering why aren't they added to the list in order of appearance?

if ( !wordsFound.isEmpty() && wordsFound.get(0).getName().equals(word)) continue;

Running the program returns:

same - (1, 1) - (2, 0)
home - (5, 3) - (2, 0)

Andrei

Level 41

15 March 2021, 10:42

public static List<Word> detectAllWords(int[][] wordSearch, String... words) {
    List<Word> wordsFound = new ArrayList<>();

    for (String word : words){
        char[] wordLetters = word.toCharArray();
        int firstLetter = wordLetters[0];
        int lastLetter = wordLetters[wordLetters.length-1];
        for (int i = 0; i < wordSearch.length; i++){
            for (int j = 0; j < wordSearch[i].length; j++){
                if (wordSearch[i][j] == firstLetter) {
                    for (int k = 0; k < wordSearch.length; k++){
                        for (int l = 0; l < wordSearch[k].length; l++) {
                            if (wordSearch[k][l] == lastLetter){
                                if ( !wordsFound.isEmpty() && wordsFound.get(0).getName().equals(word)) continue;
                                wordsFound.add(0, new Word(word));
                                wordsFound.get(0).setStartPoint(j, i);
                                wordsFound.get(0).setEndPoint(l, k);
                            }
                        }
                    }
                }
            }
        }
    }
    return wordsFound;
}

public static class Word {
    private String text;
    private int startX;
    private int startY;
    private int endX;
    private int endY;

    public Word(String text) {
        this.text = text;
    }

    private String getName(){
        return this.text;
    }

    public void setStartPoint(int i, int j) {
        startX = i;
        startY = j;
    }

Andrei

Level 41

15 March 2021, 10:43

Wait, I might have read the conditions wrong. I will double check, brb.

Nouser

Level 36 , Germany

15 March 2021, 11:07

just as a side note... with that approach your program won't work if you are looking for eg. home and that is two times in the array. And I doubt (without having tested it) that the k, l loops will work the way you believe it. What I did... beginning is the same as you do, searching for the first letter. If I have found one, I test for the second letter, and the second letter may be every neighbor field. If one of the neighbor fields matches the second letter of the search word, then you can proceed in that direction and compare the remaining letters.

Andrei

Level 41

15 March 2021, 11:53

oh god.. I just realized what you said and that I also have to look for the letters inside of the word, not just the start and end letter. And I have to search in every direction for the next letter...

Andrei

Level 41

15 March 2021, 13:46

Can you please tell me if I am going in the right direction? Also, I don't know how to handle the ArrayOutOfBounds error so it skips it if it is at the end of the array.

public static List<Word> detectAllWords(int[][] wordSearch, String... words) {
        List<Word> wordsFound = new ArrayList<>();

        for (String word : words){
            char[] wordLetters = word.toCharArray();
            int firstLetter = wordLetters[0];
            int lastLetter = wordLetters[wordLetters.length-1];
            for (int i = 0; i < wordSearch.length; i++){
                for (int j = 0; j < wordSearch[i].length; j++) {
                    if (wordSearch[i][j] == firstLetter) {
                       //if the word is just 2 letters
                       if (wordSearch[i][j + 1] == wordLetters[1] && wordLetters.length == 2) {
                            wordsFound.add(0, new Word(word));
                            wordsFound.get(0).setStartPoint(j, i);
                            wordsFound.get(0).setEndPoint(j + 1, i);
                        }
                    }
                    int countInnerLoop = 1;

                    //this checks if the right neighbouring letter in the array is the same as the next
                    //letter in the char[] and if the size of the word is at least count+1
                    if (wordSearch[i][j + 1] == wordLetters[1]) {
                        while (wordSearch[i][j + countInnerLoop + 1] == wordLetters[countInnerLoop + 1]) {
                            countInnerLoop++;
                        }
                        wordsFound.add(0, new Word(word));
                        wordsFound.get(0).setStartPoint(j, i);
                        wordsFound.get(0).setEndPoint(wordLetters[countInnerLoop + 1], i);
                    }
                }
            }
        }
        return wordsFound;
    }

Nouser

Level 36 , Germany

15 March 2021, 20:49

useful

that way you'd need to write code for each possible direction... so nearly the same code 8 times. Basically I did the following:

loop over y width
    loop over x width
        if y|x pos == first char of search word
            loop dy -1 to 1
               loop dx -1 to 1 (check if pos == 0|0 then continue)
                   add dy|dx to y|x
                      check if resulting position is in words array (y >= 0 && < size and x >= 0 && < size)
                          check if position matches second letter
                               yes -> go further into that direction and check the rest

and I didn't like the -1 to 1 loops so I've first added two static arrays

int[] yDir = new int[]{-1, -1, -1,  0, 0,  1, 1, 1};
int[] xDir = new int[]{-1,  0,  1, -1, 1, -1, 0, 1};

then I just needed one loop 0 to eg. yDir.length but I remember that task didn't allow static variables so I had to move the arrays inside the method. So now I'd code it like I initially suggested.

Andrei

Level 41

16 March 2021, 09:18

Thanks, I'll see what I can do because I don't understand your algorithm logic yet.

Nouser

Level 36 , Germany

16 March 2021, 09:27

when you found the first character of the serach word you start again two nested loops. One that adds values to the x position of the found character, and the other to the y position. if both of those loops start from -1 and end at 1 then this gives: dx|dy -1|-1 0|-1 1|-1 -1|0 0|0 1|0 -1|1 0|1 1|1 if you add these values to the first char position, then you have all second letter positions! Now test, if these positions are in the matrix, if yes, get the value from the matrix and compare to the second letter. If it matches, then you know the direction (eg. -1|0). Go further into that direction and compare to the letters of your serch word. If you found a word, add it to the list.

Andrei

Level 41

19 March 2021, 07:59

Thanks, I have tried for the past few days to understand it and your algorithm but I haven't managed so far. I have worked on a partial solution by myself and I completed the rest from the mentor solution.

Nouser

Level 36 , Germany

19 March 2021, 08:46

If you're interested in it I can send you solutions for both of these approaches. Unfortunately I do not know the mentors solution and have no clue if mine is just a repetition of that ;)

Andrei

Level 41

19 March 2021, 09:35

Yes please, I am curious to see if I understand it better this way. The mentor solution was similar to what I was going with, but taking the whole line from the matrix and checking if it contains the word. Rinse and repeat for each possible direction.