В методе main считай с консоли имя файла, который содержит слова, разделенные пробелом.
В методе getLine используя StringBuilder расставь все слова в таком порядке,
чтобы последняя буква данного слова совпадала с первой буквой следующего не учитывая регистр.
Каждое слово должно участвовать 1 раз.
Составить цепочку слов
- 24
Недоступна
Комментарии (531)
- популярные
- новые
- старые
Для того, чтобы оставить комментарий Вы должны авторизоваться
partiec
11 мая, 17:13
Мое решение не прошло по времени. Стал разбирать правильное.
Это сатанинский код! Трудно понять.
0
PhanSca
10 мая, 09:27
Чему, к сожалению, JavaRush не учит при заданиях на алгоритмы - это анализу скорости.
Многие предложенные решения были квадратичны, если не хуже.
Для ознакомления предлагаю приближенное к линейному. Постарался закомментить поподробнее, но опыта комментирования особо нет.
0
PhanSca
10 мая, 09:28
0
Gans Electro
11 мая, 10:04
Думаю требования к курсу JavaRush нет. Здесь не про алгоритмы
0
partiec
11 мая, 17:07
Если честно единственное что я понял - что
это всё серьезно☝
0
PhanSca
11 мая, 17:15
Я сам не столь уж долго учусь программированию. Но из опыта leetcode (а также информации о собеседованиях) понял, что если придется заходить на территорию алгоритмов (а этот вопрос уже на нее зашел), то нужно уметь не только написать абы какое решение.
Если вдруг на собеседовании будет задача, связанная с алгоритмами, то надо быть готовым ответить, как масштабируется ваше решение в зависимости от объема входных данных (большое O). Как можно его оптимизировать и т.д.
0
partiec
11 мая, 17:23

0
very junior java developer www.codewars.com/r/TTH6EQ
27 апреля, 21:08
Задача огонь! Не про потоки, не про StringBuilder, но про алгоритмы))
Сначала быстренько накидал код, который расставил всё как надо для списка "Киев Нью-Йорк Амстердам Вена Мельбурн". Валидатор не принял.
Понял что нужно расширять список для теста, что бы не выдумывать списки самому подсмотрел несколько штук в комментах.
В итоге выбрал эти два, ибо они в моём решении явно указали на проблему, у меня остаются лишние слова причём в первом пункте список вообще направленный, тобишь имеет только 1 вариант выходной строки:
1) Дербент Якутск Арзамас Рог Киев Кувшиново Капустин-Яр Стокгольм Флоренция Глен-Хоп Тобольск Нью-Йорк Афины Муром Осташков Прага Кострома Вена Амстердам Мельбурн Волгоград Минск
2) Венеция Ялта Минск Амстердам Москва Алушта Атланта Афины Ысити Столькольм Исбук Курск Кишинев Вена Астрахань Ьсити Иерусалим Мюнхен Норильск Канзас Киев
Потратил на задачу 4-5 часов.... алгоритм пришёл в голову только после того, как начал в текстовом редакторе самостоятельно выстраивать цепочку действий пошагово.
Суть этой задачи просто найти классный алгоритм с линейной сложностью ну или хотя бы логарифмической.
Никаких "Шафлов" я не юзал и никому не советую, ибо на более-менее большом списке такой вариант может искать верный ответ долгие-долгие годы.
Алгоритм "до чёртиков" простой. Но постить не буду, ибо тогда решать её станет не интересно)))
Лишь одна подсказка - "Проверяем конец или начало или "проворачиваем" список"
Короче по итогу у меня код отрабатывает списки большой длины(1000-5000) почти мгновенно, ну типо менее секунды. Естественно что входные данные обязательно должны быть корректны, тобишь заведомо ИМЕТЬ решение. Собственно в условии так и написано)).
Мой вариант реализации с комментариями могу прислать по запросу. Настоятельно рекомендую делать это, только в том случае, если уже решили задачу.
+1
very junior java developer www.codewars.com/r/TTH6EQ
27 апреля, 21:26
Скрин с итогом выполнения на большой выборке.
![]()

0
Viktar
29 апреля, 14:02
А на создание списка большой длины сколько пришлось потратить?)
Я задачу не решил, тестирую пока на примерах.
А чем реализован список?
0
very junior java developer www.codewars.com/r/TTH6EQ
30 апреля, 17:44
Да список легко делается просто берёшь какой-то цикличный небольшой список(хорошо перемешанный) и кучу раз его копипастишь)))
0
Dmitry Kuzmitsky
20 апреля, 15:33
Решал через shuffle, стримы и исключения. Очень долго пытался понять почему валидатор не принимает.
Оказалось, что ему не понравилась "строка" на входе getLine.
Подсмотрел в правильном решении про StringTokenizer, переделал свой метод mailn и прокатило.
Метод getLine 30 строк без дополнительных методов и сторонних классов.
0
Денис
18 марта, 23:39
Первый вопрос - где многопоточность?)))00
Второй - как спать ваще)))000
+1
Shrink #3253122
13 марта, 15:01
Как говорил главный герой сериала "Кремниевая долина":
Из центра наружу!)))
Берем слово и приставляем к нему слова со всех сторон по условию задачи. Все не вошли? Берем следующее.
Вам понадобятся:
- tempList - чтобы его резать
- int count, boolean flagForward, flagBackward - если count равен длине массива words и флаги опущены - решено, выходим из основного цикл.
count'ы увеличиваем только при изменении строки (т.е. если слова найдены) там же и флаги поднимаем и выходим из вложенного цикла.
- ну и int step - собственно слово с которого мы начинаем.
увеличивается если флаги опущены и count не равен 0 (не забываем все вернуть в исходное положение);
0
hidden #598481
9 марта, 21:50
Жаль, что нельзя закрепить комментарий, и он неизменно уползёт вниз, но может быть помогу хоть кому-то. Сейчас в топе популярных вредные советы, и я хочу это исправить. Поэтому если считаете этот комментарий полезным - ставьте лайк и выводите в топ, чтобы он висел выше.
Что не нужно делать в этой задаче
1. Если вы где-то среди комментариев вычитали, что невошедшие в цепочку слова можно просто накидать в конец цепочки с таким выражением лица
то знайте, это бред сивой кобылы. Я не могу исключать, что такие решения могли пройти валидатор просто потому, что его тесты в этой задаче похоже не самые искушённые, но это противоречит условию. По условию все слова укладываются в цепочку, лишних слов нет. То есть вам гарантируют корректность входных данных при проверке. В моём алгоритме при обнаружении слова, которое действительно не вписывается в цепочку я выбрасывал исключение - ничего страшного не произошло, проверка была пройдена.
2. Если вы вычитали или сами придумали просто переставлять слова до посинения методом shuffle или иным рандомом, пока они сами собой не уложатся в цепочку, то это чуть меньший бред. Такой способ в приемлемое время может составить цепочку из 7-8 слов и поэтому даже способен пройти проверку валидатора, но это не путь самурая. У такого "алгоритма" уже на 20+ словах уйдут годы на поиск правильного решения, в то время как хороший алгоритм найдёт за доли секунды цепочку из сотен слов.
Итак, как же на самом деле стоит решать эту задачу. Можете подумать ещё немного сами, а если нужна подсказка, то читайте второй комментарий в ветке.

+6
hidden #598481
9 марта, 22:01
Полностью решения я раскрывать не стану, но вот несколько полезных советов.
1. Составьте таблицу, в которой вы перечислите все первые и последние буквы каждого слова и сосчитаете для каждой буквы, сколько слов на каждую из них начинается и сколько заканчивается. Что для этого использовать: список, мапу, свой собственный класс - дело ваше.
Если ваши слова образуют замкнутую цепочку, то довольно очевидно, что на каждую букву должно заканчиваться столько же слов, сколько и начинаться с неё. Если вы проверили ваш набор слов, и это ваш случай - значит начинать цепочку можно с любого слова, цепочка будет заканчиваться на ту же букву, с которой начинается.
Другой возможный вариант - когда на одну из букв начинается на одно слово больше, чем ей заканчивается, и при этом на какую-то другую букву заканчивается на одно слово больше, чем начинается. Это означает, что вы нашли соответственно начало и конец цепочки. У всех остальных букв должно быть одинаковое количество входящих и исходящих, иначе никакой цепочки не получится.
Если вы проверили все буквы, и расхождение нашлось больше, чем у двух букв, или расхождение в количестве больше, чем на одно слово, то никакой цепочки не получится, можете надуть щёки и ничего не возвращать. Такие данные не участвуют в проверке.
А дальше пункт 2 (рисуем остаток совы): составляем цепочку. Мы знаем откуда начать цепочку, и где она должна закончиться. Просто берите первое попавшееся слово, начинающееся на нужную букву и пляшите от него, пока не упрётесь в то, что больше нет подходящих слов. Упереться вы можете только на последней букве, то есть на той, с которой начали в случае с замкнутой цепочкой, или на той, которую нашли в качестве последней в "незамкнутом" случае. Все остальные буквы "проходные", мы это доказали, когда сосчитали сколько входящих и исходящих. И тут у вас два варианта: либо слова у вас при этом кончились, и вы красавчик, либо ещё остались, и с этим придётся ещё немного поработать.
Сорри, снова лимит символов
+2
hidden #598481
9 марта, 22:16
Так вот, если у вы прошли свою цепочку от начала и до конца, а у вас остались ещё слова, то это означает, что оставшиеся слова образуют петлю, то есть замкнутую цепочку, которую можно найти по такому же принципу, который описан выше. Или может быть даже несколько таких петель. Главное, что каждую из этих петель можно сначала найти тем же алгоритмом и потом встроить в основную цепочку, потому что у них будет с ней пересечение хотя бы в одной букве. Поэтому просто повторяем алгоритм для оставшихся слов, пока слова не кончатся, а цепочки соединяем между собой. Хлопаем в ладоши, радуемся, пишем какой вы там по счёту среди решивших и рассказываем, как вы классно справились и креативно подошли к решению задачи.
Если вы терпеливы, то можете долистать до моего же комментария от 30 сентября 2019, там есть годные примеры для тестирования, с которыми может справиться только нормально работающий алгоритм.
Если вы из тех, кто всегда просит скинуть "статью по теме", то можете почитать дискретную математику и теорию графов. Конкретно это задача на нахождение пути Эйлера. Достаточно информации для самостоятельного гуглежа.
Удачи!
+2
Денис
19 марта, 16:27
Я думаю, что лишние слова все таки при проверке запихиваются. Ибо пройдя все тесты из популярных комментариев:
Тест 1: Киев Винница Нью-Йорк Киров Амстердам Вена Мельбурн
Тест 2: Киев Нью-Йорк Афины Прага Вена Амстердам Мельбурн Алушта
Тест 3: Венеция Ялта Минск Амстердам Москва Алушта Атланта Афины Ысити Столькольм Исбук Курск Кишинев Вена Астрахань Ьсити Иерусалим Мюнхен Норильск Канзас Киев
Тест 4: Киев Нью-Йорк Амстердам Вена Мельбурн Милан
Тест 5: Антверпен Прага Алушта
Тест 6: Киев Нью-Йорк Роттердам Вена Мельбурн
Тест 7: Дербент Якутск Арзамас Рог Киев Кувшиново Капустин-Яр Стокгольм Флоренция Глен-Хоп Тобольск Нью-Йорк Афины Муром Осташков Прага Кострома Вена Амстердам Мельбурн Волгоград Минск.
Валидацию так и не прошел, по причине долгой работы программы, хотя все тесты прекрасно проходят. Условие выхода из цикла у меня как раз таки в тот момент, когда лишних слов не осталось. В общем логика ясна, второй вариант - я написал какую то шляпу))0000
+2
hidden #598481
19 марта, 18:08
Я же выше доказал что нет. У меня в коде было прямо написано
Если бы валидатор ожидал от меня какого-то исхода на таком наборе данных, то он бы это не принял.
Если твой алгоритм работает правильно с точки зрения поиска цепочки, то значит ты не учёл какую-нибудь фигню. Например, ты не приводишь каждый раз буквы к одному регистру, ожидая что слова всегда начинаются с большой буквы и заканчиваются маленькой (этого никто не гарантирует).
В любом случае, ты можешь выложить свой код и спросить, что там не так. 0
Денис
19 марта, 18:42
Та вот с буковками так навозился, что думаю обработка достаточная) Возможно чего то не хватает в обработке оставшегося списка, но уже сил не было если честно, 18 попыток потратил) я бы взглянул на ваш, в личку, если можно. На досуге изучить. Из правильного решения вообще непонятная хренотень. Ну и конечно же возможен мой второй вариант🤣
0
hidden #598481
20 марта, 13:15
Боюсь, у меня будет ещё более непонятная хренотень, т.к. я ударился в ООП и всё вынес в отдельные уровни абстракции. Но в целом принцип сохранился такой же, что и в правильном решении: рекурсивный обход.
Да, все любят тесты, поэтому предлагаю свой набор для тестирования:
0
Дмитрий
1 марта, 06:44
Можно решить достаточно просто. Алгоритм следующий:
1) Слова из аргумента функции переменной длины добавляем в список слов (List);
2) Создаем StringBuilder и сразу добавляем в него первое слова из списка и сразу удаляем добавленное слово из списка;
3) Делаем цикл while (wordsList.size() > 0). Дальше тело цикла
3.1) Пытаемся в списке найти через stream слово, которое начинается на последнюю букву StringBuilder'а. Если нашлось - добавляем слово в конец и удаляем его из списка.
3.2) Если не нашлось слово из п.3.1, ищем в списке слово, которое заканчивается на первую букву StringBuilder'а. Если нашлось - добавляем его в начало и удаляем его из списка.
3.3) Если не нашлось слово из п.3.2 - значит список направленный. Поэтому на всякий случай проверяем, что у нас в StringBuilder'е первая и последняя буква совпадают (это условие на самом деле будет выполняться всегда, если исходные данные правильные) и переставляем последнее слово в StringBuilder'е в начало. И переходим на следующую итерацию цикла.
При таком решении размер всего файла Solution - 62 строки.
PS. И не забываем сделать проверку на пустой список в аргументе функции.
+2
Viter
16 февраля, 08:46
Задача интересная если понять что от тебя хотят из условия которое написано очень неконкретно особенно было неясно "буква данного слова" какого данного, где данного? Пришлось опробовать несколько решений пока одно из предположений не прошло валидацию
Задача которую решил я: Нужно найти максимальную последовательность слов из файла в которой последняя буква слова будет совпадать с первой буквой следующего слова взятого из того же файла (каждое слово 1 раз), последовательность добавить в StringBuilder остальные слова из файла не вошедшие в цепочку добавить в конец этой StringBuilder
оставлю комментарии из моего кода которые писал что бы не потерять цепочку мыслей может кому помогут:
+1
Андрей Остапчук
4 февраля, 15:58
сделав свой код в 54 строки и барабанная дробь........ опять не принимает валидатор! Хотя вывод правильный, что ж, стратегия взял готовое -> вставил -> дал валидатору -> обратно вставил своё снова работает.
+2