Сделать из мухи слона

[md#]

Задача

Имеется слово "муха".
Необходимо превратить в слово "слон".
Путем изменения 1 буквы.
Например, муха -> мука -> рука -> ... -> слон
Словарь для подбора слов - http://forum.elsite.ru/Downloads/books/dic.zip

Необходимо написать решение на любом языке программирования, преимущественно C++, C#, Obj-C, Python, Perl, PHP, Java.
Ветка преобразований по данному словарю насчитывает 456 слов.

Первому решившему - ключ для Windows 7 Ultimate из моей MSDN подписки.
Решение должно быть рабочим и оптимальным.

[Нервный]

 В общем, у кого мощные машины - считайте сами.
 А откуда тупые преподы насчитали цепочку аж в 456 слов - остаётся только догадываться. И почему именно 456, а не 822, интересно.
 Как всегда, нашли где-то задачу и задают её, сами не зная правильного решения.

[md#]

А откуда тупые преподы насчитали цепочку аж в 456 слов - остаётся только догадываться. И почему именно 456, а не 822, интересно.
 Как всегда, нашли где-то задачу и задают её, сами не зная правильного решения.

Это не преподы, это собеседование на работу.
456 слов - это цепочка найденная мною и названная ими единственно верным решением, из чего я решил, что 456 слов это эталон. Упор делался на качество, то есть чем больше слов, тем лучше. А мне было просто интересно развить тему дальше.

Кстати Ваш пример так и не посчитался у меня, прошло 15 минут. C2D E6600.

Так как первым решил LEO, ключ уходить ему, если никто не против=)

[LEO]

Упор делался на качество, то есть чем больше слов, тем лучше.

Кстати Ваш пример так и не посчитался у меня, прошло 15 минут. C2D E6600.

там появляется циферка 13, а на диске появляется chain13.txt
17сек на C2D E8200 @ 3.4GHz

... и мне кажется логичным, что чем короче цепочка, тем лучше. длинную-то найти не проблема))) можно даже специально повторяющихся подцепей вставить

Нервный, а киньте линк какой-нить на матчасть

[Нервный]

Это не преподы, это собеседование на работу.
456 слов - это цепочка найденная мною и названная ими единственно верным решением, из чего я решил, что 456 слов это эталон. Упор делался на качество, то есть чем больше слов, тем лучше. А мне было просто интересно развить тему дальше.

Кстати Ваш пример так и не посчитался у меня, прошло 15 минут. C2D E6600.

Так как первым решил LEO, ключ уходить ему, если никто не против=)

 Надо смотреть файлики, которые он создаёт. На Core i7 первое решение из 14 шагов находится за несколько секунд.
 Если чем больше слов, тем лучше, то первое решение моего алгоритма - восемь тысяч шагов с чем-то. Я отключил вывод решений длиной более 100 слов, чтобы не зафлудить директорию.
 На самом деле, самое оптимальное решение - самое быстрое. Поэтому, верное решение - естественно, моё. А тупой работодатеть - гораздно хуже тупого препода.

[LEO]

я в первый раз не учел, что в словаре могут быть одинаковые слова. Если повторяющиеся слова перед поиском отбросить, то

время начала (первая строчка кода) 16:37:28.4611602
начало поиска 16:37:28.4961602
поиск завершен 16:37:28.6761602

результат - 580 слов, не так много, как 8000, и не очень медленно)

без dic.txt

[Нервный]

Нервный, а киньте линк какой-нить на матчасть

 Нет там никакой матчасти. Тупой перебор и отбраковка заведомо слишком длинных цепочек.
 Подозреваю, что изначально данная задача была на хеш-функции. Определение факта вхождения слова в словарь - классичекая демонстрация возможностей хеширования. Но похоже, что пройдя через через не очень умных людей, она превратилась в поиск цепочек из сотни слов.
 Если бы компьютеры были попроще, типа 4 Mhz/16 бит, без хеширования данная задача за разумные сроки не решалась бы. Ну а сейчас что париться-то.