Если входная строка конкретно такая, то она невалидна согласно условию 4-й задачи - пробелы после двух последних запятых. Поэтому "ничего" - как раз корректный ответ, по условию.
А если их (пробелы) убрать, то запрос выдаст DC43.
WITH gameparty AS (
SELECT
*
, parts[1] code
, regexp_split_to_array(parts[1], '') chars
, parts[2]::integer b
, parts[3]::integer c
FROM
regexp_split_to_table(upper(current_setting('bulls.gameparty')), ',')
WITH ORDINALITY T(step, n)
, regexp_match(step, '^([0-9A-F]{4}) (\d)B(\d)C$') parts -- заодно и формат проверяем
)
SELECT
xcode code
FROM
generate_series(0xFFFF, 0, -1) i -- нужен максимальный код, так что сразу генерим реверсивно (до первого подходящего, благодаря LIMIT)
, lpad(upper(to_hex(i)), 4, '0') xcode
, regexp_split_to_array(xcode, '') secret
, LATERAL (
SELECT
bool_and((b, c) = (xb, xc - xb)) chk -- совпадение быков/коров во всех ходах
FROM
gameparty
, LATERAL (
SELECT
count(*) FILTER(WHERE x = y) xb
FROM
unnest(chars, secret) T(x, y)
) b
, LATERAL (
SELECT
count(*) FILTER(WHERE x = ANY(secret)) xc
FROM
unnest(chars) T(x)
) c
) T
WHERE
NOT EXISTS ( -- при корректности кодов в исходнике
SELECT
NULL
FROM
gameparty
WHERE
code IS NULL OR
code ~ '(.).*\1'
LIMIT 1
) AND
xcode !~ '(.).*\1' AND -- отсекаем коды с повторными символами
chk -- оставляем только удовлетворившие всем ходам
LIMIT 1;
По 4-й задаче предложу решение чуть на иных механизмах:
-- проверяем ходы и секрет вместе
WITH chk AS (
SELECT
*
, regexp_split_to_array(code, '') chars
, NOT(code !~ '(.).*\1' AND code ~ '^[0-9A-F]{4}$') is_error
FROM
regexp_split_to_table(upper(current_setting('bulls.secretcode') || ',' || current_setting('bulls.game')), ',')
WITH ORDINALITY step(code, n)
)
-- PG выберет за нас подзапрос в зависимости от корректности данных
(
SELECT
'error' gameparty
FROM
chk
GROUP BY
1
HAVING
bool_or(is_error) -- хоть где-то есть ошибка
UNION ALL
SELECT
string_agg(code || ' ' || b || 'B' || (c - b) || 'C', ',' ORDER BY n)
FROM
chk
, (
SELECT
chars secret
FROM
chk
WHERE
n = 1
)
, LATERAL (
SELECT
count(*) FILTER(WHERE x = y) b -- только "быки" на своих местах
FROM
unnest(chars, secret) T(x, y)
) b
, LATERAL (
SELECT
count(*) FILTER(WHERE x = ANY(secret)) c -- "коровы" вместе с "быками"
FROM
unnest(chars) T(x)
) c
WHERE
n > 1
)
LIMIT 1;
Мне кажется, что эта задача банальным подсчетом точек изменений решается изящнее и эффективнее, чем через json, рекурсию или интервалы:
WITH src(parameter_name, ts, value) AS (
VALUES ('max_connections', '2025-01-10 11:30'::timestamp, '500'),
('max_connections', '2025-01-11 12:30', NULL),
('max_connections', '2025-01-11 15:30', '500'),
('max_connections', '2025-01-12 12:30', NULL),
('max_connections', '2025-01-12 15:30', '500'),
('work_mem', '2025-01-10 11:30', '8MB'),
('work_mem', '2025-01-12 14:00', '16MB'),
('max_connections', '2025-01-12 14:00', '1000'),
('max_connections', '2025-01-17 12:30', NULL),
('shared_buffers', '2025-01-12 12:30', NULL),
('shared_buffers', '2025-01-12 13:30', '20000'),
('shared_buffers', '2025-01-14 10:00', NULL),
('shared_buffers', '2025-01-15 07:40', NULL),
('temp_buffers', '2025-01-09 10:20', '2000'),
('temp_buffers', '2025-01-11 11:30', null),
('temp_buffers', '2025-01-12 12:30', '1500'),
('temp_buffers', '2025-01-14 03:15', null),
('maintenance_work_mem', '2025-01-09 10:20','1000'),
('maintenance_work_mem', '2025-01-10 13:26', null),
('maintenance_work_mem', '2025-01-12 12:30', null),
('maintenance_work_mem', '2025-01-12 14:30', '1500'),
('maintenance_work_mem', '2025-01-15 14:30', null),
('max_worker_processes', '2025-01-08 00:30', '16'),
('max_worker_processes', '2025-01-12 14:00', null)
)
-- определяем "в точке", как должно измениться кол-во "недефолтных" параметров
, diff AS (
SELECT
*
, CASE
WHEN value IS NOT NULL AND lag(value) OVER(PARTITION BY parameter_name ORDER BY ts) IS NULL THEN +1
WHEN value IS NULL AND lag(value) OVER(PARTITION BY parameter_name ORDER BY ts) IS NOT NULL THEN -1
ELSE 0
END diff
FROM
src
)
-- находим суммарное количество "недефолтных" в каждой точке
, sum AS (
SELECT
*
, sum(diff) OVER(ORDER BY ts) parameters
FROM
diff
)
-- помечаем точки, изменяющие суммарное значение
, rngs AS (
SELECT
*
, parameters IS DISTINCT FROM lag(parameters) OVER(ORDER BY ts) is_rng_start
FROM
sum
)
-- находим следующую точку изменения суммарного значения - это конец интервала
, rnge AS (
SELECT
*
, lead(ts) OVER(ORDER BY ts) ts_end
FROM
rngs
WHERE
is_rng_start
)
-- отбираем максимум с учетом возможного дублирования
SELECT
ts ts_start
, ts_end
, parameters
FROM
rnge
ORDER BY
parameters DESC
FETCH NEXT 1 ROWS
WITH TIES;
Можно чуть ускорить вычисления пересечений массивов:
, crossing_lans AS (
SELECT
ARRAY(
SELECT
unnest(T1.links)
INTERSECT ALL
SELECT
unnest(T2.links)
ORDER BY
1
) nodes
FROM
full_links T1
JOIN
full_links T2
ON T2.nodefrom > T1.nodefrom
)
А вот подход с "арифметикой" и треугольными числами - это красиво, согласен, хотя и требует несколько более подробного объяснения, почему это так.
Я поэтому и написал: "... мы не применяли вообще никаких упрощений и оптимизаций (типа предварительного формирования только пар содержащих имена "на t"), решая задачу "в лоб" самым простым и очевидным способом, то полный "кубический" перебор (два соединения) ..."
Так-то можно уложиться в 60мс, если анализировать только t-наборы:
explain (analyze, costs off)
WITH src AS (
SELECT
regexp_matches(
$$
kh-tc
qp-kh
de-cg
ka-co
yn-aq
qp-ub
cg-tb
vc-aq
tb-ka
wh-tc
yn-cg
kh-ub
ta-co
de-co
tc-td
tb-wq
wh-td
ta-ka
td-qp
aq-cg
wq-ub
ub-vc
de-ta
wq-aq
wq-vc
wh-yn
ka-de
kh-ta
co-tc
wh-qp
tb-vc
td-yn
$$
, '([a-z]{2})-([a-z]{2})'
, 'g'
) pair
)
, tname AS ( -- собираем, с кем связаны 't?'
SELECT
pair[1] src
, array_agg(pair[2]) dst
FROM
(
SELECT
*
FROM
src
WHERE
pair[1] ^@ 't'
UNION ALL
SELECT
ARRAY[pair[2], pair[1]]
FROM
src
WHERE
pair[2] ^@ 't'
) T
GROUP BY
1
)
SELECT
count(*) -- все записи
- count(*) FILTER(
WHERE
(pair[1] ^@ 't' AND NOT pair[2] ^@ 't') OR
(NOT pair[1] ^@ 't' AND pair[2] ^@ 't')
) / 2 -- исключаем посчитанные дважды ta|{tb,x} и tb|{ta,x}
- count(*) FILTER(
WHERE
(pair[1] ^@ 't' AND pair[2] ^@ 't')
) / 3 * 2 -- исключаем посчитанные трижды ta|{tb,tc}, tb|{ta,tc} и tc|{ta,tb}
FROM
tname
, src
WHERE
pair <@ dst; -- оба элемента исходной пары связаны с одним и тем же 't?'
Не факт, что оно будет как-то существенно быстрее - это же на каждом шаге рекурсии к каждому массиву надо приписывать значение в конец и отбрасывать первое, если я понял идею правильно.
Контрпример к данному поинту можно легко нарисовать на карте размером 6х520
Очевидно, что можно, и это определенное допущение - только в реальном кейсе AoC дана карта 141x141, для которой мы такое можем себе позволить.
должно отработать за O(n * ln(n))
Тут проблема возникает ровно в хранении на каждом шаге минимального достигающего каждой клетки пути. То есть способов решения у этой задачи множество, но самый первый и наивный приведенный в статье - уже не отрабатывает за разумное время.
Система меняется, нагрузочные тесты не успевают. Многопоточная, высоконагруженная система. Что в этих условиях мерять?
Вроде ответ скрыт в вопросе - анализировать надо саму целевую систему, а не производные от нее.
Выше я приводил ссылку на демо нашей системы анализа нагрузки в PG - можно легко понять, кто из запросов "ест диск", как часто каждый стартует, heatmap времени выполнения, ...
Если под задачей понимается "мы провели какие-то тесты в одном месте, предскажите, какая будет нагрузка в других условиях в другом месте", то вряд ли кто-то ее сможет решить, кроме крайне малого количества крайних случаев.
Если входная строка конкретно такая, то она невалидна согласно условию 4-й задачи - пробелы после двух последних запятых. Поэтому "ничего" - как раз корректный ответ, по условию.
А если их (пробелы) убрать, то запрос выдаст
DC43.5-я задача на основе предыдущего варианта:
По 4-й задаче предложу решение чуть на иных механизмах:
Просто добавим
WHERE parameters > 1в последний запрос. ))К модели решения это не имеет существенного отношения.
Мне кажется, что эта задача банальным подсчетом точек изменений решается изящнее и эффективнее, чем через json, рекурсию или интервалы:
Вот тут описан этот и несколько других типовых алгоритмов над интервалами "с картинками".
У меня что с пробелами, что без - одно и тоже время с разбежкой в пределах погрешности.
Возможно, от версии PG или даже ОС зависит - у меня даже просто получение строки
'{"i" : ' || i || '}'без каста занимает примерно 570ms из 800ms.Все равно чуть хуже
row_to_jsonполучается (796ms vs 792ms), но много больше вариантов накосячить с экранированием становится.Забавный эффект... Но если избавиться от промежуточной группировки и пересечение массива искать внутри соединения:
... то удается выйти на 183мс:
Можно чуть ускорить вычисления пересечений массивов:
А вот подход с "арифметикой" и треугольными числами - это красиво, согласен, хотя и требует несколько более подробного объяснения, почему это так.
"Нет предела совершенству". ))
Я поэтому и написал: "... мы не применяли вообще никаких упрощений и оптимизаций (типа предварительного формирования только пар содержащих имена "на t"), решая задачу "в лоб" самым простым и очевидным способом, то полный "кубический" перебор (два соединения) ..."
Так-то можно уложиться в 60мс, если анализировать только t-наборы:
Согласен, так можно, только
last_changesполучается "развернутым" относительно условия. Но вроде на ответ это повлиять не должно.Если взглянуть на этот кусок плана, то на блоке с парой
WindowAggтак можно сэкономить:Дальше лишь вопрос в длине массива-последовательности - при больших размерах операции над массивами становятся очень уж небыстрыми.
Не факт, что оно будет как-то существенно быстрее - это же на каждом шаге рекурсии к каждому массиву надо приписывать значение в конец и отбрасывать первое, если я понял идею правильно.
Иногда - лучше, иногда - нет. Все зависит и от объема передаваемых туда-сюда данных, и от сложности/удобства реализации алгоритма на конкретном ЯП.
Снятие состояния блокировок в момент ее возникновения в логе:
https://habr.com/ru/companies/tensor/articles/503680/
33 секунды - это для той самой "реальной" карты со стороной 141 - в контексте у плана есть полный запрос.
Очевидно, что можно, и это определенное допущение - только в реальном кейсе AoC дана карта 141x141, для которой мы такое можем себе позволить.
Тут проблема возникает ровно в хранении на каждом шаге минимального достигающего каждой клетки пути. То есть способов решения у этой задачи множество, но самый первый и наивный приведенный в статье - уже не отрабатывает за разумное время.
Вроде ответ скрыт в вопросе - анализировать надо саму целевую систему, а не производные от нее.
Выше я приводил ссылку на демо нашей системы анализа нагрузки в PG - можно легко понять, кто из запросов "ест диск", как часто каждый стартует, heatmap времени выполнения, ...
Если под задачей понимается "мы провели какие-то тесты в одном месте, предскажите, какая будет нагрузка в других условиях в другом месте", то вряд ли кто-то ее сможет решить, кроме крайне малого количества крайних случаев.