Контекст
Алгоритмическими задачами названы задачи, которые на английском называются Competitve programming tasks (Competitive programming - Wikipedia). Обычно это математическая задача для которой нужно написать решение в виде программы на любом языке программирования за заданное время.
Так как такие задачи часто дают на собеседованиях программистам, то будучи программистом мне стало интересно можно ли применить системное мышление к решению таких задач и будет ли это иметь смысл.
В этой статье я не буду исследовать все возможные типы задач или описывать какие-то общие концепты, я просто попытаюсь применить то что успел узнать из курса системного мышления и системной инженерии к решению одной задачи и поделюсь своими наблюдениями.
Задача
Ссылка на задачу (Rectangle Area - LeetCode).
В задаче даются координаты нижнего левого и верхнего правого углов двух прямоугольников на плоскости и нужно найти общую площадь занятую этими прямоугольниками. Есть два упрощения: координаты целочисленные и стороны прямоугольников параллельны осям координат.
Решение
Притворимся, что у нас есть какая то надсистема, в которой существуют некие объекты, одно из свойств которых можно представить в виде прямоугольника на плоскости и надсистеме нужна функция вычисления площади занимаемой парой таких объектов.
Наша задача создать систему, которая предоставляет такой сервис.
Use cases
Начнем с use cases. Тут есть нюанс, что мы выдумали надсистему и у нас нет стейкхолдеров которых можно спросить о use cases, придется трудится самим в роли инженера и перечислить их:
- Прямоугольники не пересекаются
- Прямоугольники пересекаются углами
- Часть одного прямоугольника с двумя углами входит во второй прямоугольник
- Один прямоугольник входит полностью во второй
- Прямоугольники касаются друг друга сторонами, но не пересекаются
- Площадь одного из прямоугольников = 0
Концепция системы
Далее нам в роли архитектора или инженера нужно придумать основную концепцию системы.
Тут начинаются трудности, потому, что концепций может быть несколько, и нужно быстро решить какую же выбрать. Причем мы еще не приступили даже к функциональной декомпозиции и нам еще очень далеко до модульного синтеза, где можно говорить о каких-то tradeoffs.
Я вижу тут две основные концепции:
- Нужно вычислить площадь обоих прямоугольников и вычесть из этой суммы площадь прямоугольника получившегося в результате пересечения данных двух прямоугольников.
- Нужно построить прямоугольник который будет покрывать оба данных прямоугольников и далее всех его точек (координаты целочисленные) проверить входят ли они хотя бы в один данный изначально прямоугольник. Сумма положительных ответов будет решением задачи.
На этом этапе довольно трудно понять насколько сложно будет реализовать каждую из этих концепций, особенно первую, и какие могут возникнуть tradeoffs.
Один из tradeoffs который приходит в голову на этом этапе это время затраченное на разработку (design time) более совершенного алгоритма (стратегии основной концепции), который, возможно сократит время работы самого алгоритма в runtime. Этот tradeoff можно отследить на найденных выше двух концепциях:
- В первой концепции, временная сложность алгоритмы (runtime) кажется не будет зависеть от того насколько большими будут прямоугольники. Но нахождение прямоугольника пересечения не кажется простой задачей - нужно будет потратить design time, чтобы решить ее, а возможно она вообще не решится за разумное время (тут зависит от времени, на собеседовании на такую задачу могут дать 15 минут, что делает выбор первой концепции не очень очевидной, учитывая количество use cases которые нужно покрыть).
- Во второй, design time будет минимальным - сама концепция уже предполагает очень простой алгоритм. Но время работы алгоритма будет зависеть от того насколько велики прямоугольники и как расположены.
Кажется этот tradeoff должен быть знаком всем предпринимателям. Выбрать более сложную стратегию, откладывая получения результата или выбрать простую стратегию, начать получать результат и постепенно оптимизировать ее. Хочется порассуждать о локальном и глобальном эскремуме, но это опять tradeoff - количество слов в статье и количество человек ее прочитающих.
Итак, мы в роли архитектора или инженера делаем выбор в пользу первой концепции, рассчитывая на то, что вторая будет решаться слишком просто, временная сложность будет сильно хуже (O(n)), чем у первой (O(1)), а стратегии оптимизации будут ограничены. Интересно, все инженеры и архитекторы об этом осознанно думают, когда решают подобные задачи на работе? Можно ли эти tradeoffs как то формализовать? Типа двигаешь бегунок design time, а бегунок run time двигается в противоположном направлении (можно еще параметров добавить для лучшей симуляции).
Функциональная декомпозиция
Мы в роли инженера знающего доменную область, геометрию, я думаю в данном случае проводим функциональную декомпозицию первой концепции. Для функции вычисления общей площади по первой концепции нам будут нужны следующие функции:
- Функция расчета площади прямоугольника по координатам двух противоположных углов
- Функция расчета площади прямоугольника образованного пересечением двух прямоугольников (для каждого прямоугольника даны координаты двух его противоположных углов).
Далее нам нужно декомпозировать вторую функцию, и тут есть нюанс. Мы можем начать думать об этой задаче по разному и придти к двум очень разным по сложности воплощения разбиениям.
Первый способ думать
Можно начать думать о том, что у нас уже есть функция вычисления площади прямоугольника по координатам двух противоположных углов и разбить нашу вторую функцию как то так:
- Функция определения координат 4 углов прямоугольника получившегося пересечением двух других прямоугольников. Тут мы можем заметить, что углы получившегося прямоугольника это либо пересечение сторон исходных прямоугольников, либо их углы и тогда можно разбить эту функцию на:
- Функция определения координат пересечения сторон прямоугольников, для чего нам нужны функции:
- Функция определения что два отрезка пересекаются
- Функция определения точки пересечения двух отрезков
- Функция определения координат углов прямоугольников находящихся внутри другого прямоугольника, для чего нам нужны функции:
- Функция определения, что точка находится внутри прямоугольника
- Функция определения координат пересечения сторон прямоугольников, для чего нам нужны функции:
- Функция выделения двух противоположных углов из 4х углов прямоуголька
Этот способ не плох, но как видим требует как минимум 6 функций, это если мы еще не забыли чего то.
Второй способ думать
Можно подумать, что площадь прямоугольника можно вычислить зная только длины двух смежных сторон, то есть может быть нам не нужны координаты углов, может быть мы можем получить длины сторон прямоугольника пересечения сразу?
Далее, можно рассмотреть каждую ось отдельно. На оси X у нас есть 4 точки, 2 от одного прямоугольника и 2 от другого, в случае пересечения прямоугольников, 2 из этих точек принадлежат прямоугольнику пересечения, причем это будут средние две точки если представить все 4 на оси. Этого размышления достаточно, чтобы сделать функциональную декомпозицию:
- Функция определения если два отрезка на прямой имеют общую часть (наложены друг на друга). Для этого нам нужны будут следующие функции:
- Функция сравнения двух целых чисел
- Функция получения двух средних точек из 4х на каждой оси.
1. Функция сравнения двух целых чисел (или возврата минимума и максимума из двух чисел) - Функция расчета площади прямоугольника по длинам его смежных сторон
- Функция умножения двух целых чисел
Этот способ требует всего трех функций, которые к тому же выглядят сильно проще. Поэтому, конечно нужно выбрать его для дальнейшего модульного синтеза. Выбрать то его легко, но вот заметить, что он есть, различить его, особенно когда уже начал думать по первому варианту - очень сложно!
Модульный синтез
По идее тут можно было бы и закончить, потому что модульный синтез после такой подробной декомпозиции становится тривиальной задачей - либо написать свой код для каждой из функций в роли инженера, либо взять готовую имплементацию, которая понятно уже присутствует в любых языках программирования в роли архитектора.
Тестирование
Написание тестов должно быть не сложно, если этап сбора use cases был сделан хорошо. В роли тестировщики стоит лишь задать по одному примеру для каждого use case и проверить, что программа выдает правильный ответ.
Итог и выводы
Кажется, что системное мышление к этим задачам не очень хорошо применяется, так как задачи искусственные, договариваться о их решении не с кем, а система, получающаяся в результате, довольно простая.
Принципы системной инженерии подходят не плохо, но опять же из-за того, что система получается простая, архитектурные решения в общем примитивные, а количество tradeoffs и ограничений минимальное (нам не нужно maintanability, evolvability и тд, только scalability и время разработки важно).
Остался большой и очень важный вопрос в том, а как же пойти по второму способу думать в функциональном разбиении, вернее как заметить, что есть еще второй вариант думать? Потому, что от этого зависит успешность системы и прохождения интервью! Может ли системное мышление или системная инженерия помочь с этим?
К сожалению, я не смог отыскать ответ на этот вопрос в учебниках курса бесконечного развития. Возможно, это можно назвать прикладной дисциплиной, и надо было лучше учить геометрию, чтобы сразу понимать как лучше думать. Или можно сказать, что решение подобных задач нарабатывает опыт и интуицию в выборе оптимального метода думать.
Но, кажется, что идея школы ШСМ именно в том, что бы учить думать и докапываться до сути, а не полагаться на то, что нейронка в мозгу натренируется выбирать правильный метод думать после прорешивания 200 задач.
Поэтому следующая задача для меня - это выяснить, что за практика нужна при выборе метода думать о функциональной декомпозиции и о решении подобных задач и начать тренировать ее, чтобы лучше играть свою роль инженера и архитектора при решении задач.
Причем, это касается не только таких более менее абстрактных/искусственных задач, я чувствую точно такие же затруднения при решении рабочих задач, когда нужно придумать как думать о задаче и потом выбрать один из этих способов, каждый из которых приводит к разным функциональным разбиениям и, соответственно, разной сложности имплементации решения.