Составить цепочку слов

  • 24
  • Недоступна
В методе main считай с консоли имя файла, который содержит слова, разделенные пробелом. В методе getLine используя StringBuilder расставь все слова в таком порядке, чтобы последняя буква данного слова совпадала с первой буквой следующего не учитывая регистр. Каждое слово должно участвовать 1 раз.
Вы не можете решать эту задачу, т.к. не залогинены.
Комментарии (308)
  • популярные
  • новые
  • старые
Для того, чтобы оставить комментарий вы должны авторизоваться
Александр Бутаков24 уровень, Москва
четверг, 11:47
Написал небольшую статью по данной задаче: здесь.
Dmitry Gorchakov23 уровень, Москва
понедельник, 19:00
Ловушки, на которые можно напороться: 1) очевидные "тупиковые" слова, которые должны быть либо в начале, либо в конце финальной строки. Тупик вызван тем, что первая(последняя) буква не является концом(началом) ни одного из последующих слов. Тест из комментов: tuv igk xyz nop klm ghi vwx mn fgh efg zab rst def higk kmno cde abc bcd pqr 2) не очевидные "тупиковые" слова связаны с неправильным выбором первого слова, хотя по предыдущему условию они проходят. Тест из комментов: трам Нет труД муд доМ мандарин март Начав упорядочивание с первого слова попадаем в тупиковую ситуацию, когда март не попадает в финальную строку. Решение : 1) найти очевидные тупиковые слова (первое/последнее). 2.1) если определили первое и последнее слово, то начинаем упорядочивание, не учитывая последнее слово, его добавляем в конце; 2.2) если нет очевидных "тупиковых " слов - брать по умолчанию первое слово и пытаться упорядочить по заданию. Далее проверить, остались ли неиспользованные слова. Начать заново, но со следующего слова.
Александр Бутаков24 уровень, Москва
вторник, 07:51
1. Первой ситуации быть не может, т.к. должен быть цикл - в финальной строке первая буква первого слова должна быть равна последней букве последнего слова. 2. Может быть последовательность, в которой начало с любого слова приводит к кольцу и лишним словам (но вроде валидатор не проверяет такой последовательностью). Попробуйте такую скормить алгоритму: pE tZ pp ee ii dd OY mm BB Dx mm Do NN IX ps eE vS XE Ru Zt yU HH AA xD Ck Gn EE LL Nx CC Sv YY hh gw hh Xm aP Rt LA bh vv tt NR vS GG mP dA NN NN Ee eH LL kC PP En AX ZG BB wg hn Bz Ep hb OO uu xx GZ He Cw Ld KK Ad pE BB OO ku vh Sv Qo nh LT bb AA nG hM EE oQ CC sp Pg PP mX DD dL SS gP SS Py LL ji EX RA Pa AR ss AL ZZ Uy Et KH RN OO xN wC Pm XI YO ij hv gg Ep Mh yP Eb oo BB QQ TL II bE yy ww nE uu bb tE uR Ng zB PP pp gN tR NN HK XA GG tt uk oD
Александр Бутаков24 уровень, Москва
27 июня, 09:35
Задачу валидатору сдал, но решение не является устойчивым (работает не на любой произвольной последовательности). До выдачи валидатору попробуйте решение на вот таких последовательностях: 1: ab aa ba ac ab ca cc Aa Ab ba bA aC CC bb Ca BB 2 (если хотите челлендж): pE tZ pp ee ii dd OY mm BB Dx mm Do NN IX ps eE vS XE Ru Zt yU HH AA xD Ck Gn EE LL Nx CC Sv YY hh gw hh Xm aP Rt LA bh vv tt NR vS GG mP dA NN NN Ee eH LL kC PP En AX ZG BB wg hn Bz Ep hb OO uu xx GZ He Cw Ld KK Ad pE BB OO ku vh Sv Qo nh LT bb AA nG hM EE oQ CC sp Pg PP mX DD dL SS gP SS Py LL ji EX RA Pa AR ss AL ZZ Uy Et KH RN OO xN wC Pm XI YO ij hv gg Ep Mh yP Eb oo BB QQ TL II bE yy ww nE uu bb tE uR Ng zB PP pp gN tR NN HK XA GG tt uk oD Про циклы и потерю данных: 1. Слова с одинаковой первой и последней буквами могут выпасть из последовательности, например: (ab, bb, ba) -> (ab, ba), при этом bb выпало из цикла; 2. Образование колец, например: (ab, dc, bc, ca, cd) -> (ab, bc, ca), а (dc и cd) выпали из цикла; 3. При последовательном обходе начальная позиция имеет значение, например: 3.a. (ab, dc, bc, ca, cd), начинаем с 0 позиции -> (ab, bc, ca) - потеряли dc и cd 3.b. (ab, dc, bc, ca, cd), начинаем с 1 позиции -> (dc, ca, ab, bc, cd)
Александр Бутаков24 уровень, Москва
27 июня, 09:35
Некоторые варианты избежать потерь: 1. Выделить из базового массива words 2 массива: [слова с одинаковыми 1 и последней буквами] и [слова с разными первой и последней буквами], при проверке следующего слова приоритетно присоединять слова из первого массива, например: [ab aa ba ac ab ca cc Aa Ab ba bA aC CC bb Ca BB] ->[aa cc Aa CC bb BB] и [ab ba ac ab ca Ab ba bA aC Ca] 2. Присоединять слово можно как к началу строки, так и к концу: [ab bc] + da -> [da ab bc] 3. Массив можно обходить как в прямом, так и в обратном порядке Это решает проверку валидатора. Правда на последовательности 3 (из начала поста) все равно не работает - несколько слов не присоединяет. Теперь пара слов по механикам: 1. LinkedList позволяет быстро удалять свои элементы 2. Метод remove не только удаляет элемент, но и возвращает его в функцию 3. StringBuilder может добавлять слово как в конец строки, так и в ее начало Про общий алгоритм: 1. Разбиваем массив words на 2 массива в зависимости от того, одинаковые первая и последняя буква в слове [1] или нет [2] 2. Начинаем с 0 элемента в [2], пробуем присоединить элемент из [1], если нет подходящих - тогда из [2], удаляем присоединенное слово 3. Если (2) удалось - повторяем 4. Если не удается присоединить слово ни из [1], ни из [2] и они не пустые - выходим из цикла и начинаем с (2), но уже не с 0, а с 1 элемента. 5. Если и это не помогло - пробуем обратную последовательность (начать с последнего элемента и проходить от последнего к первому элементу) Для валидатора этого хватит, а вот для последовательности из примера (3) - нет. Можно, конечно брутфорсить (кто-то об этом писал внизу), но там экспоненциальный рост, так что...
Bonus25 уровень
21 июня, 21:59
Вариант для проверки: трам Нет труД муд доМ мандарин март P.S. Слова можно добавлять не только в конец, но и в начало строки (первая буква слова = последней букве строки или последняя буква слова = первой букве строки)
Serp201525 уровень, Тольятти
18 июня, 17:05
Скармливал коду на основе Collections.shuffle 21 слово, ни разу не дождался решения, не хватило терпения. Валидатор схавал.
Евгений27 уровень, Санкт-Петербург
18 июня, 07:59
Первую попытку похоронил, когда попробовал пройти с простейшим алгоритмом, не учитывающим возможность тупиковых веток (когда есть еще слова в словаре, но ни одно из них не подходит к последнему добавленному). Хотя такая мысль возникла во время тестирования и составил пример уводящий программу в вечный цикл, но понадеялся, что задача будет попроще. А во второй раз уже попробовал перебирать ветки, где возможны развилки и заодно попробовал решить с рекурсией. И выход из переборов, когда длина получившегося списка равна переданному словарю.
Serp201525 уровень, Тольятти
18 июня, 17:10
Так же вначале делал, не подходящее слово переносил в конец массива. Всегда оставалось 1-2 слова в конце ни к чему не подходящие и массив крутился до бесконечности. Решил на основе Collections.shuffle. А что за рекурсия?
Евгений27 уровень, Санкт-Петербург
18 июня, 19:29
Добавил отдельный метод, куда циклом подавался словарь и стартовое слово, а дальше уже метод формировал LinkedList начиная с переданного слова, дальше удалял это слово из списка, смотрел последнюю букву. Отдельный метод пробегался по словарю и искал кандидатов на следующее место и там вариантов несколько, кандидатов нет - возвращаем список, кандидат один, то добавляем в LinkedList и вызываем снова этот метод с новым стартовым словом, если кандидатов несколько, то циклом проходимся по списку, снова вызывая этот метод по очереди с каждым словом, если какой то из вариантов вернул LinkedList размером со словарь, то выходим из цикла возвращая этот список.
Михаил25 уровень, Воронеж
17 июня, 10:48
в условии дается семь слов, из которых можно составить минимум 3 подходящих комбинации. при валидации же, скорее всего, дают слов 15 у которых, допустим, 10 подходящих комбинаций... 15 слов дают 1,3 трлн возможных комбинаций и только десять из них выигрышных. ваш алгоритм гарантирует, что хотя бы одна из них будет найдена? вот о чем задача. самый простой путь - Collections.shuffle
11 июня, 16:33
УРАААААААААААААААААААААА!!! я победил
Zaurbeck32 уровень, Москва
7 июня, 19:30
Код, написанный мною выдавал просто идеальный результат. Со словами(городами), которые даны в условии. С учетом перемешивания. Написал 2 цикла, 2 if'a. Аппендил слова в одну строку без пробелов а потом уже в return'e возвращал строку, пропущенную через регулярку, которая вставляла пробелы в конце каждого города. Уложился где-то в 15 строк кода без учета main(). ОДНАКО!!!!111!!11! 13 ПАПЫТОК КААААРЛ!!!..,!!.1.1.,! Я уже думал, может, где-то импорт ненужный затесался или какой-нить комментарий.. Или возможно List нельзя использовать или еще че... Тыкал и тыкал раз 12, пока не нашел комментарий доброго человека с проверочной строкой "Нет мандарин муд трам труД март доМ"... Ну и до меня доперло, что имелось ввиду в 6 пункте условия))) В итоге сравнивал на выходе из метода длину результата с общей длиной слов в массиве - если не равно, то рекурсия. Спасибо авторам. Классное условие :))
Арутюн29 уровень
6 июня, 20:39
Так. 12 попыток, из них около 10 - результат моей невнимательности. Что могу порекомендовать. Пользуйтесь тем, что уже изучили. У меня получилось около 50 строк кода, с учетом метода main. В main собрать строку, засплитить её ("\\s+" - на всякий случай, вдруг в тексте будет пробел на пробеле), передать в метод getLine. В методе у меня получилось 3 цикла while, два из которых используются в целях расширения возможных комбинаций. Следом один for, и уже внутри него алгоритм из 4-х if-ов: один на проверку наличия индекса слова в листе, в самом начале алгоритма, внутри третьего цикла, чтобы лишний раз не лезть на остальные if-ы; второй на проверку последнего символа в строке результат и первого символа в i-том слове; третий на проверку первого символа в строке результат и последнего символа в i-том слове; четвертый, вне цикла for и внутреннего while, на сравнение количества слов в только что собранной строке с количеством слов в result, при true переписывает result. очистка листа, по циклам ++, и на новый круг. В качестве условий выхода из циклов использовал размер принимаемого массива. Итого, к примеру для массива из пяти слов, составляется 25 различных комбинаций (при условии их возможности). Проверял на массиве из 25 слов. Результат не более 2 секунд. Будьте внимательны к выводимому тексту, около пяти попыток я исчерпал из-за того, что выводил не только требуемый текст, но и размеры передаваемых и принимаемых массивов (нужны были для проверки, забывал убрать). Если что, пишите, подскажу по своему алгоритму.