- PVSM.RU - https://www.pvsm.ru -
Мы продолжаем свое участие в международной олимпиаде «IT-Планета». Как и в прошлые годы, проводился конкурс по SQL, состоящий из трех этапов: теоретический и практический туры, проходящие онлайн, и финальный очный тур.
В первом туре участвовало свыше 4 500 человек, из которых 245 были отобраны во второй. В этом году я занимался разработкой задач и проведением первых двух туров. Предлагаю перейти к рассмотрению задач практического этапа.
Карлсон очень любит есть варенье. Он ощущает прилив бодрости, когда третий день подряд съедает не меньше одной банки варенья в день, и притом, съедает за эти дни не меньше четырех банок варенья.
Карлсон чувствует себя счастливым, когда ощущает прилив бодрости как минимум 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.
Усложнялась логика при работе с пропусками в датах.
Отсутствовала агрегация в данных за день.
Имеется установленный кластер 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 году мы уже встречались с задачей «Многоголовый Цербер [1]». Данная задача решается аналогично. Суть решения заключается в построении для каждого параметра мультидиапазона, охватывающего все периоды, когда параметр имел значение, отличное от значения по умолчанию. Затем необходимо найти пересечения этих мультидиапазонов и определить интервалы с максимальным количеством одновременно активных параметров. Основное преимущество такого подхода — естественная работа с открытыми интервалами, поскольку диапазоны автоматически поддерживают бесконечные границы. Это избавляет от необходимости искусственно ограничивать последний период. В решениях конкурсантов встречались ограничения текущей датой, максимальной датой из таблицы или произвольно выбранной датой в будущем.
Многие участники пытались решить задачу без использования диапазонов, применяя аналитические функции и сложные соединения подзапросов. Однако такие решения часто оказывались неполными, так как не учитывали все возможные случаи, особенно с открытыми интервалами и сложными пересечениями периодов активности параметров. В отличие от них, решения на основе диапазонов и мультидиапазонов демонстрировали высокую надежность и проходили все тестовые случаи, поскольку эта технология специально разработана для работы с временными интервалами и их пересечениями. Мультидиапазоны обеспечивают точный и полный учет всех возможных комбинаций активных параметров в любой момент времени. Ключевое преимущество подхода с диапазонами заключается в его концептуальной чистоте — он позволяет работать с временными интервалами, как с объектами, избегая сложных и подверженных ошибкам ручных вычислений границ периодов и их пересечений.
Здесь и далее будем рассматривать решения использованные в качестве эталонов при тестировании запросов.
Рассмотрим решение на следующем примере данных
Скрипт
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) для обращения к следующим (предыдущим) строкам для вычисления диапазонов.
Для обеспечения бесконечности диапазона использовалась текущая дата, очень большая дата в будущем или ставилось ограничение максимальной датой из рассматриваемых.
Эта задача оказалась самой сложной, всего 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 и 5 — попытка поиграть в логическую игру «Быки и коровы».
Логическая игра рассчитана на двух игроков. Каждый из игроков задумывает и записывает тайное 4-значное число с неповторяющимися цифрами в шестнадцатеричной системе счисления (0..9, A, B, C, D, E, F). Игрок, который начинает игру по жребию, делает первую попытку отгадать число. Попытка — это 4-значное число с неповторяющимися цифрами, сообщаемое противнику. Противник сообщает в ответ, сколько цифр угадано без совпадения с их позициями в тайном числе (то есть количество «коров») и сколько угадано вплоть до позиции в тайном числе (то есть количество «быков»).
Рассмотрим пример.
Путь задумано тайное число «32F9».
Попытка: «23F0».
Результат: две «коровы» (две цифры: 2 и 3 угаданы на неверных позициях) и один «бык» (одна цифра F угадана вплоть до позиции).
Вам дана последовательность ходов одного игрока и тайное число другого игрока. Необходимо для каждого хода определить количество «коров» и «быков». Количество «быков» указывается как число перед буквой 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 codecode | 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;Правила игры были описаны ранее [2].
Вам дана последовательность ходов одного игрока с указанием количества быков и коров для каждого хода. Правила формирования строки описаны в формулировке задачи 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 баллов.
Часть запросов не смогли пройти все тесты, причем иногда достаточно простые и очевидные.
Резюме: на ИИ надейся, но сам не плошай.
Автор: Zheka22
Источник [3]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/postgresql/423582
Ссылки в тексте:
[1] Многоголовый Цербер: https://habr.com/ru/companies/postgrespro/articles/808211/
[2] ранее: #%D0%9F%D1%80%D0%B0%D0%B2%D0%B8%D0%BB%D0%B0
[3] Источник: https://habr.com/ru/companies/postgrespro/articles/919426/?utm_campaign=919426&utm_source=habrahabr&utm_medium=rss
Нажмите здесь для печати.