Делаем из мухи слона
Oct. 11th, 2009 03:26 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
thedeemonВчера давний друг, однокурсник, а ныне разработчик одной социальной сети, написал мне и другим нашим друзьям:
Я тут PHP-шников набираю, задаю всем одинаковое тестовое задание, чтобы присылали его вместе с резюме. Вот оно:
===============================================
Требуется написать программу, которая делает из "мухи" - "слона". Например:
муха -> мука -> рука -> руна -> ... -> слон
Т.е., меняя за 1 шаг по 1 букве, нужно из слова "муха" вывести слово "слон" и распечатать все шаги. Решите,
пожалуйста, задачу в этой постановке так, как сочтете нужным.
===============================================
Ощущение такое, что практически никто не может это нормально решить. Чего только не присылают...
Если у вас будет время, попробуйте, пожалуйста, решить данную задачку (на любом языке). А то я уже начинаю думать, может, я что-то не то спрашиваю...
А на днях я увидел упоминание этой задачки и там же вариант решения на PHP. Сначала не стал смотреть на решение и сделал свое, потом все же заглянул. И тогда я понял, что имел в виду автор письма.
Когда на работу устраиваются новички, это можно понять - с учетом низкого порога вхождения в РНР уровень среднего новичка там может быть сколь угодно низким. Но когда такие решения приходят от опытных вроде бы разработчиков, возникает ощущение, что все же РНР ест мозг.
Мой первый вариант на окамле получился довольно императивным, потом сделал более чистый, но все равно не без сайд эффектов. Подозреваю, что с помощью ленивости или CPS можно сотворить более красивое и чистое решение, однако быстро его придумать у меня не получилось...
Я тут PHP-шников набираю, задаю всем одинаковое тестовое задание, чтобы присылали его вместе с резюме. Вот оно:
===============================================
Требуется написать программу, которая делает из "мухи" - "слона". Например:
муха -> мука -> рука -> руна -> ... -> слон
Т.е., меняя за 1 шаг по 1 букве, нужно из слова "муха" вывести слово "слон" и распечатать все шаги. Решите,
пожалуйста, задачу в этой постановке так, как сочтете нужным.
===============================================
Ощущение такое, что практически никто не может это нормально решить. Чего только не присылают...
Если у вас будет время, попробуйте, пожалуйста, решить данную задачку (на любом языке). А то я уже начинаю думать, может, я что-то не то спрашиваю...
А на днях я увидел упоминание этой задачки и там же вариант решения на PHP. Сначала не стал смотреть на решение и сделал свое, потом все же заглянул. И тогда я понял, что имел в виду автор письма.
Когда на работу устраиваются новички, это можно понять - с учетом низкого порога вхождения в РНР уровень среднего новичка там может быть сколь угодно низким. Но когда такие решения приходят от опытных вроде бы разработчиков, возникает ощущение, что все же РНР ест мозг.
Мой первый вариант на окамле получился довольно императивным, потом сделал более чистый, но все равно не без сайд эффектов. Подозреваю, что с помощью ленивости или CPS можно сотворить более красивое и чистое решение, однако быстро его придумать у меня не получилось...
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2009-10-11 11:17 am (UTC)-- JL
no subject
Date: 2009-10-11 12:27 pm (UTC)http://hpaste.org/fastcgi/hpaste.fcgi/view?id=10615#a10616
no subject
Date: 2009-10-11 12:29 pm (UTC)no subject
Date: 2009-10-11 02:33 pm (UTC)Насчет декларативно: для меня это не антоним императивности, у меня это слово ассоциируется с наглядностью, самоописываемостью что-ли. В данном случае получилось чисто, функционально, но вот декларативно ли - не уверен. Но может быть у меня просто нет навыка читать хаскель.
no subject
Date: 2009-10-11 02:48 pm (UTC)Особенно прекрасно, что эти функции (fold/unfold) могут быть сгенерированы автоматически.
Хаскель отбил у меня желание заниматься преждевременной оптимизацией, в любом случае, мы можем без проблем отсеивать ненужное в построенном ленивом дереве. Я даже сначала что-то такое начал мудрить, а потом забросил, и так сработало.
no subject
Date: 2009-10-11 01:41 pm (UTC)no subject
Date: 2009-10-11 01:42 pm (UTC)no subject
Date: 2009-10-11 02:35 pm (UTC)2. Определенная связь между данной задачей и их реальным проектом есть - в социальной сети приходится искать цепочки в графе людей.
no subject
Date: 2009-10-14 03:46 pm (UTC)Мой пример
Date: 2009-10-12 04:53 am (UTC)У меня есть глобальные минусы в решении задачи?
$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;
}
решение
Date: 2009-10-12 04:55 am (UTC)$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;
}
Re: решение
Date: 2009-10-12 07:43 am (UTC)Мне как человеку, не пишущему на РНР, неочевиден смысл штук типа
array_flip(array_diff(array_flip($dict),array($stack['word'])));.
Я правильно понимаю, что тут идет поиск в глубину, стэк используется для хранения использованных слов, а $iteration не используется?
Код лучше пастить на сайты типа http://everfall.com/paste/, а то здесь теряется форматирование и портится удовольствие тем, кто захочет порешать задачку сам.
Re: решение
Date: 2009-10-12 07:50 am (UTC)На таком наборе слов мой нашел:
муха->муpа->туpа->таpа->каpа->каpе->кафе->кафp->
каюp->каюк->кpюк->уpюк->уpок->сpок->сток->стон->слон
no subject
Date: 2009-10-12 08:42 pm (UTC)no subject
Date: 2009-10-13 06:40 am (UTC)То, что идея более разумного решения потом посетила - это хорошо, но что поленился его реализовать - это плохо.
"был дан более быстрый вариант(на основе графа, но писать я его уже не стал)" - нонсенс, он был бы дан, если бы был написан.
no subject
Date: 2009-10-13 07:53 am (UTC)no subject
Date: 2009-10-13 10:01 am (UTC)Тогда зачем делалась оптимизация с $maxDiffLetters? :)
no subject
Date: 2009-10-13 06:26 pm (UTC)В pastebin только аглгоритм и билдер, ибо получилось довольно много кода :-) Написание заняло примерно минут 30-40.
http://www.everfall.com/paste/id.php?3j4sqr4fqkk6
p.s. Да, а ocaml мне определенно нравится :-)
no subject
Date: 2009-10-14 03:35 am (UTC)На РНР я не пишу, поэтому прошу извинить, если не правильно понял код.
Тут видно, что человек знаком с графами и знает слова "поиск в глубину", это очень хорошо.
Видно, что с ООП у него есть некоторые трудности, отчего нарушаются базовые принципы вроде SRP и это приводит к багам (при построении графа вершины добавляются несколько раз, массив вершин получается нормальный, а вот их число сильно завышено, но оно не используется и это ошибка дизайна - лишняя сущность).
Видно, что сам алгоритм поиска реализован неверно и на другом наборе данных запросто выдаст путь, где подряд будут идти несвязанные дугами вершины: в путь, который почему-то назван $visited, добавляются все вершины в порядке обхода, но если какая-то ветвь тупиковая, то идем обрабатывать другую ветвь, оставляя тупиковую ветвь в пути (тут будет прыжок). Если же требуемый путь в графе не существует, то вместо соответствующей ошибки выдается путь блуждания по всему подграфу, что уж точно неправильно. На данном наборе данных это не проявляется и можно и забить, но зачем тогда делать вид, что работа с графами сделана общо и универсально.
Т.е. с одной стороны есть некий оверинжиниринг - обобщение за пределы данной задачи, отсюда много кода, а с другой стороны он недоделан и все работает только на ней. Если работает, конечно.
no subject
Date: 2009-10-14 09:54 am (UTC)А вот насчет отсального ни разу. Массив вершин, на самом деле не массив а map
А вот насчет отсального ни разу. Массив вершин, на самом деле не массив а map<id, Vertext>. И лишних вершин там нет. Но проверку на существование добавить не помешает.
Про нарушение SRP не понял. Все сущности вроде вполне обоснованы? Edge - ребро. Vertex - вершина. Graph - граф.
no subject
Date: 2009-10-14 10:53 am (UTC)Она увеличивается, даже если вершина уже была и не добавляется. Но потом не используется - лишняя сущность.
no subject
Date: 2009-10-14 03:39 pm (UTC)http://www.everfall.com/paste/id.php?cx6jjqtbuflz
Алгоритм и правда оказался тривиальным. Спасибо за code review.
no subject
Date: 2009-10-14 04:09 pm (UTC)А какая логика скрывается за строкой 95?
Идея с общей реализацией depthFirstSearch и breadthFirstSearch интересная, но этот код не используется, как я понял. И в нем старые ошибки с прыжками в пути и выдачей бреда если путь не найден. Также, неясен смысл строк 130-131.
И что бы ты сказал кандидату, который пишет что-то разумное с третьей попытки и делает такие косяки? ;)
no subject
Date: 2009-10-14 04:44 pm (UTC)130-131, да и 90 - артефакты.
Что же касается кандидатуры, то я к вашему товарищу на собеседование уже ходил :-) И вроде как его прошел, так как был приглашен на "второй тур", но отказался.
p.s. Просто освежил немного в голове теорию графов и все. Доказывать кому-то чего-то совершенно и не собирался :-)
no subject
Date: 2009-10-14 06:35 pm (UTC)no subject
Date: 2009-10-14 06:54 pm (UTC)no subject
Date: 2009-10-25 10:11 pm (UTC)- 80 присылают примеры кода и решение задачи
- 15 приглашаются на 1-е интервью
- 7 приглашаются на 2-е интервью
- 2 приглашаются на 3-е интервью
- 1 принимается на работу
no subject
Date: 2009-10-14 12:43 pm (UTC)no subject
Date: 2009-10-14 09:15 am (UTC)Тут подразумевается, что malloc обнуляет выделенную память? Кажется, это не везде гарантировано.
Ответ выводится задом-наперед?
Константы-ограничения на число слов и связей немного расстраивают - другой словарь может потребовать подгонки программы.
Ну и сложность алгоритма неидеальная - поиск в ширину все же лучше.
Cha-Ching
Date: 2009-10-15 11:32 am (UTC)Re: Cha-Ching
Date: 2009-10-15 02:42 pm (UTC)Чисто грамматическая ремарка: word exists - подлежащее и сказуемое, is там лишнее.