Reverse engineering конкурсных списков поступления на бюджет в вузы России.
В пограничных случаях — когда документы уже сданы, но непонятно, проходишь ли по конкурсу — официальная рекомендация звучит так: «Смотрите конкурсные списки». Проблема в том, что в этих конкурсных списках невозможно ничего однозначно понять.
Общая таблица распределения абитуриентов по направлениям с учётом количества мест на каждом направлении. Можно выяснять, кто куда попал. Можно подводить самую разную статистику.
Чтобы понять, проходит ли конкретный абитуриент на бюджет, нужно распределить по направлениям всех, кто выше его по баллам.
Общий алгорифм такой.
- Собираем данные по направлениям, на которые можно подать заявление. Нужны: id направления (нпр., код специальности), количество доступных бюджетных мест.
- Собираем все заявления. По каждому заявлению: id кандидата (СНИЛС), направление, приоритет, баллы на это направление.
- Сортируем список заявлений: по убыванию баллов, потом по id кандидатов, потом по приоритетам. Так мы получим очередь кандидатов, где каждая следующая запись — это либо новый человек с меньшими баллами, либо следующий по важности приоритет того же человека. Важно: люди не группируются в таком списке, потому что у одного и того же человека на разные направления могут быть разные баллы.
- Проходим очередь от самых сильных заявлений к самым слабым.
- Для каждого следующего заявления смотрим, можно ли его удовлетворить. Можно, если человек ещё никуда не записан, и на направлении, указанном в заявлении, ещё есть места.
- Если да — записываем человека на направление, и уменьшаем количество доступных мест на этом направлении.
- Если нет — выбрасываем заявление (знаем, что для этого человека могут сработать следующие заявления).
- Доходим до конца списка.
В итоге у нас — список кандидатов, к каждому из которых приписано лучшее из доступных ему направлений. Здесь «лучшее» означает «направление из самого первого заявления, которое удалось удовлетворить, когда мы шли по очереди баллов и приоритетов».
- data/ — CSV-файлы с данными: направления + все поданные заявления. Собирать руками или с помощью Selenium, как повезёт конкретно в вашем вузе.
- bash/ — скрипты инициации (можно не трогать).
- sql/ — скрипты создания баз данных; могут отличаться на разных машинах (особенно много проблем с загрузкой данных из файлов).
- c/ — основная логика распределения; в макросах препроцессора — реквизиты доступа к базе данных.
Точно работает на Linux Mint 22 + MySQL 8 + gcc.
- Команда make создаст базу с нужными данными и откомпилирует C-программу.
- Запустить программу — build/main.
- Результат распределения смотреть в SQL-таблице candidates.
Все ограничения связаны с одноразовой природой проекта. Он просто не должен работать долго и счастливо.
- Код не проверялся на утечки памяти.
- Никакие ошибки времени исполнения никак не обрабатываются.
- Отдельно обратите внимание, что неявно предполагается консистентность данных. Тут могут быть сюрпризы.
- «Серая зона» для людей с одинаковыми баллами и одинаковыми приоритетами
- Обработка ситуации, когда у человека заявление с максимальными баллами идёт не по высшему приоритету
- Настройка MySQL для локальной (или по сети) загрузки файлов
- Парсинг сайтов вузов
- SQL-команда создания базы данных spiski в скриптах инициации
- SQL-скрипт деактивации базы данных
- Версия с публичным доступом
- Рефакторинг функциональности «сборка SQL-запроса» (шаблоном через strtok)
- Скрипты интересной статистики
- Убрать перегруз по запросам к базе
- Статья на Хабре «Reverse engineering конкурсных списков поступления на бюджет в вузы России» (2024-08-03) — вошла в Top 5 за сутки.