В шахматы меня когда-то легко обыгрывал восьмибитный компьютер, а действующего чемпиона мира IBM-овский Deep Blue одолел уже в 1997 году. Но игра Го держалась значительно дольше: победить обладателя девятого дана Ли Седоля удалось только в 2016 году компании Гугл со своей машиной AlphaGo. В Го простые правила, которые, однако, приводят к очень сложным стратегическим построениям. Ровно то, что нужно: простое условие, не дающее намека на то, как справиться с задачей одним SQL-запросом. Тема Го и легла в основу задач финала олимпиады, про которую я уже начал рассказывать в прошлый раз.
Финал проходил в Сочинском государственном университете. Пользуясь случаем, хочу сказать спасибо гостеприимным сотрудникам университета и организаторам, оперативно устранявшим все трудности.
На решение задач был отведен целый день; мы начали примерно в половине одиннадцатого и закончили в семь вечера. Участники могли работать на собственных ноутбуках и свободно пользоваться интернетом. Единственной просьбой было решать задачи самостоятельно, не прибегая к помощи друзей.
Всего я приготовил семь задач. Формально их можно было делать в любом порядке, но построены они были так, что решение предыдущей немного приближало к решению следующей.
К каждой задаче был придуман набор тестов. Задания проверялись в онлайне: участники могли отправить свое решение на проверку и через минуту узнать свои баллы, начисленные за каждый пройденный тест.
Для автоматической проверки заданий использовалась система, которую разработал наш коллега Илья Баштанов на основе Database Lab Engine. Она поддерживает пул тонких клонов PostgreSQL и запускает на них весь набор тестов в параллель. Вообще-то мы собираемся использовать эту систему для создания собственного SQL-блекджекатренажера, но это уже совсем другая история.
Решения можно было проверять сколько угодно раз, при этом учитывался максимальный достигнутый результат. Это, по моей задумке, давало участникам определенную свободу: можно было доводить до совершенства каждое задание, а можно было, получив некоторый результат, двигаться дальше к следующей задаче. Разные стратегии, конечно, имеют смысл только при условно бесконечном пуле задач, и вот с этим вышла промашка. Я даже в шутку не предполагал, что за отведенное время можно решить все задачи. У меня-то самого на них ушло гораздо больше времени. Я сказал на закрытии олимпиады и повторю еще раз: ребята-финалисты, я вами восхищаюсь! И не только теми, кто попал в верхние строчки турнирной таблицы, но и всеми, кто не сдавался до последнего. Вы смогли меня приятно удивить!
Перейдем собственно к разбору задач. Все строится вокруг следующей преамбулы с несколькими определениями.
Преамбула
Для решения задач не требуется знаний правил Го. Нам понадобятся лишь несколько следующих определений.
В игре Го два игрока по очереди выставляют на доску 19×19 пунктов (называемую гобан) черные и белые камни. Доска представлена таблицей координат и цветов камней:
CREATE TABLE goban(
x integer NOT NULL CHECK (x BETWEEN 0 AND 18),
y integer NOT NULL CHECK (y BETWEEN 0 AND 18),
stone text NOT NULL CHECK (stone IN ('B','W')),
UNIQUE (x,y)
);Камни одного цвета, соприкасающиеся по вертикалям или горизонталям, образуют группу.
Свободные пункты доски сверху, снизу, справа и слева от камней группы образуют дыхания, или свободы, этой группы. (Это важное для игры понятие, поскольку группа, оставшаяся без дыханий, считается окруженной и берется в плен.)
Атари — угроза окружения следующим ходом. Позиция атари возникает, когда соперник своим ходом уменьшает группе камней количество дыханий до одного (и, следовательно, следующим ходом сможет окружить эту группу и взять камни в плен, если не будут предприняты меры).
Глазом группы будем называть свободный пункт доски, окруженный сверху, снизу, справа и слева камнями этой группы или ограниченный краем доски. (Понятие глаза важно, поскольку группа с двумя глазами не может быть окружена.)
Задачи 1a и 1b. Разминка
Первые две задачки на визуализацию доски были практически «однострочниками», к тому же нечто похожее встречалось и во втором туре (задача про змейку). За них можно было получить по два балла.
Условие задачи 1a
Игровое поле можно представить таблицей goban (для определенности будем считать, что начало координат находится в левом верхнем углу доски).
Более наглядным (но менее удобным для запросов) представлением может служить таблица из 19-и пронумерованных строк с текстовым столбцом, содержащим 19 символов B, W или . (пустой пункт):
CREATE TABLE visual(
y integer PRIMARY KEY CHECK (y BETWEEN 0 AND 18),
col text NOT NULL CHECK (length(col) = 19 AND
translate(col,'BW.','') = '')
);Напишите запрос, выводящий игровое поле из таблицы visual в формате таблицы goban.
Пример
Для следующих входных данных:
INSERT INTO visual(y,col) VALUES
(0, '...................'),
(1, '...................'),
(2, '..B..B.............'),
(3, '.W.B...............'),
(4, '...................'),
(5, '..W................'),
(6, '...................'),
(7, '...................'),
(8, '...................'),
(9, '...................'),
(10, '...................'),
(11, '...................'),
(12, '...................'),
(13, '...................'),
(14, '...................'),
(15, '...................'),
(16, '...................'),
(17, '...................'),
(18, '...................');запрос должен вывести:
x | y | stone
---+---+-------
1 | 3 | W
2 | 2 | B
2 | 5 | W
3 | 3 | B
5 | 2 | B
(5 rows)Условие задачи 1b
Напишите запрос, выводящий доску из таблицы goban в формате таблицы visual (см. задачу 1a).
Пример
Для следующих входных данных:
INSERT INTO goban(x,y,stone) VALUES
(1,3,'W'), (2,2,'B'), (2,5,'W'),
(3,3,'B'), (5,2,'B');запрос должен вывести:
y | col
----+---------------------
0 | ...................
1 | ...................
2 | ..B..B.............
3 | .W.B...............
4 | ...................
5 | ..W................
6 | ...................
7 | ...................
8 | ...................
9 | ...................
10 | ...................
11 | ...................
12 | ...................
13 | ...................
14 | ...................
15 | ...................
16 | ...................
17 | ...................
18 | ...................
(19 rows)Решение
Эти разминочные задачи должны были ввести участников в рабочую колею и заодно подвести к идее о том, что визуализация может помочь с решением и проверкой. Первое решение позволяет быстро создавать наглядные тестовые примеры, а второе — визуально контролировать результаты.
К моему удивлению, с ними у участников возникли какие-то сложности: на каждую ушло в среднем по полчаса. Долго сомневался, стоит ли приводить решения, но пусть будут.
Задача 1a:
SELECT x, y, substr(col,x+1,1) stone
FROM visual v, generate_series(0,18) x
WHERE substr(col,x+1,1) != '.';Задача 1b:
SELECT y.y, string_agg( coalesce(g.stone,'.'),'' ORDER BY x.x ) col
FROM generate_series(0,18) x(x)
CROSS JOIN generate_series(0,18) y(y)
LEFT JOIN goban g ON g.x = x.x AND g.y = y.y
GROUP BY y.y;Кстати, пасхалочка: один из тестов во всех задачах проверял работу алгоритма на пустом поле. То есть один балл за каждую задачу можно было получить практически на халяву, чем пара участников и воспользовались.
Задача 2. Группы
В этой задаче, за которую можно было получить 12 баллов, требовалось найти на доске все группы камней. Напомню, что группой считаются камни одного цвета, соприкасающиеся по вертикалям или горизонталям.
Условие
Напишите запрос, выводящий цвет и количество камней каждой из имеющихся на доске групп. Запрос должен вывести два столбца:
color— цвет группы (BилиW);size— количество камней в группе.
Пример
Для следующих входных данных:
INSERT INTO goban(x,y,stone) VALUES
(1,1,'B'), (2,1,'B'), (1,2,'B'), (3,2,'B'), (2,2,'W');запрос должен вывести:
color | size
-------+------
W | 1
B | 1
B | 3
(3 rows)Решение
Это задача оказалась самой сложной, как, в общем-то, и предполагалось. Многие потеряли на ней слишком много времени, а двигаться дальше, не имея хоть какого-то решения, было невозможно. Но что делать, олимпиада есть олимпиада.
Схема решения видится мне так. Нам надо найти все группы, а они могут иметь произвольную конфигурацию, стало быть необходим итерационный процесс (то есть рекурсивный запрос): начинаем с «зародышей» групп, состоящих из единичных камней, и постепенно расширяем их соседними камнями.
Группу было бы очень удобно представить в виде множества (поскольку порядок камней нам не важен, и дубликатов камней в группе быть не может), однако встроенного типа для множества в Постгресе нет (но может появиться). Поэтому придется использовать массив, для него по крайней мере имеется полезная операция пересечения &&.
Основа запроса может быть такой (для упрощения я игнорирую цвет камней — его несложно добавить потом):
WITH RECURSIVE a(grp) AS (
-- начинаем с одиночных камней
SELECT array[(x,y)] FROM goban
UNION ALL
-- добавляем камень, если он примыкает к группе
SELECT array[(x,y)] || a.grp AS grp
FROM a
CROSS JOIN ( VALUES (1,0),(0,1),(-1,0),(0,-1) ) delta(dx,dy)
JOIN goban ON array[(x+dx,y+dy)] && a.grp AND NOT array[(x,y)] && a.grp
)
SELECT * FROM a;Элементами массива у нас выступают значения составного типа. Можно писать ROW(x,y), но слово ROW необязательное, чем я и воспользовался.
Проверка примыкания устроена здесь так: мы сдвигаем гобан относительно группы на одну клетку по горизонтали и вертикали и находим пересекающиеся с группой сдвинутые камни. Такие камни мы добавляем к группе, если они в нее еще не входят.
В результате у нас получится целая куча массивов-групп. Возьмем для примера такое поле:
....
.BB.
.B..
....Запрос даст нам:
grp
---------------------------
{"(1,1)"}
{"(2,1)"}
{"(1,2)"}
{"(2,1)","(1,1)"}
{"(1,2)","(1,1)"}
{"(1,1)","(2,1)"}
{"(1,1)","(1,2)"}
{"(1,2)","(2,1)","(1,1)"}
{"(2,1)","(1,2)","(1,1)"}
{"(1,2)","(1,1)","(2,1)"}
{"(2,1)","(1,1)","(1,2)"}
(11 rows)Первые три строки — это начальные однокамневые зародыши групп. Вторая итерация представлена следующими четырьмя строками — потому что у камня (1,1) два соседа, а у камней (1,2) и (2,1) — по одному. Наконец, последние четыре строки представляют одну и ту же итоговую группу с разным порядком одних и тех же трех камней.
Дальше рекурсивный запрос не идет, поскольку на следующем шаге не находится ни одного камня, который можно было бы добавить к группе.
Кстати, если рекурсивные запросы вызывают благоговейный трепет, почитайте вот эту статью.
Теперь нам осталось избавиться от лишнего: из всех пересекающихся между собой строк мы должны оставить какую-нибудь одну, но максимального размера. Это можно сделать, например, так:
WITH RECURSIVE a(grp) AS (
-- начинаем с одиночных камней
SELECT array[(x,y)] FROM goban
UNION ALL
-- добавляем камень, если он примыкает к группе
SELECT array[(x,y)] || a.grp AS grp
FROM a
CROSS JOIN ( VALUES (1,0),(0,1),(-1,0),(0,-1) ) delta(dx,dy)
JOIN goban ON array[(x+dx,y+dy)] && a.grp AND NOT array[(x,y)] && a.grp
), b AS (
-- нумеруем все строки в порядке возрастания размера групп
SELECT a.grp, row_number() OVER (ORDER BY cardinality(a.grp)) r
FROM a
)
SELECT grp FROM b
WHERE NOT EXISTS (
SELECT NULL FROM b AS bb
WHERE b.grp && bb.grp AND b.r < bb.r
);Проблема этого простого решения в том, что оно о-о-очень медленное и неэффективное. Представьте, что вся доска заставлена камнями. На первом шаге мы получим 361 строку, на втором — 1368, на третьем... нет, даже думать об этом не хочется.
Чтобы исправить ситуацию, во-первых будем добавлять к группе не по одному камню за итерацию, а все соседние камни сразу. Это позволит ускорить рост групп и, соответственно, уменьшить число необходимых шагов. Для этого вместо конкатенации камня с имеющейся группой, соберем новую группу заново с помощью агрегатной функции array_agg. Новая группа должна быть образована всеми камнями, которые без сдвига или со сдвигом на одну клетку пересекаются с исходной группой.
Меняется только рекурсивный запрос:
WITH RECURSIVE a(grp) AS (
SELECT array[(x,y)] FROM goban
UNION ALL
(
WITH s AS (
-- собираем камни, составляющие новую группу
SELECT DISTINCT a.grp, x, y
FROM a
CROSS JOIN ( VALUES (0,0),(1,0),(0,1),(-1,0),(0,-1) ) delta(dx,dy)
JOIN goban ON array[(x+dx,y+dy)] && a.grp
), t AS (
-- группируем камни в массив
SELECT grp AS old_grp, array_agg( (x,y) ) AS grp
FROM s
GROUP BY grp
)
SELECT grp FROM t
WHERE grp != old_grp -- останавливаем рекурсию
)
)
...Здесь приходится останавливать рекурсию, сравнивая старую и новую группы, поскольку иначе каждый раз будет формироваться дубликат группы.
Во-вторых, мы можем устранять лишние группы на каждом шагу рекурсивного алгоритма ровно так же, как делаем это в конце запроса. Это позволит существенно уменьшить количество групп, передаваемых на следующий шаг.
На примере, который я приводил выше, запрос с такими усовершенствованиями будет получать результат всего за одну итерацию:
grp
---------------------------
{"(1,1)"}
{"(2,1)"}
{"(1,2)"}
{"(1,1)","(1,2)","(2,1)"}
(4 rows)Итоговый запрос будет примерно таким:
WITH RECURSIVE a(grp) AS (
SELECT array[(x,y)] FROM goban
UNION ALL
(
WITH s AS (
-- собираем камни, составляющие новую группу
SELECT DISTINCT a.grp, x, y
FROM a
CROSS JOIN ( VALUES (0,0),(1,0),(0,1),(-1,0),(0,-1) ) delta(dx,dy)
JOIN goban ON array[(x+dx,y+dy)] && a.grp
), t AS (
-- группируем камни в массив
SELECT grp AS old_grp, array_agg( (x,y) ) AS grp
FROM s
GROUP BY grp
), u AS (
-- нумеруем все строки в порядке возрастания размера групп
SELECT grp, row_number() OVER (ORDER BY cardinality(grp)) r
FROM t
WHERE grp != old_grp -- останавливаем рекурсию
)
-- устраняем лишнее
SELECT grp
FROM u
WHERE NOT EXISTS (
SELECT NULL FROM u AS uu
WHERE u.grp && uu.grp AND u.r < uu.r
)
)
), b AS (
-- нумеруем все строки в порядке возрастания размера групп
SELECT a.grp, row_number() OVER (ORDER BY cardinality(a.grp)) r
FROM a
), c AS (
-- устраняем лишнее
SELECT grp FROM b
WHERE NOT EXISTS (
SELECT NULL FROM b AS bb
WHERE b.grp && bb.grp AND b.r < bb.r
)
SELECT * FROM c;Конечно, это не единственный способ решить задачу. Только трое финалистов смогли прийти к решениям, которые прошли все тесты (что в конечном итоге и определило судьбу призовых мест), но в состоянии стресса они проявили изрядную изобретательность.
Задача 3. Дыхания
Следующая задача предлагала определить дыхания групп. Напомню, что дыханиями (или свободами) называются свободные пункты доски сверху, снизу, справа и слева от камней группы.
Условие
Напишите запрос, выводящий для каждой группы камней ее цвет, количество камней и количество дыханий.
Запрос должен вывести три столбца:
color— цвет группы (BилиW);size— количество камней в группе;liberties— количество дыханий группы.
Пример
Для тех же входных данных, что и в задаче 2:
INSERT INTO goban(x,y,stone) VALUES
(1,1,'B'), (2,1,'B'), (1,2,'B'), (3,2,'B'), (2,2,'W');запрос должен вывести:
color | size | liberties
-------+------+-----------
B | 1 | 3
W | 1 | 1
B | 3 | 6
(3 rows)Решение
За эту задачу, как и за вторую, можно было получить 12 баллов. Хотя, имея на руках алгоритм нахождения групп, добавить поиск дыханий уже не так трудно. В рекурсивном запросе второй задачи мы научились расширять группу на ее соседей, применяя сдвиг доски на одну клетку. Ровно тот же прием можно использовать и здесь, но проделать это нужно только один раз и для пустых пунктов доски вместо камней.
Вот соответствующий код:
WITH RECURSIVE a(stone, grp) AS (
...
), b AS (
...
), c AS (
...
), antigoban AS (
-- свободные пункты доски
SELECT x, y FROM generate_series(0,18) x, generate_series(0,18) y
EXCEPT
SELECT x, y FROM goban
), lib AS (
-- дыхания каждой группы
SELECT DISTINCT grp, x, y
FROM c
CROSS JOIN ( VALUES (1,0),(0,1),(-1,0),(0,-1) ) delta(dx,dy)
JOIN antigoban ON array[(x+dx,y+dy)] && grp
)
SELECT
c.grp,
count(lib.grp) liberties -- учитываем, что у группы может не оказаться дыханий
FROM c
LEFT JOIN lib on c.grp = lib.grp
GROUP BY c.grp;Кстати, для творческих экспериментов может пригодиться возможность развернуть группу, представленную массивом, до координат входящих в нее камней. В случае массива значений составного типа это можно сделать, взяв все камни гобана, пересекающиеся с группой. А если в массив вместо составного типа складывать JSON-ы, то развернуть группу можно непосредственно:
SELECT (grp->>'f1')::integer x, (grp->>'f2')::integer y
FROM (
SELECT unnest(grp) grp
FROM (
SELECT ARRAY[ to_jsonb((1,1)), to_jsonb((2,2)), to_jsonb((3,3)) ] grp
) b
) a;Задача 3a. Дыхания — визуализация
Условие
Напишите запрос, выводящий решение задачи 3 в виде таблицы из 19-и пронумерованных строк с текстовым столбцом, содержащим 19 символов.
Камни одной группы должны отображаться одинаковыми заглавными буквами английского алфавита. Буквы присваиваются группам в алфавитном порядке по убыванию идентификатора, который вычисляется как
Для этой задачи можно считать, что количество групп камней на доске не превышает количество букв алфавита.
Дыхания группы обозначатся соответствующими строчными буквами. Дыхания, общие для нескольких групп, обозначаются символом *.
Пример
Для тех же входных данных, что и в задаче 3:
INSERT INTO goban(x,y,stone) VALUES
(1,1,'B'), (2,1,'B'), (1,2,'B'),
(3,2,'B'), (2,2,'W');запрос должен вывести:
(0, '.aa................'),
(1, 'aAA*...............'),
(2, 'aABCc..............'),
(3, '.abc...............'),
(4, '...................'),
(5, '...................'),
(6, '...................'),
(7, '...................'),
(8, '...................'),
(9, '...................'),
(10, '...................'),
(11, '...................'),
(12, '...................'),
(13, '...................'),
(14, '...................'),
(15, '...................'),
(16, '...................'),
(17, '...................'),
(18, '...................');
(19 rows)Решение
Несмотря на длинное условие, все, что нужно сделать в этой задаче, — наглядно отобразить уже готовое решение третьей задачи. Это снова намек на то, что визуализация может помочь с отладкой. «Страшная» формула понадобилась лишь для того, чтобы как-то упорядочить группы.
За правильное решение давалось 8 баллов: меньше, чем за «основные» задачи, но достаточно весомо, поскольку здесь требуется не совсем тривиальная модернизация алгоритма, к тому же надо определить общие для нескольких групп дыхания.
Здесь и далее я не буду приводить готовых решений, а ограничусь только намеками. Попробуйте сами.
Задача 4. Глаза
В следующей «полновесной» задаче на 12 баллов требовалось посчитать глаза группы, то есть свободные пункты доски, окруженные сверху, снизу, справа и слева камнями этой группы или ограниченные краем доски.
Условие
Напишите запрос, выводящий для каждой группы камней ее цвет, количество камней и количество глаз.
Запрос должен вывести три столбца:
color— цвет группы (BилиW);size— количество камней в группе;eyes— количество глаз группы.
Пример
Для входных данных:
INSERT INTO goban(x,y,stone) VALUES
(0,3,'W'),
(0,1,'B'), (1,0,'B'), (1,1,'B'), (1,2,'B'),
(2,0,'B'), (2,2,'B'), (3,0,'B'), (3,1,'B');запрос должен вывести:
color | size | eyes
-------+------+------
B | 8 | 2
W | 1 | 0
(2 rows)Решение
Поскольку глаз — это дыхание, решение может базироваться на третьей задаче. Для каждого дыхания группы нам надо понять, является ли оно глазом, то есть проверить всех соседей. А для этого снова можно применить прием со сдвигом доски на одну клетку. Нужно, конечно, учесть и края доски, но для тех, кто сюда добрался, это уже не должно представлять сложностей.
Задача 5. Атари
Последняя задача за 12 баллов предлагала определить позицию «атари», возникающую, когда соперник своим ходом уменьшает группе камней количество дыханий до одного.
Условие
Напишите запрос, выводящий такие ходы черных и белых, которые создают позицию «атари» сразу для двух или более групп камней соперника. Для этой задачи разрешается ход на любой незанятый пункт доски и можно считать, что начальная позиция не является «атари».
Запрос должен вывести три столбца:
x— позиция камня по горизонтали (от 0 до 18);y— позиция камня по вертикали (от 0 до 18);stone— цвет камня (BилиW).
Начало координат находится в левом верхнем углу доски.
Пример
Для входных данных:
INSERT INTO goban(x,y,stone) VALUES
(1,1,'B'), (1,2,'W'), (2,2,'B'), (2,3,'W'), (3,3,'B');запрос должен вывести:
x | y | stone
---+---+-------
1 | 3 | B
(1 row)Решение
Создать позицию «атари» можно только для группы с двумя дыханиями, забрав одно из них. Поэтому достаточно взять дыхания (задача 3) именно таких групп, причем дыхания должны разделяться несколькими группами («звездочка» из задачи 3a). Эти пункты и будут подходящими ходами соперника.
Итоги
За отведенное время все задачи успела решить только Дарья Рябова из Москвы, она и стала победителем финала олимпиады.
Совсем немного не хватило Яну Сенину из Минска: он не успел добить задачу 3а про визуализацию, успешно справившись со всеми остальными.
На третьем месте оказался Олег Крюков из Тулы, получивший 9 баллов за четвертую задачу и не успевший решить пятую.
Следом шли Вадим Смирнов из Шуи, Ольга Филатова и Адам Раши из Санкт-Петербурга и Ярослав Дель из Челябинска, которые смогли построить корректный алгоритм поиска групп, но недостаточно его оптимизировали. Из-за таймаутов они получили за вторую задачу только 8 баллов и не смогли конкурировать за призовые места.
Победителей от души поздравляю, а остальным участникам желаю не расстраиваться (вы молодцы!) и вновь попробовать свои силы на следующей олимпиаде. Мне хотелось показать, что SQL не такой уж скучный язык, и решение задач на нем может стать интересным приключением. Надеюсь, вы получили удовольствие, а я обещаю подумать над новыми задачами.
