TrainsTestTask

Post-HR technical task. Тестовое задание для "НИИАС". Привет, читатель!

Содержание:

• Пункты ТЗ,
• Комментарии по разедлу "Важное", успехи и провалы,
• Отсебятина.

Я бы хотел начать с пунктов по ТЗ:

1. Структура данных:

Иерархия получилась примерно в следующим виде:

Класс Point - элементарная составляющая схемы станции. На основании точек я строил направленный граф. Из точки можно попасть в другие точки (коллекция OutgointPoints), в точку можно прийти из других точек (IncomingPoints).

Класс Track. Представляет из себя коллекцию точек, составляя таким образом участок пути. Используется при поиске путей как выходные данные.

Класс Park. Содержит в себе пути (Tracks). На основании этих путей выполняет заливку (класс Polygon).

Класс Station - агрегирующая составляющая для всего вышеуказанного. Включает в себя точки, пути, парки.

2. Захардкодить данные. Реализовано в классе StationParser.

3. WPF + CustomControls.

4. Алгоритм заливки. Реализовано в классе Polygon. В классе содержится список сторон полигона. Каждая сторона задается прямой. В каждой стороне хранится направление "внутренней стороны". Проверяем лежит ли точка на внутренней стороне каждой стороны. Если это так, то точка не добавляется в полигон (ибо она уже в нем). В противном случае пытаемся добавить точку. Проверяем для каких сторон не выполняется условие "лежит на внутренней стороне", эти стороны удаляются, а на основании двух освободившихся верших и текущей точки строятся две новые стороны полигона.

Оценка сложности сверху: O(n^2), где n - количество точек для добавление.

5. ComboBox для выбора парка и цвета заливки.

6. Подсветка кратчайшего пути между участками. Класс Pathfinder отвечает за поиск.

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

Также в алгоритме поиска предусмотрены некоторые ограничения, вот пара из них:

1. ForbidSharpCornerRestriction - если три точки (предыдущая, текущая и следующая)

образую острый угол, то такая ветвь не будет продолжаться ("эмуляция" плавного поворота поезда).

2. AllowOnlyDeadEndReverseRestriction - позволяет пойти "обратно" только в тупкие.

Классы ограничений реализуют общий интерфейс IPathfinderRestriction.

7. Написать unit-тесты для схемы станции, алгоритма заливки и поиска.

8. Залить на GitHub. Вы здесь.

Небольшие комментарии по разделу "Важно":

1. MVVM. В простейшем виде паттерн реализован за исключением нескольких моментов:

а. Во всех ViewModel я храню List<Line>, которые можно сразу рендерить (Canvas.Children.Add(line)). Сложность заключалась в том чтобы сделать Bind для коллекции линий в CustomControls и я на это потратил много времени.

б. Скорее всего, у меня просто "не ехали лыжи", но я очень долго разбирался как сделать Bind для ComboBox, а точнее каким образом извлечь SelectedValue из CustomControls. У меня не получилось по-человечески забайндить через View, поэтому принял решение добавить в несколько Property обработчики на уровне ViewModel (что ломает MVVM).

в. Также из-за пункта выше пришлось сделать еще один ужас: байндить прямо на ViewModel. То есть в CustomControls у меня висят не {TemplateBinding <поле_из_CustomControls>}, а {Binding <поле_из_ViewModel>}.

2. Не реализована модель команд. Присутствуют классы, в тестовых вариантах пробовал использовать команды (как способ разрешить какие-то конкретные моменты), получилось не очень успешно, отказался.

Отсебятина:

Я написал эту простыню в надежде что это упростит немного работу проверяющему, подскажет куда смотреть в этом хаосе и некоторые причины и решения, которые я принимал по ходу решения задачи. Указал на все места, которые по своему же мнению я сделал "не очень хорошо", но у меня есть осознание что можно сделать лучше. Надеюсь, у вас получится найти что-то хорошее, или, наоброт, указать что я не увидел что могло бы стать лучше.

Трудозатраты на проект:

Граф и наполнение ~2-3 часа

Заливка ~4 часа

Попытка отобразить List - 8+ часов

Попытка разобраться с Combobox в Custom Controls - 6+ часов, бросил, решил простейшим способом, пошел дальше.