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

Алгоритм применяется к строке, начальное значение которой задано в конфигурационном параметре 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)

--для решения задачи используем рекурсию
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;

Номер месяца передается в параметре 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)

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;>

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

В таблице 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)

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

/*
 Суть решения:
    - Вычисляем аналитическую сумму с надбавкой для количества апельсинов.
        Пример: закупили ящики по 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";
 */

В таблице 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;

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

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)

-- 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;