Кроссворд

  • 11
  • Недоступна
Нет, нам не придётся решать кроссворды. Нам нужно решить нетривиальную задачку про кроссворды. Есть двумерный массив, а в нём — слова, слова, слова. По горизонтали, по вертикали, по диагонали… Нужно найти все слова в массиве.
Вы не можете решать эту задачу, т.к. не залогинены.
Комментарии (114)
  • популярные
  • новые
  • старые
Для того, чтобы оставить комментарий вы должны авторизоваться
Антон22 уровень, Москва
четверг, 12:39
с первой попытки... делал в лоб, 3 метода по горизонтали, по вертикали и по диагонали соответственно
Игорь24 уровень, Харьков
25 апреля, 14:49
Приветствую всех, решающих эту задачу! У вас всё получится - валидатор примет ваше решение! Решил задачу с двадцатой попытки без рекурсии и графов - не освоил ещё эти приёмы. Весь код решения записан в одном методе detectAllWords на 40 строк. По состоянию "на сегодня" задачу решили 4554 ученика. Среднее количество попыток - 2,54. Если все идеи перепробовали и не знаете "куда копать" - прочтите этот список. Существенные моменты, которые я не учитывал/не понимал и которые "пили кровь" два дня: 0. Таки да - в примере "Ожидаемый результат" речь идёт о приведённом в задаче массиве, но координаты записаны не (индекс строки, индекс в строке), а (индекс в строке, индекс строки) именно такого порядка следования координат и ждёт валидатор. 1. Слова из одной буквы можно не искать и ими не заниматься. 2. Слова в массиве ищутся до первого обнаружения и можно переходить к следующему слову. 3. "Непрямолинейные" слова можно не искать, то есть от найденной первой буквы все следующие буквы можно искать исключительно по одному из восьми лучей (влево-вправо, вверх-вниз, четыре диагонали). 4. Если все тесты выдают верное решение, а "ментор говорит", что неверно находятся координаты слов, то проверьте return метода detectAllWords - в List<Word> должно быть добавлено: - искомое слово (wordList.add(new Word(word))); - начальная координата (wordList.get(.....)), используя метод setStartPoint; - конечная координата (wordList.get(.....)), используя метод setEndPoint. Если в методе main вызвать forech с печатью элементов List<Word> и на экране будут искомые слова с координатами из нулей, то, может вам и повезёт, но у меня не принималось валидатором. Удачи вам и хорошего настроения!!!
Aleksei Dobrovolskii23 уровень
21 марта, 05:32
13 попыток и полтора дня ушло чтобы понять, что надо перебирать циклом массив внутри цикла с перебором слов, а не наоборот *facepalm* При этом, в список результатов попадали все значения, какие бы я ему не подсовывал (всё верно, так и должно быть), но только не в том порядке, естественно. git
Андрей23 уровень, Москва
18 марта, 20:00
Спасибо комментировавшим свой прогресс. Я сначала сделал ну очень просто тремя циклами, но получал только по одному экземпляру каждого слова. Что вроде бы не противоречит условию, но, как оказалось, не проходит валидатор. Спасибо Voyager, за пример с несколькими экземплярами одного слова. В итоге замутил алгоритм с кучей циклов один в другом (по словам, по первой букве, по направлению...) и тогда уже заработало, валик прошёл с первой попытки.
Kazbek35 уровень, Москва
2 марта, 19:19
на сколько я понял у валидатора в проверке нет слов из 1 символа, но на всякий случай добавил это условие, чтобы в итоговом списке не было по 8 повторений одного Word'a
gts32034 уровень, Харьков
22 февраля, 17:53
Метод detectAllWords 40 строк. Без рекурсии.
Voyager29 уровень, Киев
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)]
maxboot41 уровень, Днепр
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 и потом сравнивал со словом. валидатор не принимал, видимо не нравилось запись составленного слова, переделал сравнение каждой буквы. вроде прошло все.
Artur41 уровень
7 февраля, 21:36
C первого захода не смог решить эту задачу, решил оставить на потом. Но покоя она мне не давала, в итоге на 24 уровне вернулся к ней и решил за час, а до этого сидел около 6 часов. Так что мой вам совет, если совсем не идёт, оставьте на потом.
Bazi4ek22 уровень, Минск
23 марта, 15:14
Ну ты даешь за 6 часов, люди днями задачу решают) мой 2х дневный вариант))