Привет,
на топкодерах принято после марафонов делать топик с post your approach и писать вкратце идеи решения и это весьма полезно как для участников так и сочувствующих, особенно топовые решения. (Я уточнил у Майка и он не возражает против обсуждения, если не постить код).
Мне особенно интересен вопрос реиспользования кода, я смотрел с большой надеждой на всякие библиотечки по построению синтаксических деревьев или байткода(привет llvm) или хотя бы автоформатирования кода, но они были все на плюсах, огромные и с зависимостями, поэтому я велосипедил на джаве.
Так же должны быть наверняка крутые статьи по теме, но то что я бегло нашел касалось более high-scale подходов для тысяч документов.
Я занял третье место.
Заслав простое решение я понял что сплагиаченные решения сильно похожи и простые подходы набирают много баллов, поэтому мой high-level подход выглядит так:
1) Нормализовать код
2) Искать совпадающие последовательности команд в обоих решениях для каждой пары и если их много, значит плагиат. Причем совпадение очень нечеткое, с возможностью пропуска команды или небольших изменениях, из расчета что код читеров слегка пошафлен, но функции те же.
3) Разбить на компоненты связности плагиата и вывести их.
Подробнее,
1) Нормализация кода состоит из замены простых дефайнов, удаление табов, комментариев, импортов, добавления ровно одного пробела между токенами, новой строки после ";", выпиливания стандартных классов CHelper'а, удаления глупых слов вроде спецификаторов доступа и последним шагом замена всех слов на одну букву и всех чисел на другую. При таком процессе несомненно теряется много индивидуальности, которую было бы круто сохранить, но чтобы хорошо потестить комбинацию из нескольких классификаторов нужно было явно больше тестов.
2) Совпадение последовательностей эволюционировало до такого монстра: для каждой команды из первого файла(в нормализованном виде) мы ищем абсолютно такие же команды в втором файле, а потом для каждой такой пары смотрим на следующие восемь команд из первого файла и если для хотя бы шести из них можно найти нечеткую копию(одна ошибка при сравнение двух нормализованных строчек допустима) недалеко от исходной команды во втором файле, то значит это грубо говоря одинаковый блок и первый файлик получает +1 к подозрительности.
Если подозрительность достигает 49% от числа операторов в файлике то мы считаем два файла плагиатом.
Понятно что это не так сложно обмануть, но решения, которые не делают байткод сильно ограничены by design и тут много не сделаешь.
Для тестирования я скачал 50к решений и принтил в файлик все пары, которые были близки к границе согласно моему классификатору, крутил ручки, чтобы это было лучше и приходил в уныние.
Спасибо и интересно, кто к чему пришел и как все это тестил)
Первый раз участвовал в подобном, было интересно. Времени на разработку и написание чего-то крутого не было, поэтому не очень сложное решение, тем не менее 16ое место:
1) Удалим комментарии
2) Удалим пробелы, переводы строк, табуляцию...
3) Удалим все буквы
4) Для каждой пары решений считается функция f(s1, s2). f(s1, s2) = наименьшему количеству подстрок строки s2 плюс единичных символов алфавита, которыми можно покрыть строку s1. Функция f считается жадно с суффиксным массивом за |s1|·log(|s1| + |s2|). Функция g — относительный вариант f, g(s1, s2) = f(s1, s2)÷ |s1|. Для обработанной пары исходников, если min(g(s1, s2), g(s2, s1)) ≤ 0.15, то проводим ребро между соответствующей парой.
5) Выводим компоненты свзяности
Я тоже Первый раз участвовал в подобном, было интересно. (Место — неочень.. 119-oe).
1.0. Удалим не ascii 1.1. Удалим комментарии 1.2. Простенький препроцесс с #define и #undef (без скобок, т.е. только "Object-like Macros") для С языков. 1.3. Перевод чисел из экспонентальной формы в обычную. 1.4. с typedef как с macro'сами. 1.5. офф-сайд перевожу в фигурные скобки и ";" 1.6. стираю плюсы между "=" и числом. 2.1 все слова в одну букву. (optional) 2.2 все пробелы стираем (optional) 3. выбор 1 или нескольких фильтров (к некоторым подберая коэфициенты): a) является ли один код подстрокой другово. b) поделить код на строчки длинны N и посчитать сколько их встречаються хоть раз в другом коде. c) поделить код на строчки по границам слова (a-zA-Z_0-9) и посчитать сколько их встречаються хоть раз в другом коде. d) посчитать сколько каких символов, cравнить. e) несколько подстрок кода поискать в другом коде, подстроки создавая вырезая из строки напр. по 30 симв., каждые 37 симв. f) вырезать общие длинные последовательности, уменьшая длинну: если один из кодов сильно сократился — считаем плагиатом.
a, c, f методы, и комбинированные неплохо претестов прошли.Я в начале тоже хотел написать подобное решение, но потом подумал, что топовые участники пишут, что-то более адекватное с полноценным парсингом и всеми вытекающими нормализациями, например разворот
>=в<=, заменаfor>>>while>>>do whileи т.д.Если бы были библиотеки это было бы более осуществимо, наверное. Может кто-нибудь что-нибудь еще и собрал. У меня есть ощущение что это все равно не поможет, например, против мертвых переменных, потому что тут уже начинается переход в сферу алгоритмически неразрешимых задач)
Но используя мой подход, если кто-то развернет for в do и оставит все остальное как прежде это не изменит ничего, потому что можно пропускать пару операторов в блоке из-за нечеткости сравнений, а читеры на то и читеры, чтобы совсем все решение не переписывать.
19 место в неофф. зачёте:
1.1 Удаляем строчки в которых есть следующие слова: template read write next
Все идентификаторы и числа заменяем одним символом(одинаковые — одинаковым, разные — разным). Да, алфавит получается самую малость немаленьким
Если 2 текста различаются по длине хотя бы в 2 раза — они разные
Считаем расстояние Левенштейна между решениями. Нормируем к 0; 1
Считаем количество подстрок длины 7 из второго текста, встречающихся в 1м тексте. Также нормируем (b)
если max(a, b * 0.9) > 0.74 — тексты совпадают, иначе — разные
На 27 апреля 4 место (и 5 место с неофицальными участниками).
Никакие сторонние библиотеки, парсеры не использовал.
Берем код. Вытягиеваем из него все команды, удаляем из них все идентификаторы. (Делается это простым самописным парсером. =)) Два файла одинаковы, если выполняется одно из условий:
1) если (количество_общих_команд) / max(кол-во команд в I файле, кол-во команд в II файле) >= 0.9
2) Можно оставить в каждом файле только уникальные команды. И сравнить файлы как в 1ом пункте.
P.S.: теперь читеры не будут переименовывать переменные, функции. Теперь они будут просто кидать в свой код много-много левого кода, который вызывается, но ничего на самом деле не делает. =)
Мне интересно, а кто-нибудь машинное обучение писал?
1 место:
Долго анализировал тесты, которые нам были даны, в итоге выяснил, что во время контеста сильно код изменить не успеешь, есдинственное что может подпортить анализ — это перестановка кусков кода. Поэтому придумал особую метрику. (Сначала как все использовал Левенштейна, но он далеко не пошёл у меня).
По сути подход как у всех: нормализуем код, вводим метрику, выделяем компоненты связности.
1) Конечно нужно запустить препроцессор (как компилятор), но т.к. временные ресрусы ограничены просто удалим комметарии и некоторые ifdef'ы. Потом выяснилась проблема с шапками кода, поэтому я удалял все строки не начинающиеся на tab или два пробела (ещё можно посмотреть не лежит ли символ внутри фигурных скобок). Удаляем все слова (начинающиеся на букву, оканчивающиеся на букву или цифру)
2) Метрика. Будем сравнивать два кода: возьмём случайную подстроку в одном из кодов и посчитаем количество вхождений в первый и второй код. Получится два числа a и b, метрика будет 1 — min(a/b, b/a) (если какое-то из чисел 0 то значение зададим 1). Таких случайных строк я взял 300.
P.S. В основном ориентировался на С++, так что с явой у меня были проблемы, если объявлено много каких-то функций для быстрого ввода-вывода, которые из кода в код повторяются у всех.