Reverse engineering конкурсных списков поступления на бюджет в вузы России

Сегодня, 3 августа 2024 года, был последний день подачи документов в вузы России на бюджет.

Ситуация нервная: слишком много факторов.

1. Предварительно подать заявления можно в 5 вузов.

2. В каждом вузе — заявления на 5 направлений.

3. Направления в пределах вуза нужно ранжировать по приоритетам.

4. Документы нужно отнести только в один вуз.

Вузы публикуют так называемые конкурсные списки. Это списки заявлений по направлениям. Для каждого направления — кто подал, сколько баллов, какой приоритет этого конкретного направления у этого конкретного заявителя.

Просто смотреть в конкурсные списки полезно, если вы гарантированно проходите на первое из выбранных направлений. Это посчитать легко.

Всё остальное — туман.

Яжемать!

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

Психовать было очень утомительно. Допсиховалась до того, что написала несколько скриптов, предсказывающих поступление.

Что происходит в этих скриптах.

1. Заявления упорядочиваются по убыванию баллов, а для одного человека — по убыванию приоритета.

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

3. Очередь можно рассматривать постепенно, выбрасывая каждый элемент навсегда. Возвращаться к заявлениям не нужно: отработали — выбросили.

4. Как только мы удовлетворили заявление конкретного человека, все остальные его заявления становятся неактуальными. В очереди пусть болтаются, просто когда до них дойдёт дело — выбросим.

5. Заявление можно удовлетворить, если в нём указано направление, в котором на момент рассмотрения есть свободные места.

6. Как только мы удовлетворили заявление, абитуриент оказывается окончательно приписан к направлению. Поступил, всё.

7. И в этот же момент у направления уменьшается количество оставшихся свободных мест.

8. Если заявление указывает на направление, на которое нет мест, мы его выбрасываем. Если у человека есть ещё заявления в общей очереди (а они точно на другие направления) — у них ещё, возможно, есть шанс. Дойдёт дело — рассмотрим и их.

9. Будут люди, до которых дойдёт очередь только тогда, когда все места на всех направлениях будут заняты. Они не поступили.

Основной C-скрипт короче, чем описание его поведения.

#include <stdio.h>
#include <mysql/mysql.h>
#include <string.h>

#define HOST "localhost"
#define USER "root"
#define PSWD ""
#define DBASE "spiski"

int main() {

	MYSQL *mysql = mysql_init(NULL);

	mysql_real_connect(mysql,
											HOST, USER, PSWD, DBASE,
											3306, NULL, 0);

	// Очистить результаты предыдущих попыток распределения по направлениям
	mysql_query(mysql, "UPDATE departments SET counter=0");
	mysql_query(mysql, "UPDATE candidates SET department=NULL");

	// Получить список всех заявлений
	mysql_query(mysql, "SELECT * FROM inbox ORDER BY points DESC, id ASC, priority ASC");
	MYSQL_RES * inbox = mysql_store_result(mysql);

	// Обработать список заявлений
	MYSQL_ROW application;
	while ((application = mysql_fetch_row(inbox))) {

		// Получить запись о кандидате в таблице кандидатов
		char select_candidate[200] = {0};
		strcat(select_candidate, "SELECT * FROM candidates WHERE id='");
		strcat(select_candidate, application[0]);  // id
		strcat(select_candidate, "'");

		mysql_query(mysql, select_candidate);
		MYSQL_RES *candidate_search_result = mysql_store_result(mysql);
		MYSQL_ROW candidate = mysql_fetch_row(candidate_search_result);

		if (candidate[1] == NULL) {  // ещё не распределён

			// Получить информацию о направлении, указанном в заявлении
			char select_department[200] = {0};
			strcat(select_department, "SELECT * from departments WHERE id='");
			strcat(select_department, application[3]);
			strcat(select_department, "'");
			
			mysql_query(mysql, select_department);
			MYSQL_RES *department_search_result = mysql_store_result(mysql);
			MYSQL_ROW department = mysql_fetch_row(department_search_result);

			// Если есть места — зачислить кандидата на направление
			int department_budget;
			sscanf(department[2], "%d", &department_budget);

			int department_counter;
			sscanf(department[4], "%d", &department_counter);

			if (department_budget > department_counter) {
				// Увеличиваем счётчик зачисленных на направление (можно обойтись сложным SQL-запросом)
				char increase_counter[200] = {0};
				strcat(increase_counter, "UPDATE departments SET counter = counter + 1 WHERE id='");
				strcat(increase_counter, application[3]);
				strcat(increase_counter, "'");

				mysql_query(mysql, increase_counter);

				// Записываем кандидата на направление
				char set_department[200] = {0};
				strcat(set_department, "UPDATE candidates SET department='");
				strcat(set_department, application[3]);
				strcat(set_department, "', points='");
				strcat(set_department, application[1]);
				strcat(set_department, "', priority='");
				strcat(set_department, application[2]);
				strcat(set_department, "' WHERE id='");
				strcat(set_department, application[0]);
				strcat(set_department, "'");

				mysql_query(mysql, set_department);
			}

			mysql_free_result(department_search_result);
		}

		mysql_free_result(candidate_search_result);
	}

	// Освобождаем ресурсы
	mysql_free_result(inbox);
  mysql_close(mysql);
}

Всё работает. Ответ «поступило ли дитё» получен (ну так, средней радости, но всё-таки не мимо с песнями).

Технические нюансы

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

• Где взять данные по вузу? Скопипастить с сайта вуза. У всех разные форматы, Selenium помог слабо — а копипаст и Google Sheets сильно. Оказалось, что не так всё и страшно (в МГУ ребёнок не поступал, а на вузы поменьше ручная работа посильна).

• Linux Mint + MySQL + gcc. Просто что под рукой было. Извините, Windows у меня просто-напросто нет.

• Язык C — тоже из серии «что под рукой было». Наверное, на Python было бы проще, но книжка про Python лежала на полке повыше — лень тянуться.

• Возможны мелкие погрешности, связанные с кодировками. Разбираться пока не стала, потому что этот нюанс всплыл уже после получения от системы основных ответов.

Можно вкуривать на Github. И ещё разок: суть в поиске ответа, а не в качестве кода.

В этом году система уже никому не пригодится, но — будут и ещё годы. У желающих есть время допилить. Что непонятно — расскажу, дёргайте.