Мы продолжаем свое участие в международной олимпиаде «IT-Планета». Как и в прошлые годы, проводился конкурс по SQL, состоящий из трех этапов: теоретический и практический туры, проходящие онлайн, и финальный очный тур.
В первом туре участвовало свыше 4 500 человек, из которых 245 были отобраны во второй. В этом году я занимался разработкой задач и проведением первых двух туров. Предлагаю перейти к рассмотрению задач практического этапа.
Задача 1. Счастливый Карлсон
Условие
Карлсон очень любит есть варенье. Он ощущает прилив бодрости, когда третий день подряд съедает не меньше одной банки варенья в день, и притом, съедает за эти дни не меньше четырех банок варенья.
Карлсон чувствует себя счастливым, когда ощущает прилив бодрости как минимум 5 дней подряд. В остальные дни Карлсон несчастен.
Весь год Карлсон записывал в таблицу jam, сколько банок варенья съедал. Иногда Карлсон ошибался и записывал съеденные банки варенья на определенную дату несколькими отдельными записями.
Таблица создана следующей командой:
CREATE TABLE jam (
at date not null,
qty integer not null check (qty>=0)
);На основании данных таблицы необходимо определить, сколько дней Карлсон чувствовал себя счастливым.
Пример:
Для следующих входных данных
INSERT INTO jam VALUES
('2025-01-04',1),('2025-01-05',1),('2025-01-07',1),
('2025-01-08',2),('2025-01-09',2),('2025-01-10',1),
('2025-01-11',1),('2025-01-12',2),('2025-01-13',1),
('2025-01-14',1),('2025-01-15',1);ожидается результат:
happydays
-----------
2
(1 row)
Разбор решения
Формализуем правила:
Прилив бодрости возникает, если Карлсон ел варенье 3 дня подряд без пропусков, и в эти дни он съедал не менее 4 банок варенья.
День считаем счастливым, если прилив бодрости длится не менее 5 дней подряд.
В остальные дни Карлсон несчастен.
В таблице могут оказаться любые данные, если это не запрещено ограничениями целостности или явно не оговорено в условии задачи. Это относится как к данной задаче, так и к остальным рассматриваемым.
Данные:
Возможны дублирующиеся записи за одну дату (несколько строк с qty > 0)
Некоторые дни могут содержать qty = 0 (Карлсон не ел варенье в этот день, но запись об этом сохранил).
Решение
Рассмотрим задачу на примере решения одного из участников. Преимущество данного решения заключается в том, что оконные функции уменьшают количество подзапросов, а использование RANGE вместо ROWS позволяет корректно обработать пропуски в датах.
Рассмотрим решение на примере следующих данных. Это тест, который не прошли решения многих участников. В данных есть даты, где было съедено 0 банок варенья, несколько записей с одной и той же датой.
Пример данных
Скрипт добавления данных
INSERT INTO jam VALUES('2025-01-04',1),('2025-01-05',1),('2025-01-07',1),
('2025-01-08',1),('2025-01-09',1),('2025-01-10',1),
('2025-01-08',1),('2025-01-09',0),('2025-01-10',1),
('2025-01-11',1),('2025-01-12',1),('2025-01-13',1),
('2025-01-11',0),('2025-01-12',1),('2025-01-13',0),
('2025-01-16',2),('2025-01-16',0),('2025-01-17',0),
('2025-01-17',1),('2025-01-18',1),('2025-01-19',2),
('2025-01-20',1),('2025-01-21',1),('2025-01-22',2),
('2025-01-23',1),('2025-01-25',6),('2025-01-26',1);olymp=# select * from jam order by at;
at | qty
------------+-----
2025-01-04 | 1
2025-01-05 | 1
2025-01-07 | 1
2025-01-08 | 1
2025-01-08 | 1
2025-01-09 | 1
2025-01-09 | 0
2025-01-10 | 1
2025-01-10 | 1
2025-01-11 | 1
2025-01-11 | 0
2025-01-12 | 1
2025-01-12 | 1
2025-01-13 | 1
2025-01-13 | 0
2025-01-16 | 2
2025-01-16 | 0
2025-01-17 | 0
2025-01-17 | 1
2025-01-18 | 1
2025-01-19 | 2
2025-01-20 | 1
2025-01-21 | 1
2025-01-22 | 2
2025-01-23 | 1
2025-01-25 | 6
2025-01-26 | 1
(27 rows)-
Подзапрос daily_jam - подготовка данных.
Исключаем дни с qty=0 и суммируем данные по датам.SELECT at AS at, SUM(qty) AS qty FROM jam GROUP BY at HAVING SUM(qty) > 0Результат выполнения
at | qty ------------+----- 2025-01-04 | 1 2025-01-05 | 1 2025-01-07 | 1 2025-01-08 | 2 2025-01-09 | 1 2025-01-10 | 2 2025-01-11 | 1 2025-01-12 | 2 2025-01-13 | 1 2025-01-16 | 2 2025-01-17 | 1 2025-01-18 | 1 2025-01-19 | 2 2025-01-20 | 1 2025-01-21 | 1 2025-01-22 | 2 2025-01-23 | 1 2025-01-25 | 6 2025-01-26 | 1 (19 rows) -
Подзапрос daily_courage — определяем дни с приливами бодрости по условию «3 дня подряд и больше 4 банок за этот период». Используем аналитические функции со скользящим окном, охватывающим текущий день и два предыдущих (используем range по датам, а не по строкам). Добавляем условие count(*)=3, чтобы исключить пропуски.
SELECT at AS at, CASE WHEN COUNT(*) over w = 3 AND SUM(qty) over w > 3 THEN 1 ELSE 0 END AS is_courage FROM daily_jam WINDOW w AS (ORDER BY at RANGE BETWEEN INTERVAL '2' DAY PRECEDING AND CURRENT ROW)Результат выполнения
at | is_courage ------------+------------ 2025-01-04 | 0 2025-01-05 | 0 2025-01-07 | 0 2025-01-08 | 0 2025-01-09 | 1 2025-01-10 | 1 2025-01-11 | 1 2025-01-12 | 1 2025-01-13 | 1 2025-01-16 | 0 2025-01-17 | 0 2025-01-18 | 1 2025-01-19 | 1 2025-01-20 | 1 2025-01-21 | 1 2025-01-22 | 1 2025-01-23 | 1 2025-01-25 | 0 2025-01-26 | 0 (19 rows) -
Подзапрос daily_happy - определяем счастливые дни. День счастливый, если у Карлсона 5 дней подряд был прилив бодрости. Находим такие дни аналогичным способом.
SELECT at AS at, is_courage, CASE WHEN SUM(is_courage) OVER w = 5 THEN 1 ELSE 0 END AS is_happy FROM daily_courage WINDOW w AS (ORDER BY at RANGE BETWEEN INTERVAL '4' DAY PRECEDING AND CURRENT ROW)Результат выполнения
at | is_courage | is_happy ------------+------------+---------- 2025-01-04 | 0 | 0 2025-01-05 | 0 | 0 2025-01-07 | 0 | 0 2025-01-08 | 0 | 0 2025-01-09 | 1 | 0 2025-01-10 | 1 | 0 2025-01-11 | 1 | 0 2025-01-12 | 1 | 0 2025-01-13 | 1 | 1 2025-01-16 | 0 | 0 2025-01-17 | 0 | 0 2025-01-18 | 1 | 0 2025-01-19 | 1 | 0 2025-01-20 | 1 | 0 2025-01-21 | 1 | 0 2025-01-22 | 1 | 1 2025-01-23 | 1 | 1 2025-01-25 | 0 | 0 2025-01-26 | 0 | 0 (19 rows) Теперь осталось посчитать количество счастливых дней.
Решение полностью
WITH daily_jam AS (
SELECT at AS at,
SUM(qty) AS qty
FROM jam
GROUP BY at
HAVING SUM(qty) > 0
),
daily_courage AS (
SELECT at AS at,
CASE WHEN COUNT(*) over w = 3 AND SUM(qty) over w > 3
THEN 1
ELSE 0
END AS is_courage
FROM daily_jam
WINDOW w AS (ORDER BY at RANGE BETWEEN INTERVAL '2' DAY PRECEDING
AND CURRENT ROW)
),
daily_happy AS (
SELECT at AS at,
CASE WHEN SUM(is_courage) OVER w = 5
THEN 1
ELSE 0
END AS is_happy
FROM daily_courage
WINDOW w AS (ORDER BY at RANGE BETWEEN INTERVAL '4' DAY PRECEDING
AND CURRENT ROW)
)
SELECT COALESCE(SUM(is_happy), 0) AS happydays
FROM daily_happy;Результат выполнения запроса
happydays
-----------
3
(1 row)Другие участники в своих решениях использовали:
Соединение подзапросов со сдвигами на 1–2 дня.
Функции LEAD (LAG) для обращения к следующим (предыдущим) строкам.
Генерацию календаря с шагом 1 день и соединение с исходными данными.
Данные подходы позволяют решить задачу, но усложняют решение по сравнению с предложенным.
Проблемы, замеченные в решениях:
Не учитывались дни с qty = 0.
Усложнялась логика при работе с пропусками в датах.
Отсутствовала агрегация в данных за день.
Задача 2. Параметры системы
Условие
Имеется установленный кластер PostgreSQL. Администратор решил сохранять информацию об изменениях конфигурации этого кластера. Для этого он создал таблицу params:
CREATE TABLE params (
parameter_name TEXT NOT NULL,
ts timestamp NOT NULL,
value TEXT NULL,
PRIMARY KEY (parameter_name,ts));При изменении параметра в таблицу params сохраняется его новое значение и временнáя метка действия. Восстановление значения параметра по умолчанию записывается в таблицу params значением null с временнóй меткой.
Необходимо найти промежутки времени, когда максимальное количество параметров принимало значение, отличное от значения по умолчанию, и таких параметров было более одного. Если таких промежутков несколько, то необходимо вывести их все.
Пример:
Для следующих входных данных
INSERT INTO params (parameter_name, ts, value)
VALUES ('max_connections', '2025-01-10 11:30', '500'),
('max_connections', '2025-01-14 09:30', NULL),
('work_mem', '2025-01-11 08:35', '8MB'),
('work_mem', '2025-01-17 14:00', NULL),
('shared_buffers', '2025-01-14 10:00', '20000'),
('shared_buffers', '2025-01-15 07:40', NULL),
('temp_buffers', '2025-01-22 11:15', '2000'),
('maintenance_work_mem', '2025-01-19 10:20', '1000'),
('maintenance_work_mem', '2025-01-19 13:26', null),
('max_worker_processes', '2025-01-09 00:30', '16'),
('max_worker_processes', '2025-01-14 08:30', null);ожидается результат:
ts_start | ts_end | parameters
---------------------+---------------------+------------
2025-01-11 08:35:00 | 2025-01-14 08:30:00 | 3
(1 row)Разбор решения
Формализуем правила:
Найдем все непересекающиеся временные интервалы, где одновременно выполняются два условия:
Количество параметров с измененными значениями (не NULL) достигает максимума.
Одновременно изменено минимум 2 параметра.
Дополнительные требования:
Границы интервалов полуоткрытые [start, end).
null-значение трактуется как сброс параметра к значению по умолчанию.
Интервалы активности определяются последовательностью изменений.
В интервале должно быть наибольшее число одновременно активных параметров за весь период наблюдений.
Результат не должен содержать вложенные интервалы, удовлетворяющие тем же условиям.
Результаты:
Если ни один интервал не удовлетворяет условиям — возвращается пустой результат.
Интервалы с одинаковым максимальным количеством параметров все входят в результат.
Открытые интервалы (без конечной даты) обрабатываются как бесконечные.
Анализ задачи
Задача специально разработана для демонстрации эффективности работы с диапазонами и мультидиапазонами в PostgreSQL. В 2024 году мы уже встречались с задачей «Многоголовый Цербер». Данная задача решается аналогично. Суть решения заключается в построении для каждого параметра мультидиапазона, охватывающего все периоды, когда параметр имел значение, отличное от значения по умолчанию. Затем необходимо найти пересечения этих мультидиапазонов и определить интервалы с максимальным количеством одновременно активных параметров. Основное преимущество такого подхода — естественная работа с открытыми интервалами, поскольку диапазоны автоматически поддерживают бесконечные границы. Это избавляет от необходимости искусственно ограничивать последний период. В решениях конкурсантов встречались ограничения текущей датой, максимальной датой из таблицы или произвольно выбранной датой в будущем.
Многие участники пытались решить задачу без использования диапазонов, применяя аналитические функции и сложные соединения подзапросов. Однако такие решения часто оказывались неполными, так как не учитывали все возможные случаи, особенно с открытыми интервалами и сложными пересечениями периодов активности параметров. В отличие от них, решения на основе диапазонов и мультидиапазонов демонстрировали высокую надежность и проходили все тестовые случаи, поскольку эта технология специально разработана для работы с временными интервалами и их пересечениями. Мультидиапазоны обеспечивают точный и полный учет всех возможных комбинаций активных параметров в любой момент времени. Ключевое преимущество подхода с диапазонами заключается в его концептуальной чистоте — он позволяет работать с временными интервалами, как с объектами, избегая сложных и подверженных ошибкам ручных вычислений границ периодов и их пересечений.
Решение
Здесь и далее будем рассматривать решения использованные в качестве эталонов при тестировании запросов.
Рассмотрим решение на следующем примере данных
Данные
Скрипт
INSERT INTO params
(parameter_name, ts, value)
VALUES ('max_connections', '2025-01-10 11:30', '500'),
('max_connections', '2025-01-11 12:30', NULL),
('max_connections', '2025-01-11 15:30', '500'),
('max_connections', '2025-01-12 12:30', NULL),
('max_connections', '2025-01-12 15:30', '500'),
('work_mem', '2025-01-10 11:30', '8MB'),
('work_mem', '2025-01-12 14:00', '16MB'),
('max_connections', '2025-01-12 14:00', 1000),
('max_connections', '2025-01-17 12:30', NULL),
('shared_buffers', '2025-01-12 12:30', NULL),
('shared_buffers', '2025-01-12 13:30', '20000'),
('shared_buffers', '2025-01-14 10:00', NULL),
('shared_buffers', '2025-01-15 07:40', NULL),
('temp_buffers', '2025-01-09 10:20', '2000'),
('temp_buffers', '2025-01-11 11:30', null),
('temp_buffers', '2025-01-12 12:30', '1500'),
('temp_buffers', '2025-01-14 03:15', null),
('maintenance_work_mem', '2025-01-09 10:20','1000'),
('maintenance_work_mem', '2025-01-10 13:26', null),
('maintenance_work_mem', '2025-01-12 12:30', null),
('maintenance_work_mem', '2025-01-12 14:30', '1500'),
('maintenance_work_mem', '2025-01-15 14:30', null),
('max_worker_processes', '2025-01-08 00:30', '16'),
('max_worker_processes', '2025-01-12 14:00', null);olymp=# select * from params order by 1,2;
parameter_name | ts | value
----------------------+---------------------+-------
maintenance_work_mem | 2025-01-09 10:20:00 | 1000
maintenance_work_mem | 2025-01-10 13:26:00 |
maintenance_work_mem | 2025-01-12 12:30:00 |
maintenance_work_mem | 2025-01-12 14:30:00 | 1500
maintenance_work_mem | 2025-01-15 14:30:00 |
max_connections | 2025-01-10 11:30:00 | 500
max_connections | 2025-01-11 12:30:00 |
max_connections | 2025-01-11 15:30:00 | 500
max_connections | 2025-01-12 12:30:00 |
max_connections | 2025-01-12 14:00:00 | 1000
max_connections | 2025-01-12 15:30:00 | 500
max_connections | 2025-01-17 12:30:00 |
max_worker_processes | 2025-01-08 00:30:00 | 16
max_worker_processes | 2025-01-12 14:00:00 |
shared_buffers | 2025-01-12 12:30:00 |
shared_buffers | 2025-01-12 13:30:00 | 20000
shared_buffers | 2025-01-14 10:00:00 |
shared_buffers | 2025-01-15 07:40:00 |
temp_buffers | 2025-01-09 10:20:00 | 2000
temp_buffers | 2025-01-11 11:30:00 |
temp_buffers | 2025-01-12 12:30:00 | 1500
temp_buffers | 2025-01-14 03:15:00 |
work_mem | 2025-01-10 11:30:00 | 8MB
work_mem | 2025-01-12 14:00:00 | 16MB
(24 rows)-
Подзапрос P — подготовка временных интервалов для параметров. Для каждого параметра определяем начало и конец периода действия.
select parameter_name, ts as ts_start, lead(ts) over (partition by parameter_name order by ts) as ts_end, value from paramsРезультат выполнения
parameter_name | ts_start | ts_end | value ----------------------+---------------------+---------------------+------- maintenance_work_mem | 2025-01-09 10:20:00 | 2025-01-10 13:26:00 | 1000 maintenance_work_mem | 2025-01-10 13:26:00 | 2025-01-12 12:30:00 | maintenance_work_mem | 2025-01-12 12:30:00 | 2025-01-12 14:30:00 | maintenance_work_mem | 2025-01-12 14:30:00 | 2025-01-15 14:30:00 | 1500 maintenance_work_mem | 2025-01-15 14:30:00 | | max_connections | 2025-01-10 11:30:00 | 2025-01-11 12:30:00 | 500 max_connections | 2025-01-11 12:30:00 | 2025-01-11 15:30:00 | max_connections | 2025-01-11 15:30:00 | 2025-01-12 12:30:00 | 500 max_connections | 2025-01-12 12:30:00 | 2025-01-12 14:00:00 | max_connections | 2025-01-12 14:00:00 | 2025-01-12 15:30:00 | 1000 max_connections | 2025-01-12 15:30:00 | 2025-01-17 12:30:00 | 500 max_connections | 2025-01-17 12:30:00 | | max_worker_processes | 2025-01-08 00:30:00 | 2025-01-12 14:00:00 | 16 max_worker_processes | 2025-01-12 14:00:00 | | shared_buffers | 2025-01-12 12:30:00 | 2025-01-12 13:30:00 | shared_buffers | 2025-01-12 13:30:00 | 2025-01-14 10:00:00 | 20000 shared_buffers | 2025-01-14 10:00:00 | 2025-01-15 07:40:00 | shared_buffers | 2025-01-15 07:40:00 | | temp_buffers | 2025-01-09 10:20:00 | 2025-01-11 11:30:00 | 2000 temp_buffers | 2025-01-11 11:30:00 | 2025-01-12 12:30:00 | temp_buffers | 2025-01-12 12:30:00 | 2025-01-14 03:15:00 | 1500 temp_buffers | 2025-01-14 03:15:00 | | work_mem | 2025-01-10 11:30:00 | 2025-01-12 14:00:00 | 8MB work_mem | 2025-01-12 14:00:00 | | 16MB (24 rows) -
Подзапрос PS — фильтруем активные параметры. Для этого оставляем только диапазоны, где параметр не null, и формируем из них тип-диапазон.
select parameter_name, tsrange(ts_start, ts_end) as ParameterSetRange, value from P where value is not nullРезультат выполнения
parameter_name | parametersetrange | value ----------------------+-----------------------------------------------+------- maintenance_work_mem | ["2025-01-09 10:20:00","2025-01-10 13:26:00") | 1000 maintenance_work_mem | ["2025-01-12 14:30:00","2025-01-15 14:30:00") | 1500 max_connections | ["2025-01-10 11:30:00","2025-01-11 12:30:00") | 500 max_connections | ["2025-01-11 15:30:00","2025-01-12 12:30:00") | 500 max_connections | ["2025-01-12 14:00:00","2025-01-12 15:30:00") | 1000 max_connections | ["2025-01-12 15:30:00","2025-01-17 12:30:00") | 500 max_worker_processes | ["2025-01-08 00:30:00","2025-01-12 14:00:00") | 16 shared_buffers | ["2025-01-12 13:30:00","2025-01-14 10:00:00") | 20000 temp_buffers | ["2025-01-09 10:20:00","2025-01-11 11:30:00") | 2000 temp_buffers | ["2025-01-12 12:30:00","2025-01-14 03:15:00") | 1500 work_mem | ["2025-01-10 11:30:00","2025-01-12 14:00:00") | 8MB work_mem | ["2025-01-12 14:00:00",) | 16MB (12 rows) -
Подзапрос PAS — строим тип-диапазон для всех временных точек. В результате получаем «атомарные» диапазоны между соседними точками, из которых складывается всё время наблюдений.
select tsrange(ts, lead(ts) over (order by ts)) as ParameterSetRange from params where ts is not nullРезультат выполнения
parametersetrange ----------------------------------------------- empty empty empty empty empty empty empty ["2025-01-08 00:30:00","2025-01-09 10:20:00") ["2025-01-09 10:20:00","2025-01-10 11:30:00") ["2025-01-10 11:30:00","2025-01-10 13:26:00") ["2025-01-10 13:26:00","2025-01-11 11:30:00") ["2025-01-11 11:30:00","2025-01-11 12:30:00") ["2025-01-11 12:30:00","2025-01-11 15:30:00") ["2025-01-11 15:30:00","2025-01-12 12:30:00") ["2025-01-12 12:30:00","2025-01-12 13:30:00") ["2025-01-12 13:30:00","2025-01-12 14:00:00") ["2025-01-12 14:00:00","2025-01-12 14:30:00") ["2025-01-12 14:30:00","2025-01-12 15:30:00") ["2025-01-12 15:30:00","2025-01-14 03:15:00") ["2025-01-14 03:15:00","2025-01-14 10:00:00") ["2025-01-14 10:00:00","2025-01-15 07:40:00") ["2025-01-15 07:40:00","2025-01-15 14:30:00") ["2025-01-15 14:30:00","2025-01-17 12:30:00") ["2025-01-17 12:30:00",) (24 rows) -
Подзапрос RES - агрегация результатов. Для каждого интервала анализа считаем количество пересекающихся с ним параметров. Группируем результаты по количеству активных параметров и объединяем смежные интервалы с одинаковым количеством параметров с помощью range_agg(). Для наглядности изменим вывод результата.
select range_agg (ParameterSetRange) as ParameterSetRange, cnt_parameter from (select PAS.ParameterSetRange, count(parameter_name) as cnt_parameter from PS, PAS where not isempty (PS.ParameterSetRange*PAS.ParameterSetRange) group by PAS.ParameterSetRange) group by cnt_parameterРезультат выполнения
\x -[ RECORD 1 ]-----+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ parametersetrange | {["2025-01-08 00:30:00","2025-01-09 10:20:00"),["2025-01-17 12:30:00",)} cnt_parameter | 1 -[ RECORD 2 ]-----+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ parametersetrange | {["2025-01-09 10:20:00","2025-01-10 11:30:00"),["2025-01-11 11:30:00","2025-01-11 12:30:00"),["2025-01-11 15:30:00","2025-01-12 13:30:00"),["2025-01-14 10:00:00","2025-01-15 14:30:00")} cnt_parameter | 3 -[ RECORD 3 ]-----+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ parametersetrange | {["2025-01-10 11:30:00","2025-01-10 13:26:00"),["2025-01-12 14:30:00","2025-01-14 03:15:00")} cnt_parameter | 5 -[ RECORD 4 ]-----+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ parametersetrange | {["2025-01-10 13:26:00","2025-01-11 11:30:00"),["2025-01-12 13:30:00","2025-01-12 14:30:00"),["2025-01-14 03:15:00","2025-01-14 10:00:00")} cnt_parameter | 4 -[ RECORD 5 ]-----+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ parametersetrange | {["2025-01-11 12:30:00","2025-01-11 15:30:00"),["2025-01-15 14:30:00","2025-01-17 12:30:00")} cnt_parameter | 2 -
Финальный запрос — вывод результатов. Выбираем интервалы с максимальным количеством параметров, но не менее 2-х активных. Разбиваем объединенные интервалы мультидиапазона на отдельные с помощью unnest(). Выводим начало, конец и количество параметров для каждого диапазона.
select lower(ParameterSetRange) as ts_start, upper(ParameterSetRange) as ts_end, cnt_parameter as parameters from (select unnest(ParameterSetRange) as ParameterSetRange, cnt_parameter from Res where cnt_parameter = (select max(cnt_parameter) from Res where cnt_parameter != 1) ) order by ParameterSetRange
Результат выполнения
ts_start | ts_end | parameters
---------------------+---------------------+------------
2025-01-10 11:30:00 | 2025-01-10 13:26:00 | 5
2025-01-12 14:30:00 | 2025-01-14 03:15:00 | 5
(2 rows)Решение полностью
with
P as (
select parameter_name,
ts as ts_start,
lead(ts) over (partition by parameter_name order by ts) as ts_end,
value
from params
),
PS as (
select parameter_name,
tsrange(ts_start, ts_end) as ParameterSetRange,
value
from P
where value is not null
),
PAS as (
select tsrange(ts, lead(ts) over (order by ts)) as ParameterSetRange
from params
where ts is not null
),
Res as (
select range_agg (ParameterSetRange) as ParameterSetRange,
cnt_parameter
from (select PAS.ParameterSetRange,
count(parameter_name) as cnt_parameter
from PS,
PAS
where not isempty (PS.ParameterSetRange * PAS.ParameterSetRange)
group by PAS.ParameterSetRange)
group by cnt_parameter
)
select lower(ParameterSetRange) as ts_start,
upper(ParameterSetRange) as ts_end,
cnt_parameter parameters
from (select unnest(ParameterSetRange) as ParameterSetRange,
cnt_parameter
from Res
where cnt_parameter = (select max(cnt_parameter)
from Res
where cnt_parameter != 1))
order by ParameterSetRange;Участники в своих решениях использовали:
Функции LEAD (LAG) для обращения к следующим (предыдущим) строкам для вычисления диапазонов.
Для обеспечения бесконечности диапазона использовалась текущая дата, очень большая дата в будущем или ставилось ограничение максимальной датой из рассматриваемых.
Задача 3. ИТ-конференция
Эта задача оказалась самой сложной, всего 2 решения прошли все тесты. Рассмотрим данную задачу.
Условие
Компания «СУБД инжиниринг» проводит ежегодную конференцию. Участие в конференции платное. Есть три уровня билетов:
Standard стоимостью 2000 р за одного участника;
Allinclusive стоимостью 4000 р за одного участника;
Dual стоимостью 6000 р за двух участников.
Программист сделал таблицу tickets для сохранения информации о приобретении билетов участниками.
CREATE TABLE tickets
(Id_Ticket int, -- идентификатор билета
TicketDate date, -- дата приобретения
TicketType text CHECK (TicketType IN ('Standard', 'Allinclusive', 'Dual')),
Person text, -- ФИО участника
PRIMARY KEY (Id_Ticket, Person),
UNIQUE (TicketDate, Person, TicketType)
);Часть участников сразу не смогли определиться, какой билет приобрести, поэтому в дальнейшем меняли свое решение. В таблице продажи билетов факт возврата билета никак не отражается, но появляется новая запись о приобретении билета другого уровня. При этом участник мог изменять уровень билета несколько раз в день. Считается, что среди участников конференции нет полных тёзок, то есть ФИО каждого участника уникально.
Перед конференцией бухгалтерия решила провести сверку. Для этого ей необходимо определить:
количество проданных билетов, количество участников и сумму билетов отдельно по каждому уровню;
общее количество проданных билетов, общее количество участников и общую сумму.
Уровень участника определяется по следующим правилам:
Уровень билета определяется по последней дате приобретения билета;
Если в одну дату одним участником были приобретены несколько билетов, то выбирается билет максимального уровня (уровни в порядке убывания: Dual, Allinclusive, Standard);
Билет уровня Dual считается действительным, если на конференцию идут оба внесенные в него участника. В противном случае (если хотя бы один из участников позже приобрел другой билет) билет Dual аннулируется и уровень каждого участника определяется последним по дате действующим билетом.
Пример:
Для следующих входных данных
INSERT INTO tickets VALUES
(1,'2025.02.18','Allinclusive','Иванов Иван Иванович'),
(2,'2025.02.18','Dual', 'Попов Федор Иванович'),
(2,'2025.02.18','Dual', 'Иванов Иван Иванович'),
(3,'2025.02.17','Allinclusive', 'Кузнецов Петр Сергеевич'),
(4,'2025.02.15','Standard', 'Зайцев Сергей Петрович');запрос должен вывести:
tickettype | tickets | participants | sum
--------------+---------+--------------+-------
Allinclusive | 1 | 1 | 4000
Dual | 1 | 2 | 6000
Standard | 1 | 1 | 2000
| 3 | 4 | 12000
(4 rows)Разбор решения
Формализуем правила
Определение текущего уровня участника:
Приоритет даты. Учитывается последняя дата приобретения билета для каждого участника.
-
Приоритет типа билета при одинаковых датах:
Dual (высший приоритет);
Allinclusive;
Standard (низший приоритет);
-
Для билетов Dual:
Билет Dual определяется двумя записями с одинаковым id_ticket.
Билет Dual считается действительным, если оба участника, указанные в этом билете, не имеют более поздних покупок билетов.
Если хотя бы один из участников позже купил другой билет, билет Dual аннулируется, уровень каждого участника определяется по последнему действующему билету.
Расчет статистики:
-
По типам билетов:
-
Standard:
Количество билетов = число действительных билетов этого типа.
Количество участников = число людей с билетом этого уровня.
Сумма = количество билетов × 2000 руб.
-
Allinclusive:
Количество билетов = число действительных билетов этого типа.
Количество участников = число людей с билетом этого уровня.
Сумма = количество билетов × 4000 руб.
-
Dual:
Количество билетов = число действительных билетов этого типа.
Количество участников = число действительных билетов × 2.
Сумма = количество билетов × 6000 руб.
-
-
Общая статистика:
Общее количество билетов = сумма по всем типам.
Общее количество участников = сумма участников по всем типам.
Общая сумма = сумма стоимостей по всем типам.
Дополнительные условия:
Участник может менять тип билета несколько раз.
Возвраты билетов явно не фиксируются, но покупка нового билета аннулирует предыдущие.
Для Dual-билетов проверяется статус обоих участников.
Все расчеты выполняются на актуальных данных (последние действующие покупки).
Решение
Рассмотрим решение на примере следующих данных. Это тест, который не прошли решения многих участников. В данных есть отмененные билет уровня dual, из за чего в расчет необходимо принять ранее купленный билет уровня dual.
Пример данных
Скрипт
INSERT INTO tickets VALUES
(1,'2025.02.18','Standard','Иванов Иван Иванович'),
(2,'2025.02.18','Dual', 'Попов Федор Иванович'),
(2,'2025.02.18','Dual', 'Иванов Иван Иванович'),
(3,'2025.02.19','Allinclusive', 'Иванов Иван Иванович'),
(4,'2025.02.15','Allinclusive', 'Попов Федор Иванович'),
(5,'2025.02.20','Standard', 'Иванов Иван Иванович'),
(6,'2025.02.17','Dual', 'Попов Федор Иванович'),
(6,'2025.02.17','Dual', 'Кузнецов Петр Сергеевич');olymp=# select * from tickets t order by 2,1;
id_ticket | ticketdate | tickettype | person
-----------+------------+--------------+-------------------------
4 | 2025-02-15 | Allinclusive | Попов Федор Иванович
6 | 2025-02-17 | Dual | Кузнецов Петр Сергеевич
6 | 2025-02-17 | Dual | Попов Федор Иванович
1 | 2025-02-18 | Standard | Иванов Иван Иванович
2 | 2025-02-18 | Dual | Попов Федор Иванович
2 | 2025-02-18 | Dual | Иванов Иван Иванович
3 | 2025-02-19 | Allinclusive | Иванов Иван Иванович
5 | 2025-02-20 | Standard | Иванов Иван Иванович
(8 rows)-
Подзапрос grp - получаем данные по билетам. Для каждого билета получается одна строка. Данная строка будет содержать дату билета, тип билета и его стоимость, двух участников для билета dual и одного участника для остальных типов билета.
SELECT id_ticket, min(ticketdate) ticketdate, min(tickettype) tickettype, min(person) person1, max(person) person2, count(*) qty, CASE min(tickettype) WHEN 'Standard' THEN 2000 WHEN 'Allinclusive' THEN 4000 ELSE 6000 END AS amount FROM tickets t GROUP BY id_ticketРезультат выполнения
id_ticket | ticketdate | tickettype | person1 | person2 | qty | amount -----------+------------+--------------+-------------------------+----------------------+-----+-------- 3 | 2025-02-19 | Allinclusive | Иванов Иван Иванович | Иванов Иван Иванович | 1 | 4000 5 | 2025-02-20 | Standard | Иванов Иван Иванович | Иванов Иван Иванович | 1 | 2000 4 | 2025-02-15 | Allinclusive | Попов Федор Иванович | Попов Федор Иванович | 1 | 4000 6 | 2025-02-17 | Dual | Кузнецов Петр Сергеевич | Попов Федор Иванович | 2 | 6000 2 | 2025-02-18 | Dual | Иванов Иван Иванович | Попов Федор Иванович | 2 | 6000 1 | 2025-02-18 | Standard | Иванов Иван Иванович | Иванов Иван Иванович | 1 | 2000 (6 rows) -
Подзапрос t — приоритизация билетов. Вычисляем приоритет билетов вначале по дате, потом по стоимости. Проставляем этот приоритет каждому билету.
SELECT ticketdate, tickettype, person1, person2, qty, amount, row_number() OVER (ORDER BY ticketdate DESC, amount DESC) as p FROM grpРезультат выполнения
ticketdate | tickettype | person1 | person2 | qty | amount | p ------------+--------------+-------------------------+----------------------+-----+--------+--- 2025-02-20 | Standard | Иванов Иван Иванович | Иванов Иван Иванович | 1 | 2000 | 1 2025-02-19 | Allinclusive | Иванов Иван Иванович | Иванов Иван Иванович | 1 | 4000 | 2 2025-02-18 | Dual | Иванов Иван Иванович | Попов Федор Иванович | 2 | 6000 | 3 2025-02-18 | Standard | Иванов Иван Иванович | Иванов Иван Иванович | 1 | 2000 | 4 2025-02-17 | Dual | Кузнецов Петр Сергеевич | Попов Федор Иванович | 2 | 6000 | 5 2025-02-15 | Allinclusive | Попов Федор Иванович | Попов Федор Иванович | 1 | 4000 | 6 (6 rows) -
Подзапрос r — вычисление статуса билета. Определяем статус билета. Обрабатываем рекурсивно билеты, начиная с тех, статус которых еще не определен. Для каждого билета определяем статус ‘A’ (Approved), ‘R’ (Rejected) или оставляем null, пока статус неопределен. Повторяем рекурсивно, пока статусы всех билетов не будут определены.
SELECT p, tickettype, person1, person2, qty, amount, NULL::text status FROM t UNION ALL (WITH rr AS (SELECT * FROM r), top AS ( SELECT * FROM rr WHERE status IS NULL ORDER BY p LIMIT 1 ) SELECT t.p, t.tickettype, t.person1, t.person2, t.qty, t.amount, CASE WHEN t.p = top.p THEN 'A' -- approved WHEN t.person1 = top.person1 OR t.person1 = top.person2 OR t.person2 = top.person1 OR t.person2 = top.person2 THEN 'R' -- rejected ELSE NULL -- пока непонятно END FROM t JOIN rr ON t.p = rr.p CROSS JOIN top WHERE rr.status IS NULL )Результат выполнения
p | tickettype | person1 | person2 | qty | amount | status ---+--------------+-------------------------+----------------------+-----+--------+------- 1 | Standard | Иванов Иван Иванович | Иванов Иван Иванович | 1 | 2000 | 2 | Allinclusive | Иванов Иван Иванович | Иванов Иван Иванович | 1 | 4000 | 3 | Dual | Иванов Иван Иванович | Попов Федор Иванович | 2 | 6000 | 4 | Standard | Иванов Иван Иванович | Иванов Иван Иванович | 1 | 2000 | 5 | Dual | Кузнецов Петр Сергеевич | Попов Федор Иванович | 2 | 6000 | 6 | Allinclusive | Попов Федор Иванович | Попов Федор Иванович | 1 | 4000 | 1 | Standard | Иванов Иван Иванович | Иванов Иван Иванович | 1 | 2000 | A 2 | Allinclusive | Иванов Иван Иванович | Иванов Иван Иванович | 1 | 4000 | R 3 | Dual | Иванов Иван Иванович | Попов Федор Иванович | 2 | 6000 | R 4 | Standard | Иванов Иван Иванович | Иванов Иван Иванович | 1 | 2000 | R 5 | Dual | Кузнецов Петр Сергеевич | Попов Федор Иванович | 2 | 6000 | 6 | Allinclusive | Попов Федор Иванович | Попов Федор Иванович | 1 | 4000 | 5 | Dual | Кузнецов Петр Сергеевич | Попов Федор Иванович | 2 | 6000 | A 6 | Allinclusive | Попов Федор Иванович | Попов Федор Иванович | 1 | 4000 | R (14 rows) -
Подзапрос approved — отбор только действительных билетов. Оставляем только билеты со статусом Approved.
SELECT * FROM t WHERE p IN (SELECT p FROM r WHERE status = 'A')Результат выполнения
ticketdate | tickettype | person1 | person2 | qty | amount | p ------------+------------+-------------------------+----------------------+-----+--------+-- 2025-02-20 | Standard | Иванов Иван Иванович | Иванов Иван Иванович | 1 | 2000 | 1 2025-02-17 | Dual | Кузнецов Петр Сергеевич | Попов Федор Иванович | 2 | 6000 | 5 (2 rows) -
Финальный запрос - агрегация результатов. Считаем статистику по типам билетов; если каких-либо типов билетов нет, в статистику не добавляем пустые строки. Для каждого типа билета вычисляем количество билетов, количество участников и общую сумму. В конце вычисляем итоговую строку с помощью grouping sets.
SELECT tickettype, count(*) AS tickets, sum(qty) participants, sum(amount) AS sum FROM approved GROUP BY GROUPING SETS (tickettype,()) order by tickettype;Результат выполнения
tickettype | tickets | participants | sum ------------+---------+--------------+------ Dual | 1 | 2 | 6000 Standard | 1 | 1 | 2000 | 2 | 3 | 8000 (3 rows)
Решение полностью
WITH RECURSIVE grp AS (
SELECT id_ticket,
min(ticketdate) ticketdate,
min(tickettype) tickettype,
min(person) person1,
max(person) person2,
count(*) qty,
CASE min(tickettype) WHEN 'Standard' THEN 2000
WHEN 'Allinclusive' THEN 4000
ELSE 6000
END AS amount
FROM tickets t
GROUP BY id_ticket
), t AS (
SELECT ticketdate,
tickettype,
person1,
person2,
qty,
amount,
row_number() OVER (ORDER BY ticketdate DESC, amount DESC) p
FROM grp
), r AS (
SELECT p,
tickettype,
person1,
person2,
qty,
amount,
NULL::text status
FROM t
UNION ALL
(
WITH rr AS (SELECT * FROM r),
top AS (
SELECT *
FROM rr
WHERE status IS NULL
ORDER BY p
LIMIT 1
)
SELECT t.p,
t.tickettype,
t.person1,
t.person2,
t.qty,
t.amount,
CASE WHEN t.p = top.p
THEN 'A' -- approved
WHEN t.person1 = top.person1
OR t.person1 = top.person2
OR t.person2 = top.person1
OR t.person2 = top.person2
THEN 'R' -- rejected
ELSE NULL -- пока непонятно
END
FROM t
JOIN rr ON t.p = rr.p
CROSS JOIN top
WHERE rr.status IS NULL
)
), approved AS (
SELECT *
FROM t
WHERE p IN (SELECT p
FROM r
WHERE status = 'A'
)
)
SELECT tickettype,
count(*) AS tickets,
sum(qty) participants,
sum(amount) AS sum
FROM approved
GROUP BY GROUPING SETS (tickettype,())
order by tickettype;Задача 4. Игра «Быки и коровы»
Задача 4 и 5 — попытка поиграть в логическую игру «Быки и коровы».
Правила игры
Логическая игра рассчитана на двух игроков. Каждый из игроков задумывает и записывает тайное 4-значное число с неповторяющимися цифрами в шестнадцатеричной системе счисления (0..9, A, B, C, D, E, F). Игрок, который начинает игру по жребию, делает первую попытку отгадать число. Попытка — это 4-значное число с неповторяющимися цифрами, сообщаемое противнику. Противник сообщает в ответ, сколько цифр угадано без совпадения с их позициями в тайном числе (то есть количество «коров») и сколько угадано вплоть до позиции в тайном числе (то есть количество «быков»).
Рассмотрим пример.
Пусть задумано тайное число «32F9».
Попытка: «23F0».
Результат: две «коровы» (две цифры: 2 и 3 угаданы на неверных позициях) и один «бык» (одна цифра F угадана вплоть до позиции).
Условие 4-й задачи
Вам дана последовательность ходов одного игрока и тайное число другого игрока. Необходимо для каждого хода определить количество «коров» и «быков». Количество «быков» указывается как число перед буквой B, количество «коров» — как число перед буквой C. В нашем примере для тайного числа 32F9 и попытки 23F0 мы должны получить 1B2C. Результат должен быть представлен в виде строки с последовательностью ходов, в которой к каждому ходу через пробел дописан ответ другого игрока.
Исходная строка ходов одного игрока должна состоять только из четырехзначных шестнадцатеричных чисел с неповторяющимися цифрами, разделенных запятыми. Секретное число также должно быть четырехзначным шестнадцатеричным числом с неповторяющимися цифрами. Если эти условия нарушены, то запрос должен вернуть строку error в качестве результата своей работы. Все сравнения букв должны быть регистронезависимыми.
Последовательность ходов задается в конфигурационном параметре bulls.game.
Секретное число в находится в конфигурационном параметре bulls.secretcode.
Пример:
-
Правильные данные
set bulls.game = '56F8,9D13,3426,25b3,6D9A,3029'; set bulls.secretcode = '3D29';Запрос должен вернуть
gameparty ------------------------------------------------------------- 56F8 0B0C,9D13 1B2C,3426 2B0C,25B3 0B2C,6D9A 1B1C,3029 3B0C (1 row) -
Данные с ошибкой, в третьем числе 5 цифр.
set bulls.game = '56F8,9D13,3426F,25B3,6D9A,3029'; set bulls.secretcode = '3D29';Запрос должен вернуть
gameparty ----------- error (1 row)
Разбор решения
Формализуем правила:
Секретное число — строка из 4-х уникальных символов шестнадцатеричной системы счисления.
Последовательность ходов — строка, содержащая одно или более четырехзначных шестнадцатеричных чисел с уникальными символами, числа разделены запятыми.
Все числа должны записываться ровно четырьмя символами, все символы должны быть уникальны.
Допустимые символы 0-9, A-F.
-
Выходные данные — строка, содержащая все ходы, дополненные через пробел результатом в формате XBYC, где:
X — количество «быков» (полных совпадений цифры и ее позиции в секретном числе);
Y — количество «коров» (совпадение цифры, но не позиции).
Если входные данные не соответствуют требованиям, возвращаем строку error.
Решение
Будем рассматривать запрос на примере данных из формулировки задачи.
-
Подзапрос lvGame — обработка ходов игрока. Разбиваем строку с ходами на массив с сохранением порядка ходов. Для каждого хода проверяем правильность формирования. Одним регулярным выражением проверяем, что все символы в коде уникальны, другим проверяем, что ход состоит ровно из 4 шестнадцатеричных цифр. Если условия не выполняются, то признак isError будет истинным.
select N, code, not (code !~ '(.).*\1' and code ~ '^[0-9A-F]{4}$') isError from unnest(('{'||upper(current_setting('bulls.game'))||'}')::text[]) with ordinality as G(code,N)Результат выполнения
n | code | iserror ---+------+--------- 1 | 56F8 | f 2 | 9D13 | f 3 | 3426 | f 4 | 25B3 | f 5 | 6D9A | f 6 | 3029 | f (6 rows) -
Подзапрос lvSecretCode — обработка секретного кода.Секретный код проверяем аналогично и устанавливаем признак isError в истинное значение в случае ошибки.
select code, not (code !~ '(.).*\1' and code ~ '^[0-9A-F]{4}$') as isError from upper(current_setting('bulls.secretcode')) as codeРезультат выполнения
code | iserror ------+--------- 3D29 | f (1 row) -
Подзапрос lvCodes — вычисление «быков» и «коров». Вычисляем «быков» и «коров», если в исходных данных нет ошибки. Первый подзапрос вычисляет «быков», идет проверка на совпадение символов и их позиций. Второй подзапрос вычисляет «коров», проверяется совпадение символов и несовпадение позиций.
select N, code, (SELECT COUNT(*) FROM unnest(string_to_array(g.code, NULL)) WITH ORDINALITY AS gv(digit, pos) JOIN unnest(string_to_array((select code from lvSecretCode), NULL)) WITH ORDINALITY AS sc(digit, pos) ON gv.pos = sc.pos AND gv.digit = sc.digit) as bulls, (SELECT COUNT(*) FROM unnest(string_to_array(g.code, NULL)) WITH ORDINALITY AS gv(digit, pos) JOIN unnest(string_to_array((select code from lvSecretCode), NULL)) WITH ORDINALITY AS sc(digit, pos) ON gv.pos != sc.pos AND gv.digit = sc.digit) as cows from lvgame g where not exists (select 1 from lvgame where isError) and not exists (select 1 from lvSecretCode where isError)Результат выполнения
n | code | bulls | cows ---+------+-------+------ 1 | 56F8 | 0 | 0 2 | 9D13 | 1 | 2 3 | 3426 | 2 | 0 4 | 25B3 | 0 | 2 5 | 6D9A | 1 | 1 6 | 3029 | 3 | 0 (6 rows) -
Финальный запрос формирует выходную строку. Собираем выходную строку в порядке кодов в исходной строке и добавляем количество «быков» и «коров». Если была ошибка, то выводим ‘error’.
select coalesce (string_agg(code||' '||bulls||'B'||cows||'C',',' order by n),'error') as gameparty from lvCodes;Результат выполнения
gameparty ------------------------------------------------------------- 56F8 0B0C,9D13 1B2C,3426 2B0C,25B3 0B2C,6D9A 1B1C,3029 3B0C (1 row)
Решение полностью
with lvgame as (
select N,
code,
not (code !~ '(.).*\1' and code ~ '^[0-9A-F]{4}$') as isError
from unnest(('{'||upper(current_setting('bulls.game'))||'}')::text[]) with ordinality as G(code,N)
),
lvSecretCode as (
select code,
not (code !~ '(.).*\1' and code ~ '^[0-9A-F]{4}$') as isError
from upper(current_setting('bulls.secretcode')) as code
),
lvCodes as(
select N,
code,
(select COUNT(*)
from unnest(string_to_array(g.code, NULL)) with ordinality as gv(digit, pos)
JOIN unnest(string_to_array((select code from lvSecretCode), NULL)) with ordinality as sc(digit, pos)
ON gv.pos = sc.pos AND gv.digit = sc.digit) as bulls,
(select COUNT(*) from unnest(string_to_array(g.code, NULL)) with ordinality as gv(digit, pos)
JOIN unnest(string_to_array((select code from lvSecretCode), NULL)) with ordinality as sc(digit, pos)
ON gv.pos != sc.pos AND gv.digit = sc.digit) as cows
from lvgame g
where not exists (select 1 from lvgame where isError)
and not exists (select 1 from lvSecretCode where isError)
)
select coalesce (string_agg(code||' '||bulls||'B'||cows||'C',',' order by n),'error') as gameparty
from lvCodes;Задача 5. Вариант хода игры «Быки и коровы»
Правила игры были описаны ранее.
Условие
Вам дана последовательность ходов одного игрока с указанием количества быков и коров для каждого хода. Правила формирования строки описаны в формулировке задачи 4 для строки результата. Вам необходимо найти вариант следующего хода как максимальное четырехзначное число, удовлетворяющее последовательности заданных ходов. Если входные данные нарушают правила игры, либо в строке не указано количество быков или коров, то запрос ничего не возвращает, так как следующий ход невозможен. Все сравнения символов должны быть регистронезависимыми.
Последовательность ходов задается в конфигурационном параметре bulls.gameparty.
Пример:
-
Правильные данные.
set bulls.gameparty='56f8 0B0C,9D13 1B2C,341F 1B0C,25B3 0B2C';Запрос должен вернуть
code ------ 3D9B (1 row)В данном примере последовательности ходов соответствуют три числа 3D9B, 3D92 и 3D29, большее из них — 3D9B.
-
Данные с ошибкой: в третьем числе используется символ, не являющийся шестнадцатеричной цифрой.
set bulls.gameparty='56F8 0B0C,9D13 1B2C,341H 1B0C,25B3 0B2C';Запрос должен вернуть
code ------ (0 rows)
Разбор решения
Данная задача, конечно же, перекликается с предыдущей. По сути, сначала была придумана эта задача, но в процессе подготовки тестов для их формирования был сделан запрос 4-й задачи. Так и появилась данная связка. Было предложено находить максимально возможное число, тем самым мы формализуем ответ и добиваемся его единственности.
Формализуем правила:
Последовательность ходов — строка символов, разделенных запятыми в формате 9999 XBYC, где 9999 — четырехзначное шестнадцатеричное число, X — количество «быков», Y — количество «коров» по сравнению с секретным числом.
Каждый ход должен записываться ровно четырьмя символами, все символы должны быть уникальны.
Допустимые символы 0-9, A-F.
Число «быков» и «коров» — цифры от 0 до 4.
Вся строка должна соответствовать формату входных данных.
В результате мы должны получить четырехзначное шестнадцатеричное число, которое согласуется со всеми предыдущими ходами и их результатами, а также является максимальным из возможных.
Если исходные данные не корректны, то возвращается пустой результат.
Решение
Будем рассматривать запрос на примере данных из формулировки задачи.
-
Подзапрос lvGameParty — парсинг входных данных. Разбиваем исходную строку на массив с сохранением порядка ходов. Для извлечения числа и количества «быков» и «коров» используем регулярные выражения.
select N, substring(code,'^[0-9A-F]{4} ') code, substring(code,' (\d)B.C')::int bulls, substring(code,' .B(\d)C')::int cows from unnest(('{'||upper(current_setting('bulls.gameparty'))||'}')::text[]) with ordinality as G(code,N)Результат выполнения
n | code | bulls | cows ---+-------+-------+------ 1 | 56F8 | 0 | 0 2 | 9D13 | 1 | 2 3 | 341F | 1 | 0 4 | 25B3 | 0 | 2 (4 rows) -
Подзапрос lvPossibleCodes — генерация всех возможных ходов. Генерируем все варианты ходов от 0000 до FFFF, из них оставляем только те, которые удовлетворяют требованиям к ходам (все цифры в числе уникальны). Числа будут сгенерированы, только если входные данные корректны.
select code::CHAR(4) from (select LPAD(upper(to_hex(num)), 4, '0') AS code from generate_series(0, 65535) AS num) where code !~ '(.).*\1' and code ~ '^[0-9A-F]{4}$' and not exists (select 1 from lvGameParty GP where (GP.code is null or GP.bulls is null or GP.cows is null or GP.code ~ '(.).*\1'))Результат выполнения
code ------ 0123 0124 0125 0126 0127 0128 0129 012A 012B 012C 012D 012E 012F 0132 0134 0135 0136 0137 0138 0139 ... -
Подзапрос lvValidCodes — проверка возможного хода на соответствие истории игры. Каждое сгенерированное число проверяется на соответствие ходам из истории игры. Оставлены только те числа, которые соответствуют всем ходам из истории, то есть у них совпадает количество «быков» и «коров» в сравнении с ходом из истории.
select pc.code from lvPossibleCodes pc where not exists (select 1 from lvGameParty g where ((select COUNT(*) from unnest(string_to_array(g.Code, NULL)) with ordinality as gv(digit, pos) join unnest(string_to_array(pc.Code, NULL)) with ordinality as sc(digit, pos) on gv.pos = sc.pos AND gv.digit = sc.digit) != g.bulls or (select COUNT(*) from unnest(string_to_array(g.Code, NULL)) with ordinality AS gv(digit, pos) join unnest(string_to_array(pc.Code, NULL)) with ordinality AS sc(digit,pos) on gv.digit = sc.digit and gv.pos != sc.pos) != g.cows) )Результат выполнения
code ------ 3D29 3D92 3D9B (3 rows) -
Финальный запрос. Он из всех подходящих ходов оставляет один максимальный, как было указано в условии.
select Code from lvValidCodes order by Code desc limit 1;Результат выполнения
code ------ 3D9B (1 row)
Решение полностью:
with lvGameParty as (
select N,
substring(code,'^[0-9A-F]{4} ') code, -- берем само число 4 цифры и проверяем что после него пробел
substring(code,' (\d)B.C')::int bulls, -- определяем количество быков
substring(code,' .B(\d)C')::int cows -- определяем количество коров
from unnest(('{'||upper(current_setting('bulls.gameparty'))||'}')::text[]) with ordinality as G(code,N)
),
lvPossibleCodes AS (
select
code::CHAR(4)
from
(select
LPAD(upper(to_hex(num)), 4, '0') AS code
from
generate_series(0, 65535) AS num
)
where
code !~ '(.).*\1' -- все цифры в числе уникальны
and code ~ '^[0-9A-F]{4}$' -- проверка что 4 цифры в 16-тиричной системе счисления
-- проверка что данные в строке партии корректны, если это не так, не генерируем ходы
and not exists (select 1 from lvGameParty GP where (GP.code is null or GP.bulls is null or GP.cows is null or GP.code ~ '(.).*\1'))
),
lvValidCodes AS (
select
pc.code
from
lvPossibleCodes pc
where
not exists (
select 1
from lvGameParty g
where
(
-- Проверка на быков и коров
(select COUNT(*) from unnest(string_to_array(g.Code, NULL)) with ordinality as gv(digit, pos)
join unnest(string_to_array(pc.Code, NULL)) with ordinality as sc(digit, pos)
ON gv.pos = sc.pos AND gv.digit = sc.digit) != g.bulls
OR
(select COUNT(*) from unnest(string_to_array(g.Code, NULL)) with ordinality AS gv(digit, pos)
join unnest(string_to_array(pc.Code, NULL)) with ordinality AS sc(digit,pos)
on gv.digit = sc.digit and gv.pos != sc.pos) != g.cows
)
)
)
select Code
from lvValidCodes
order by Code desc
limit 1;Общие наблюдения
Очень много запросов даже не проверялись на корректность путем запуска на тестовой базе с примером из формулировки. Как следствие, они не проходили даже начальный тест из формулировки. Зачем прислать запрос, который не дает известный ответ на предложенных данных, ведь это значит, что он заведомо не правильный?
Но были примеры еще более интересные. Много запросов, которые в принципе не выполнялись, с синтаксическими ошибками, использованием несуществующих в PostgreSQL функций и конструкций. Все это выглядело, как будто ИИ сформировал запрос, и его, даже не попытавшись запустить на тестовых данных, просто отправили на проверку. Какой будет результат на проверке? Конечно же 0 баллов.
Часть запросов не смогли пройти все тесты, причем иногда достаточно простые и очевидные.
Резюме: на ИИ надейся, но сам не плошай.
erogov
Покажу и свое решение задачи про параметры. Оно использует рекурсивный запрос и JSON для отслеживания текущего состояния параметров (есть удобные операции
-и||для удаления и добавления ключа в объект, получается имитация множества).