Главная » Хабрахабр » Олимпиада SQL: разбор задачи про календарь

Олимпиада SQL: разбор задачи про календарь

Здравствуйте, в эфире Радио SQL!

Впрочем, жители других планет, тоже подтягивайтесь. Продолжаем тему популяризации языка SQL среди широких масс IT-населения нашей планеты, на этот раз в русскоязычной его части.

Настраивайтесь на нашу гравитационную волну, смахивайте слизь, поправляйте панцири и устраивайтесь поудобнее — мы начинаем!..

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

Чтобы избежать тупого copy-paste, я намерено предприму пару действий, которые позволят получить готовый результат только тем, кто немного поработает головой. Обращаю внимание, что это именно разбор, а не готовое решение.

Чтобы получить финальное решение, придётся осмысленно собрать все части запроса в одно целое. Во-первых, я не буду приводить полный и окончательный код запроса. Также я опущу некоторые громоздкие, но совершенно неинтересные части (типа выравнивания названий месяцев по центру) для доработки желающими напильником по месту самостоятельно. Для человеков это несложно, достаточно задействовать головные ганглии. Но меня это не волнует ни капли, так как моя цель — показать как подобные задачи решаются в принципе, а не получить готовый результат в данном частном случае. Соответственно, собранный результат без некоторой доводки формально не будет правильным решением исходной задачи.

Конечно любая сколько-нибудь нетривиальная задача требует всяких плюшек, которые в разных вариантах SQL поддерживаются слегка по-разному, вызывая размышления о том, что наша матрица всё же слегка сбоит. Во-вторых, я возьму другой, не оракловый диалект SQL. Также нам будут нужны рекурсивные запросы или их аналог для генерации последовательностей заранее неизвестной длины, и, наконец, агрегатная функция склейки строк, чтобы собрать всё вместе. Нам существенным образом нужны будут CTE, которые позволяют собирать части запроса с подвыражением WITH ..., да и входные параметры в условии задачи так заданы. Это и PostgreSQL, и SQLite, и даже MySQL наконец-то стал поддерживать CTE. С такими мягкими ограничениями на роль SQL-сервера может претендовать любая кофемолка почти что угодно, где в описании встречается аббревиатура SQL. Коммерческие БД само собой всё это давно умеют.

Выразить все необходимые шаги решения на другом диалекте SQL не должно быть проблемой, лично я с этим справился быстро. Поколебавшись некоторое время, я остановил свой выбор на PostgreSQL, чтобы пощупать поближе, как он по сравнению с оракловой базой будет смотреться в этой задаче. Ну и мне интереснее будет, не всё же только публике развлечения. Напомню, что на олимпиаде, откуда взята задача, использовался именно Oracle SQL, на котором и было изначально написано референсное решение.

Напомню условие. Что ж, шутки в сторону, приступим к разбору.

Задача №1. Календарь

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

with param(year, c, r) (…)

где, соответственно,

  • year – год календаря
  • c – количество столбцов матрицы календаря
  • r – количество строк матрицы.

Числа в каждом месяце расположены по дням недели, первый день недели в первом столбце и так далее. Месяцы расположены в клетках матрицы календаря по порядку слева направо и потом сверху вниз. Название месяца берётся тоже из настроек локализации и выводится по центру над числами. Начало недели должно соответствовать настройкам локализации базы на момент запуска запроса. Самой первой строчкой должен идти выровненный по центру год. Между месяцами нужно оставить промежуток, чтобы числа соседних месяцев «не слипались». Пустых строк быть не должно.

Например, при следующих заданных параметрах:

with param(year, c, r) as (select 2016, 3, 4 from dual)

должен получиться следующий вывод запроса:

2016 Январь Февраль Март 1 2 3 1 2 3 4 5 6 7 1 2 3 4 5 6 4 5 6 7 8 9 10 8 9 10 11 12 13 14 7 8 9 10 11 12 13 11 12 13 14 15 16 17 15 16 17 18 19 20 21 14 15 16 17 18 19 20 18 19 20 21 22 23 24 22 23 24 25 26 27 28 21 22 23 24 25 26 27 25 26 27 28 29 30 31 29 28 29 30 31 Апрель Май Июнь 1 2 3 1 1 2 3 4 5 4 5 6 7 8 9 10 2 3 4 5 6 7 8 6 7 8 9 10 11 12 11 12 13 14 15 16 17 9 10 11 12 13 14 15 13 14 15 16 17 18 19 18 19 20 21 22 23 24 16 17 18 19 20 21 22 20 21 22 23 24 25 26 25 26 27 28 29 30 23 24 25 26 27 28 29 27 28 29 30 30 31 Июль Август Сентябрь 1 2 3 1 2 3 4 5 6 7 1 2 3 4 4 5 6 7 8 9 10 8 9 10 11 12 13 14 5 6 7 8 9 10 11 11 12 13 14 15 16 17 15 16 17 18 19 20 21 12 13 14 15 16 17 18 18 19 20 21 22 23 24 22 23 24 25 26 27 28 19 20 21 22 23 24 25 25 26 27 28 29 30 31 29 30 31 26 27 28 29 30 Октябрь Ноябрь Декабрь 1 2 1 2 3 4 5 6 1 2 3 4 3 4 5 6 7 8 9 7 8 9 10 11 12 13 5 6 7 8 9 10 11 10 11 12 13 14 15 16 14 15 16 17 18 19 20 12 13 14 15 16 17 18 17 18 19 20 21 22 23 21 22 23 24 25 26 27 19 20 21 22 23 24 25 24 25 26 27 28 29 30 28 29 30 26 27 28 29 30 31 31

Подход к решению

Ну, то есть нужно уметь программировать вообще, полезно знать, что такое рекурсия и т.п. Чем мне самому очень импонирует эта задача, так это тем, что для её решения не нужны никакие специальные знания алгоритмов или ещё чего бы то ни было специфического из компьютерных наук. Но задача распадается на несколько шагов, на каждом из которых есть свои нюансы. По моему это всё сейчас ещё в школе проходят. В результате и задачка получилась не слишком сложная, но и не сказать чтобы тривиальная.

С высотой всё совсем просто — все диалекты SQL так или иначе позволяют генерировать запросами заданное параметром количество записей. Единственное действительно нетривиальное, что тут есть — это представить себе, как можно сгенерировать матрицу календаря, когда ширина и высота задаются параметрами. Например, в том же PostgreSQL нашлась специальная конструкция generate_series(MIN, MAX), которая генерирует серию значений от MIN до MAX. Обычно это рекурсивные запросы, хотя иногда и попадаются специальные конструкции. Можно воспользоваться и "классическим" рекурсивным запросом вида:

with recursive seq(n) as ( select MIN union all select n+1 from seq where n<MAX)

Так можно получить нужное количество строк. , но специальная конструкция будет короче.

В принципе всё так же, как и со строками выше, можно сгенерировать необходимое количество записей. Теперь определимся с тем, как сгенерировать количество столбцов, заданных параметром. В PostgreQSL для этого нашлась подходящая функция string_agg(): А потом, когда их надо будет вывести, сгруппируем и склеим эти записи агрегатной функцией для работы со строками.

select string_agg(t::text,'-') from generate_series(MIN,MAX) as s(t);

Каждый месяц будем представлять в виде знакомест в 6 строк по 7 столбцов для каждого из дней месяца, вот так: С помощью этой техники мы сгенерируем матрицу-заготовку для календаря, в которой по горизонтали и вертикали будет нужное количество месяцев, заданное в параметрах.

xx xx xx xx xx xx xx
xx xx xx xx xx xx xx
xx xx xx xx xx xx xx
xx xx xx xx xx xx xx
xx xx xx xx xx xx xx
xx xx xx xx xx xx xx

По столбцам месяцеместа мы потом будем расставлять числа в соответствии с днями недели. Назовём каждую такую конструкцию месяцеместом, так дальше будет удобно ссылаться. Столбцов нужно семь по количеству дней недели, строк пусть будет шесть. А по строкам в соответствии с номером недели в месяце — сначала первую строчку заполнять, потом вторую и так далее. Я конечно имею в виду земной Григорианский календарь. Больше шести недель в месяце никак не может быть. Просьба жителям других планет отнестись с пониманием, эта задача была придумана в первую очередь для землян XXI века (013 в тентуре, налево от БМ).

Нам нужно будет сгенерировать все дни года, чтобы потом их расставить в полученную выше матрицу. Теперь, когда с самым нетривиальным стало всё понятно, займёмся остальными техническими деталями. Например, с учётом того, что год может быть високосный. Тут закавыка может быть с тем, чтобы правильно определить это количество дней. Так что дни нужного года будем получать так: все дни с первого дня года, указанного в параметрах, и до (но не включая) первого дня следующего года. Или вот в земном Григорианском календаре в 1582 году отсутствуют дни с 05 по 14 октября (и Oracle честно это показывает!).

И последним шагом нам нужно будет аккуратно собрать всё вместе, добавить названия месяцев и номер года сверху, убрать пустые строчки и т.п.

Итого по порядку:

  1. Сгенерировать все дни года.
  2. Сгенерировать матрицу-заготовку с нужным количеством строк и столбцов.
  3. Вписать дни года в матрицу календаря на нужные места.
  4. Собрать всё вместе для вывода результатов.

Реализация

Поехали.

Вот наши исходные параметры для задачи:

with params(year, r, c) as (select 2016, 3, 4)

Сами дни можно сгенерировать через generate_series(START_DATE, END_DATE), указав началом первый день года и концом предыдущий день от первого дня следующего года. Генерация всех дней года. Мы можем получать эти данные по мере надобности, но это будет громоздко, лучше посчитать сразу. Дальше нам кроме самой даты понадобится из неё получить некоторые полезные данные, которые нам пригодятся: номер дня недели, номер месяца, номер дня в месяце и день недели для первого дня месяца. Посмотрев документацию по функциям работы с датами в PostgreSQL, я вижу, что для этого можно воспользоваться функцией extract().

...
days(day, moy, dom, dow, fdow) as (select d -- day of year (date) , extract(month from d)::int-1 -- month, 0-11 , extract(day from d)::int -- day of month, 1-31 , extract(isodow from d)::int-1 -- day of week, 0-6 , extract(isodow from date_trunc('month', d))::int-1 -- day of week of first day in month, 0-6 from params p , generate_series( (p.year ||'-01-01')::date , ((p.year+1)||'-01-01')::date - 1, '24:00') as s(d))

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

...
matrix(c, r, moy, pos) as (select c.c, r.r, c.c/7 + r.r/6*p.c, c.c%7 + r.r%6*7 + 1 from params p , generate_series(0, p.c*7-1) as c(c) -- columns , generate_series(0, p.r*6-1) as r(r)) -- rows

Как я и сказал, с учётом предварительной подготовки, это делается на раз: Теперь собираем вместе, расставляя дни по местам.

...
cal (r,c,dom) as (select r,c,dom from matrix m left outer join days d on d.moy = m.moy -- same month and d.fdow+d.dom = m.pos -- position is day no plus weekday of first day
)

Либо заполнятся все месяцеместа и часть останется пустыми, либо лишние месяцы не поместятся, но в обоих случаях матрица не разъедется. Что характерно, если в параметрах задачи матрица календаря по размерам получится больше или меньше 12 месяцев, то всё сработает корректно.

Осталось всё аккуратно собрать вместе в cal_all. Всё, основная часть сделана. Начнём с месяцемест с числами:

...
cal_all (no, line) as (-- days in cal matrix select r, string_agg(lpad(coalesce(dom::text,' '), 3+case when c%7=0 then 2 else 0 end) ,'' order by c) from cal group by r
...

При этом пустые значения дней заменяются на пробелы, и все числа дополняются слева пробелами, чтобы их выровнять. Тут склеивается в одну строчку функцией string_agg() всё, что попало в одну строку матрицы календаря. Это позволяет визуально отделить месяцы друг от друга. Причём внутри одного месяцеместа на каждое число отводится по 3 знакоместа, а между месяцами (условие c%7=0) — по 5. По нему будет определяться правильный порядок в финальном выводе. Также обращаю внимание на то, что мы сохраняем номер строки.

Для этого выбираем из уже сделанного ранее представления days только первые дни месяца, группируем их по params.c штук в строке и склеиваем с помощью string_agg(). Дальше добавляем сюда же названия месяцев. Не забываем дополнить каждое имя пробелами, чтобы месяцы были над своими месяцеместами, а также дать каждой получившейся строке такой номер, чтобы в финальной сортировке месяцы встали на свои места. Если в матрицу календаря не помещаются все месяцы, то возьмём названия только тех, что помещаются. Всё вместе получается так: То есть первая строчка с месяцами должна встать перед первой строкой с числами, вторая перед седьмой (помните, что мы по шесть строк на месяц отводили?) и так далее.

... union all -- month names select (moy/p.c)*6-0.5, string_agg(lpad(to_char(day, 'Month'), 7*3+2) , '' order by moy) from days d, params p where dom = 1 -- first days of months only and moy < p.r*p.c group by (moy/p.c)

Осталось сверху посередине дописать год:

... union all select -1, lpad(year::text, (7*3+2)*c/2+length(year::text)/2) from params

Теперь осталось из cal_all выбрать все строки в правильном порядке и отбросить пустые, если таковые найдутся:

...
select line from cal_all where trim(line) <> ''
order by no

Это и есть финальная часть нашего запроса.

Напрашивается сделать представление params2 и вынести в него константы типа "количество знакомест на каждое число месяца" и "количество пробелов между месяцеместами". Что осталось за кадром. Ну и все функции выравнивания я упростил, чтобы не перегружать код. Потому что если вдруг понадобится их поменять, то придётся выискивать эти числа в коде, который не везде очевиден, что чревато ошибками. А по условию задачи всё нужно выравнивать по центру.

Выводы

Главный и основной, который я старался донести до аудитории: нет ничего сверхсложного в решении подобных задач.

Функционально всё соответствует, выразить можно приблизительно то же и приблизительно так же. Что можно сказать про PostgreSQL в сравнении с Oracle по итогам данной задачи. Функции отличаются, но на то и документация нам дана. Некоторые нюансы удобнее в одном диалекте, некоторые в другом. Да, есть. Есть ли в чём-то существенная разница? На примере данной задачи я вижу по крайней мере в двух местах.

Например, в большей части Европы неделя начинается понедельником, а в США с воскресенья. Во-первых, Oracle поддерживает локали, и в разных локалях неделя может начинаться с разных дней недели. В PostgreSQL нет настроек локали для первого дня недели и невозможно сгенерировать календарь так, чтобы он начинался с привычного пользователю дня.

В Oracle за 04 октября 1582 года идёт 15 октября (как и было определено при вводе Григорианского календаря), в PostgreSQL есть 05 и все остальные числа октября 1582 года. Во-вторых, отличается поддержка преобразования дат и работа с календарём. Но факт остаётся фактом: календари в Oracle и PostgreSQL разные, хоть оба и Григорианские, и, соответственно, логика работы с датами существенно отличается. Вопрос не так прост, как может показаться сходу, в документации PostgreSQL есть даже специальный раздел, объясняющий проблему и почему в PostgreSQL она решена таким образом. Это может быть важно при портировании.

Также можете ответить на вопрос внизу, поддерживаете ли вы публикацию разбора олимпиадных задач. Если вам понравилось изложение, и у вас есть идеи о чём ещё околоSQLном следует написать, жду вас в комментариях.

На этом сегодня я прощаюсь с нашей аудиторией, stay tuned!..


Оставить комментарий

Ваш email нигде не будет показан
Обязательные для заполнения поля помечены *

*

x

Ещё Hi-Tech Интересное!

Погружение в AD: разбираем продвинутые атаки на Microsoft Active Directory и способы их детекта

Изображение: Pexels Участники рассказывают о новых векторах и своих изобретениях, но не забывают и о советах, как можно их обнаружить и предотвратить. За последние четыре года ни один Black Hat или DEF CON не обошелся без докладов на тему атак ...

На все компьютеры в России хотят предустанавливать российские антивирусы

В правительство РФ внесён национальный проект «Цифровая экономика», в паспорте которого указано интересное предложение от Министерство цифрового развития, связи и массовых коммуникаций России: законодательно обеспечить предустановку отечественных антивирусных программ на все персональные компьютеры, ввозимые и создаваемые на территории РФ, начиная ...