Comments 10
Ну навскидку, без оптимизации, где-то так:
WITH RECURSIVE
-- нумеруем точки
cte1 (x,y,stone,stone_number) AS (
SELECT x,y,stone, ROW_NUMBER() OVER () stone_number
FROM goban
)
, cte2 (x,y,stone,stone_number) AS (
-- берём начальное состояние
SELECT x,y,stone,stone_number FROM cte1
UNION
-- если номер соседа меньше - берём его
SELECT cte1.x, cte1.y, cte1.stone, cte2.stone_number
FROM cte1
-- проверяем совпадение цвета
JOIN cte2 ON (cte1.stone = cte2.stone)
-- проверяем, что это сосед
AND ( ((cte1.x=cte2.x) AND (cte1.y-cte2.y) IN (-1, 1))
OR
((cte1.y=cte2.y) AND (cte1.x-cte2.x) IN (-1, 1))
)
-- проверяем, что номер соседа меньше
AND cte1.stone_number > cte2.stone_number
)
-- берём самый меньший номер
SELECT x,y,stone,MIN(stone_number) group_number
FROM cte2
GROUP BY 1,2,3
ORDER BY 4,1,2Полигон для тестов: https://dbfiddle.uk/Ha1E_BIx
Что-то деление на группы уж больно сложное... неужели никто не додумался до простейшего алгоритма минимизации номера группы?
Для начала нумеруем камни в произвольном порядке. Затем для каждого камня рекурсивно вместо его номера берём номер его одноцветного соседа, если тот меньше. Финально для каждого камня берём минимальный из номеров за всю историю рекурсии. Как итог - все камни поделятся на группы, номер группы будет равен минимальному номеру камня в группе.
На словах-то выглядит красиво, а вы покажите работающий код.
Ну навскидку, без оптимизации, где-то так:
WITH RECURSIVE
-- нумеруем точки
cte1 (x,y,stone,stone_number) AS (
SELECT x,y,stone, ROW_NUMBER() OVER () stone_number
FROM goban
)
, cte2 (x,y,stone,stone_number) AS (
-- берём начальное состояние
SELECT x,y,stone,stone_number FROM cte1
UNION
-- если номер соседа меньше - берём его
SELECT cte1.x, cte1.y, cte1.stone, cte2.stone_number
FROM cte1
-- проверяем совпадение цвета
JOIN cte2 ON (cte1.stone = cte2.stone)
-- проверяем, что это сосед
AND ( ((cte1.x=cte2.x) AND (cte1.y-cte2.y) IN (-1, 1))
OR
((cte1.y=cte2.y) AND (cte1.x-cte2.x) IN (-1, 1))
)
-- проверяем, что номер соседа меньше
AND cte1.stone_number > cte2.stone_number
)
-- берём самый меньший номер
SELECT x,y,stone,MIN(stone_number) group_number
FROM cte2
GROUP BY 1,2,3
ORDER BY 4,1,2Полигон для тестов: https://dbfiddle.uk/Ha1E_BIx
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)
);
Если мы создадим такую доску, мы не сможем обозначить незанятую клетку? Ведь камень не может быть NULL , а варианта “пусто” не предусмотрено?
Все правильно, мы храним в таблице только камни, а не пустые пункты. Посмотрите примеры дальше.
Тогда, чтобы понять, где у нас пустые клетки, мы каждый раз должны проверять, не занята ли эта клетка? И алгоритм определения пустой клетки будет отличаться от алгоритма определения занятой? По-моему, это вносит уровень усложнения - да, пусть и путём экономии места на диске...
В данном случае речь же не идет о том, какое представление более удобное или более эффективное. Просто у участников было такое условие задачи. Если формат данных кажется неудобным, вы можете легко добавить недостающие пункты и работать дальше уже с таким представлением.
А в реальных задачах решение о том, хранить или не хранить «пустышки» зависит от того, насколько разрежены данные, и от того, как вы собираетесь с ними работать.
Вангую, эти олимпиадники потом не захотят что-то скучное типа максимальной просрочки за период считать.
Задачи третьего этапа олимпиады «IT-Планеты» по PostgreSQL