Привет,

на топкодерах принято после марафонов делать топик с post your approach и писать вкратце идеи решения и это весьма полезно как для участников так и сочувствующих, особенно топовые решения. (Я уточнил у Майка и он не возражает против обсуждения, если не постить код).

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

Так же должны быть наверняка крутые статьи по теме, но то что я бегло нашел касалось более high-scale подходов для тысяч документов.

Я занял третье место.

Заслав простое решение я понял что сплагиаченные решения сильно похожи и простые подходы набирают много баллов, поэтому мой high-level подход выглядит так:

1) Нормализовать код

2) Искать совпадающие последовательности команд в обоих решениях для каждой пары и если их много, значит плагиат. Причем совпадение очень нечеткое, с возможностью пропуска команды или небольших изменениях, из расчета что код читеров слегка пошафлен, но функции те же.

3) Разбить на компоненты связности плагиата и вывести их.

Подробнее,

1) Нормализация кода состоит из замены простых дефайнов, удаление табов, комментариев, импортов, добавления ровно одного пробела между токенами, новой строки после ";", выпиливания стандартных классов CHelper'а, удаления глупых слов вроде спецификаторов доступа и последним шагом замена всех слов на одну букву и всех чисел на другую. При таком процессе несомненно теряется много индивидуальности, которую было бы круто сохранить, но чтобы хорошо потестить комбинацию из нескольких классификаторов нужно было явно больше тестов.

2) Совпадение последовательностей эволюционировало до такого монстра: для каждой команды из первого файла(в нормализованном виде) мы ищем абсолютно такие же команды в втором файле, а потом для каждой такой пары смотрим на следующие восемь команд из первого файла и если для хотя бы шести из них можно найти нечеткую копию(одна ошибка при сравнение двух нормализованных строчек допустима) недалеко от исходной команды во втором файле, то значит это грубо говоря одинаковый блок и первый файлик получает +1 к подозрительности.

Если подозрительность достигает 49% от числа операторов в файлике то мы считаем два файла плагиатом.

Понятно что это не так сложно обмануть, но решения, которые не делают байткод сильно ограничены by design и тут много не сделаешь.

Для тестирования я скачал 50к решений и принтил в файлик все пары, которые были близки к границе согласно моему классификатору, крутил ручки, чтобы это было лучше и приходил в уныние.

Спасибо и интересно, кто к чему пришел и как все это тестил)