Делаем из мухи слона

[thedeemon]

Вчера давний друг, однокурсник, а ныне разработчик одной социальной сети, написал мне и другим нашим друзьям:

Я тут PHP-шников набираю, задаю всем одинаковое тестовое задание, чтобы присылали его вместе с резюме. Вот оно:

===============================================
Требуется написать программу, которая делает из "мухи" - "слона". Например:

муха -> мука -> рука -> руна -> ... -> слон

Т.е., меняя за 1 шаг по 1 букве, нужно из слова "муха" вывести слово "слон" и распечатать все шаги. Решите,
пожалуйста, задачу в этой постановке так, как сочтете нужным.
===============================================

Ощущение такое, что практически никто не может это нормально решить. Чего только не присылают...

Если у вас будет время, попробуйте, пожалуйста, решить данную задачку (на любом языке). А то я уже начинаю думать, может, я что-то не то спрашиваю...

А на днях я увидел упоминание этой задачки и там же вариант решения на PHP. Сначала не стал смотреть на решение и сделал свое, потом все же заглянул. И тогда я понял, что имел в виду автор письма.
Когда на работу устраиваются новички, это можно понять - с учетом низкого порога вхождения в РНР уровень среднего новичка там может быть сколь угодно низким. Но когда такие решения приходят от опытных вроде бы разработчиков, возникает ощущение, что все же РНР ест мозг.

Мой первый вариант на окамле получился довольно императивным, потом сделал более чистый, но все равно не без сайд эффектов. Подозреваю, что с помощью ленивости или CPS можно сотворить более красивое и чистое решение, однако быстро его придумать у меня не получилось...

Comments

[(Anonymous)]

Так вот почему в мой блог периодически приходят по поисковому запросу "как из мухи сделать слона PHP". Это они работу ищут!

-- JL

[voidex.livejournal.com]

Вот декларативно: развертка в дерево + свертка в список и вуаля

http://hpaste.org/fastcgi/hpaste.fcgi/view?id=10615#a10616

[volodymir-k.livejournal.com]

Спорю на бутылку коньяка, что из 100 программистов такие задачи для реального бизнеса будет решать один и раз в20 лет.

Мой пример

[(Anonymous)]

Мне кажется я решил достаточно хорошо эту задачу. Но чел вроде сначала предложил встретится, я попросил отложить встречу и чел пропал.
У меня есть глобальные минусы в решении задачи?

$current,'next'=>array());
process($dict ,$current,$end,$stack);
echo "МУХА\n";
exit(0);


function process($dict ,$current,$end,$stack,$iteration=0){
$dict = array_flip(array_diff(array_flip($dict),array($stack['word'])));
$result= getWords($dict,$current);
foreach($result as $item){
$new_item = process($dict ,$item['word'],$end,$item,++$iteration);
if($new_item === false){ echo $item['word'].'<='; return false;}
$item = $new_item;
$stack['next'][] = $item;
if($item['word'] === 'слон'){ echo 'СЛОН<='; return false;}
}
return $stack;
}



function getWords($words,$etalon){
$result = array();
foreach($words as $w=>$x){
$diff = 0;
for($i = 0; $i<4; ++$i)
{
if(mb_substr($w,$i,1,'utf-8')!=mb_substr($etalon,$i,1,'utf-8')) ++$diff;
}
if($diff === 1) $result[] = array('word'=>$w,'next'=>array());
}
return $result;
}

решение

[(Anonymous)]

$words = ' мука туpа стоп попа кола стол пирс флуд лужа сpок хлеб уран уpок форс фляг слон стек круг каpа кафе каюp куль заря уpюк папа дурь скан кура дуля море таpа соки лист муpа вода бриф зола каpе шуба крэк бриз таpа уpюк кафp стул стон уpок буль доха стон деда кpюк пуля туpа мула вист клан мама кило крюк торс каша мало сток кpюк каpе пиво дура киса горе каpа бяка кафе мера сpок морс каюк флаг кафp хала каюp каюк слон мура сток лажа стук софа';

$dict = array_unique(explode(' ',$words));

shuffle($dict);
$dict = array_flip($dict);
$start = 'муха';
$end = 'слон';
$stack = array();
$current = $start;
$counter = 0;
$stack = array('word'=>$current,'next'=>array());
process($dict ,$current,$end,$stack);
echo "МУХА\n";
exit(0);


function process($dict ,$current,$end,$stack,$iteration=0){
$dict = array_flip(array_diff(array_flip($dict),array($stack['word'])));
$result= getWords($dict,$current);
foreach($result as $item){
$new_item = process($dict ,$item['word'],$end,$item,++$iteration);
if($new_item === false){ echo $item['word'].'<='; return false;}
$item = $new_item;
$stack['next'][] = $item;
if($item['word'] === 'слон'){ echo 'СЛОН<='; return false;}
}
return $stack;
}



function getWords($words,$etalon){
$result = array();
foreach($words as $w=>$x){
$diff = 0;
for($i = 0; $i<4; ++$i)
{
if(mb_substr($w,$i,1,'utf-8')!=mb_substr($etalon,$i,1,'utf-8')) ++$diff;
}
if($diff === 1) $result[] = array('word'=>$w,'next'=>array());
}
return $result;
}

[gabaidulin.livejournal.com]

Решение мое. И написано было за двадцать минут. А немного позже был дан более быстрый вариант(на основе графа, но писать я его уже не стал). И в чем тогда причина наезда, да еще и так глобально? :-)

[gabaidulin.livejournal.com]

Ддя небольшого словаря такая гарантия есть(в основе генерации равномерное распределение, а кол-во вариантов сильно зависит от словаря). Про кучи неоптимальных функций - не это субъективное мнение. Забавно читатать про оптимизацию, когда я уже в 10-ый раз вам написал что это просто прототип :-)

[gabaidulin.livejournal.com]

Чтобы подытожить всю машну, приведу решение и на графах. Используеся поиск в глубину.

В pastebin только аглгоритм и билдер, ибо получилось довольно много кода :-) Написание заняло примерно минут 30-40.

http://www.everfall.com/paste/id.php?3j4sqr4fqkk6

p.s. Да, а ocaml мне определенно нравится :-)

Cha-Ching

[signate (from livejournal.com)]

мой вариант http://www.everfall.com/paste/id.php?397gs9dnwn61