Электростальский форум
Hi-Tech => Компьютеры, периферия, мультимедиа и ПО => Тема начата: md# от 10.10.09, 12:03:35
-
Задача
Имеется слово "муха".
Необходимо превратить в слово "слон".
Путем изменения 1 буквы.
Например, муха -> мука -> рука -> ... -> слон
Словарь для подбора слов - http://forum.elsite.ru/Downloads/books/dic.zip (http://forum.elsite.ru/Downloads/books/dic.zip)
Необходимо написать решение на любом языке программирования, преимущественно C++, C#, Obj-C, Python, Perl, PHP, Java.
Ветка преобразований по данному словарю насчитывает 456 слов.
Первому решившему - ключ для Windows 7 Ultimate из моей MSDN подписки.
Решение должно быть рабочим и оптимальным.
-
в словаре не только 4х буквенные слова - добавлять буквы нельзя?
так же там слова с буквами в разных регистрах - А и а - считать одной и той же буквой?
-
У меня нет прав на загрузку этого словаря, но задача преобразования из муха->слон является классической и цепочка преобразований не насчитывает более 20 этапов. В зависимости от степени паршивости словаря может быть и меньше. Что за словать такой ?
-
в словаре не только 4х буквенные слова - добавлять буквы нельзя?
так же там слова с буквами в разных регистрах - А и а - считать одной и той же буквой?
Муха --> Мука --> Сука --> Сук --> Сок --> Сон --> Слон
-
Муха --> Мука --> Сука --> Сук --> Сок --> Сон --> Слон
Незачет. Букв должно быть всегда четыре.
-
Незачет. Букв должно быть всегда четыре.
Ну да.
А Вы что, не верите, что я знаю решение данной задачи для слов из четырёх букв ?
Там слова получаются хитрые, не во всяком словаре есть. Поэтому и спрашиваю, что за словарь.
В любом случае, цепочка из 400 слов - это маразм. 20 - реальная цифра.
-
Нервный, дайте попробовать тем, кто не очень умеет программировать)
муха -> чуха -> чоха -> доха -> соха -> саха -> саха -> сага -> вага -> гага -> нага -> рага -> чага -> чара -> вара -> жара -> кара -> мара -> пара -> тара -> фара -> хара -> хора -> бора -> гора -> дора -> кора -> мора -> нора -> пора -> тора -> фора -> шора -> шура -> аура -> бура -> дура -> кура -> лура -> мура -> сура -> тура -> фура -> фуга -> дуга -> куга -> нуга -> руга -> шуга -> шуба -> губа -> луба -> туба -> туда -> дуда -> зуда -> иуда -> куда -> луда -> нуда -> руда -> рада -> лада -> лада -> леда -> беда -> деда -> дева -> дева -> дива -> нива -> нива -> шива -> шина -> вина -> дина -> мина -> тина -> хина -> чина -> чинк -> линк -> ринк -> риск -> рыск -> рысь -> высь -> весь -> ведь -> медь -> мель -> бель -> гель -> лель -> сель -> тель -> таль -> даль -> жаль -> паль -> шаль -> шале -> дале -> доле -> поле -> пола -> зола -> кола -> кила -> вила -> жила -> пила -> сила -> фила -> фига -> гига -> жига -> лига -> рига -> риза -> виза -> ваза -> база -> фаза -> фата -> вата -> дата -> ката -> хата -> цата -> цаца -> маца -> мака -> кака -> рака -> река -> дека -> чека -> чека -> щека -> щука -> бука -> лука -> мука -> рука -> сука -> сума -> дума -> дума -> кума -> пума -> чума -> чуфа -> гуфа -> гута -> рута -> тута -> тета -> бета -> кета -> лета -> лета -> мета -> чета -> четь -> деть -> петь -> сеть -> суть -> дуть -> жуть -> муть -> путь -> чуть -> чать -> гать -> дать -> жать -> мать -> рать -> тать -> таты -> гаты -> латы -> лады -> лазы -> тазы -> тази -> гази -> кази -> кави -> кади -> вади -> ради -> рами -> вами -> важи -> вали -> кали -> пали -> поли -> доли -> коли -> кули -> пули -> пуло -> дуло -> дело -> вело -> зело -> село -> тело -> теле -> желе -> реле -> ребе -> бебе -> себе -> тебе -> тебя -> себя -> семя -> темя -> тема -> нема -> рема -> сема -> сима -> сома -> дома -> кома -> лома -> нома -> нога -> гога -> йога -> йота -> нота -> рота -> хота -> хода -> вода -> кода -> мода -> сода -> сова -> сона -> вона -> дона -> зона -> нона -> ноша -> ниша -> миша -> мира -> вира -> лира -> липа -> кипа -> пипа -> папа -> капа -> лапа -> рапа -> сапа -> тапа -> тама -> дама -> лама -> мама -> рама -> рама -> раба -> баба -> даба -> жаба -> жабо -> сабо -> саго -> маго -> мало -> гало -> жало -> зало -> рало -> сало -> соло -> коло -> поло -> подо -> бодо -> водо -> воды -> веды -> кеды -> кеты -> геты -> готы -> боты -> коты -> ноты -> соты -> соры -> боры -> горы -> поры -> хоры -> хары -> дары -> лары -> нары -> нард -> бард -> дард -> дари -> лари -> мари -> пари -> сари -> саки -> баки -> даки -> каки -> лаки -> маки -> паки -> пики -> пити -> сити -> сати -> соти -> сони -> пони -> пани -> рани -> сани -> сени -> пени -> тени -> тент -> мент -> сент -> цент -> цена -> вена -> жена -> иена -> мена -> пена -> пуна -> буна -> куна -> луна -> лана -> кана -> мана -> рана -> хана -> хала -> гала -> зала -> мала -> пала -> пава -> лава -> лажа -> лёжа -> ложа -> кожа -> рожа -> роба -> роза -> доза -> коза -> лоза -> поза -> пока -> дока -> кока -> лока -> локо -> лоно -> моно -> фоно -> форо -> лоро -> моро -> хоро -> хорт -> борт -> корт -> порт -> сорт -> торт -> форт -> фарт -> гарт -> карт -> март -> парт -> пакт -> такт -> факт -> фант -> бант -> кант -> кант -> рант -> раит -> раут -> раус -> ракс -> факс -> фикс -> бикс -> кикс -> кекс -> кокс -> бокс -> фокс -> форс -> ворс -> морс -> торс -> тирс -> тире -> шире -> ширь -> шить -> бить -> вить -> жить -> лить -> нить -> пить -> пять -> зять -> мять -> мыть -> быть -> выть -> ныть -> рыть -> сыть -> сыпь -> сырь -> пырь -> пыль -> быль -> боль -> голь -> золь -> коль -> моль -> ноль -> поль -> роль -> соль -> толь -> топь -> лопь -> ложь -> ломь -> лось -> лоск -> воск -> волк -> полк -> полу -> долу -> долг -> донг -> гонг -> зонг -> сонг -> сонм -> сонь -> вонь -> конь -> корь -> хорь -> хоть -> хошь -> вошь -> вишь -> бишь -> лишь -> тишь -> тушь -> сушь -> чушь -> чудь -> нудь -> нуль -> буль -> куль -> киль -> кило -> било -> жило -> шило -> шизо -> сизо -> сито -> жито -> фито -> фото -> лото -> лето -> вето -> вено -> рено -> сено -> сен- -> сень -> день -> лень -> пень -> тень -> темь -> земь -> семь -> сечь -> жечь -> лечь -> печь -> речь -> сечь -> сеча -> неча -> нега -> бега -> вега -> мега -> межа -> вежа -> вера -> гера -> мера -> сера -> серп -> верп -> шерп -> шерл -> перл -> пери -> перо -> пежо -> пезо -> безо -> безе -> бозе -> боже -> ложе -> тоже -> туже -> туше -> суше -> суша -> душа -> туша -> туча -> буча -> куча -> муча -> муза -> буза -> луза -> лужа -> лупа -> жупа -> жопа -> копа -> коса -> роса -> раса -> ласа -> леса -> лиса -> киса -> кика -> вика -> ника -> пика -> пита -> бита -> кита -> фита -> фифа -> фифи -> фифо -> лифо -> либо -> любо -> люба -> люфа -> люфт -> лифт -> лист -> аист -> вист -> вест -> бест -> гест -> жест -> пест -> тест -> шест -> шуст -> дуст -> куст -> руст -> фуст -> фунт -> бунт -> бинт -> винт -> финт -> фиат -> флат -> блат -> плат -> плот -> глот -> слот -> слон
-
в словаре 2360 слов из 4х букв, включая слона и муху
длина цепочки = муха + 624 слова + слон = 626 слов
-
в словаре 2360 слов из 4х букв, включая слона и муху
длина цепочки = муха + 624 слова + слон = 626 слов
Херня. Словарь в студию.
Единственное сомнение у меня было в слове "мура". 15 слов в цепочке.
-
длина цепочки с условием не сошлась...
корявый имплементейшн на скорую руку прикреплен.
по алгоритмам книжек не читал, даже кнутта, поэтому, вероятно, код не самый быстрый и правильный...
vb.net 2008
в папке debug скомпиленная прога и словарь, выложенный автором.
-
На самом деле 626 слов это наверно даже лучше=)
Я решал эту задачу на PHP на собеседовании, с использованием этого же словаря.
Моя цепочка была муха + 455 слов + слон. Ну или 456 не считая мухи.
Решение назвали единственно верным, после чего я решил, что больше 456 быть не может.
-
усложним, из слова ЖОПА нада сделать слово СЧАСТЬЕ :ag:
-
Орфографический словарь п/р проф. Лопатина (2000 год)
Последняя редакция (163294 статьи) 31.01.03
http://dict.buktopuha.net/lop2v2.zip (http://dict.buktopuha.net/lop2v2.zip)
-
На самом деле 626 слов это наверно даже лучше=)
Я решал эту задачу на PHP на собеседовании, с использованием этого же словаря.
Моя цепочка была муха + 455 слов + слон. Ну или 456 не считая мухи.
Решение назвали единственно верным, после чего я решил, что больше 456 быть не может.
а у меня не ищется самая короткая цепочка... вот, например, франгмент:
"река -> дека -> чека -> чека -> щека"
почему-то чека два раза, да и вообще всю цепочку можно заменить на "река -> щека"
Update: проверил исходный словарь. 2360 4х-буквенных слов, из которых только 2332 неповторяющихся :)
у меня алгоритм перебирает все варианты по порядку, и останавливается на первом подходящем...
можно попробовать удалить из результата такие вот лишние преобразования, есть вероятность, что тогда результаты сойдутся. Надо?
-
усложним, из слова ЖОПА нада сделать слово СЧАСТЬЕ :ag:
:ap: :ag:
Чем только люди не заморачиваются... :ag:
-
Я не знаю, как у вас получаются такие цифры.
Мой алгоритм уже нашёл цепочку из 52 слов. Надо ещё подождать, найдет короче. Вообще, правильный ответ, как я уже говорил, лежит в районе 15 слов.
-
Вот, цепочку из 22 слов нашёл.
муза
мука
муки
маки
саки
каки
хаки
таки
маки
баки
каки
кади
кадр
каюр
каюк
каик
клик
клык
клок
клон
слон
как-то так. Core i7 считает медленно.
-
ну я не искал самую короткую цепочку.
мой алгоритм прекращал работу когда находил первую ветку, которая кончается слоном.
муза => буза => база => баба => даба => дабы => дыбы => дыба => дыра => дора => бора => борт => болт => боль => бель => бели => беби => бебе => безе => безо => мезо => пезо => пежо => перо => зеро => зело => вело => вено => вена => вежа => вера => вара => вага => ваза => вата => дата => дама => дача => чача => чага => гага => гала => гало => газо => гази => кази => кави => кади => вади => важи => вали => вами => нами => рами => ради => рада => лада => лава => лавр => ливр => литр => лить => бить => бит- => бита => бета => бега => беда => деда => дева => дежа => деза => дека => дока => доза => дома => дона => вона => вина => виза => вика => вила => вилт => винт => бинт => бант => байт => бейт => бест => вест => весы => весь => ведь => веди => леди => педи => пени => пани => паки => баки => буки => бука => букс => бикс => бокс => босс => косс => кокс => кекс => кейс => кейф => сейф => сейв => рейв => рейд => рейс => пейс => пенс => пена => жена => иена => мена => мана => кана => кака => каки => даки => дари => дард => бард => барк => банк => панк => паёк => парк => пара => жара => жаба => жабо => жако => жало => жаль => даль => дале => доле => долг => доли => долу => доля => воля => волк => воск => лоск => лось => ложь => ложа => кожа => кода => вода => водо => Бодо => додо => подо => поди => поли => коли => кали => кули => куль => буль => буле => фуле => филе => фила => жила => жига => гига => гога => гора => горб => герб => герр => герц => Герц => Гера => мера => мара => кара => капа => ката => кафа => кафе => каре => карп => карт => гарт => гарь => гать => дать => дань => день => деть => дуть => дурь => дура => аура => бура => буна => бунт => бурт => бург => бурш => буры => боры => боны => бонд => зонд => зона => зола => зала => зало => мало => маго => мано => манс => маис => марс => барс => барн => баро => таро => тара => тама => лама => лажа => лана => ланч => лань => ларь => лари => лаки => маки => мака => мала => мама => маца => цаца => цата => фата => фаза => фара => фарм => фарс => факс => ракс => рака => раба => рага => нага => нега => Вега => мега => межа => меса => леса => ласа => лапа => лафа => люфа => люба => луба => губа => гута => гуфа => гуща => гуще => пуще => пуща => куща => куга => дуга => дуда => дума => Дума => кума => кома => коза => кока => кика => кикс => фикс => фокс => форс => ворс => морс => мора => кора => кола => кила => кило => било => жило => живо => диво => дива => дина => мина => мини => вини => виги => виши => вишь => бишь => лишь => линь => лень => лечь => жечь => печь => пень => пеня => меня => мент => Сент => тент => тени => сени => сани => рани => рана => рама => рамс => рапс => рапа => папа => пава => пала => пали => палм => паль => падь => кадь => кадр => каюр => каюк => каик => каяк => кряк => бряк => брак => арак => арап => арат => агат => агар => авар => увар => увал => овал => опал => опад => опак => шпак => шлак => злак => знак => зрак => мрак => трак => трал => трап => драп => драм => драч => врач => грач => граб => град => глад => глаз => плаз => план => клан => клав => клад => слад => слаг => слог => глог => глот => глёт => влёт => слёт => слот => плот => плат => блат => брат => брас => брус => прус => пруд => пред => бред => брег => брек => дрек => дрок => дром => бром => брод => Ирод => урод => увод => ввод => ввоз => своз => свод => овод => обод => обед => обер => опер => опор => спор => сбор => сбой => свой => своп => скоп => окоп => окот => скот => скат => сват => свал => свая => стая => став => стаж => стаз => сказ => скак => скок => сков => скол => скос => икос => укос => укол => угол => угон => огон => сгон => сион => слон
-
Вот, цепочку из 22 слов нашёл.
муза
мука
муки
маки
саки
каки
хаки
таки
маки
баки
каки
кади
кадр
каюр
каюк
каик
клик
клык
клок
клон
слон
как-то так. Core i7 считает медленно.
Используя НЕСУЩЕСТВУЮЩИЕ слова можно что хочешь насочинять.
каки, таки, хаки, саки - это чего такое есть на самом деле?
и слово маки два раза...
-
Используя НЕСУЩЕСТВУЮЩИЕ слова можно что хочешь насочинять.
каки, таки, хаки, саки - это чего такое есть на самом деле?
и слово маки два раза...
Эти слова из данного словаря.
Они там есть, проверьте сами.
Вот ещё короче и без этих слов.
муча
буча
бура
бурт
бунт
фунт
финт
фиат
флат
флот
глот
слот
слон
-
В общем, у кого мощные машины - считайте сами.
А откуда тупые преподы насчитали цепочку аж в 456 слов - остаётся только догадываться. И почему именно 456, а не 822, интересно.
Как всегда, нашли где-то задачу и задают её, сами не зная правильного решения.
-
А откуда тупые преподы насчитали цепочку аж в 456 слов - остаётся только догадываться. И почему именно 456, а не 822, интересно.
Как всегда, нашли где-то задачу и задают её, сами не зная правильного решения.
Это не преподы, это собеседование на работу.
456 слов - это цепочка найденная мною и названная ими единственно верным решением, из чего я решил, что 456 слов это эталон. Упор делался на качество, то есть чем больше слов, тем лучше. А мне было просто интересно развить тему дальше.
Кстати Ваш пример так и не посчитался у меня, прошло 15 минут. C2D E6600.
Так как первым решил LEO, ключ уходить ему, если никто не против=)
-
Упор делался на качество, то есть чем больше слов, тем лучше.
Кстати Ваш пример так и не посчитался у меня, прошло 15 минут. C2D E6600.
там появляется циферка 13, а на диске появляется chain13.txt
17сек на C2D E8200 @ 3.4GHz
... и мне кажется логичным, что чем короче цепочка, тем лучше. длинную-то найти не проблема))) можно даже специально повторяющихся подцепей вставить :)
Нервный, а киньте линк какой-нить на матчасть
-
Это не преподы, это собеседование на работу.
456 слов - это цепочка найденная мною и названная ими единственно верным решением, из чего я решил, что 456 слов это эталон. Упор делался на качество, то есть чем больше слов, тем лучше. А мне было просто интересно развить тему дальше.
Кстати Ваш пример так и не посчитался у меня, прошло 15 минут. C2D E6600.
Так как первым решил LEO, ключ уходить ему, если никто не против=)
Надо смотреть файлики, которые он создаёт. На Core i7 первое решение из 14 шагов находится за несколько секунд.
Если чем больше слов, тем лучше, то первое решение моего алгоритма - восемь тысяч шагов с чем-то. Я отключил вывод решений длиной более 100 слов, чтобы не зафлудить директорию.
На самом деле, самое оптимальное решение - самое быстрое. Поэтому, верное решение - естественно, моё. А тупой работодатеть - гораздно хуже тупого препода.
-
я в первый раз не учел, что в словаре могут быть одинаковые слова. Если повторяющиеся слова перед поиском отбросить, то
время начала (первая строчка кода) 16:37:28.4611602
начало поиска 16:37:28.4961602
поиск завершен 16:37:28.6761602
результат - 580 слов, не так много, как 8000, и не очень медленно)
без dic.txt
-
Нервный, а киньте линк какой-нить на матчасть
Нет там никакой матчасти. Тупой перебор и отбраковка заведомо слишком длинных цепочек.
Подозреваю, что изначально данная задача была на хеш-функции. Определение факта вхождения слова в словарь - классичекая демонстрация возможностей хеширования. Но похоже, что пройдя через через не очень умных людей, она превратилась в поиск цепочек из сотни слов.
Если бы компьютеры были попроще, типа 4 Mhz/16 бит, без хеширования данная задача за разумные сроки не решалась бы. Ну а сейчас что париться-то.