Делаем из мухи слона
Очень часто мне в голову приходят всякие дурацкие вопросы: “Сколько ангелов разместится на конце иглы?” или “Какова общая переплата по кредиту на 10 лет?” Ответы на некоторые из этих вопросов можно легко получить, написав совсем небольшую программку.
Вот и недавно мне подумалось, что можно написать программу, которая будет решать старую задачку, делать из слова “муха” слово “слон”, меняя на каждом шаге не более одной буквы, так чтобы получалось новое слово. Например, из слона плед можно сделать довольно просто: слон-слот-плот-плод-плед. А вот из мухи слона сделать у меня без компьютера не получилось. Поэтому я решил написать программку, а заодно потренироваться в новой технологии LINQ. Исходный текст программы можно скачать тут.
Общая идея была самая примитивная: от основного слова выбираем соседей, потом соседей соседей, потом соседей этих соседей и так, пока не найдется финальное слово. Все найденные слова-соседи маркируются указанием слова-родителя. В коде это выглядит очень просто:
43 public IEnumerable<WordItem> Step(WordItem item)
44 {
45 var neighbours = items.Where(s => (s - item) == 1 // На расстоянии 1
46 && s.parent == null).ToArray(); // И еще не посчитаны
47 foreach (var n in neighbours) n.parent = item; // Установим родителя
48 return neighbours;
49 }
А после остается уже совсем тривиальная работа по итеративному вызову этой функции и поиску в результате нужного слова:
59 generation = generation.SelectMany(m => Step(m)).ToArray(); // Получим следующее поколение
60 var endWord = generation.Where(w => w == secondWord).FirstOrDefault(); // Поищем, нет ли финального слова
Конечно, вокруг еще довольно много всякой возни с составлением набора четырехбуквенных слов (оказалось очень непросто найти нормальный словарь), поиском первого слова, выводом результирующей последовательности и т.д. Но все равно удивительно, что вообщем-то вся программа, благодаря LINQ, поместилась в четыре строчки! И вообще в программе много мест, которые LINQ позволяет записать просто удивительно компактно.
В реальных проектах, кстати, ситуация такая же: с появлением LINQ большие куски просто выкидываются и заменяются крошечными запросами. Не все так просто, к сожалению, но об этом лучше потом... Пусть первый пост журнала будет позитивным. :)
Ну и, конечно, напишу результат поисков. Цепочка получилась такая:
муха-мура-фура-фара-фарт-факт-пакт-паут-плут-плот-плод-плед-плен-клен-клон-слон