Вдохновившись прошлогодним опытом, мы продолжили начинание и снова проводим конкурс по SQL на международной олимпиаде «IT-Планета».
Конкурс состоит из трех этапов. Заочный теоретический тест собрал почти 3000 человек, из которых на следующий этап мы отобрали примерно 200. Вопросы для этого этапа были подготовлены моим коллегой, Евгением Давыдовым.
Второй этап — также заочный. Здесь участникам было предложено подумать над пятью задачами моего авторства, о которых я сегодня и хочу рассказать.
Третий — очный — этап пройдет в конце мая; постараюсь не затягивать с отчетом, но пока храню интригующее молчание.
Поскольку все вводные слова про мотивацию я уже сказал в прошлый раз, сразу приступим к делу.
Задача 1. Многоголовый Цербер
Условие
Вход в подземелье охраняет многоголовый пес. Музыка на него не действует, но время от времени некоторые из голов отдыхают. Гарри установил на безопасном расстоянии систему видеонаблюдения, которая регистрирует состояние голов. Система надежно фиксирует засыпания и просыпания голов, но может записать состояние и в произвольные промежуточные моменты.
Известно, что в момент включения системы все головы бодрствовали, а за период наблюдения каждая из голов засыпала хотя бы раз.
Выведите интервалы времени, в которые Гарри и его друзья могли бы пробраться мимо пса.
События фиксируются в таблице cerberus:
CREATE TABLE cerberus(
head_id integer NOT NULL, -- номер головы
event_time timestamp NOT NULL, -- время события
head_state boolean NOT NULL, -- true - бодрствует, false - спит
UNIQUE (head_id, event_time)
);Запрос должен вывести интервалы (в пределах времени наблюдения), в которые все головы спали.
Пример
Для следующих входных данных
INSERT INTO cerberus VALUES
(1, '2024-04-01 01:00:00'::timestamp, false), -- 1-я уснула
(3, '2024-04-01 02:00:00'::timestamp, false), -- 3-я уснула
(2, '2024-04-01 03:00:00'::timestamp, false), -- 2-я уснула
(2, '2024-04-01 04:00:00'::timestamp, true), -- 2-я проснулась
(1, '2024-04-01 04:30:00'::timestamp, false), -- 1-я спит
(1, '2024-04-01 05:00:00'::timestamp, true), -- 1-я проснулась
(3, '2024-04-01 06:00:00'::timestamp, true); -- 3-я проснулась
запрос должен вывести:
time_from | time_to
---------------------+---------------------
2024-04-01 03:00:00 | 2024-04-01 04:00:00
(1 rows) (В условии задачи я не вполне четко написал, что должен вывести запрос, если в конце времени наблюдения все головы спят. Поэтому принимал любой вариант.)
Решение
Задача виделась мне как аперитив для разминки перед основным блюдом, но со своей изюминкой. Дело в том, что решать ее можно и традиционными средствами, но если вспомнить, что PostgreSQL умеет работать с диапазонами, а начиная с 14-й версии — и с мультидиапазонами, жить сразу становится веселее и проще.
Все решение сводится к тому, чтобы для каждой головы определить диапазоны сна и объединить их в один мультидиапазон, а затем найти пересечение мультидиапазонов всех голов.
Диапазоны сна легко вычисляются с помощью оконной функции lead: берем интервал от события засыпания до следующего за ним события. Что приятно, нам не важно, следует ли за засыпанием пробуждение или система повторно зарегистрировала состояние сна: в последнем случае просто получим несколько примыкающих друг к другу диапазонов, это ни на что не влияет.
Объединение диапазонов в мультидиапазон и пересечение мультизиапазонов выполняется стандартными функциями range_agg и range_intersect_agg, а развернуть полученный мультидиапазон полного сна в отдельные диапазоны можно функцией unnest. Всю сложную и скучную работу PostgreSQL выполняет за нас.
Решение
WITH ranges AS (
-- Объединяем подряд идущие строки (начиная от засыпания) в один диапазон.
-- Повторяющиеся события нам не мешают: будет несколько интервалов, которые дальше
-- все равно сольются в один мультидиапазон.
SELECT head_id, tsrange(event_time, next_time) off_range
FROM (
SELECT head_id, event_time, head_state,
lead(event_time) OVER (PARTITION BY head_id ORDER BY event_time) next_time
FROM cerberus
) t
WHERE NOT head_state
), multiranges AS (
-- группируем диапазоны каждой головы в мультидиапазон
SELECT range_agg(off_range) off_multirange
FROM ranges
GROUP BY head_id
), intersections AS (
-- находим пересечение всех мультидиапазонов
SELECT unnest(range_intersect_agg(off_multirange)) off_range
FROM multiranges
)
-- преобразуем в требуемый по условию вид
SELECT lower(off_range), upper(off_range)
FROM intersections;Такое решение нашел только один участник, Леонид Алексеев. Остальным пришлось расчехлять аналитические функции, рекурсивные запросы, массивы и даже json-ы.
Рубрика «Не делайте так»
Если есть уверенность, что логическое выражение не обращается в
NULL, не надо громоздить конструкции типаcase when cnt.sleepHeadCnt = cnt.totalHeads then true else false end. Достаточно написатьcnt.sleepHeadCnt = cnt.totalHeads. (А если такой уверенности нет, лучше уж сделать этот факт более явным, используяcoalesce.)В большинстве случаев не стоит вкладывать друг в друга конструкции
WITH. Преимущество общих табличных выражений над подзапросами как раз в том, что их можно записывать последовательно, уменьшая вложенность и упрощая чтение запроса.Выделять ли заглавными ключевые слова — дело вкуса, но не стоит набирать большими буквами весь запрос. Все-таки двадцать первый век на дворе, восьмибитные кодировки уже давно завезли.
Задача 2. Волшебная палочка
Условие
Когда Незнайка совершит пять добрых дел подряд, появится волшебник и вручит ему волшебную палочку.
Когда Незнайка совершит пять плохих дел подряд, волшебник отберет у него палочку.
Чтобы получить палочку в следующий раз, Незнайке придется совершить на одно доброе дело больше, чем в прошлый (но чтобы лишиться палочки, всегда достаточно пяти плохих дел — такая несправедливость).
Незнайкины дела записываются в таблицу deeds:
CREATE TABLE deeds(
ts timestamp PRIMARY KEY,
good boolean NOT NULL -- t - хорошее дело, f - плохое
);Определите диапазоны (tsrange) владения волшебной палочкой.
Пример
Для следующих входных данных
INSERT INTO deeds VALUES
('2024-04-01 01:00:00'::timestamp, true),
('2024-04-01 02:00:00'::timestamp, true),
('2024-04-01 03:00:00'::timestamp, false),
('2024-04-01 04:00:00'::timestamp, true),
('2024-04-01 05:00:00'::timestamp, true),
('2024-04-01 06:00:00'::timestamp, true),
('2024-04-01 07:00:00'::timestamp, true),
('2024-04-01 08:00:00'::timestamp, true),
('2024-04-01 09:00:00'::timestamp, false);запрос должен вывести:
range
------------------------
[2024-04-01 08:00:00,)
(1 rows)Решение
Еще одна разминочная задача на владение аналитическими функциями и рекурсивными подзапросами.
Довольно очевидно, что перво-наперво надо разбить все дела на группы одинаковых подряд идущих. Это делается примерно так:
WITH prev AS ( -- добавляем предыдущее дело
SELECT ts, good, lag(good) OVER (ORDER BY ts) prev_good
FROM deeds
),
changes AS ( -- находим переходы из одного состояния в другое
SELECT ts, good, prev_good, CASE WHEN good != prev_good THEN 1 END change
FROM prev
)
-- подсчет переходов нарастающим итогом дает номера групп
SELECT ts, good, prev_good, change, count( change ) OVER (ORDER BY ts) grp
FROM changes
ORDER BY ts; ts | good | prev_good | change | grp
---------------------+------+-----------+--------+-----
2024-04-01 01:00:00 | t | | | 0
2024-04-01 02:00:00 | t | t | | 0
2024-04-01 03:00:00 | f | t | 1 | 1
2024-04-01 04:00:00 | t | f | 1 | 2
2024-04-01 05:00:00 | t | t | | 2
2024-04-01 06:00:00 | t | t | | 2
2024-04-01 07:00:00 | t | t | | 2
2024-04-01 08:00:00 | t | t | | 2
2024-04-01 09:00:00 | f | t | 1 | 3
(9 rows)Теперь мы можем посчитать нарастающим итогом количество дел в каждой группе: удобно взять хорошие дела с плюсом, а плохие — с минусом.
WITH grps AS (
-- это мы уже видели выше, но тут +1/-1 вместо boolean
SELECT ts,
CASE WHEN good THEN 1 ELSE -1 END grade,
count( change ) OVER (ORDER BY ts) grp
FROM (
SELECT ts, good,
CASE WHEN good != lag(good) OVER (ORDER BY ts) THEN 1 END change
FROM deeds
)
)
SELECT ts, grade, grp, sum(grade) OVER (PARTITION BY grp ORDER BY ts)
FROM grps
ORDER BY ts; ts | grade | grp | sum
---------------------+-------+-----+-----
2024-04-01 01:00:00 | 1 | 0 | 1
2024-04-01 02:00:00 | 1 | 0 | 2
2024-04-01 03:00:00 | -1 | 1 | -1
2024-04-01 04:00:00 | 1 | 2 | 1
2024-04-01 05:00:00 | 1 | 2 | 2
2024-04-01 06:00:00 | 1 | 2 | 3
2024-04-01 07:00:00 | 1 | 2 | 4
2024-04-01 08:00:00 | 1 | 2 | 5
2024-04-01 09:00:00 | -1 | 3 | -1
(9 rows)Остается взять первую по порядку 5-ку, затем следующую за ней -5, затем 6, -5, 7 и так далее. Это работа для рекурсивного (читай, итеративного) запроса. Ну и надо будет склеить пары строк, идущих друг за другом, в один диапазон, как требуется в условии.
Полное решение
WITH RECURSIVE grps AS (
SELECT ts,
CASE WHEN good THEN 1 ELSE -1 END grade,
count( change ) OVER (ORDER BY ts) grp
FROM (
SELECT ts, good,
CASE WHEN good != lag(good) OVER (ORDER BY ts) THEN 1 END change
FROM deeds
)
), s AS (
SELECT ts, sum(grade) OVER (PARTITION BY grp ORDER BY ts) score
FROM grps
), r AS (
-- выбираем первое достижение пятерки...
(SELECT ts, score,
score+0.5 AS score_plus -- добавляем по 0.5, чтобы отрастало за два раза
FROM s
WHERE score = 5
ORDER BY ts LIMIT 1
)
UNION ALL
-- ...затем -5, 6, -5, 7 и т. д., чередуем знак
(SELECT s.ts, s.score, r.score_plus+0.5
FROM s CROSS JOIN r
WHERE s.ts > r.ts
AND s.score = CASE WHEN r.score > 0 THEN -5 ELSE r.score_plus END
ORDER BY s.ts LIMIT 1
)
)
-- склеиваем две последовательные строки в диапазон
SELECT tsrange(ts, next_ts)
FROM (
SELECT ts, lead(ts) OVER (ORDER BY ts) next_ts, score
FROM r
)
WHERE score > 0
ORDER BY ts;Не делайте так
В этой задаче строки упорядочены по временнóй метке. Многие приделали еще и возрастающий числовой номер, но зачем? Это лишние действия.
Никогда не следует давать имена транслитом. Идентификаторы типа
kolvoилиizmenсмотрятся очень непрофессионально.Длинный псевдоним подзапроса может поспособствовать понятности, но если он часто повторяется, то будет скорее мешать. Мне сложновато читать такие конструкции:
SELECT sorted_deeds.deed_id, sorted_deeds.ts, sorted_deeds.good, CASE WHEN (sorted_deeds.good) AND (deeds_with_rating.rating > 0) THEN deeds_with_rating.rating + 1.
Лучше сократить псевдоним до нескольких букв и написать расшифровку в комментарии.Многие зачем-то стали «подгонять» ответ к тому виду, как в условии, приводя значение к строке и добавляя-вырезая символы. Этого, конечно, не требовалось: значение tsrange может выводиться по-разному в зависимости от локали. Но сильно я к этому не придирался.
Задача 3. Шахматы
Условие
Шахматная партия (возможно, неоконченная) записана в виде текстовой строки в полной нотации:
Элементы нотации состоят из порядкового номера хода, за которым следуют точка и пробел; затем следует запись хода белых, после которого через пробел может следовать запись хода черных.
Запись хода (как белых, так и черных) включает букву, обозначающую фигуру, за которой следует описание движения этой фигуры. Список допустимых букв:
–
N— конь (kNight);
–B— слон (Bishop);
–R— ладья (Rook);
–Q— ферзь (Queen);
–K— король (King);Если буква отсутствует, ходит пешка
p(pawn).
Движение фигуры состоит из следующих друг за другом указаний двух клеток: начальной (на которой фигура стоит) и конечной (на которую фигура должна переместиться).
Пример:Ba1c3— слон идет с a1 на c3.Если своим ходом фигура бьет фигуру противника, перед указанием целевой клетки ставится символ взятия
x.
Пример:e4xd5— пешка с e4 бьет на d5.
В этом задании не требуется учитывать взятие на проходе.Если ход завершается шахом, после конечной клетки ставится символ
+; если матом — символ#.
Пример:Qg3g7+— ферзь идет с g3 на g7 и ставит шах.Фигура, в которую превращается пешка, дойдя до последней горизонтали, записывается после указания конечной клетки. По умолчанию считается, что пешка превращается в ферзя.
Пример:f7f8N#— пешка ходит с f7 на f8, становится конем и объявляет мат.Короткая рокировка обозначается
O-O, длинная —O-O-O.Другие обозначения не применяются.
Запрос получает запись партии в конфигурационном параметре chess.game. Известно, что все ходы в предоставленной записи корректны, то есть не нарушают обычных правил игры в шахматы.
Напишите запрос, выводящий позицию, которая возникнет на шахматной доске после воспроизведения всех записанных ходов. Позиция должна быть показана как поле 8×8 символов со следующими обозначениями:
«
.» — пустое черное поле;«
P» — белая пешка, «p» — черная пешка;«
N» — белый конь, «n» — черный конь;«
B» — белый слон, «b» — черный слон;«
R» — белая ладья, «r» — черная ладья;«
Q» — белый ферзь, «q» — черный ферзь;«
K» — белый король, «k» — черный король.
Запрос должен вывести два столбца:
line— номер горизонтали от 1 до 8;chess— восемь символов данной горизонтали, от a до h.
Пример
Для следующих входных данных
SET chess.game =
'1. e2e4 e7e5 2. Bf1c4 Nb8c6 3. Qd1h5 Ng8f6 4. Qh5xf7#';запрос должен вывести:
line | chess
------+----------
8 | r.bqkb r
7 | pppp.Qpp
6 | .n. n .
5 | . . p .
4 | .B.P. .
3 | . . . .
2 | PPPP PPP
1 | RNB K NR
(8 rows)Решение
Для решения этой задачи достаточно поверхностного знакомства с формальными правилами игры. Если с первого взгляда непонятно, как подступиться к задаче — не беда, сейчас будем есть этого слона по частям. Я расскажу про свой вариант, а в конце покажу совсем другое решение одного из участников.
Итак, первое, что нам надо сделать — преобразовать строку с записью партии в удобоваримый единообразный табличный вид. Начнем с того, что заметим: ни шахматная нумерация ходов, ни символы взятия, шаха и мата нам совершенно не нужны. Это чистой воды избыточность, рассчитанная на вечно ошибающихся человеков. Оставшиеся символы можно разложить на отдельные ходы с помощью регулярного выражения и функции regexp_matches.
Неплохо также подстелить соломки на случай, если параметр chess.game окажется пустым или вообще не установленным (это догадался сделать один только Руслан Парфенов, хотя я предупреждал в прошлый раз).
Заодно я проставляю номер и вычисляю цвет ходящей фигуры. Вот что у нас пока получается:
-- возьмем пример посложнее
SET chess.game = '1. e2e4 e7e5 2. Ng1f3 Nb8c6 3. Bf1c4 Bf8c5 4. b2b4 Bc5xb4 5. c2c3 Bb4a5 6. d2d4 e5xd4 7. O-O d4d3';
WITH rawmoves(n,color,move) AS (
-- разбиваем на отдельные ходы и определяем цвет
SELECT row_number() OVER() * 2,
CASE WHEN row_number() OVER() % 2 = 0 THEN 'B' ELSE 'W' END,
move[1]
FROM regexp_matches(
coalesce(translate(current_setting('chess.game',true),'x+#',''),'') || ' ',
'([a-h1-8RBNQKO-]+) ', 'g'
) move
)
SELECT * FROM rawmoves ORDER BY n; n | color | move
----+-------+-------
2 | W | e2e4
4 | B | e7e5
6 | W | Ng1f3
8 | B | Nb8c6
10 | W | Bf1c4
12 | B | Bf8c5
14 | W | b2b4
16 | B | Bc5b4
18 | W | c2c3
20 | B | Bb4a5
22 | W | d2d4
24 | B | e5d4
26 | W | O-O
28 | B | d4d3
(14 rows)Обратите внимание, что номер идет с шагом 2. Дело в том, что нам неудобно работать с обозначением рокировки — она не укладывается в общую схему. Лучше заменить ее на два обычных хода, а для этого нам и пригодится промежуток между номерами.
WITH ... (
...
), castling(color,move,n,newmove) AS (
VALUES -- ходы рокировок
('W', 'O-O', 0, 'Rh1f1'),
('W', 'O-O', 1, 'Ke1g1'),
('W', 'O-O-O', 0, 'Ra1d1'),
('W', 'O-O-O', 1, 'Ke1c1'),
('B', 'O-O', 0, 'Rh8f8'),
('B', 'O-O', 1, 'Ke8g8'),
('B', 'O-O-O', 0, 'Ra8d8'),
('B', 'O-O-O', 1, 'Ke8c8')
), castlingmoves(n,color,move) AS (
-- заменяем рокировку на обычные ходы
SELECT r.n+coalesce(c.n,0), r.color, coalesce(c.newmove,r.move)
FROM rawmoves r
LEFT JOIN castling c ON c.color = r.color AND c.move = r.move
)
SELECT * FROM castlingmoves ORDER BY n; n | color | move
----+-------+-------
2 | W | e2e4
4 | B | e7e5
6 | W | Ng1f3
8 | B | Nb8c6
10 | W | Bf1c4
12 | B | Bf8c5
14 | W | b2b4
16 | B | Bc5b4
18 | W | c2c3
20 | B | Bb4a5
22 | W | d2d4
24 | B | e5d4
26 | W | Rh1f1
27 | W | Ke1g1
28 | B | d4d3
(15 rows)Здесь вместо одной рокировочной строки 26 появились строки 26 и 27 с ходами ладьи и короля.
Теперь разобьем ходы на отдельные компоненты: исходные фигуру, вертикаль и горизонталь, и целевые фигуру, вертикаль и горизонталь. И снова удобно воспользоваться регулярным выражением:
WITH ... AS (
...
), components(n,color,piece_from,v_from,h_from,piece_to,v_to,h_to) AS (
-- разбиваем каждый ход на отдельные компоненты
SELECT n, color, coalesce(nullif(m[1],''),'P'),
nullif(m[2],''), nullif(m[3],''), nullif(m[6],''), m[4], m[5]
FROM (
SELECT n, color,
regexp_matches(move,'([RBNQK]?)([a-h]?)([1-8]?)([a-h])([1-8])([RBNQ])?') m
FROM castlingmoves
)
)
SELECT * FROM components ORDER BY n; n | color | piece_from | v_from | h_from | piece_to | v_to | h_to
----+-------+------------+--------+--------+----------+------+------
2 | W | P | e | 2 | | e | 4
4 | B | P | e | 7 | | e | 5
6 | W | N | g | 1 | | f | 3
8 | B | N | b | 8 | | c | 6
10 | W | B | f | 1 | | c | 4
12 | B | B | f | 8 | | c | 5
14 | W | P | b | 2 | | b | 4
16 | B | B | c | 5 | | b | 4
18 | W | P | c | 2 | | c | 3
20 | B | B | b | 4 | | a | 5
22 | W | P | d | 2 | | d | 4
24 | B | P | e | 5 | | d | 4
26 | W | R | h | 1 | | f | 1
27 | W | K | e | 1 | | g | 1
28 | B | P | d | 4 | | d | 3
(15 rows)Пустую исходную фигуру я заменяю на P. Целевая фигура пока будет заполнена только для превращающейся пешки, но это мы скоро исправим. Кстати, в следующей задаче исходные вертикаль и горизонталь могут отсутствовать, поэтому в регулярном выражении я сразу предполагаю такую возможность, чтобы уже не возвращаться к этому.
Последние штрихи: перенумеровываем ходы по порядку, заменяем буквенные обозначения вертикалей на числа, аккуратно заполняем целевую фигуру во всех строках, и все черные фигуры приводим к нижнему регистру — как на игровом поле. После этого цвет нам уже не нужен.
WITH ... AS (
...
), moves(n,piece_from,v_from,h_from,piece_to,v_to,h_to) AS (
SELECT n,
CASE WHEN color = 'B' THEN lower(piece_from) ELSE piece_from END,
v_from, h_from,
CASE WHEN color = 'B' THEN lower(piece_to) ELSE piece_to END,
v_to, h_to
FROM (
SELECT row_number() OVER (ORDER BY n) AS n,
color,
piece_from,
ascii(v_from) - ascii('a') + 1 AS v_from,
nullif(h_from,'')::integer AS h_from,
coalesce(piece_to,
CASE
WHEN piece_from = 'P' AND h_to IN ('1','8') THEN 'Q'
ELSE piece_from
END) AS piece_to,
ascii(v_to) - ascii('a') + 1 AS v_to,
nullif(h_to,'')::integer AS h_to
FROM components
)
)
SELECT * FROM moves ORDER BY n; n | piece_from | v_from | h_from | piece_to | v_to | h_to
----+------------+--------+--------+----------+------+------
1 | P | 5 | 2 | P | 5 | 4
2 | p | 5 | 7 | p | 5 | 5
3 | N | 7 | 1 | N | 6 | 3
4 | n | 2 | 8 | n | 3 | 6
5 | B | 6 | 1 | B | 3 | 4
6 | b | 6 | 8 | b | 3 | 5
7 | P | 2 | 2 | P | 2 | 4
8 | b | 3 | 5 | b | 2 | 4
9 | P | 3 | 2 | P | 3 | 3
10 | b | 2 | 4 | b | 1 | 5
11 | P | 4 | 2 | P | 4 | 4
12 | p | 5 | 5 | p | 4 | 4
13 | R | 8 | 1 | R | 6 | 1
14 | K | 5 | 1 | K | 7 | 1
15 | p | 4 | 4 | p | 4 | 3
(15 rows)Ну вот, с таким представлением можно работать. Теперь нам надо изобразить начальное положение фигур на доске в виде таблицы: номер вертикали, номер горизонтали, фигура. Например, так:
WITH ... (
...
), board(v,h,p) AS (
-- начальная позиция (все клетки)
VALUES
(1,1,'R'),(2,1,'N'),(3,1,'B'),(4,1,'Q'),(5,1,'K'),(6,1,'B'),(7,1,'N'),(8,1,'R'),
(1,2,'P'),(2,2,'P'),(3,2,'P'),(4,2,'P'),(5,2,'P'),(6,2,'P'),(7,2,'P'),(8,2,'P'),
(1,7,'p'),(2,7,'p'),(3,7,'p'),(4,7,'p'),(5,7,'p'),(6,7,'p'),(7,7,'p'),(8,7,'p'),
(1,8,'r'),(2,8,'n'),(3,8,'b'),(4,8,'q'),(5,8,'k'),(6,8,'b'),(7,8,'n'),(8,8,'r')
UNION ALL
SELECT v, h, ' ' FROM generate_series(1,8) v, generate_series(3,6) h
)
...Пустые клетки — пробелы. По условию черные клетки должны обозначаться точками, но сейчас это будет только мешать.
Нам остались сущие пустяки: «проиграть» каждый ход партии, изменяя таблицу игрового поля. С этим справится рекурсивный запрос. Начинаем с начальной позиции, а на очередном ходу соединяем позицию с подготовленной ранее таблицей moves: на ту клетку, с которой ушла фигура, ставим пробел; на ту клетку, куда фигура пришла, ставим символ фигуры (при этом мы автоматически «затрем» фигуру противника, если ей не посчастливилось оказаться взятой); остальные клетки просто оставляем без изменений.
WITH RECURSIVE ... (
...
), game(n,v,h,p) AS (
-- начинаем с начальной позиции
SELECT 1, v, h, p
FROM board
UNION ALL
-- делаем очередной шаг
SELECT g.n+1, v, h,
CASE
WHEN v=v_to AND h=h_to THEN piece_to
WHEN v=v_from AND h=h_from THEN ' '
ELSE p
END
FROM game g
JOIN moves m ON m.n = g.n
)
...На каждом ходу у нас будут добавляться 8×8=64 строки, что вполне терпимо для партии в несколько сотен ходов. Осталось взять последнюю итерацию и показать то, что получилось, в удобоваримом виде, попутно заменяя пустые черные клетки точками:
WITH RECURSIVE ... (
...
), last_position AS (
-- берем последнюю итерацию
SELECT * FROM game WHERE n = (SELECT max(n) FROM game)
)
-- красиво выводим результат
SELECT h.h AS line,
string_agg(
CASE WHEN b.p = ' ' AND (v.v+h.h) % 2 = 0 THEN '.' ELSE b.p END,
'' ORDER BY v.v
) AS chess
FROM generate_series(1,8) h(h)
CROSS JOIN generate_series(1,8) v(v)
LEFT JOIN last_position b ON b.h = h.h AND b.v = v.v
GROUP BY h.h
ORDER BY h.h DESC; line | chess
------+----------
8 | r.bqk.nr
7 | pppp.ppp
6 | .n. . .
5 | b . . .
4 | .B.P. .
3 | . Pp.N.
2 | P. . PPP
1 | RNBQ.RK
(8 rows)Полное решение
WITH RECURSIVE rawmoves(n,color,move) AS (
-- разбиваем на отдельные ходы и определяем цвет
SELECT row_number() over() * 2,
CASE WHEN row_number() over() % 2 = 0 THEN 'B' ELSE 'W' END,
move[1]
FROM regexp_matches(
coalesce(translate(current_setting('chess.game',true),'x+#',''),'') || ' ',
'([a-h1-8RBNQKO-]+) ', 'g'
) move
), castling(color,move,n,newmove) AS (
VALUES -- ходы рокировок
('W', 'O-O', 0, 'Rh1f1'),
('W', 'O-O', 1, 'Ke1g1'),
('W', 'O-O-O', 0, 'Ra1d1'),
('W', 'O-O-O', 1, 'Ke1c1'),
('B', 'O-O', 0, 'Rh8f8'),
('B', 'O-O', 1, 'Ke8g8'),
('B', 'O-O-O', 0, 'Ra8d8'),
('B', 'O-O-O', 1, 'Ke8c8')
), castlingmoves(n,color,move) AS (
-- заменяем рокировку на обычные ходы
SELECT r.n+coalesce(c.n,0), r.color, coalesce(c.newmove,r.move)
FROM rawmoves r
LEFT JOIN castling c ON c.color = r.color AND c.move = r.move
), components(n,color,piece_from,v_from,h_from,piece_to,v_to,h_to) AS (
-- разбиваем каждый ход на отдельные компоненты
SELECT n, color, coalesce(nullif(m[1],''),'P'),
nullif(m[2],''), nullif(m[3],''), nullif(m[6],''), m[4], m[5]
FROM (
SELECT n, color,
regexp_matches(move,'([RBNQK]?)([a-h]?)([1-8]?)([a-h])([1-8])([RBNQ])?') m
FROM castlingmoves
)
), moves(n,piece_from,v_from,h_from,piece_to,v_to,h_to) AS (
SELECT n,
CASE WHEN color = 'B' THEN lower(piece_from) ELSE piece_from END,
v_from, h_from,
CASE WHEN color = 'B' THEN lower(piece_to) ELSE piece_to END,
v_to, h_to
FROM (
SELECT row_number() OVER (ORDER BY n) AS n,
color,
piece_from,
ascii(v_from) - ascii('a') + 1 AS v_from,
nullif(h_from,'')::integer AS h_from,
coalesce(piece_to,
CASE
WHEN piece_from = 'P' AND h_to IN ('1','8') THEN 'Q'
ELSE piece_from
END) AS piece_to,
ascii(v_to) - ascii('a') + 1 AS v_to,
nullif(h_to,'')::integer AS h_to
FROM components
)
), board(v,h,p) AS (
-- начальная позиция (все клетки)
VALUES
(1,1,'R'),(2,1,'N'),(3,1,'B'),(4,1,'Q'),(5,1,'K'),(6,1,'B'),(7,1,'N'),(8,1,'R'),
(1,2,'P'),(2,2,'P'),(3,2,'P'),(4,2,'P'),(5,2,'P'),(6,2,'P'),(7,2,'P'),(8,2,'P'),
(1,7,'p'),(2,7,'p'),(3,7,'p'),(4,7,'p'),(5,7,'p'),(6,7,'p'),(7,7,'p'),(8,7,'p'),
(1,8,'r'),(2,8,'n'),(3,8,'b'),(4,8,'q'),(5,8,'k'),(6,8,'b'),(7,8,'n'),(8,8,'r')
UNION ALL
SELECT v, h, ' ' FROM generate_series(1,8) v, generate_series(3,6) h
), game(n,v,h,p) AS (
-- начинаем с начальной позиции
SELECT 1, v, h, p
FROM board
UNION ALL
-- делаем очередной шаг
SELECT g.n+1, v, h,
CASE
WHEN v=v_to AND h=h_to THEN piece_to
WHEN v=v_from AND h=h_from THEN ' '
ELSE p
END
FROM game g
JOIN moves m ON m.n = g.n
), last_board AS (
-- берем последнюю итерацию
SELECT * FROM game WHERE n = (SELECT max(n) FROM game)
)
-- красиво выводим результат
SELECT h.h AS line,
string_agg(
CASE WHEN b.p = ' ' AND (v.v+h.h) % 2 = 0 THEN '.' ELSE b.p END,
'' ORDER BY v.v
) AS chess
FROM generate_series(1,8) h(h)
CROSS JOIN generate_series(1,8) v(v)
LEFT JOIN last_board b ON b.h = h.h AND b.v = v.v
GROUP BY h.h
ORDER BY h.h DESC;А вот для разнообразия решение Артема Сухова. В нем ходы находятся в массиве, а поле представлено объектом jsonb: ключ — номер клетки, значение — фигура в этой клетке. В jsonb не бывает дубликатов ключей, поэтому повторное добавление ключа приводит к перезаписи значения (об этом, кстати, стоило написать в комментариях).
Решение Артема Сухова
-- Решение строится на обновлении игрового поля после каждого хода
-- убираем из данных: порядковый номер хода, х(убийство), +(шах), #(мат) для упрощения парсинга
WITH RECURSIVE input as (
SELECT regexp_replace((select current_setting('chess.game')), '\d+\. |[x+#]', '', 'g') AS data
)
-- обновление игровой доски после каждого шага
,moves as (
select 0 as move_number
-- массив ходов
, string_to_array((select data from input), ' ') as moves_array
-- игровое поле
, '{"a1" : "R", "a2" : "P", "a3" : " ", "a4" : " ", "a5" : " ", "a6" : " ", "a7" : "p", "a8" : "r"
,"b1" : "N", "b2" : "P", "b3" : " ", "b4" : " ", "b5" : " ", "b6" : " ", "b7" : "p", "b8" : "n"
,"c1" : "B", "c2" : "P", "c3" : " ", "c4" : " ", "c5" : " ", "c6" : " ", "c7" : "p", "c8" : "b"
,"d1" : "Q", "d2" : "P", "d3" : " ", "d4" : " ", "d5" : " ", "d6" : " ", "d7" : "p", "d8" : "q"
,"e1" : "K", "e2" : "P", "e3" : " ", "e4" : " ", "e5" : " ", "e6" : " ", "e7" : "p", "e8" : "k"
,"f1" : "B", "f2" : "P", "f3" : " ", "f4" : " ", "f5" : " ", "f6" : " ", "f7" : "p", "f8" : "b"
,"g1" : "N", "g2" : "P", "g3" : " ", "g4" : " ", "g5" : " ", "g6" : " ", "g7" : "p", "g8" : "n"
,"h1" : "R", "h2" : "P", "h3" : " ", "h4" : " ", "h5" : " ", "h6" : " ", "h7" : "p", "h8" : "r"
}'::jsonb as chessboard
union ALL
select move_number + 1
-- оставшиеся шаги в партии
, moves_array[2:array_length(moves_array, 1)] AS moves_array
-- обновляем игровое поле. короткая рокировка
, case when moves_array[1] = 'O-O'
-- если ходит первый игрок
then case when mod(move_number+1, 2) = 1
then chessboard ||
'{"e1": " "}'::jsonb ||
'{"h1": " "}'::jsonb ||
'{"g1": "K"}'::jsonb ||
'{"f1": "R"}'::jsonb
else chessboard ||
'{"e8": " "}'::jsonb ||
'{"h8": " "}'::jsonb ||
'{"g8": "k"}'::jsonb ||
'{"f8": "r"}'::jsonb end
-- длинная рокировка
else case when moves_array[1] = 'O-O-O'
then case when mod(move_number+1, 2) = 1
then chessboard ||
'{"e1": " "}'::jsonb ||
'{"a1": " "}'::jsonb ||
'{"c1": "K"}'::jsonb ||
'{"d1": "R"}'::jsonb
else chessboard ||
'{"e8": " "}'::jsonb ||
'{"a8": " "}'::jsonb ||
'{"c8": "k"}'::jsonb ||
'{"d8": "r"}'::jsonb end
-- если не рокировка
else chessboard ||
-- убираем фигуру из начальной позиции
('{"' || (regexp_match(moves_array[1], '([a-h][1-8])'))[1] || '": " "}')::jsonb ||
-- ставим фигуру на конечную позицию
('{"' || (regexp_match(moves_array[1], '[a-h][1-8].*?([a-h][1-8])'))[1] || '": "'||
case when mod(move_number+1, 2) = 1
-- шаг длины 5 = или ход НЕ пешки, или явное превращение пешки
then upper(case when length(moves_array[1]) = 5
then case when substring(moves_array[1], 1, 1) in ('N', 'B', 'R', 'Q', 'K')
then substring(moves_array[1], 1, 1)
else substring(moves_array[1], 5, 1) end
-- иначе или неявное превращение пешки
else case when substring(moves_array[1], 4, 1) in ('1', '8')
then 'Q'
-- иначе ход пешки
else 'P' end
end)
else lower(case when length(moves_array[1]) = 5
then case when substring(moves_array[1], 1, 1) in ('N', 'B', 'R', 'Q', 'K')
then substring(moves_array[1], 1, 1)
else substring(moves_array[1], 5, 1) end
else case when substring(moves_array[1], 4, 1) in ('1', '8')
then 'Q'
else 'P' end
end) end
||'"}')::jsonb end end
FROM moves
WHERE move_number < array_length(string_to_array((select data from input), ' '), 1)
)
-- разбиваем jsonb на столбцы и строки для отображения игрового поля
, cells_data as (
select (regexp_match(key, '\d'))[1]::int as line
, row_number() over(partition by (regexp_match(key, '\d'))[1] order by key) as col
, key
, value
-- берем игровую доску с последнего хода
from jsonb_each_text((select chessboard
from moves
where move_number = (select max(move_number) from moves)))
)
select line, string_agg(case when value != ' '
then value
else case when mod(line+col, 2) = 0 then '.' else ' ' end end, '' order by key) as chess
from cells_data
group by line
order by line descНе делайте так
Почему-то несколько участников взялись нумеровать пункты решения. Доходило даже до такого:
-- 2.2.1.2.5 Превращение в слона
Не могу найти в этом смысла. Кому и о чем могут говорить эти номера?В PostgreSQL нет необходимости писать
SELECT ... UNION ALL SELECT ... UNION ALL ..., когда надо вернуть фиксированный набор строк. Для этого есть более лаконичная конструкцияVALUES.Чтобы набрать сколько-нибудь баллов за задачу, проверяемую тестами, надо сделать хотя бы часть задания, но до конца. Например, в этой задаче реализация всего, кроме рокировок и превращений пешек, давала вполне солидные 8 баллов. Если же задача «почти решена», но не проходит ни одного теста — увы, остается только посочувствовать.
Капитанский совет: решение необходимо тестировать. Например, можно взять из сборника шахматных задач или даже из википедии какую-нибудь партию, для которой известна финальная позиция.
Задача 4. Шахматы (продолжение)
Условие
Полная запись шахматной партии из предыдущей задачи может быть сокращена: в ней разрешается опускать указание текущего положения фигуры — либо целиком, либо только одной из координат — так, чтобы такое сокращение не приводило к неоднозначности.
Примеры:
Rb7— ладья идет на b7 (допустимо, если нет другой ладьи, которая может сделать такой же ход);R6b7— ладья идет на b7 с шестой горизонтали (уточнение требуется, если, например, другая ладья стоит на b8);Rab7— ладья идет на b7 c вертикали a (возможно, на седьмой горизонтали стоит другая ладья).При взятии пешкой текущая вертикаль пешки в нашей сокращенной нотации никогда не опускается. Например:
exd5— пешка с вертикали e бьет на d5.
Запрос получает запись партии в конфигурационном параметре chess.game. Известно, что предоставленная запись корректна, то есть все ходы определяются однозначно и не нарушают правил игры.
Напишите запрос, выводящий позицию, которая возникнет на шахматной доске после воспроизведения всех ходов, записанных в сокращенной нотации. Запрос должен вывести информацию в том же виде, что и в предыдущей задаче.
Пример
Для следующих входных данных
SET chess.game='1. e4 e5 2. Bc4 Nc6 3. Qh5 Nf6 4. Qxf7#';запрос должен вывести:
line | chess
------+----------
8 | r.bqkb r
7 | pppp.Qpp
6 | .n. n .
5 | . . p .
4 | .B.P. .
3 | . . . .
2 | PPPP PPP
1 | RNB K NR
(8 rows)Решение
По условию этой задачи в записи партии может отсутствовать указание исходной клетки (вертикали, горизонтали, или обеих координат), если это не приводит к неоднозначности. Вот пример неоднозначной записи:
1. e4 e5 2. Nc3 d6 3. Ne2Здесь на клетку e2 могут пойти оба белых коня, поэтому ход обязательно нужно уточнять, например, Nge2.
Понятно, что мы не можем заранее узнать, какая именно фигура имеется в виду; для этого надо сделать все предыдущие ходы и посмотреть на текущее состояние поля. Это говорит нам о том, что изменения потребуются в рекурсивном табличном выражении. Зато весь остальной код мы можем оставить без изменений.
Следующий фрагмент партии иллюстрирует еще одну проблему:
1. a4 e5 2. Ra3 d5 3. Rh3Здесь последний ход записан однозначно, хотя клетка h3 находится на одной горизонтали с ладьей a3 и на одной вертикали с ладьей h8. Но ладья h не может сделать ход на h3, поскольку перед ней стоит пешка. Те немногие участники, которые добрались до этого места, решили пойти таким путем: 1) выбрать все ладьи на горизонтали или вертикали целевой клетки и 2) отбросить те ладьи, которые отделены от целевой клетки какими-либо фигурами. Я предлагаю попробовать по-другому: 1) выбрать ближайшие к целевой клетке фигуры, которые стоят на ее горизонтали или вертикали, и 2) оставить из найденного только ладьи. Кажется, что в этом случае решение получается попроще.
С ладей и начнем. Вот что мы получим в таблице moves, воспользовавшись решением предыдущей задачи:
SET chess.game = '1. a2a4 e7e5 2. Ra3 d7d5 3. Rh3';
WITH RECURSIVE ... (
...
)
SELECT * FROM moves ORDER BY n; n | piece_from | v_from | h_from | piece_to | v_to | h_to
---+------------+--------+--------+----------+------+------
1 | P | 1 | 2 | P | 1 | 4
2 | p | 5 | 7 | p | 5 | 5
3 | R | | | R | 1 | 3
4 | p | 4 | 7 | p | 4 | 5
5 | R | | | R | 8 | 3
(5 rows)Пешкам я пока подставил полную нотацию, а у ладей ожидаемо не заполнены исходные координаты v_from и h_from. Их-то нам и предстоит выяснить.
Основное изменение подзапроса game состоит в том, что я добавляю соединение (CROSS JOIN LATERAL) с подзапросом, в котором вычисляются исходные координаты; эти координаты затем используются вместо координат из таблицы moves. LATERAL нужен, чтобы иметь в этом подзапросе доступ к столбцам moves.
В подзапросе пока две части: одна реализует ход ладьей, а вторая служит заглушкой и просто возвращает исходные координаты из moves для всех остальных фигур. Дальше в этот подзапрос можно будет постепенно добавлять логику для оставшихся фигур.
По неведомым мне причинам PostgreSQL считает, что ссылка на рекурсивное табличное выражение может появиться в рекурсивной части запроса только один раз (recursive reference to query must not appear more than once). Нам надо больше, но это, к счастью, легко преодолевается оборачиванием ссылки в табличное выражение g.
Итак, вот что у нас получается:
WITH RECURSIVE ... (
...
), game(n,v,h,p) AS (
-- начинаем с начальной позиции
SELECT 1, v, h, p
FROM board
UNION ALL
-- делаем очередной шаг
SELECT * FROM (
WITH g AS (
-- все игровое поле
SELECT * FROM game
), pcs AS (
-- только фигуры
SELECT * FROM g WHERE p != ' '
)
SELECT g.n+1, v, h,
CASE
WHEN v = v_to AND h = h_to THEN piece_to
-- исходные координаты берем из подзапроса ниже
WHEN v = v_from2 AND h = h_from2 THEN ' '
ELSE p
END
FROM g
JOIN moves m ON m.n = g.n
-- тут вычисляем исходные координаты
CROSS JOIN LATERAL (
-- Ладья
SELECT v AS v_from2, h AS h_from2
FROM (
-- ближайшая фигура ниже
(SELECT pcs.p, pcs.v, pcs.h FROM pcs
WHERE pcs.v = v_to AND pcs.h < h_to
ORDER BY abs(pcs.h - h_to) LIMIT 1)
UNION ALL
-- выше
(SELECT pcs.p, pcs.v, pcs.h FROM pcs
WHERE pcs.v = v_to AND pcs.h > h_to
ORDER BY abs(pcs.h - h_to) LIMIT 1)
UNION ALL
-- слева
(SELECT pcs.p, pcs.v, pcs.h FROM pcs
WHERE pcs.h = h_to AND pcs.v < v_to
ORDER BY abs(pcs.v - v_to) LIMIT 1)
UNION ALL
-- справа
(SELECT pcs.p, pcs.v, pcs.h FROM pcs
WHERE pcs.h = h_to AND pcs.v > v_to
ORDER BY abs(pcs.v - v_to) LIMIT 1)
)
WHERE p = piece_from -- из найденных фигур берем ладьи
AND piece_from IN ('R','r')
-- учитываем исходные координаты, если они указаны
AND (v_from IS NULL OR v = v_from)
AND (h_from IS NULL OR h = h_from)
UNION ALL
-- Остальные фигуры
-- временная заглушка: рассчитываем на полную нотацию
SELECT v_from, h_from
WHERE piece_from NOT IN ('R','r')
)
)
), ...
... line | chess
------+----------
8 | rnbqkbnr
7 | ppp .ppp
6 | . . . .
5 | . .pp .
4 | P. . . .
3 | . . . .R
2 | PPPPPPP
1 | .NBQKBNR
(8 rows)На последнем ходу в подзапросе были выбраны три фигуры, ближайшие к целевой клетке h3: пешки h7 и h2 и ладья a3. Пешки мы отбросили, а ладья осталась и совершила ход.
Если запись партии будет неоднозначной или неправильной, подзапрос может вернуть несколько строк или не вернуть ни одной. Это все сломает, но, к счастью, по условию задачи нам не надо обрабатывать такие ситуации.
В отличие от варианта, в котором сначала выбираются все фигуры, равные целевой, а затем проверяется отсутствие препятствий для хода, здесь вся логика, касающаяся конкретной фигуры, не размазана по запросу, а локализована в одном месте. Это полезное для отладки свойство.
На этом можно и остановиться, поскольку добавить остальные фигуры по аналогии не так уж и сложно (хотя и громоздковато). Сделаю несколько подсказок на случай, если захотите попробовать сами.
Во-первых, надо помнить, что из-за пешек на доске могут появиться несколько любых фигур (кроме короля). Например, два ферзя или два белопольных слона. Так что рассчитывать на уникальность нельзя.
Во-вторых, конь «перепрыгивает» через фигуры, что упрощает задачу (хотя казалось бы).
В-третьих, не надо забывать про взятие на проходе (ни один участник его не реализовал, хотя в условии предыдущей задачи намек был дан). Тут, в отличие от обычного хода, участвуют три клетки, что требует особой обработки.
Полное решение
WITH RECURSIVE rawmoves(n,color,move) AS (
-- разбиваем на отдельные ходы и определяем цвет
SELECT row_number() over() * 2,
CASE WHEN row_number() over() % 2 = 0 THEN 'B' ELSE 'W' END,
move[1]
FROM regexp_matches(
coalesce(translate(current_setting('chess.game',true),'x+#',''),'') || ' ',
'([a-h1-8rbnqkRBNQKO-]+) ', 'g'
) move
), castling(color,move,n,newmove) AS (
VALUES -- ходы рокировок
('W', 'O-O', 0, 'Rh1f1'),
('W', 'O-O', 1, 'Ke1g1'),
('W', 'O-O-O', 0, 'Ra1d1'),
('W', 'O-O-O', 1, 'Ke1c1'),
('B', 'O-O', 0, 'Rh8f8'),
('B', 'O-O', 1, 'Ke8g8'),
('B', 'O-O-O', 0, 'Ra8d8'),
('B', 'O-O-O', 1, 'Ke8c8')
), castlingmoves(n,color,move) AS (
-- заменяем рокировку на обычные ходы
SELECT r.n+coalesce(c.n,0), r.color, coalesce(c.newmove,r.move)
FROM rawmoves r
LEFT JOIN castling c ON c.color = r.color AND c.move = r.move
), components(n,color,piece_from,v_from,h_from,piece_to,v_to,h_to) AS (
-- разбиваем каждый ход на отдельные компоненты
SELECT n, color, coalesce(nullif(m[1],''),'P'),
nullif(m[2],''), nullif(m[3],''), nullif(m[6],''), m[4], m[5]
FROM (
SELECT n, color,
regexp_matches(move,'([RBNQK]?)([a-h]?)([1-8]?)([a-h])([1-8])([RBNQ])?') m
FROM castlingmoves
)
), moves(n,piece_from,v_from,h_from,piece_to,v_to,h_to) AS (
SELECT n,
CASE WHEN color = 'B' THEN lower(piece_from) ELSE piece_from END,
v_from, h_from,
CASE WHEN color = 'B' THEN lower(piece_to) ELSE piece_to END,
v_to, h_to
FROM (
SELECT row_number() OVER (ORDER BY n) AS n,
color,
piece_from,
ascii(v_from) - ascii('a') + 1 AS v_from,
nullif(h_from,'')::integer AS h_from,
coalesce(piece_to,
CASE
WHEN piece_from = 'P' AND h_to IN ('1','8') THEN 'Q'
ELSE piece_from
END) AS piece_to,
ascii(v_to) - ascii('a') + 1 AS v_to,
nullif(h_to,'')::integer AS h_to
FROM components
)
), board(v,h,p) AS (
-- начальная позиция (все клетки)
VALUES
(1,1,'R'),(2,1,'N'),(3,1,'B'),(4,1,'Q'),(5,1,'K'),(6,1,'B'),(7,1,'N'),(8,1,'R'),
(1,2,'P'),(2,2,'P'),(3,2,'P'),(4,2,'P'),(5,2,'P'),(6,2,'P'),(7,2,'P'),(8,2,'P'),
(1,7,'p'),(2,7,'p'),(3,7,'p'),(4,7,'p'),(5,7,'p'),(6,7,'p'),(7,7,'p'),(8,7,'p'),
(1,8,'r'),(2,8,'n'),(3,8,'b'),(4,8,'q'),(5,8,'k'),(6,8,'b'),(7,8,'n'),(8,8,'r')
UNION ALL
SELECT v, h, ' ' FROM generate_series(1,8) v, generate_series(3,6) h
), game(n,v,h,p) AS (
-- начинаем с начальной позиции
SELECT 1, v, h, p
FROM board
UNION ALL
-- делаем очередной шаг
SELECT * FROM (
WITH g AS (
-- все игровое поле
SELECT * FROM game
), pcs AS (
-- только фигуры
SELECT * FROM g WHERE p != ' '
)
SELECT g.n+1, v, h,
CASE
WHEN v = v_to AND h = h_to THEN piece_to
-- исходные координаты берем из подзапроса ниже
WHEN (v = v_from2 OR (enpass AND v = v_to)) AND h = h_from2 THEN ' '
ELSE p
END
FROM g
JOIN moves m ON m.n = g.n
-- тут вычисляем исходные координаты
CROSS JOIN LATERAL (
---- Пешка - взятие
SELECT pcs.v AS v_from2, pcs.h AS h_from2,
-- признак взятия на проходе - отсутствие фигуры в целевой клетке
NOT EXISTS (
SELECT NULL FROM pcs WHERE h = h_to AND v = v_to
) AS enpass
FROM pcs
WHERE pcs.p = piece_from
AND piece_from IN ('P','p')
-- при взятии указаны обе вертикали, и они не совпадают
AND v_from != v_to
AND pcs.v = v_from
-- наискосок
AND pcs.h = h_to + CASE
WHEN piece_from = 'p' THEN +1 ELSE -1
END
UNION ALL
---- Пешка - простой ход
(SELECT pcs.v, pcs.h, false
FROM pcs
WHERE pcs.p = piece_from
-- только вертикаль
AND pcs.v = v_to
-- направление зависит от цвета пешки
AND ( (piece_from = 'p' AND pcs.h > h_to)
OR
(piece_from = 'P' AND pcs.h < h_to) )
-- учитываем исходные координаты, если они указаны
AND (v_from IS NULL OR pcs.v = v_from)
AND (h_from IS NULL OR pcs.h = h_from)
-- вертикали совпадают, если указаны обе
AND (v_from IS NULL OR v_from = v_to)
ORDER BY abs(h_to - pcs.h) LIMIT 1)
UNION ALL
---- Ладья
SELECT v, h, false
FROM (
-- ниже
(SELECT pcs.p, pcs.v, pcs.h FROM pcs
WHERE pcs.v = v_to AND pcs.h < h_to
ORDER BY abs(pcs.h - h_to) LIMIT 1)
UNION ALL
-- выше
(SELECT pcs.p, pcs.v, pcs.h FROM pcs
WHERE pcs.v = v_to AND pcs.h > h_to
ORDER BY abs(pcs.h - h_to) LIMIT 1)
UNION ALL
-- слева
(SELECT pcs.p, pcs.v, pcs.h FROM pcs
WHERE pcs.h = h_to AND pcs.v < v_to
ORDER BY abs(pcs.v - v_to) LIMIT 1)
UNION ALL
-- справа
(SELECT pcs.p, pcs.v, pcs.h FROM pcs
WHERE pcs.h = h_to AND pcs.v > v_to
ORDER BY abs(pcs.v - v_to) LIMIT 1)
)
WHERE p = piece_from
AND piece_from IN ('R','r')
-- учитываем исходные координаты, если они указаны
AND (v_from IS NULL OR v = v_from)
AND (h_from IS NULL OR h = h_from)
UNION ALL
---- Слон
SELECT v, h, false
FROM (
-- слева ниже
(SELECT pcs.p, pcs.v, pcs.h FROM pcs
WHERE abs(pcs.v - v_to) = abs(pcs.h - h_to)
AND pcs.h < h_to AND pcs.v < v_to
ORDER BY abs(pcs.v - v_to) LIMIT 1)
UNION ALL
-- слева выше
(SELECT pcs.p, pcs.v, pcs.h FROM pcs
WHERE abs(pcs.v - v_to) = abs(pcs.h - h_to)
AND pcs.h < h_to AND pcs.v > v_to
ORDER BY abs(pcs.v - v_to) LIMIT 1)
UNION ALL
-- справа ниже
(SELECT pcs.p, pcs.v, pcs.h FROM pcs
WHERE abs(pcs.v - v_to) = abs(pcs.h - h_to)
AND pcs.h > h_to AND pcs.v < v_to
ORDER BY abs(pcs.v - v_to) LIMIT 1)
UNION ALL
-- справа выше
(SELECT pcs.p, pcs.v, pcs.h FROM pcs
WHERE abs(pcs.v - v_to) = abs(pcs.h - h_to)
AND pcs.h > h_to AND pcs.v > v_to
ORDER BY abs(pcs.v - v_to) LIMIT 1)
)
WHERE p = piece_from
AND piece_from IN ('B','b')
-- учитываем исходные координаты, если они указаны
AND (v_from IS NULL OR v = v_from)
AND (h_from IS NULL OR h = h_from)
UNION ALL
---- Ферзь
SELECT v, h, false
FROM (
-- ниже
(SELECT pcs.p, pcs.v, pcs.h FROM pcs
WHERE pcs.v = v_to AND pcs.h < h_to
ORDER BY abs(pcs.h - h_to) LIMIT 1)
UNION ALL
-- выше
(SELECT pcs.p, pcs.v, pcs.h FROM pcs
WHERE pcs.v = v_to AND pcs.h > h_to
ORDER BY abs(pcs.h - h_to) LIMIT 1)
UNION ALL
-- слева
(SELECT pcs.p, pcs.v, pcs.h FROM pcs
WHERE pcs.h = h_to AND pcs.v < v_to
ORDER BY abs(pcs.v - v_to) LIMIT 1)
UNION ALL
-- справа
(SELECT pcs.p, pcs.v, pcs.h FROM pcs
WHERE pcs.h = h_to AND pcs.v > v_to
ORDER BY abs(pcs.v - v_to) LIMIT 1)
UNION ALL
-- слева ниже
(SELECT pcs.p, pcs.v, pcs.h FROM pcs
WHERE abs(pcs.v - v_to) = abs(pcs.h - h_to)
AND pcs.h < h_to AND pcs.v < v_to
ORDER BY abs(pcs.v - v_to) LIMIT 1)
UNION ALL
-- слева выше
(SELECT pcs.p, pcs.v, pcs.h FROM pcs
WHERE abs(pcs.v - v_to) = abs(pcs.h - h_to)
AND pcs.h < h_to AND pcs.v > v_to
ORDER BY abs(pcs.v - v_to) LIMIT 1)
UNION ALL
-- справа ниже
(SELECT pcs.p, pcs.v, pcs.h FROM pcs
WHERE abs(pcs.v - v_to) = abs(pcs.h - h_to)
AND pcs.h > h_to AND pcs.v < v_to
ORDER BY abs(pcs.v - v_to) LIMIT 1)
UNION ALL
-- справа выше
(SELECT pcs.p, pcs.v, pcs.h FROM pcs
WHERE abs(pcs.v - v_to) = abs(pcs.h - h_to)
AND pcs.h > h_to AND pcs.v > v_to
ORDER BY abs(pcs.v - v_to) LIMIT 1)
)
WHERE p = piece_from
AND piece_from IN ('Q','q')
-- учитываем исходные координаты, если они указаны
AND (v_from IS NULL OR v = v_from)
AND (h_from IS NULL OR h = h_from)
UNION ALL
---- Конь
(SELECT pcs.v, pcs.h, false
FROM pcs
WHERE pcs.p = piece_from
AND piece_from IN ('N','n')
AND ( (abs(pcs.v - v_to) = 1 AND abs(pcs.h - h_to) = 2)
OR (abs(pcs.v - v_to) = 2 AND abs(pcs.h - h_to) = 1) )
-- учитываем исходные координаты, если они указаны
AND (v_from IS NULL OR pcs.v = v_from)
AND (h_from IS NULL OR pcs.h = h_from)
)
UNION ALL
---- Король (всегда один)
SELECT pcs.v, pcs.h, false
FROM pcs
WHERE pcs.p = piece_from
AND piece_from in ('K','k')
)
)
), last_board AS (
-- берем последнюю итерацию
SELECT * FROM game WHERE n = (SELECT max(n) FROM game)
)
SELECT h.h AS line,
string_agg(
CASE WHEN b.p = ' ' AND (v.v+h.h) % 2 = 0 THEN '.' ELSE b.p END,
'' ORDER BY v.v
) AS chess
FROM generate_series(1,8) h(h)
CROSS JOIN generate_series(1,8) v(v)
LEFT JOIN last_board b ON b.h = h.h AND b.v = v.v
GROUP BY h.h
ORDER BY h.h DESC;Если придумаете, как написать более компактный запрос, буду признателен за комментарий.
Не делайте так
Нереляционные решения (манипулирующие JSON-ами или строками) оказалось сложнее приспособить под изменившиеся условия. Если счет строкам запроса идет уже на тысячи — дело неладно, пора насторожиться.
Я и раньше подозревал, что некоторые (хотя чего уж там, многие) участники пытаются проскочить на ChatGPT, присылая откровенно нерабочий код. Но в этот раз я в этом абсолютно уверен: ведь ни одному живому человеку не пришло бы в голову вставить в запрос таблицу
deedsиз позапрошлой задачи. А кое-кто обленился до такой степени, что даже не стал удалять вводные слова. MySQL, Карл!
Для решения данной задачи на SQL можно использовать следующий код:
...
Этот SQL-запрос создает временную таблицу для хранения состояния шахматной доски и заполняет ее начальным состоянием. Затем он разбивает запись партии на отдельные ходы и применяет каждый ход к доске. Наконец, он выводит текущее состояние доски в виде шахматной доски. Вы можете выполнить этот SQL-запрос в среде работы с базами данных MySQL или другой поддерживающей SQL для получения результата для вашего примера.
Задача 5. Ханойская башня
Условие
Согласно известной легенде, провинившиеся перед Брахмой монахи должны в наказание перекладывать диски разного диаметра со стержня на стержень так, чтобы меньшие диски всегда покоились на больших.
Однако наплыв туристов очень мешал монахам спокойно работать над приближением конца света, который наступит, когда все 64 диска будут переставлены с одного из стержней на какой-либо другой. Тогда монахи решили перенести свою задачу в онлайн, чтобы каждый желающий мог поучаствовать в процессе. Из клиентской части написанного ими приложения вызывается единственная хранимая функция:
FUNCTION move(rod_from integer, rod_to integer) RETURNS integer;Функция принимает номера исходного и целевого стержней и должна перенести верхний диск с исходного стержня на целевой, если это возможно. Запрещено переставлять диск на диск меньшего диаметра, а также снимать диск и возвращать его на тот же стержень.
Стержни пронумерованы от 1 до 64. Обычно думают, что Брахма создал всего три алмазных стержня, но монахи решили восстановить историческую справедливость: они хорошо помнят, что первой же ночью почти все стержни исчезли в неизвестном направлении.
Известно, что перестановка выполняется только с помощью указанной функции, но в нее могут передаваться и некорректные параметры (монахи не сильны во фронтенде).
В случае успеха функция должна вернуть номер переставленного диска (диски пронумерованы от 1 до 64 в порядке возрастания диаметра). Если указанное перемещение невозможно, функция должна завершиться ошибкой (любой).
Спроектируйте схему данных и реализуйте для нее функцию move на языке SQL так, чтобы гарантировать согласованность данных. Решение должно содержать SQL-команды создания функции и таблицы, заполненной начальными данными так, чтобы все 64 диска находились на первом стержне.
Необходимо учитывать, что функция будет одновременно вызываться множеством приложений. Среди правильных решений дополнительные баллы получат более производительные; решения, допускающие некорректное поведение, не получат дополнительных баллов.
Пример
Если все диски находятся на стержне 1 (начальное положение), то следующий вызов:
SELECT move(1,2);должен переставить диск 1 со стержня 1 на стержень 2 и вернуть
move
------
1
(1 rows)Затем вызов
SELECT move(1,3);должен переставить диск 2 со стержня 1 на стержень 3 и вернуть
move
------
2
(1 rows)После чего вызов
SELECT move(3,2);должен завершиться ошибкой, поскольку диск 2 не может быть поставлен на диск 1 меньшего диаметра.
Решение
Эту задачу я дал из двух соображений. Во-первых, для разнообразия: в отличие от предыдущих задач, тут можно и нужно было написать несколько SQL-запросов (но только SQL, никакие процедурные решения не принимались). Во-вторых, я считаю тему изоляции крайне важной, но очень плохо понимаемой. Мне хотелось показать на простом примере, что происходит, когда про изоляцию забывают.
С проектированием схемы данных почти ни у кого проблем не возникло: нужна таблица соответствий, строка в которой с номером диска и номером стержня означает, что данный диск находится на данном стержне.
По условию задачи функция должна завершаться ошибкой при попытке совершить некорректное перемещение. В SQL нет такой штуки, как RAISE EXCEPTION, поэтому участникам пришлось проявлять изобретательность. Кто-то делил на ноль, кто-то возвращал в подзапросе несколько строк. Все это принималось (в условии сказано, что ошибка может быть любой), хотя на мой вкус лучше, чтобы ошибка вызвалась нарушением ограничения целостности. Исходя из этого в своем решении я создал такую таблицу:
CREATE TABLE hanoi(
disk integer,
rod integer NOT NULL CHECK (rod BETWEEN 1 AND 64),
chk boolean NOT NULL CHECK (chk)
);Ограничение диапазона значений столбца disk отсутствует, поскольку таблица изначально будет заполнена только нужными значениями, а меняться будет только номер стержня. Также здесь нет первичного ключа: в моем решении это не добавило бы гарантий целостности, зато создало бы ненужный для такой небольшой таблицы индекс.
В столбец chk я буду записывать false, когда мне нужно будет бросить исключение.
Кто-то пошел другим путем: создал таблицу стержней, в строках которой хранятся массивы дисков:
CREATE TABLE rods(
rod integer, -- PRIMARY KEY
disks integer[]
);Можно и так, но перенос диска со стержня на стержень будет требовать две операции UPDATE, а это не добавляет скорости.
Теперь переходим к функции move.
Как сказано в условии, на вход ей могут подаваться некорректные данные: номер несуществующего стержня или диска (включая NULL, о чем некоторые забыли). Кроме того, функция не должна допускать некорректные операции:
перекладывание диска со стержня на тот же самый стержень;
попытка взять диск с пустого стержня;
перекладывание диска большего диаметра на диск меньшего диаметра.
Выполнение этих требований проверялось двумя тестами. Простой «smoke-тест» проверял обработку некорректных входных данных и выполнял несколько перемещений дисков, как корректных, так и нет. Второй тест генерировал случайную последовательность из 50 тысяч операций (как корректных, так и нет) и сверял результат с ожидаемым, полученным от альтернативной «эталонной» реализации (я написал ее на PL/pgSQL).
Прохождение этих тестов давало половину возможных баллов. Наверное, пора показать решение, которое справится с этой задачей:
CREATE FUNCTION move(rod_from integer, rod_to integer) RETURNS integer
LANGUAGE sql
AS $$
-- ...тут пока кое-чего не хватает...
UPDATE hanoi h
SET rod = rod_to,
chk = disk < coalesce(( -- нельзя класть больший на меньший и сам на себя
SELECT min(disk)
FROM hanoi
WHERE rod = rod_to
),65)
AND ( -- исходный стержень должен быть непустым
SELECT min(disk)
FROM hanoi
WHERE rod = rod_from
) IS NOT NULL
WHERE disk = coalesce((
SELECT min(disk) -- верхний диск
FROM hanoi
WHERE rod = rod_from
),1) -- надо всегда какой-то выбрать, чтобы update мог сломаться на chk
RETURNING disk;
$$;Другая половина баллов причиталась решениям, корректно работающим в условиях конкурентного выполнения.
В условии нам не сказали, какой уровень изоляции используют монахи, поэтому приходится рассчитывать на худшее (и, в то же время, самое распространенное) — Read Committed. На этом уровне изоляции у каждого запроса — свой снимок данных. Чем нам это грозит?
В варианте с массивами обновление может выглядеть примерно так:
...
... проверки корректности ...
UPDATE rods SET disks = ... WHERE red = rod_from;
UPDATE rods SET disks = ... WHERE red = rod_to;
...Между проверкой, первым обновлением и вторым обновлением может произойти все что угодно. Например, кто-то может убрать диск со стержня rod_from, который мы собрались переставить. Или успеть положить небольшой диск на стержень rod_to, в результате чего перемещение станет недопустимым. Все это приведет к нарушению согласованности, хотя, пока функция выполнялась в единственном экземпляре, она работала корректно.
Чтобы такая функция работала корректно в условиях конкурентности, надо перед выполнением проверок заблокировать оба стержня rod_from и rod_to. В этом случае нам уже никто не сможет помешать перенести диск с одного стержня на другой.
Но большинство участников, добравшихся до мысли о конкурентности, блокировали всю таблицу, обычно в исключительном режиме (LOCK TABLE). Безусловно, это работает, но запрещает переносить диски и между другими стержнями, что несколько просаживает производительность.
Ян Сенин догадался до того, что достаточно заблокировать два стержня, но попался в другую ловушку: блокировки на уровне строк (SELECT ... FOR UPDATE) — затратные операции, связанные с записью информации на страницу данных. На моей тестовой нагрузке простой LOCK TABLE оказался ощутимо, процентов на 20, быстрее.
Еще одна ловушка, которая подстерегает при работе с несколькими ресурсами — это порядок блокирования. Стержни надо блокировать в одном и том же порядке, например, от меньшего к большему, иначе будут возникать взаимоблокировки, которые погубят всю производительность.
Хорошо, а что может пойти не так с моим вариантом, в котором и проверки, и обновление выполняется в одном операторе, изменяющем одну строку? Ровно то же самое: блокировка одной строки (то есть пары стержень—диск) не блокирует оба стержня. Например, два таких запроса могут одновременно перенести на один и тот же стержень диски разных размеров, а затем завершиться в неправильном порядке, в результате чего окажется, что больший диск положили на меньший.
Понятно, что LOCK TABLE сработает и в этом случае, но как заблокировать стержни? А для этого в PostgreSQL этого есть рекомендательные блокировки, которые к тому же и быстро работают. Такой вариант в моих тестах оказался быстрее процентов на 15. До рекомендательных блокировок догадался только Андрей Кудинов; к сожалению, досадная ошибка помешала ему вырваться вперед.
Полное решение
CREATE TABLE hanoi(
disk integer,
rod integer NOT NULL CHECK (rod BETWEEN 1 AND 64),
chk boolean NOT NULL CHECK (chk)
);
INSERT INTO hanoi
SELECT disk, 1, true FROM generate_series(1,64) disk;
CREATE FUNCTION move(rod_from integer, rod_to integer) RETURNS integer
LANGUAGE sql
AS $$
SELECT pg_advisory_xact_lock(least(rod_from,rod_to));
SELECT pg_advisory_xact_lock(greatest(rod_from,rod_to));
UPDATE hanoi h
SET rod = rod_to,
chk = disk < coalesce(( -- нельзя класть больший на меньший и сам на себя
SELECT min(disk)
FROM hanoi
WHERE rod = rod_to
),65)
AND ( -- исходный стержень должен быть непустым
SELECT min(disk)
FROM hanoi
WHERE rod = rod_from
) IS NOT NULL
WHERE disk = coalesce((
SELECT min(disk) -- верхний диск
FROM hanoi
WHERE rod = rod_from
),1) -- надо всегда какой-то выбрать, чтобы update мог сломаться на chk
RETURNING disk;
$$;Для проверки поведения функции в условиях конкурентности я поступил так:
Подавал тестовую нагрузку в несколько потоков. После вызова функции сохранял номер транзакции, а также параметры и результат функции в журнальную таблицу.
В конце обновлл журнальную таблицу временем фиксации транзакций (см. параметр track_commit_timestamp и функцию pg_xact_commit_timestamp), сериализуя таким образом транзакции.
Сверял результат сериализованных вызовов с эталонной реализацией.
В заключение не могу не поделиться радостью от комментария Ильи Дерксена, в котором он процитировал пять правил программирования Роба Пайка, и затем честно пытался следовать им (я, правда, всегда считал, что про преждевременную оптимизацию сказал Кнут).
Ну а примерно через месяц расскажу о том, как прошел финал олимпиады. Stay tuned!
