Кроссворд

  • 11
  • Недоступна
Нет, нам не придётся решать кроссворды. Нам нужно решить нетривиальную задачку про кроссворды. Есть двумерный массив, а в нём — слова, слова, слова. По горизонтали, по вертикали, по диагонали… Нужно найти все слова в массиве.
Вы не можете решать эту задачу, т.к. не залогинены.
Комментарии (109)
  • популярные
  • новые
  • старые
Для того, чтобы оставить комментарий вы должны авторизоваться
Андрей20 уровень, Москва
вчера, 20:00
Спасибо комментировавшим свой прогресс. Я сначала сделал ну очень просто тремя циклами, но получал только по одному экземпляру каждого слова. Что вроде бы не противоречит условию, но, как оказалось, не проходит валидатор. Спасибо Voyager, за пример с несколькими экземплярами одного слова. В итоге замутил алгоритм с кучей циклов один в другом (по словам, по первой букве, по направлению...) и тогда уже заработало, валик прошёл с первой попытки.
Kazbek28 уровень, Москва
2 марта, 19:19
на сколько я понял у валидатора в проверке нет слов из 1 символа, но на всякий случай добавил это условие, чтобы в итоговом списке не было по 8 повторений одного Word'a
gts32027 уровень, Харьков
22 февраля, 17:53
Метод detectAllWords 40 строк. Без рекурсии.
Voyager24 уровень, Киев
21 февраля, 23:24
Создал 3 метода: 1) слева на право; 2) сверху вниз; 3) по диагонали; потом дублировал их для реверсивной строки которая вычисляется так:
new StringBuilder(word).reverse().toString();
Когда находил слово менял координаты местами в зависимости реверсивная строка или нет:
if (!wordIsReversed) {
     w = new Word(word);
     w.setStartPoint(startX, startY);
     w.setEndPoint(endX, endY);
} else {
       w = new Word(reverseWord(word));
       w.setStartPoint(endX, endY);
       w.setEndPoint(startX, startY);
}
result.add(w);
Валидатор сначала валился на последней проверке по этим причинам: 1) забыл поменять координаты местами для реверсивной строки; 2) сделал ложное предположение что если слово найдено - прекратись его поиск. Слово может повторяться; 3) по диагонали искал начиная только с левого верхнего угла. Добавил потом поиск с правого верхнего угла. Найти ошибку помогла эта тестовая матрица:
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'},
        };
        List<Word> words = (detectAllWords(crossword, "one"));
        for (Word word:words) {
            System.out.println(word);
        }
должно находить 8 решений:
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)
Вы решили задачу лучше, чем 14% учеников. Вам удалось ее решить с 4 попытки. Среднее количество попыток для этой задачи 2.53. Всего эту задачу решили 4395 учеников. Одни вундеркинды собрались, думал будет хуже статистика.
Kad22 уровень
25 февраля, 14:45
спасибо за тест, помог найти ошибку
Костя25 уровень, Москва
1 марта, 21:13
у меня находится одно решение на твою тестовую матрицу, но валидатор принял решение [one - (3, 2) - (5, 4)]
maxboot35 уровень, Днепр
9 февраля, 19:11
Для проверки можно заменить в последней строке первую "e" на "r" и выполнить поиск по слову "rr". Должно получится 8 значений: [rr - (3, 2) - (3, 3), rr - (3, 2) - (4, 3), rr - (3, 3) - (4, 3), rr - (3, 3) - (2, 4), rr - (3, 3) - (3, 2), rr - (4, 3) - (3, 2), rr - (4, 3) - (3, 3), rr - (2, 4) - (3, 3)]
Evgenii26 уровень, Санкт-Петербург
9 февраля, 17:11
уфф с 15 го раза, решал два дня, пытался решить записывая буквы в stringbuilder и потом сравнивал со словом. валидатор не принимал, видимо не нравилось запись составленного слова, переделал сравнение каждой буквы. вроде прошло все.
Artur38 уровень
7 февраля, 21:36
C первого захода не смог решить эту задачу, решил оставить на потом. Но покоя она мне не давала, в итоге на 24 уровне вернулся к ней и решил за час, а до этого сидел около 6 часов. Так что мой вам совет, если совсем не идёт, оставьте на потом.
Sergey Moroz26 уровень, Киев
4 февраля, 03:24
Персик, а не задача - схавала целый день, но оно того стоило - мозги еще не отсохли. Для спортивного интереса - гитка.
Sasha S28 уровень, Киев
16 декабря 2018, 20:21
загальна кількість рядків коду 285. після попередніх задач було впадло рефакторити. но зато з першої спроби))
Gogogo31 уровень
14 ноября 2018, 14:31
Если у Вас всё верно, но не проходит валидацию, протестируйте так. Добавьте в кроссворд одно и то же слово несколько раз, в т.ч. начинающееся из одной точки и идущее в разных направлениях. Ваш код должен внести его в лист столько раз, сколько есть разных вариантов.
Сергей36 уровень, Нижний Новгород
28 ноября 2018, 22:18
У меня валидатор принял решение где находится хотя бы один вариант слова из списка.