Прохожу все тест-кейсы из комментов, но валидатор не принимает

Вопрос по задаче

Решен

Прошу даже не подсказки по решению, а пример тест-кейса, который моя программа не проходит. То, что код неоптимальный и запутанный, я знаю, принципиально решал сам без подсказок. Вот такие тесты корректно отрабатывает (дефолтный из задачи, разумеется, тоже): поиск "home" в двух вариантах

int[][] crossword = new int[][]{
                {'f', 'd', 'e', 'r', 'l', 'k'},
                {'u', 's', 'a', 'm', 'e', 'o'},
                {'l', 'n', 'g', 'r', 'o', 'v'},
                {'m', 'l', 'e', 'm', 'o', 'h'},
                {'p', 'o', 'e', 'e', 'j', 'j'}
        };

Результат: home - (5, 3) - (2, 0) home - (5, 3) - (2, 3) same - (1, 1) - (4, 1) поиск 8 вариантов "one"

int[][] crossword = new int[][]{
                {'f', 'e', 'e', 'e', 'l', 'e'},
                {'u', 's', 'n', 'n', 'n', 'o'},
                {'l', 'e', 'n', 'o', 'n', 'e'},
                {'m', 'm', 'n', 'n', 'n', 'h'},
                {'p', 'e', 'e', 'e', 'j', 'e'},
        };

Результат: one - (3, 2) - (1, 0) one - (3, 2) - (3, 0) one - (3, 2) - (5, 0) one - (3, 2) - (1, 2) one - (3, 2) - (5, 2) one - (3, 2) - (1, 4) one - (3, 2) - (3, 4) one - (3, 2) - (5, 4) поиск pmlpml

int[][] crossword = new int[][]{
                {'f', 'd', 'e', 'r', 'l', 'k', 'd', 'e', 'r', 'l', 'k'},
                {'u', 's', 'a', 'm', 'e', 'o', 's', 'a', 'm', 'e', 'o'},
                {'l', 'n', 'g', 'r', 'o', 'v', 'n', 'g', 'r', 'o', 'v'},
                {'m', 'l', 'p', 'r', 'r', 'h', 'l', 'p', 'r', 'r', 'h'},
                {'p', 'o', 'e', 'e', 'j', 'j', 'o', 'e', 'e', 'j', 'j'},
                {'l', 'n', 'g', 'r', 'o', 'v', 'n', 'g', 'r', 'o', 'v'},
                {'m', 'l', 'p', 'r', 'r', 'h', 'l', 'p', 'r', 'r', 'h'},
                {'p', 'o', 'e', 'e', 'j', 'j', 'o', 'e', 'e', 'j', 'j'}
        };

Результат: pmlpml - (0, 7) - (0, 2)

1. Дан двумерный массив, который содержит буквы английского алфавита в нижнем регистре.
2. Метод detectAllWords должен найти все слова из words в массиве crossword.
3. Элемент(startX, startY) должен соответствовать первой букве слова, элемент(endX, endY) - последней.
text - это само слово, располагается между начальным и конечным элементами
4. Все слова есть в массиве.
5. Слова могут быть расположены горизонтально, вертикально и по диагонали как в нормальном, так и в обратном порядке.
6. Метод main не участвует в тестировании.

Требования:

В классе Solution должен существовать метод detectAllWords.
В классе Solution должен существовать статический класс Word.
Класс Solution не должен содержать статические поля.
Метод detectAllWords должен быть статическим.
Метод detectAllWords должен быть публичным.
Метод detectAllWords должен возвращать список всех слов в кроссворде (согласно условию задачи).

package com.javarush.task.task20.task2027; import java.util.ArrayList; import java.util.List; /* Кроссворд */ public class Solution { public static void main(String[] args) { int[][] crossword = 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(crossword, "home", "same"); /* Ожидаемый результат home - (5, 3) - (2, 0) same - (1, 1) - (4, 1) */ } public static List<Word> detectAllWords(int[][] crossword, String... words) { List<Word> allWords = new ArrayList<>(); for (String w : words) { ArrayList<Symbol> symbList = new ArrayList<>(); char[] symbols = w.toCharArray(); for (int c = 0; c < symbols.length; c++) { for (int i = 0; i < crossword.length; i++) { for (int q = 0; q < crossword[i].length; q++) { if (crossword[i][q] == (int) symbols[c]) { symbList.add(new Symbol((int) symbols[c], i, q, c)); } } } } for (Symbol symbol : symbList) { if (symbol.numberInWord == 0) { for (Symbol symbol2 : symbList) { if (symbol2.numberInWord == 1 && symbol2.xCount >= symbol.xCount - 1 && symbol2.xCount <= symbol.xCount + 1 && symbol2.yCount >= symbol.yCount - 1 && symbol2.yCount <= symbol.yCount + 1) { ArrayList<Symbol> word = new ArrayList<>(); word.add(symbol); word.add(symbol2); int countLetter = 2; if (symbol2.xCount < symbol.xCount && symbol2.yCount == symbol.yCount) { // проверяем север for (Symbol symbol3 : symbList) { if (symbol3.numberInWord == countLetter && symbol3.xCount == word.get(countLetter - 1).xCount - 1 && symbol3.yCount == word.get(countLetter - 1).yCount) { word.add(symbol3); countLetter++; } } } if (symbol2.xCount > symbol.xCount && symbol2.yCount == symbol.yCount) { // проверяем юг for (Symbol symbol3 : symbList) { if (symbol3.numberInWord == countLetter && symbol3.xCount == word.get(countLetter - 1).xCount + 1 && symbol3.yCount == word.get(countLetter - 1).yCount) { word.add(symbol3); countLetter++; } } } if (symbol2.xCount == symbol.xCount && symbol2.yCount < symbol.yCount) { // проверяем запад for (Symbol symbol3 : symbList) { if (symbol3.numberInWord == countLetter && symbol3.xCount == word.get(countLetter - 1).xCount && symbol3.yCount == word.get(countLetter - 1).yCount - 1) { word.add(symbol3); countLetter++; } } } if (symbol2.xCount == symbol.xCount && symbol2.yCount > symbol.yCount) { // проверяем восток for (Symbol symbol3 : symbList) { if (symbol3.numberInWord == countLetter && symbol3.xCount == word.get(countLetter - 1).xCount && symbol3.yCount == word.get(countLetter - 1).yCount + 1) { word.add(symbol3); countLetter++; } } } if (symbol2.xCount < symbol.xCount && symbol2.yCount > symbol.yCount) { // проверяем северо-восток for (Symbol symbol3 : symbList) { if (symbol3.numberInWord == countLetter && symbol3.xCount == word.get(countLetter - 1).xCount - 1 && symbol3.yCount == word.get(countLetter - 1).yCount + 1) { word.add(symbol3); countLetter++; } } } if (symbol2.xCount < symbol.xCount && symbol2.yCount < symbol.yCount) { // проверяем северо-запад for (Symbol symbol3 : symbList) { if (symbol3.numberInWord == countLetter && symbol3.xCount == word.get(countLetter - 1).xCount - 1 && symbol3.yCount == word.get(countLetter - 1).yCount - 1) { word.add(symbol3); countLetter++; } } } if (symbol2.xCount > symbol.xCount && symbol2.yCount < symbol.yCount) { // проверяем юго-запад for (Symbol symbol3 : symbList) { if (symbol3.numberInWord == countLetter && symbol3.xCount == word.get(countLetter - 1).xCount + 1 && symbol3.yCount == word.get(countLetter - 1).yCount - 1) { word.add(symbol3); countLetter++; } } } if (symbol2.xCount > symbol.xCount && symbol2.yCount > symbol.yCount) { // проверяем юго-восток for (Symbol symbol3 : symbList) { if (symbol3.numberInWord == countLetter && symbol3.xCount == symbol2.xCount + 1 && symbol3.yCount == symbol2.yCount + 1) { word.add(symbol3); countLetter++; } } } StringBuilder builder = new StringBuilder(); for (Symbol s : word) { builder.append((char) s.unicode); } String text = builder.toString(); //System.out.println(text); for (String myword : words) { if (myword.equals(text)) { Word newWord = new Word(text); newWord.startX = word.get(0).yCount; newWord.startY = word.get(0).xCount; newWord.endX = word.get(word.size() - 1).yCount; newWord.endY = word.get(word.size() - 1).xCount; allWords.add(newWord); } } } } } } } //for (Word word : allWords) { // System.out.println(word); //} return allWords; } public static class Symbol { private int unicode; private int xCount; private int yCount; private int numberInWord; public Symbol(int unicode, int xCount, int yCount, int numberInWord) { this.unicode = unicode; this.xCount = xCount; this.yCount = yCount; this.numberInWord = numberInWord; } public int getxCount() { return this.xCount; } public int getyCount() { return this.yCount; } @Override public String toString() { return String.format("%d - %d, %d - %d", unicode, xCount, yCount, numberInWord); } } 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); } } } /* for (Symbol symbol : symbList) { ArrayList<Symbol> word = new ArrayList<>(); if (symbol.numberInWord == 0) { word.add(symbol); for (Symbol symbol2 : symbList) { if (symbol2.numberInWord == 1 && symbol2.xCount >= symbol.xCount - 1 && symbol2.xCount <= symbol.xCount + 1 && symbol2.yCount >= symbol.yCount - 1 && symbol2.yCount <= symbol.yCount + 1) { word.add(symbol2); int countLetter = 2; if (symbol2.xCount < symbol.xCount && symbol2.yCount == symbol.yCount) { // проверяем север for (Symbol symbol3 : symbList) { if (symbol3.numberInWord == countLetter && symbol3.xCount == word.get(countLetter - 1).xCount - 1 && symbol3.yCount == word.get(countLetter - 1).yCount) { word.add(symbol3); countLetter++; } } } if (symbol2.xCount > symbol.xCount && symbol2.yCount == symbol.yCount) { // проверяем юг for (Symbol symbol3 : symbList) { if (symbol3.numberInWord == countLetter && symbol3.xCount == word.get(countLetter - 1).xCount + 1 && symbol3.yCount == word.get(countLetter - 1).yCount) { word.add(symbol3); countLetter++; } } } if (symbol2.xCount == symbol.xCount && symbol2.yCount < symbol.yCount) { // проверяем запад for (Symbol symbol3 : symbList) { if (symbol3.numberInWord == countLetter && symbol3.xCount == word.get(countLetter - 1).xCount && symbol3.yCount == word.get(countLetter - 1).yCount - 1) { word.add(symbol3); countLetter++; } } } if (symbol2.xCount == symbol.xCount && symbol2.yCount > symbol.yCount) { // проверяем восток for (Symbol symbol3 : symbList) { if (symbol3.numberInWord == countLetter && symbol3.xCount == word.get(countLetter - 1).xCount && symbol3.yCount == word.get(countLetter - 1).yCount + 1) { word.add(symbol3); countLetter++; } } } if (symbol2.xCount < symbol.xCount && symbol2.yCount > symbol.yCount) { // проверяем северо-восток for (Symbol symbol3 : symbList) { if (symbol3.numberInWord == countLetter && symbol3.xCount == word.get(countLetter - 1).xCount - 1 && symbol3.yCount == word.get(countLetter - 1).yCount + 1) { word.add(symbol3); countLetter++; } } } if (symbol2.xCount < symbol.xCount && symbol2.yCount < symbol.yCount) { // проверяем северо-запад for (Symbol symbol3 : symbList) { if (symbol3.numberInWord == countLetter && symbol3.xCount == word.get(countLetter - 1).xCount - 1 && symbol3.yCount == word.get(countLetter - 1).yCount - 1) { word.add(symbol3); countLetter++; } } } if (symbol2.xCount > symbol.xCount && symbol2.yCount < symbol.yCount) { // проверяем юго-запад for (Symbol symbol3 : symbList) { if (symbol3.numberInWord == countLetter && symbol3.xCount == word.get(countLetter - 1).xCount + 1 && symbol3.yCount == word.get(countLetter - 1).yCount - 1) { word.add(symbol3); countLetter++; } } } if (symbol2.xCount > symbol.xCount && symbol2.yCount > symbol.yCount) { // проверяем юго-восток for (Symbol symbol3 : symbList) { if (symbol3.numberInWord == countLetter && symbol3.xCount == symbol2.xCount + 1 && symbol3.yCount == symbol2.yCount + 1) { word.add(symbol3); countLetter++; } } } } } StringBuilder builder = new StringBuilder(); for (Symbol s : word) { builder.append((char) s.unicode); } String text = builder.toString(); System.out.println(text); for (String myword : words) { if (myword.equals(text)) { Word newWord = new Word(text); newWord.startX = word.get(0).yCount; newWord.startY = word.get(0).xCount; newWord.endX = word.get(word.size() - 1).yCount; newWord.endY = word.get(word.size() - 1).xCount; allWords.add(newWord); } } } } } int[][] crossword = new int[][]{ {'f', 'd', 'e', 'r', 'l', 'k'}, {'u', 's', 'a', 'm', 'e', 'o'}, {'l', 'a', 'g', 'r', 'o', 'v'}, {'m', 'm', 'e', 'm', 'o', 'h'}, {'p', 'e', 'e', 'e', 'j', 'j'} int[][] crossword = 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'} }; int[][] crossword = new int[][]{ {'f', 'd', 'e', 'r', 'l', 'k', 'd', 'e', 'r', 'l', 'k'}, {'u', 's', 'a', 'm', 'e', 'o', 's', 'a', 'm', 'e', 'o'}, {'l', 'n', 'g', 'r', 'o', 'v', 'n', 'g', 'r', 'o', 'v'}, {'m', 'l', 'p', 'r', 'r', 'h', 'l', 'p', 'r', 'r', 'h'}, {'p', 'o', 'e', 'e', 'j', 'j', 'o', 'e', 'e', 'j', 'j'}, {'l', 'n', 'g', 'r', 'o', 'v', 'n', 'g', 'r', 'o', 'v'}, {'m', 'l', 'p', 'r', 'r', 'h', 'l', 'p', 'r', 'r', 'h'}, {'p', 'o', 'e', 'e', 'j', 'j', 'o', 'e', 'e', 'j', 'j'} }; */

Комментарии (7)

популярные
новые
старые

Для того, чтобы оставить комментарий Вы должны авторизоваться

Сергей Козырев

Уровень 30

26 июня 2019, 14:04

полезный

Для будущих поколений несколько нетривиальных тест-кейсов (не встречал их в ответах на другие вопросы): 1. Алгоритм должен обрабатывать слова из 1 буквы 2. Алгоритм должен обрабатывать слова, являющиеся частями других проверяемых слов - например, "ho", "hom" и "home" И не пытайтеся понять мой код выше, я почти вызвал им Сатану. Я специально сяду и причешу его, чтоб можно было людям показать - мне опытные в джаве друзья обещали заценить оптимальность решения и корректность оформления, но сюда я итог, ессно, выкладывать не буду:)

Justinian Judge в Mega City One

Master

26 июня 2019, 10:06

полезный

Слишком глубоко зашел как по мне, я запустил код и просто проверил по одному слову основные направление, и одно из них зафейлилось сходу. Я мог бы сразу указать какое, но тестирование своего кода это важный скилл, такие ошибки ты должен сам находить в течении минуты. Дам только подсказку - на досуге почитай про тестирование, разработчику тоже полезно. Есть одна из тем - тестирование на пограничных значениях. Если метод на вход принимает допустим числа от 0 до 100, то наибольшая вероятность встретить ошибку именно там где 0 и 100, а не 50. Причем ошибку можно легко найти и другим способом (найдешь, напишу каким ) нашел, даже получилось быстро исправить, заработало. Правда пройдет ли валидацию, проверишь.

Сергей Козырев

Уровень 30

26 июня 2019, 10:43

Я понял, что не проходят слова длиной в 1 символ, эту ошибку исправил, но валидацию не проходит, и даже понятно, почему: вот для такого тест-кейса:

int[][] crossword = new int[][]{
                {'f', 'd', 'e', 'r', 'l', 'k'},
                {'u', 's', 'o', 's', 'o', 's'},
                {'l', 'o', 'o', 'o', 'o', 'o'},
                {'m', 's', 'o', 's', 'o', 's'},
                {'p', 'o', 'e', 'e', 'j', 'j'}
        };
        detectAllWords(crossword, "so", "sos");

В результатах дублируется результат so - (1, 3) - (1, 4). Почему - пока не понимаю. Хотя я уже вообще ничего не понимаю))

Justinian Judge в Mega City One

Master

26 июня 2019, 13:11

полезный

на один символ кстати даже не знаю нужно ли, мой алгоритм работает, но я специально не делал. Не знаю в каком виде алгоритм сейчас, но то что было изначально. Еще раз по пограничным значениям. В данном случае имеется ввиду проверка маленьких слов, допустим на два символа, и больших слов, от одного края до второго края. Одно из направлений у тебя работает на словах сугубо до 3 символов включительно, 4 и более оно уже не воспринимает. Еще уточню, что это диагональ. Но что интересно, если ты пролистаешь код отвечающий за направления - 8 блоков копипаста, который идет подряд, то можно увидеть что один блок существенно отличается от остальных семи! :) Это очень легко увидеть, недокопипастил наверное :)

Сергей Козырев

Уровень 30

26 июня 2019, 13:58

решение

Спасибо! Вот буквально 5 минут назад я решил. Это было жёстко, но давненько я не чувствовал такого прилива дофамина. Все перечисленные тобой ошибки нашёл сам + обработал случаи, когда одно слово является частью второго - например, "ho" и "home". Мой алгоритм их дублировал.

Justinian Judge в Mega City One

Master

26 июня 2019, 14:23

эт хорошо, поздравляю! За тебя мы всегда решить успеем, но когда решаешь сам это бесценный опыт, наше дело, присмотреть и подставить плечо когда нам кажется это уместно )

Сергей Козырев

Уровень 30

26 июня 2019, 07:07

И вот такой тоже прохожу, тест на 22 "sos":

int[][] crossword = new int[][]{
        {'f', 'd', 'e', 'r', 'l', 'k'},
        {'u', 's', 'o', 's', 'o', 's'},
        {'l', 'o', 'o', 'o', 'o', 'o'},
        {'m', 's', 'o', 's', 'o', 's'},
        {'p', 'o', 'e', 'e', 'j', 'j'}
};

Результат: sos - (1, 1) - (3, 1) sos - (1, 1) - (1, 3) sos - (1, 1) - (3, 3) sos - (3, 1) - (1, 1) sos - (3, 1) - (5, 1) sos - (3, 1) - (1, 3) sos - (3, 1) - (3, 3) sos - (3, 1) - (5, 3) sos - (5, 1) - (3, 1) sos - (5, 1) - (3, 3) sos - (5, 1) - (5, 3) sos - (1, 3) - (1, 1) sos - (1, 3) - (3, 1) sos - (1, 3) - (3, 3) sos - (3, 3) - (1, 1) sos - (3, 3) - (3, 1) sos - (3, 3) - (5, 1) sos - (3, 3) - (1, 3) sos - (3, 3) - (5, 3) sos - (5, 3) - (3, 1) sos - (5, 3) - (5, 1) sos - (5, 3) - (3, 3)