Задачи второго этапа олимпиады «IT-Планеты» по PostgreSQL

В этом году наша компания впервые провела конкурс по базам данных в рамках международной олимпиады IT-Планета по информационным технологиям. Раньше на олимпиаде использовалась СУБД Oracle; наш коллега Евгений Бредня в свое время делился таким опытом.

Олимпиада проходила в три этапа. Первым шел заочный теоретический тест, который преодолели примерно двести человек из двух тысяч зарегистрировавшихся.

На втором этапе участникам было предложено подумать над пятью задачами, каждую из которых следовало решить одним SQL-запросом. Этот этап также проводился заочно: на раздумья было дано примерно три недели. Условия всех задач были опубликованы одновременно, но у каждой был свой крайний срок; поэтому первыми шли задачи полегче, чтобы на более сложные осталось больше времени. Задачи проверялись на корректность (автоматическими тестами) и на качество кода (вручную). По результатам мы отобрали двадцать человек для последнего, очного этапа.

Третий этап состоялся 27 мая в Сочи. К сожалению, из двадцати приглашенных приехать смогли только четырнадцать; между ними и состоялось соревнование. Задачи этого этапа также предполагали решение одним запросом, но сами задания были объединены общей темой, навеянной игрой Го, и строились так, что решение одной задачи помогало подступиться к следующей.

Я занимался придумыванием задач для второго и третьего этапов. Хочу поблагодарить участников олимпиады, которым пришлось их решать, организаторов, собравших нас вместе, и своих коллег: Дарью Рисухину, взвалившую на себя все оргвопросы, Евгения Моргунова, предоставившего задания для первого этапа, а также всех помогавших мне с задачами.

В этой статье поговорим о втором этапе.

И зачем это все?

Но сначала пара слов о том, зачем вообще нужны эти задачи «одним запросом». На прошлой работе один умудренный опытом администратор не уставал повторять зеленым разработчикам: «вы не на олимпиаде по программированию!» И действительно, часто ли в реальной жизни приходится использовать SQL для чего-то эдакого?

Не часто. Зато гораздо чаще, чем хотелось бы, разработчики городят циклы на процедурных языках в задачах, которые легко решаются на SQL. Думаю, что SQL ни у кого не был первым языком; все начинают с чего-то процедурного-императивного. Перестраиваться на другую парадигму всегда тяжело, поэтому большинству проще написать цикл, в котором вызываются небольшие запросы, вместо того чтобы одним запросом решить задачу целиком. Проблема здесь не только в избыточном коде, но и в том, что база данных не может оптимизировать всю задачу, а оптимизация отдельных запросов помогает далеко не всегда.

Решение же на SQL «ненормальных», «атипичных» задач раздвигает границы сознания. После этого и стандартные повседневные задачи будут решаться легче — снимается барьер переключения парадигм.

Ну и наконец, это просто весело. Нельзя же всю жизнь ковыряться с поставщиками и деталями, надо и удовольствие получать.

К делу

Итак, приступим к задачам. В основном тексте я ограничусь кратким условием, а полное буду приводить под катом.

Задача 1. Интерпретатор

Напишите интерпретатор упрощенной версии нормальных алгоритмов Маркова (НАМ).

Алгоритм задан в таблице nma в виде последовательности правил:

CREATE TABLE nma(
  id integer PRIMARY KEY GENERATED ALWAYS AS IDENTITY,
  a text NOT NULL,
  b text NOT NULL
);

Продолжение условия

Алгоритм применяется к строке, начальное значение которой задано в конфигурационном параметре nma.string. (Для получения значения параметра можно воспользоваться функцией current_setting).

Шаг алгоритма состоит в том, что выбирается первое по порядку правило, подстрока a которого содержится в строке; первое слева вхождение подстроки a заменяется на подстроку b. Если подходящее правило нашлось, выполняется следующий шаг алгоритма. Если ни одного правила не удалось применить, алгоритм заканчивает работу.

Запрос должен вывести последовательность применений правил алгоритма. В выводе должно быть три столбца:

• n — номер шага алгоритма; нулевой шаг соответствует исходному значению строки;

• s — состояние строки после выполнения данного шага;

• id — номер примененного на данном шаге правила (NULL для нулевого
  шага).

Алгоритм может зациклиться, поэтому его работу необходимо ограничить 1000 шагами.

Пример

Следующие входные данные определяют алгоритм, увеличивающий запись двоичного числа на единицу:

INSERT INTO nma(a,b) VALUES
  ('0++','1'),
  ('1++','++0'),
  ('++','1');
Для следующей строки:
SET nma.s = '1011++';

запрос должен вывести:

 n |   s    | id
−−−+−−−−−−−−+−−−−
 0 | 1011++ |
 1 | 101++0 |  2
 2 | 10++00 |  2
 3 | 1100   |  1
(4 rows)

Небольшое упрощение состояло в том, что из НАМ были исключены терминальные замены.

Я дал эту задачу из ностальгических соображений: когда-то давным-давно наша команда от Школы Юных Программистов Протвино участвовала в олимпиаде в Красноярске. Там, правда, задача была сложнее: надо было написать нормальный алгоритм, складывающий два числа (попробуйте). А чтобы его отладить, пришлось написать и интерпретатор (не на SQL, конечно, а на Бейсике. Или на Паскале, не помню уже). Кстати, алгоритм сложения я использовал в качестве одного из тестов. Надеюсь, участники погуглили про Маркова и его нормальные алгоритмы.

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

Однако проблем оказалось достаточно. Забавно, что некоторые присланные участниками запросы вообще не работали, падая с синтаксической ошибкой. У меня есть предположение, что это варианты решений от ChatGPT. Не подумайте, я не против. Если какой-то инструмент может ускорить вашу работу — это прекрасно. Если (точнее, когда) ИИ научится щелкать олимпиадные задачи, можно будет давать задачи еще более сложные и интересные. Но за проверку решения вы сами отвечаете, по-любому.

Дальше. Строка передается алгоритму в конфигурационном параметре, и никто не догадался обработать ситуацию, когда параметр не задан. Довольно очевидная же подстава со стороны организаторов. Так что максимальный балл за первую задачу никто не получил.

Одной из частых проблем было использование функции replace. Она не годится, поскольку заменяет сразу все вхождения подстроки, а нам нужна только первая. Подойдет overlay, или можно вручную вырезать из строки нужные части и склеить их.

И еще многие пытались искать подстроку с помощью выражения LIKE, приклеивая к ней «проценты». Но такой способ некорректно работает, если подстрока содержит тот же знак процента. Конкатенация вообще опасная штука, чреватая внедрением SQL-кода, так что рекомендую изучить ассортимент строковых функций.

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

Про критерии качества кода стоит сказать особо, поскольку они не формализуются. Задание намекает: «Аккуратно отформатированное решение с комментариями, поясняющими удачно выбранный алгоритм и его тонкие места, и разумно подобранными именами столбцов и подзапросов, может удвоить набранные баллы>.

С аккуратным форматированием проблем почти ни у кого не возникло (кто поленился — ССЗБ), а вот что такое хорошие комментарии? Плохо, когда комментариев нет совсем. Но и когда их больше самого кода — тоже радости мало: ведь их надо прочитать, потом прочитать код, а потом найти, в чем одно противоречит другому. Не противоречит? Смотрите внимательнее.

Хрестоматийный пример плохого комментария (насчитал таких штук пять минимум):

n + 1 AS n -- увеличиваем счетчик на 1

Комментировать надо то, что сложно понять из самого кода. Мотивацию выбора алгоритма, верхнеуровневое описание, тонкие места, допущения. Скажем, во многих решениях на «отлично» было отмечено, почему нельзя использовать replace — это полезный комментарий, в реальной жизни он может удержать последователей от поспешных решений «все переписать по-человечески».

Ну и хватит о первой задаче. Вот одно из решений, набравших больше всего баллов:

Решение Анны Глазачевой (Санкт-Петербург)

--для решения задачи используем рекурсию
WITH RECURSIVE markov_steps(n, s, id) AS (
  --задаем базу рекурсии
  SELECT 0, current_setting('nma.string'), NULL::integer
  UNION ALL
  --извлекаем измененную строку
  --подзапрос соединяет текущую строку и первое подходящее правило, а также применяет это правило
  --overlay используется из-за того, что replace меняет все вхождения, а regexp_replace может воспирнять символы как метасимволы
  SELECT *
  FROM (SELECT n + 1 n, overlay(s placing nma.b from strpos(s, nma.a) for length(nma.a)), nma.id
                FROM markov_steps
                JOIN (SELECT * FROM nma) nma ON position(nma.a IN s) > 0
                --необходимо извлечь первое подходящее правило
                ORDER BY id
                LIMIT 1) take_first
  --ставим ограничение в 1000 шагов
  --(база рекурсии не учитывается в подсчете шагов, так как не является шагом алгоритма)
  WHERE n <= 1000
)
--выводим результат
SELECT * FROM markov_steps;

Задача 2. Календарь

Напишите запрос, выводящий календарь на заданный месяц.

Продолжение условия

Номер месяца передается в параметре calendar.month (в формате MM), номер года — в параметре calendar.year (в формате YYYY).

Запрос должен вывести семь строк со следующими столбцами:

• n — день недели, от 1 (понедельник) до 7 (воскресенье);

• calendar — строка календаря, соответствующая дню недели. Строка образована следующей последовательностью символов:
  - название дня недели в текущей локали с заглавной буквы;
  - пробел;
  - номера дней (дополненные пробелами до двух символов), разделенные пробелом.

Строки календаря не должны содержать замыкающих пробелов.

Пример

Входные данные:

SET calendar.year=2023;
SET calendar.month=4;

В локали en_US запрос должен вывести:

 n |      calendar
−−−+−−−−−−−−−−−−−−−−−−−−
 1 | Mon     3 10 17 24
 2 | Tue     4 11 18 25
 3 | Wed     5 12 19 26
 4 | Thu     6 13 20 27
 5 | Fri     7 14 21 28
 6 | Sat  1  8 15 22 29
 7 | Sun  2  9 16 23 30
(7 rows)

В локали ru_RU запрос должен вывести:

 n |     calendar
−−−+−−−−−−−−−−−−−−−−−−−
 1 | Пн     3 10 17 24
 2 | Вт     4 11 18 25
 3 | Ср     5 12 19 26
 4 | Чт     6 13 20 27
 5 | Пт     7 14 21 28
 6 | Сб  1  8 15 22 29
 7 | Вс  2  9 16 23 30
(7 rows)

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

В качестве изюминки запрос должен был учитывать локаль, и на этом многие посыпались. Кто-то ее просто игнорировал, кто-то пытался хардкодить названия месяцев в разных языках (угадайте, предусмотрел ли кто-то непальский). Хотя решается это простым добавлением модификатора TM к маске формата.

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

Так что, по сути, требовалась лишь определенная аккуратность. Так или иначе надо было сформировать «сетку» дней (учитывая, что в месяце может быть разное количество недель) и заполнить ее конкретными числами.

Кто-то на самом деле формировал сетку из символов, заменяя их затем датами; кто-то делал это «в уме», конкатенируя даты и пробелы в нужном порядке — можно придумать много разных вариантов.

Тем не менее много ошибок было связано именно с тем, что иногда цифры оказывались не на своих местах. Стоит лучше тестировать решение.

Очень много баллов сгорело из-за невнимательности. В задании было сказано: «строки календаря не должны содержать замыкающих пробелов», а про trim многие забыли.

Ну и рекурсивный запрос тут не нужен, достаточно функции generate_series.

Решение Максима Логвиненко (Челябинск)

with dates as (select d.start_date,
                      d.start_date + interval '1' month - interval '1' day as stop_date,
                      -- запоминаем номер дня недели 1-го числа, чтобы затем строки с меньшими номерами дополнить
                      -- пробелами слева, а также правильно распределить числа месяца по колонкам
                      to_char(d.start_date, 'ID')::integer                 as first_num_of_week
               from (select to_timestamp(format('%s-%s', CURRENT_SETTING('calendar.year'),
                                                CURRENT_SETTING('calendar.month')),
                                         'yyyy-mm') as start_date) d)
select cl.num_day_of_week as n, format('%s %s', cl.day_of_week, cl.calendar_str) as calendar
from (select dl.num_day_of_week,
             dl.day_of_week,
             -- добавляем 2 пробела в строки, соотвествующие дням недели меньшим, чем номер дня недели 1-го числа
             -- имитируем невидимые дни предыдущего месяца
             concat(case when dl.num_day_of_week < dl.first_num_of_week then '   ' end,
                 -- с помощью lpad дополняем номера слева до 2х символов, согласно ТЗ
                    string_agg(lpad(dl.day_of_month::text, 2, ' '), ' ' order by dl.day_of_month)) as calendar_str
      from (select extract('day' from dt)     as day_of_month,
                   -- используем префикс TM, чтобы отображать название дня недели согласно выставленной локали
                   to_char(dt, 'TMDy')        as day_of_week,
                   to_char(dt, 'ID')::integer as num_day_of_week,
                   d.first_num_of_week
            from dates d
                     cross join generate_series(d.start_date, d.stop_date, interval '1' day) as dt) dl
      group by dl.num_day_of_week, dl.day_of_week, dl.first_num_of_week
      order by dl.num_day_of_week) cl;>

Задача 3. Апельсины

Напишите запрос, определяющий сумму складских запасов методом FIFO.

Продолжение условия

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

В таблице oranges продавец фиксирует приобретение апельсинов на складе (дату, массу нетто в килограммах и цену за килограмм) и продажи апельсинов в ларьке (то же, но с отрицательной массой; цена продажи не влияет на стоимость остатков, но нужна продавцу для других целей).

CREATE TABLE oranges(
  ts timestamptz PRIMARY KEY,
  net_weight numeric NOT NULL,
  price numeric(10,2) NOT NULL CHECK (price > 0)
);

Запрос должен вывести один столбец amount и одну строку, содержащую стоимость остатка апельсинов в ларьке, округленную до копеек.

Пример

Для следующих входных данных:

-- закупки: три ящика
INSERT INTO oranges VALUES
  (current_timestamp - interval '3 day', +10.0, 40.00),
  (current_timestamp - interval '2 day', +11.0, 60.00),
  (current_timestamp - interval '1 day',  +9.0, 50.00);
-- продажи (первый день)
INSERT INTO oranges
  SELECT current_timestamp - interval '2 day' - n*interval '5 min',
         -1.0, 100.00
  FROM generate_series(1, 7) n;
-- продажи (второй день)
INSERT INTO oranges
  SELECT current_timestamp - interval '1 day' - n*interval '5 min',
         -1.0, 110.00
  FROM generate_series(1, 6) n;
-- продажи (третий день)
INSERT INTO oranges
  SELECT current_timestamp - n*interval '5 min',
         -1.0, 120.00
  FROM generate_series(1, 5) n;

запрос должен вывести:

 amount
−−−−−−−−
 630.00
(1 rows)

(Первый ящик считаем распроданным полностью, второй — частично, а третий ящик пока полон.)

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

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

поступило	поступило (нарастающим итогом)	всего должны продать	разница
A	B = sum(A) OVER (ORDER BY ...)	C	D = B - C
5	5	6	-1
4	9	6	3
2	11	6	5

Тут возможны три варианта:

• Разница отрицательна (D < 0):
  этого и предыдущих ящиков не хватило для продажи, остаток равен нулю.

• Разница меньше количества в данном ящике (0 ≤ D < A):
  этого ящика уже хватило, остаток равен разнице.

• Разница не меньше количества в данном ящике (D ≥ A):
  до апельсинов из этого ящика дело не дошло.

«Алгоритм простейший», как написал один участник. Но можно и рекурсивным запросом решать, конечно.

Но именно с алгоритмом было больше всего сложностей. Зачастую решения выводили совсем не то, что требовалось. Надо хорошенько тестировать!

Много ошибки было связано с округлением. Его то вовсе забывали, то применяли слишком рано, из-за чего терялись копеечки.

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

Решение Данила Антонова (Санкт-Петербург)

/*
 Суть решения:
    - Вычисляем аналитическую сумму с надбавкой для количества апельсинов.
        Пример: закупили ящики по 5, 6, 7 апельсинов. Сумма с надбавкой будет: 5, 11, 18.

    - Находим сколько всего апельсинов продали с помощью подзапроса.
        Пример: допустим, продали 8 кг апельсинов.

    - Находим сколько всего апельсинов осталось:
        Если количество проданных апельсинов БОЛЬШЕ текущей подсуммы, то этот ящик полностью
            распродан и не интересует нас. В первом примере полностью распродан первый ящик и частично второй.
        Если МЕНЬШЕ, то определяем сколько апельсинов осталось в ящике, либо ящик полный и не затронут.
        Для этого находим МИНИМУМ(текущая подсумма минус количество проданных, всего апельсинов в ящике).
        Если первый параметр меньше, то ящик частично распродан, иначе он полный.
        Пример для первого и второго пункта. 5, 6, 7 - апельсинов в ящике. 8 - продано апельсинов:
            5:  8 > 5 - не интересует, ящик распродан
            6: МИН(11 - 8, 6) = 3 апельсина осталось
            7: МИН(18 - 8, 7) = 7 апельсинов осталось (ящик не трогали)

    - Находим сумму оставшихся апельсинов путем умножения оставшегося количества на цену.
 */
with remain_amount_in_boxes as (
    select case
           when sum(net_weight) over (order by ts) >
                    (select coalesce(-sum(net_weight), 0) from oranges where net_weight < 0)
           then price * least(sum(net_weight) over (order by ts) -
                              (select coalesce(-sum(net_weight), 0) from oranges where net_weight < 0), net_weight)
           end as sum_by_box
    /*
     С помощью условия when находим те ящики, в которых остались апельсины.
        Подсумма количества для текущего ящика > всего продано количества.
        Если больше, то апельсины остались, иначе нас не интересует.
     В подзапросе вычисляем сумму килограмм проданных апельсинов.
     В then производим умножение цены на количество оставшихся апельсинов в ящике.
        Функцию минимума описал в комментарии общего решения.
     С помощью сортировки по ts в аналитической сумме выполняем условие FIFO, сначала расчитывая
        самые первые завезенные апельсины.
     Coalesce используем для ситуации, когда ничего не продали.
     Минут перед sum используем, что из отрицательного числа сделать положительно и корректно
        сравнивать проданное и оставшееся.
     */
    from oranges
    where net_weight > 0
    /*
     Выбираем только те строки, которые соответствуют завезенному товару,
        потому что нужно найти сумму оставшихся товаров.
     */
)
select coalesce(round(sum(sum_by_box), 2), 0) as amount
from remain_amount_in_boxes;
/*
    С помощью sum суммируем сумму оставшегося товара в ящиках.
    С помощью round округляем до копеек.
    С помощью coalesce обрабатываем ситуацию, когда распроданы все товары и нужно вывести "0";
 */

Задача 4. Змейка

Напишите запрос, визуализирующий «змейку» из известной игры.

Продолжение условия

В таблице snake хранятся координаты сегментов «змейки» от хвоста до головы в порядке возрастания идентификатора. Размер поля — 10×10 с началом координат в левом верхнем углу, координаты отсчитываются от 0 до 9.

CREATE TABLE snake(
  id integer NOT NULL GENERATED ALWAYS AS IDENTITY,
  x integer NOT NULL CHECK (x BETWEEN 0 AND 9),
  y integer NOT NULL CHECK (y BETWEEN 0 AND 9)
);

Гарантируется, что:

• каждый следующий сегмент прилегает к предыдущему по горизонтали или вертикали;

• нет самопересечений.

Запрос должен вывести два столбца:

• line — номер строки;

• snake — текстовая строка поля, состоящая из десяти символов. Пустая клетка обозначается точкой «.», голова змейки — символом «ö», а остальные ее сегменты — символами «│», «─», «┌», «┐», «└» и «┘» в зависимости от взаимоположения сегментов.

В выводе должно быть ровно десять строк.

Пример

Для следующих входных данных:

INSERT INTO snake(x,y) VALUES
  (4,4), (4,5),
  (3,5), (2,5),
  (2,4), (2,3), (2,2),
  (3,2), (4,2), (5,2), (6,2),
  (6,3), (6,4), (6,5), (6,6);

запрос должен вывести:

 line |   snake
−−−−−−+−−−−−−−−−−−−
    0 | ..........
    1 | ..........
    2 | ..┌───┐...
    3 | ..│...│...
    4 | ..│.│.│...
    5 | ..└─┘.│...
    6 | ......ö...
    7 | ..........
    8 | ..........
    9 | ..........
(10 rows)

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

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

Из-за того что каждый символ может возникать в двух случаях (змейка ползет в одну сторону или в другую), решение получается громоздким. Его можно немного сократить, если придумать функцию, отображающую движение в обе стороны в одно и то же число. К счастью, никто из участников не стал этим заморачиваться.

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

Решение Дмитрия Жаворонкова (Томск)

with directions as (
    select
        id, x, y,
        -- A direction that the snake moved from a cell in.
        -- Because the snake can not move diagonally
        -- x and y can not have non-zero difference
        -- at the same time
        case lead(x, 1, x) over (order by id) - x
            when -1 then 'L'
            when 1 then 'R'
            else case lead(y, 1, y) over (order by id) - y
                when -1 then 'U'
                when 1 then 'D'
                else 'H'
            end
        end as dir
    from snake
),  segments as (
    select
        id, x, y,
        -- because of default value of lag function
        -- the snake's tail is mapped to one of the first 4 cases
        case lag(dir, 1, dir) over (order by id) || dir
            when 'UU' then '│'
            when 'DD' then '│'
            when 'RR' then '─'
            when 'LL' then '─'
            when 'RU' then '┘'
            when 'DL' then '┘'
            when 'RD' then '┐'
            when 'UL' then '┐'
            when 'UR' then '┌'
            when 'LD' then '┌'
            when 'LU' then '└'
            when 'DR' then '└'
            -- 'LR', 'RL', 'UD', 'DU' are impossible
            else 'ö'
        end as seg
    from directions
) select
        t1.line,
        string_agg(
            coalesce(s.seg, '.'),
            ''
            -- Order cells in a row by column
            order by col
        ) as snake
    -- Create empty cells
    from (select generate_series(0, 9)) as t1(line)
    join (select generate_series(0, 9)) t2(col) on true
    -- Insert the snake segments into the cells
    left join segments s on s.x = t2.col and s.y = t1.line
    group by t1.line
    order by t1.line;

Задача 5. Банкомат

Напишите запрос, «выдающий» требуемую сумму минимальным количеством купюр.

Продолжение условия

Номиналы и количество имеющихся в банкомате купюр хранятся в таблице:

CREATE TABLE atm(
  face_value integer PRIMARY KEY CHECK (face_value > 0),
  quantity integer NOT NULL CHECK (quantity >= 0)
);

Запрашиваемая сумма передается в параметре atm.amount; значение гарантированно приводится к целому числу.

Запрос должен вывести номиналы и количество купюр, в сумме дающих требуемую сумму. Количество купюр было минимально возможным. Если задача не имеет решения, запрос не должен вывести ни одной строки.

Пример

Для следующих входных данных:

SET atm.amount = 9300;
INSERT INTO atm(face_value,quantity) VALUES
  (5000,10), (2000,10),
  (1000,10),  (500,10),
(100,10);

запрос должен вывести:

 face_value | quantity
−−−−−−−−−−−−+−−−−−−−−−−
       5000 |        1
       2000 |        2
        100 |        3
(3 rows)

Для частного случая, когда все номиналы кратны, задача решается даже без рекурсивного запроса, поскольку достаточно двигаться от крупных купюр к мелким. Такой пример разобран у нас в курсе DEV2-12; он демонстрирует пользовательские оконные функции, но можно обойтись и стандартными.

Но номиналы не обязаны быть кратными. Скажем, купюрами в 5000 и 2000 можно выдать 6000, но если начать с пятерки, ничего не получится. В общем случае необходим перебор, то есть рекурсивный запрос. В качестве текущего состояния удобно взять массив пар (номинал, количество купюр), определяющий выданную на текущий момент сумму. Начать можно с пустого состояния и добавлять к нему разные купюры, двигаясь от бóльших к меньшим.

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

Решение Яна Сенина (Минск)

-- This query performs some sort of backpack algorithm. Firstly it
-- chooses some bill(let's call it's face_value a), takes all
-- possible quantities of it and gets rows(sum, bills) like these:
-- (a, {a}), (a * 2, {a, a}), (a * 3, {a, a, a}), ...,
-- (a * n, {a, a, ..., a}). Then it chooses second bill and tries
-- to add all possible quantities of it to all of currently
-- existing arrays(second element in pair), so it just computes
-- all possible bill combinations with total sum <= atm.amount
-- Then it takes pair with minimal array_length(i.e. with minimal
-- number of bills) with sum = atm.amount, formats it and returns.
WITH RECURSIVE index_to_atm AS (
    SELECT row_number() OVER ()::INT AS index,
           face_value,
           quantity
    FROM atm
), sums(sum, face_values, last_face_value_index) AS (
    SELECT 0, '{}'::INT[], 0
    UNION ALL
    SELECT sum + face_value * quantity.quantity,
           face_values || array_fill(face_value, ARRAY[quantity.quantity]),
           index
    FROM sums
    JOIN index_to_atm ON last_face_value_index + 1 = index
    CROSS JOIN generate_series(
        0, least(index_to_atm.quantity,
               (current_setting('atm.amount')::INT - sum) / face_value)) AS quantity
), face_values AS (
    SELECT face_values FROM sums
    WHERE sum = current_setting('atm.amount')::INT
    ORDER BY array_length(face_values, 1)
    LIMIT 1
)
SELECT unnest(face_values) AS face_value, count(*) AS quantity FROM face_values
GROUP BY face_value;

На этом пока все, а в следующий раз расскажу о задачах финала.