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

[thedeemon]

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

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

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

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

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

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

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

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

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

Comments

[thedeemon.livejournal.com]

Спасибо! Уже гораздо лучше и интересней!
На РНР я не пишу, поэтому прошу извинить, если не правильно понял код.

Тут видно, что человек знаком с графами и знает слова "поиск в глубину", это очень хорошо.

Видно, что с ООП у него есть некоторые трудности, отчего нарушаются базовые принципы вроде SRP и это приводит к багам (при построении графа вершины добавляются несколько раз, массив вершин получается нормальный, а вот их число сильно завышено, но оно не используется и это ошибка дизайна - лишняя сущность).

Видно, что сам алгоритм поиска реализован неверно и на другом наборе данных запросто выдаст путь, где подряд будут идти несвязанные дугами вершины: в путь, который почему-то назван $visited, добавляются все вершины в порядке обхода, но если какая-то ветвь тупиковая, то идем обрабатывать другую ветвь, оставляя тупиковую ветвь в пути (тут будет прыжок). Если же требуемый путь в графе не существует, то вместо соответствующей ошибки выдается путь блуждания по всему подграфу, что уж точно неправильно. На данном наборе данных это не проявляется и можно и забить, но зачем тогда делать вид, что работа с графами сделана общо и универсально.

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

[gabaidulin.livejournal.com]

Насчет прыжка - согласен. Есть такая ошибка.

А вот насчет отсального ни разу. Массив вершин, на самом деле не массив а map

[Error: Irreparable invalid markup ('<id,>') in entry. Owner must fix manually. Raw contents below.]

Насчет прыжка - согласен. Есть такая ошибка.

А вот насчет отсального ни разу. Массив вершин, на самом деле не массив а map<id, Vertext>. И лишних вершин там нет. Но проверку на существование добавить не помешает.

Про нарушение SRP не понял. Все сущности вроде вполне обоснованы? Edge - ребро. Vertex - вершина. Graph - граф.

[thedeemon.livejournal.com]

Я имел в виду ++$this->verticiesCount;
Она увеличивается, даже если вершина уже была и не добавляется. Но потом не используется - лишняя сущность.

[gabaidulin.livejournal.com]

Исправленная версия:
http://www.everfall.com/paste/id.php?cx6jjqtbuflz

Алгоритм и правда оказался тривиальным. Спасибо за code review.

[thedeemon.livejournal.com]

Ну вот, уже лучше!
А какая логика скрывается за строкой 95?

Идея с общей реализацией depthFirstSearch и breadthFirstSearch интересная, но этот код не используется, как я понял. И в нем старые ошибки с прыжками в пути и выдачей бреда если путь не найден. Также, неясен смысл строк 130-131.

И что бы ты сказал кандидату, который пишет что-то разумное с третьей попытки и делает такие косяки? ;)

[gabaidulin.livejournal.com]

depthFirstSearch & breadthFirstSearch - это просто функции обхода графа.

130-131, да и 90 - артефакты.

Что же касается кандидатуры, то я к вашему товарищу на собеседование уже ходил :-) И вроде как его прошел, так как был приглашен на "второй тур", но отказался.

p.s. Просто освежил немного в голове теорию графов и все. Доказывать кому-то чего-то совершенно и не собирался :-)

[signate (from livejournal.com)]

Немного оффтопика. А нафига нужны эти бредовые статические методы create? В чем выгода?

[gabaidulin.livejournal.com]

Нивчем, привычка(coding style).

[(Anonymous)]

У меня статистика такова. Из примерно 130 человек, приславших резюме:
- 80 присылают примеры кода и решение задачи
- 15 приглашаются на 1-е интервью
- 7 приглашаются на 2-е интервью
- 2 приглашаются на 3-е интервью
- 1 принимается на работу