Решил в лоб путем перебора всех вариантов, но валидатор не принимает.

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

Обсуждается

8 методов - по числу вариантов расположения слова относительно первой буквы слова (вверх (от первой буквы), вниз, влево, вправо и по варианты по диагоналям). Проверил разные варианты слов. Все верно пишет в список и выводит в консоль. Не могу понять почему не принимается валидатором. Либо лыжи не едут, либо мой глаз уже замылился. Код конечно получился длинный, зато читаемый на мой взгляд.

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'}
        };
        List<Word> listResult = detectAllWords(crossword, "home", "same", "masu", "meo", "nu", "npe");
        /*
Ожидаемый результат
home - (5, 3) - (2, 0)
same - (1, 1) - (4, 1)
         */
        for (Word x : listResult) {
            System.out.println(x);
        }
    }

    public static List<Word> detectAllWords(int[][] crossword, String... words) {
        List<Word> list = new ArrayList<>();
        for (String wordElement : words) {
            char[] wordToChar = wordElement.toCharArray();
            for (int y = 0; y < 5; y++) {
                for (int x = 0; x < 6; x++) {
                    findPattern(x, y, wordToChar, crossword, list);
                }
            }
        }
        return list;
    }

    public static Word findPattern(int x1, int y1, char[] wordToChar, int[][] crossword, List<Word> list) {
        Word objResult = null;
        if ((char) crossword[y1][x1] != wordToChar[0] || wordToChar.length == 1) return null;
        if ((char) crossword[y1][x1] == wordToChar[0]) {
            objResult = findPatternUp(x1, y1, wordToChar, crossword);
            if (objResult != null) list.add(objResult);
            objResult = findPatternDown(x1, y1, wordToChar, crossword);
            if (objResult != null) list.add(objResult);
            objResult = findPatternLeft(x1, y1, wordToChar, crossword);
            if (objResult != null) list.add(objResult);
            objResult = findPatternRight(x1, y1, wordToChar, crossword);
            if (objResult != null) list.add(objResult);
            objResult = findPatternLeftUp(x1, y1, wordToChar, crossword);
            if (objResult != null) list.add(objResult);
            objResult = findPatternLeftDown(x1, y1, wordToChar, crossword);
            if (objResult != null) list.add(objResult);
            objResult= findPatternRightUp(x1, y1, wordToChar, crossword);
            if (objResult != null) list.add(objResult);
            objResult = findPatternRightDown(x1, y1, wordToChar, crossword);
            if (objResult != null) list.add(objResult);
        }
        return null;
    }

    public static Word findPatternUp(int x2, int y2, char[] wordToChar, int[][] crossword ) {
        Word objResult = null;
        int lengthWord = wordToChar.length;
        int endX = x2;
        int endY = y2 - lengthWord + 1;
        int startX = x2;
        int startY = y2;
        if (endY < 0) return objResult;
        char endSymbolWord = wordToChar[lengthWord - 1];

        if (endSymbolWord == (char) crossword[endY][endX]) {
            for (int i = 1; i < lengthWord - 1; i++) {
                if (wordToChar[i] != (char) crossword[--y2][x2]) return objResult;
            }
            objResult = new Word(new String(wordToChar));
            objResult.setStartPoint(startX, startY);
            objResult.setEndPoint(endX, endY);
            return objResult;
        } else return objResult;
    }

    public static Word findPatternDown(int x3, int y3, char[] wordToChar, int[][] crossword ) {
        Word objResult = null;
        int lengthWord = wordToChar.length;
        int endX = x3;
        int endY = y3 + lengthWord - 1;
        int startX = x3;
        int startY = y3;
        if (endY > 4) return objResult;
        char endSymbolWord = wordToChar[lengthWord - 1];

        if (endSymbolWord == (char) crossword[endY][endX]) {
            for (int i = 1; i < lengthWord - 1; i++) {
                if (wordToChar[i] != (char) crossword[++y3][x3]) return objResult;
            }
            objResult = new Word(new String(wordToChar));
            objResult.setStartPoint(startX, startY);
            objResult.setEndPoint(endX, endY);
            return objResult;
        } else return objResult;
    }

    public static Word findPatternLeft(int x4, int y4, char[] wordToChar, int[][] crossword ) {
        Word objResult = null;
        int lengthWord = wordToChar.length;
        int endX = x4 - lengthWord + 1;
        int endY = y4;
        if (endX < 0) return objResult;
        int startX = x4;
        int startY = y4;
        char endSymbolWord = wordToChar[lengthWord - 1];

        if (endSymbolWord == (char) crossword[endY][endX]) {
            for (int i = 1; i < lengthWord - 1; i++) {
                if (wordToChar[i] != (char) crossword[y4][--x4]) return objResult;
            }
            objResult = new Word(new String(wordToChar));
            objResult.setStartPoint(startX, startY);
            objResult.setEndPoint(endX, endY);
            return objResult;
        } else return objResult;
    }

    public static Word findPatternRight(int x5, int y5, char[] wordToChar, int[][] crossword ) {
        Word objResult = null;
        int lengthWord = wordToChar.length;
        int endX = x5 + lengthWord - 1;
        int endY = y5;
        if (endX > 5) return objResult;
        int startX = x5;
        int startY = y5;
        char endSymbolWord = wordToChar[lengthWord - 1];

        if (endSymbolWord == (char) crossword[endY][endX]) {
            for (int i = 1; i < lengthWord - 1; i++) {
                if (wordToChar[i] != (char) crossword[y5][++x5]) return objResult;
            }
            objResult = new Word(new String(wordToChar));
            objResult.setStartPoint(startX, startY);
            objResult.setEndPoint(endX, endY);
            return objResult;
        } else return objResult;
    }

    public static Word findPatternLeftUp(int x6, int y6, char[] wordToChar, int[][] crossword ) {
        Word objResult = null;
        int lengthWord = wordToChar.length;
        int endX = x6 - lengthWord + 1;
        int endY = y6 - lengthWord + 1;
        if (endX < 0 || endY < 0) return objResult;
        int startX = x6;
        int startY = y6;
        char endSymbolWord = wordToChar[lengthWord - 1];

        if (endSymbolWord == (char) crossword[endY][endX]) {
            for (int i = 1; i < lengthWord - 1; i++) {
                y6--;
                x6--;
                if (wordToChar[i] != (char) crossword[y6][x6]) return objResult;
            }
            objResult = new Word(new String(wordToChar));
            objResult.setStartPoint(startX, startY);
            objResult.setEndPoint(endX, endY);
            return objResult;
        } else return objResult;
    }

    public static Word findPatternLeftDown(int x7, int y7, char[] wordToChar, int[][] crossword ) {
        Word objResult = null;
        int lengthWord = wordToChar.length;
        int endX = x7 - lengthWord + 1;
        int endY = y7 + lengthWord - 1;
        if (endX < 0 || endY > 4) return objResult;
        int startX = x7;
        int startY = y7;
        char endSymbolWord = wordToChar[lengthWord - 1];

        if (endSymbolWord == (char) crossword[endY][endX]) {
            for (int i = 1; i < lengthWord - 1; i++) {
                if (wordToChar[i] != (char) crossword[++y7][--x7]) return objResult;
            }
            objResult = new Word(new String(wordToChar));
            objResult.setStartPoint(startX, startY);
            objResult.setEndPoint(endX, endY);
            return objResult;
        } else return objResult;
    }

    public static Word findPatternRightUp(int x8, int y8, char[] wordToChar, int[][] crossword ) {
        Word objResult = null;
        int lengthWord = wordToChar.length;
        int endX = x8 + lengthWord - 1;
        int endY = y8 - lengthWord + 1;
        if (endX > 5 || endY < 0) return objResult;
        int startX = x8;
        int startY = y8;
        char endSymbolWord = wordToChar[lengthWord - 1];

        if (endSymbolWord == (char) crossword[endY][endX]) {
            for (int i = 1; i < lengthWord - 1; i++) {
                if (wordToChar[i] != (char) crossword[--y8][++x8]) return objResult;
            }
            objResult = new Word(new String(wordToChar));
            objResult.setStartPoint(startX, startY);
            objResult.setEndPoint(endX, endY);
            return objResult;
        } else return objResult;
    }

    public static Word findPatternRightDown(int x9, int y9, char[] wordToChar, int[][] crossword ) {
        Word objResult = null;
        int lengthWord = wordToChar.length;
        int endX = x9 + lengthWord - 1;
        int endY = y9 + lengthWord - 1;
        if (endX > 5 || endY > 4) return objResult;
        int startX = x9;
        int startY = y9;
        char endSymbolWord = wordToChar[lengthWord - 1];

        if (endSymbolWord == (char) crossword[endY][endX]) {
            for (int i = 1; i < lengthWord - 1; i++) {
                if (wordToChar[i] != (char) crossword[++y9][++x9]) return objResult;
            }
            objResult = new Word(new String(wordToChar));
            objResult.setStartPoint(startX, startY);
            objResult.setEndPoint(endX, endY);
            return objResult;
        } else return objResult;
    }

    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);
        }
    }
}

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'} }; List<Word> listResult = detectAllWords(crossword, "home", "same", "masu", "meo"); /* Ожидаемый результат home - (5, 3) - (2, 0) same - (1, 1) - (4, 1) */ for (Word x : listResult) { System.out.println(x); } } public static List<Word> detectAllWords(int[][] crossword, String... words) { List<Word> list = new ArrayList<>(); for (String wordElement : words) { char[] wordToChar = wordElement.toCharArray(); for (int y = 0; y < 5; y++) { for (int x = 0; x < 6; x++) { Word objResult = null; objResult = findPattern(x, y, wordToChar, crossword, list); // if (objResult != null) { // list.add(objResult); // } } } } return list; } public static Word findPattern(int x1, int y1, char[] wordToChar, int[][] crossword, List<Word> list) { Word objResult = null; if ((char) crossword[y1][x1] != wordToChar[0] || wordToChar.length == 1) return null; if ((char) crossword[y1][x1] == wordToChar[0]) { objResult = findPatternUp(x1, y1, wordToChar, crossword); if (objResult != null) list.add(objResult); objResult = findPatternDown(x1, y1, wordToChar, crossword); if (objResult != null) list.add(objResult); objResult = findPatternLeft(x1, y1, wordToChar, crossword); if (objResult != null) list.add(objResult); objResult = findPatternRight(x1, y1, wordToChar, crossword); if (objResult != null) list.add(objResult); objResult = findPatternLeftUp(x1, y1, wordToChar, crossword); if (objResult != null) list.add(objResult); objResult = findPatternLeftDown(x1, y1, wordToChar, crossword); if (objResult != null) list.add(objResult); objResult= findPatternRightUp(x1, y1, wordToChar, crossword); if (objResult != null) list.add(objResult); objResult = findPatternRightDown(x1, y1, wordToChar, crossword); if (objResult != null) list.add(objResult); } return null; } public static Word findPatternUp(int x2, int y2, char[] wordToChar, int[][] crossword ) { Word objResult = null; int lengthWord = wordToChar.length; int endX = x2; int endY = y2 - lengthWord + 1; int startX = x2; int startY = y2; if (endY < 0) return objResult; char endSymbolWord = wordToChar[lengthWord - 1]; if (endSymbolWord == (char) crossword[endY][endX]) { for (int i = 1; i < lengthWord - 1; i++) { if (wordToChar[i] != (char) crossword[--y2][x2]) return objResult; } objResult = new Word(new String(wordToChar)); objResult.setStartPoint(startX, startY); objResult.setEndPoint(endX, endY); return objResult; } else return objResult; } public static Word findPatternDown(int x3, int y3, char[] wordToChar, int[][] crossword ) { Word objResult = null; int lengthWord = wordToChar.length; int endX = x3; int endY = y3 + lengthWord - 1; int startX = x3; int startY = y3; if (endY > 4) return objResult; char endSymbolWord = wordToChar[lengthWord - 1]; if (endSymbolWord == (char) crossword[endY][endX]) { for (int i = 1; i < lengthWord - 1; i++) { if (wordToChar[i] != (char) crossword[++y3][x3]) return objResult; } objResult = new Word(new String(wordToChar)); objResult.setStartPoint(startX, startY); objResult.setEndPoint(endX, endY); return objResult; } else return objResult; } public static Word findPatternLeft(int x4, int y4, char[] wordToChar, int[][] crossword ) { Word objResult = null; int lengthWord = wordToChar.length; int endX = x4 - lengthWord + 1; int endY = y4; if (endX < 0) return objResult; int startX = x4; int startY = y4; char endSymbolWord = wordToChar[lengthWord - 1]; if (endSymbolWord == (char) crossword[endY][endX]) { for (int i = 1; i < lengthWord - 1; i++) { if (wordToChar[i] != (char) crossword[y4][--x4]) return objResult; } objResult = new Word(new String(wordToChar)); objResult.setStartPoint(startX, startY); objResult.setEndPoint(endX, endY); return objResult; } else return objResult; } public static Word findPatternRight(int x5, int y5, char[] wordToChar, int[][] crossword ) { Word objResult = null; int lengthWord = wordToChar.length; int endX = x5 + lengthWord - 1; int endY = y5; if (endX > 5) return objResult; int startX = x5; int startY = y5; char endSymbolWord = wordToChar[lengthWord - 1]; if (endSymbolWord == (char) crossword[endY][endX]) { for (int i = 1; i < lengthWord - 1; i++) { if (wordToChar[i] != (char) crossword[y5][++x5]) return objResult; } objResult = new Word(new String(wordToChar)); objResult.setStartPoint(startX, startY); objResult.setEndPoint(endX, endY); return objResult; } else return objResult; } public static Word findPatternLeftUp(int x6, int y6, char[] wordToChar, int[][] crossword ) { Word objResult = null; int lengthWord = wordToChar.length; int endX = x6 - lengthWord + 1; int endY = y6 - lengthWord + 1; if (endX < 0 || endY < 0) return objResult; int startX = x6; int startY = y6; char endSymbolWord = wordToChar[lengthWord - 1]; if (endSymbolWord == (char) crossword[endY][endX]) { for (int i = 1; i < lengthWord - 1; i++) { y6--; x6--; if (wordToChar[i] != (char) crossword[y6][x6]) return objResult; } objResult = new Word(new String(wordToChar)); objResult.setStartPoint(startX, startY); objResult.setEndPoint(endX, endY); return objResult; } else return objResult; } public static Word findPatternLeftDown(int x7, int y7, char[] wordToChar, int[][] crossword ) { Word objResult = null; int lengthWord = wordToChar.length; int endX = x7 - lengthWord + 1; int endY = y7 + lengthWord - 1; if (endX < 0 || endY > 4) return objResult; int startX = x7; int startY = y7; char endSymbolWord = wordToChar[lengthWord - 1]; if (endSymbolWord == (char) crossword[endY][endX]) { for (int i = 1; i < lengthWord - 1; i++) { if (wordToChar[i] != (char) crossword[++y7][--x7]) return objResult; } objResult = new Word(new String(wordToChar)); objResult.setStartPoint(startX, startY); objResult.setEndPoint(endX, endY); return objResult; } else return objResult; } public static Word findPatternRightUp(int x8, int y8, char[] wordToChar, int[][] crossword ) { Word objResult = null; int lengthWord = wordToChar.length; int endX = x8 + lengthWord - 1; int endY = y8 - lengthWord + 1; if (endX > 5 || endY < 0) return objResult; int startX = x8; int startY = y8; char endSymbolWord = wordToChar[lengthWord - 1]; if (endSymbolWord == (char) crossword[endY][endX]) { for (int i = 1; i < lengthWord - 1; i++) { if (wordToChar[i] != (char) crossword[--y8][++x8]) return objResult; } objResult = new Word(new String(wordToChar)); objResult.setStartPoint(startX, startY); objResult.setEndPoint(endX, endY); return objResult; } else return objResult; } public static Word findPatternRightDown(int x9, int y9, char[] wordToChar, int[][] crossword ) { Word objResult = null; int lengthWord = wordToChar.length; int endX = x9 + lengthWord - 1; int endY = y9 + lengthWord - 1; if (endX > 5 || endY > 4) return objResult; int startX = x9; int startY = y9; char endSymbolWord = wordToChar[lengthWord - 1]; if (endSymbolWord == (char) crossword[endY][endX]) { for (int i = 1; i < lengthWord - 1; i++) { if (wordToChar[i] != (char) crossword[++y9][++x9]) return objResult; } objResult = new Word(new String(wordToChar)); objResult.setStartPoint(startX, startY); objResult.setEndPoint(endX, endY); return objResult; } else return objResult; } 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); } } }

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

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

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

JustinianJudge в Mega City One

Master

7 июня 2019, 16:32

полезный

Сравнил со своим кодом, единственную разницу которую смог найти - у меня отрабатывает на слова с одной буквы. Но нужно ли это по условиям и проверяет ли валидатор, без малейшего понятия. По поводу читаемости, неплохо, но нужно больше.

for (Word x : listResult) {
        System.out.println(x);
    }

буквенные обозначения мы оставляем на первых уровнях (оставляем разве что привычные i,j,n,s,str и тд), а здесь мы печатаем что? Слово. Значит Word word : listResult int x2, int y2, в методах нумерованные координаты выглядят неуместно. Просто х, просто y в каждом методе. Иначе возникают вопросы которые лишь отвлекают от чтения кода. if (wordToChar[i] != (char) crossword[--y2][x2]) return objResult; в алгоритмических задачах в принципе такое допустимо. Но в уме держим, чем выше уровень абстракции, тем жестче нужно придерживатся правила IF/FOR пишутся с фигурными скобками даже если всего один оператор, это плодит ошибки, это понижает читабельность, это усложняет рефакторинг. Но в целом для решения в лоб, мне понравилось, у меня тоже в лоб вариант, и он страшнее на многие порядки. Еще бы успешно сдал валидатору и вообще отлично ) Но не знаю что ему не так, знать бы какие тесты валятся.

Валерий Поляков

Уровень 28

7 июня 2019, 21:14

спасибо что посмотрел мой код. По поводу х2, у2 и т.д. это моя попытка исправить ситуацию после того как у idea снесло крышу

for (int y = 0; y < 5; y++) {
                for (int x = 0; x < 6; x++) {
                    Word objResult = null;
                    objResult = findPattern(x, y, wordToChar, crossword, list);
                }
            }

в этом вложенном цикле сразу на первой итерации х и у становились равными "-1" у меня случился разрыв шаблона, в итоге помогло только это. Из-за чего это произошло я так и не понял.

JustinianJudge в Mega City One

Master

7 июня 2019, 21:27

ну когда конфликт имен в логике всякое бывает, но сама суть думаю понятна, нумеровать от 1 до 8 точно не стоит, так никто не делает, каждый метод он как бы отдельный. Просто в методах переименовать переменные, чтобы не было совпадений. Допустим есть x, y, есть pointX, pointY, если циклы то и i, j достаточно. Я только досмотрелся, я правильно понял, что твой код будет работать только на матрице размерностью как в исходном коде? Валидатор скорее всего проверяет только на ней, но сам факт, хардкодинг нужно заменять привязкой к относительным величинам. Хардкодинг это костылинг, иногда без него никак, но он должен быть в крайних случаях..

Валерий Поляков

Уровень 28

7 июня 2019, 21:32

все верно, код работает только на матрице из задания. Переделаю на более универсальный вариант, спсб за мысль подсказку.

JustinianJudge в Mega City One

Master

7 июня 2019, 21:36

Мне кажется маловероятно что это имеет значение, хотя чем черт не шутит. Я комментировал больше на будущее, чтобы обращать на такое внимание. А вот версия про одну букву интересней мне кажется имеет больше оснований. Ну либо какой-то плавающий баг, что все супер определяет, а при определенных обстоятельствах клинит, такое проверить сложно, только пересмотреть еще раз алгоритм.