Привет! После долгого перерыва мы решили вернуться на Хабр и хотим поделиться опытом участия в хакатоне. В сентябре в Москве прошел Diversity.Hack, партнерами которого стали Dostavista, Waves и мы — «Новые Облачные Технологии». Участие в хакатоне, организованном Phystech.Genesis, проектом Бизнес-инкубатора МФТИ, стало первым и одновременно успешным опытом для нашей компании. Но не будем забегать вперед — давайте посмотрим, как все прошло и что интересного удалось придумать его участникам. 

Как проходил Diversity.Hack

На хакатон в коворкингe GrowUp собрались 208 человек в составе 44 команд, что стало рекордом для организаторов. О том, по какому принципу формировались команды, в деталях можно прочитать в статье от Phystech.Genesis. Участники решали одну из трех предложенных задач от каждой компании чуть больше суток, имея возможность остаться на ночь прямо на месте проведения и с питанием от организаторов. Призовой фонд в размере 300 000 рублей равноценно делился между треками. Кроме генерации идей и кодинга, участники могли посетить интенсивы о том, как побеждать на хакатонах.



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

Среди участников были как студенты, так и опытные специалисты, встречались очень перспективные ребята. В итоге нам и другим компаниям-партнерам удалось почерпнуть новые идеи. Например, компания Waves предложила разработать мобильное приложение при помощи языка Ride и платформы Waves Platform. Для службы доставки Dostavista команды разрабатывали систему по оптимизации маршрутов курьеров.

Под руководством наших коллег из «Новых Облачных Технологий» нужно было придумать удобный инструмент (алгоритм, UI) для анализа изменений в документах при сравнении двух и более версий.
 

Почему именно эта задача? 

Наша компания с 2013 года развивает МойОфис — набор офисных приложений, работающий на всех основных операционных системах, включая мобильные. Изначально у нас было 7-8 вариантов заданий, и чтобы выбрать одно для хакатона, мы даже устроили закрытое голосование внутри компании. Среди вариантов были, например, сравнение двух и более документов (разработка самой технологии и UX), автоматизированное сравнение качества рендеринга документов (на примере экспорта в PDF из двух разных редакторов), также была идея, связанная с анализом шрифтов в документе. Еще мы хотели дать задание на сбор информации из чатов о датах встреч для их автоматизированного добавления в календарь смартфона (интересно для, например, написания ботов в Telegram) и несколько других.

В итоге мы остановились на задаче на сравнения двух и более документов. Глобально идея состоит в том, что используя офисный пакет на своем компьютере, к одному и тому же исходному файлу различные сотрудники могут вносить свои правки. Нужно создать технологию, которая позволит комфортно сравнивать несколько версий одного и того же документа, а после чего принять одну из предложенных правок. Правки предстоит еще проверить на противоречие друг другу, после чего получится единый финальный документ.  



Казалось бы, как вообще такая задача может быть актуальной? Сейчас доступны различные облака, в которых отображается вся история изменений — кто, что и когда отредактировал. Однако во многих компаниях документы не разрешают хранить в облаке из соображений безопасности. По этой или какой-либо другой причине правки в файл могут быть внесены оффлайн, без использования облака, а затем ту или иную версию документа обычно отправляют коллегам по почте. Правки может вносить не один человек, и в итоге версий документа становится так много, что неизбежно возникает неразбериха.

Так мы и столкнулись с потребностью использования инструмента для одновременного сравнения более чем двух документов. Но вот незадача! На рынке просто не оказалось решений этой проблемы, есть лишь сервисы для сравнения двух документов, причем существующий выбор не блещет разнообразием. Так, есть ABBYY Comparator, который умеет сравнивать документы не только в текстовом формате, но и PDF, сканы и фотографии. Недостатком использования этого сервиса может стать его стоимость. Другой сервис — Text Compare! — и похожие на него позволяют просто вставлять текст в два специальных окошка. А это сильно ограничивает возможности — даже файлы загрузить нельзя, а только Ctrl+C и Ctrl+V! 

Средство от возникшей «боли» наша компания решила искать у талантливых разработчиков со всей России, убрав ограничение на формат документа. Мы предложили использовать знакомый всем html — в нем удобно представляется древовидная структура документа. Все участники откликнулись на это предложение. Нам было интересно получить саму технологию сравнения, а также удобный и интерактивный интерфейс.

Решения команд-победителей

На Хабре есть немало статей-интервью о том, как участники выстроили рабочий процесс во время того или иного хакатона, как им удалось победить. Нашу задачу решали восемь команд, три из которых заняли призовые места: первое заняли ZenDocs, второе разделили SerotoninMix и SegFault. Мы выбирали победителей по следующим критериям: удобство пользовательского интерфейса (его интерактивность и минимализм), качество проработки различных кейсов в этом интерфейсе (как будет выглядеть сравнение таблиц — структурных изменений и изменений текста внутри, диаграмм, изображений), сам алгоритм сравнения (временная сложность, способность распознать разные типы правок). Хороший рабочий прототип считался большим плюсом :)

Интерфейсные решения у большинства команд оказались в значительной степени похожими. Возможно, это говорит о том, что интерфейсы получились удобными для пользователя, если все разработчики пришли к одному и тому же. Отличалась детальность проработки пользовательских кейсов и качество прототипа — кто-то успел сделать больше, кто-то меньше.



Тем не менее, после презентаций решений фаворит определился четко — им оказалась команда ZenDocs, сделавшая упор на алгоритмическую часть. Они провели эффективное исследование имеющихся подходов и нашли научную статью с алгоритмом сравнения xml-деревьев. Этот алгоритм хорошо масштабируется на N документов: если сравнивать документы попарно, как делают многие другие алгоритмы, сложность будет расти полиномиально от числа документов, а при таком подходе она увеличивается линейно. Алгоритм возвращает id элементов дерева, которые изменились, и тип изменения — вставка, удаление, замена.

Такой формат ответа удобно отдавать фронтенду — не нужно его дополнительно обрабатывать. Картинки, строки и столбцы таблицы являются обычными структурными блоками документа, такими же как абзацы, поэтому такой алгоритм позволяет обнаружить изменение картинки, структуры таблицы или ее содержимого, то есть отлично справляется со многими юзеркейсами, а это важный критерий оценивания. Команда предложила дальнейшую оптимизацию алгоритма, использующую дерево Меркла. Такая оптимизация позволит проверять только те поддеревья, для которых изменился хеш, что ускоряет алгоритм. Прототип доступен по ссылке: https://zendocs.ru





Выбирать второе и третье места было сложнее, потому что на них претендовали три достойных решения. В итоге мы остановились на SerotoninMix и SegFault. Одни из них были лучше по интерактивности, другие — по навигации, и это нормальная ситуация: за два дня сложно разработать идеальное решение. Некоторые команды практически полностью реализовали алгоритм на простой модели, среди них и были ZenDocs и SerotoninMix. 

Последних мы выделили в том числе за творческий подход — оценили их юмор (они назвали свой проект «НеМой офис», а еще в их презентации было много веселых моментов) и впечатлились тем, что они успели сделать полноценный прототип.




Ребята из SegFault нашли очень оригинальный подход. При разработке прототипа они использовали Vue.js; сервер писался на языке Python с использованием Flask и Docker, использовались алгоритмы Word2Vec и Crochemore. Немного пересмотрев алгоритмы, участники сравнивали главный документ со всеми остальными, выделяли общую и различающиеся части. В созданной среде есть блок редактирования, где отображаются фрагменты из разных документов. Можно выбрать один из них и отредактировать его при необходимости. В панели управления можно принять правку или просмотреть принятые ранее. Команда также провела сравнение изображений, сравнивая их как base64-encoded и конвертируя изображение в формат base64, и проработала метод сравнения таблиц и отображения изменений в них.  

На хакатоне было мало дизайнеров, а наша задача на большой процент состояла из прототипирования интерфейса и создания макетов, что предполагало использование таких инструментов, как Sketch и Figma. Нам в душу запала команда Talestorm, один из участников которой всего за ночь научился в них работать с нуля.

Взаимодействие после хакатона

В конце сентября состоялась встреча победителей, представителей «Новых Облачных Технологий», в том числе генерального директора Дмитрия Комиссарова, и Phystech.Genesis. На встрече обсудили задачи компании, в которых победители хакатона могут принять участие. Мы рассчитываем на сотрудничество с командами!