В части 2 предложу такой вариант, у меня выполнился за 0.4 сек.
WITH src AS
(
SELECT
line[1] nodefrom,
line[2] nodeto
FROM
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
$$
,
'(\w+)\-(\w+)'
,'g'
) AS src(line)
)
,transform_src AS (
SELECT
nodefrom,nodeto
FROM
src
UNION ALL
SELECT
nodeto,nodefrom
FROM
src
)
,full_links AS
(
--полный набор узлов включая узел источник
SELECT
nodefrom,
nodefrom || array_agg(nodeto) AS links
FROM
transform_src
GROUP BY
nodefrom
)
,crossing_lans AS
(
--найти пересечения узлов в массивах и сформировать из них новый массив
SELECT
array_agg(l1 ORDER BY l1) AS nodes
FROM
full_links AS fl1
CROSS JOIN full_links AS fl2,
unnest(fl1.links) AS l1,
unnest(fl2.links) AS l2
WHERE
fl1.nodefrom > fl2.nodefrom
AND l1 = l2
GROUP BY
fl1.nodefrom || fl2.nodefrom
)
--TABLE crossing_lans;
SELECT
array_to_string(nodes,',')
FROM
crossing_lans
GROUP BY
nodes
HAVING
--Кол-во комбинаций узлов fl1.nodefrom и fl2.nodefrom = арифметметической прогрессии от длины массива
count(*) = array_length(nodes,1) * (array_length(nodes,1) - 1) / 2
ORDER BY
count(*) DESC
LIMIT 1;
WITH RECURSIVE r AS
(
WITH nums AS
(
SELECT
line[1]::int8 secret,
client
FROM
regexp_matches(
$$
1
2
3
2024
$$
, '[^\r\n]+(?=$|[\r\n])'
, 'g'
) WITH ORDINALITY nums(line,client)
)
SELECT
client,
secret,
null::int2[] AS last_changes,
0 AS cnt
FROM
nums
UNION ALL
SELECT
client,
secret3,
(secret3 % 10 - secret % 10)::int2 || last_changes[1:3],
cnt + 1
FROM
r,
LATERAL
(SELECT ((secret * 64) # secret) % 16777216) AS seq1(secret1),
LATERAL
(SELECT ((secret1 / 32) # secret1) % 16777216) AS seq2(secret2),
LATERAL
(SELECT ((secret2 * 2048) # secret2) % 16777216) AS seq3(secret3)
WHERE
cnt < 2000
)
SELECT
sum(price)
FROM
(
SELECT DISTINCT ON (client,last_changes)
client,
secret % 10 AS price,
last_changes
FROM
r
WHERE
cnt > 3
ORDER BY
client,
last_changes,
cnt,
price DESC
) AS q
GROUP BY
last_changes
ORDER BY
sum(price) DESC
LIMIT 1;
В части №2 решение выбрано для демонстрации возможностей оконок? Вроде как более очевидное и быстрое решение, это иметь массив с последними изменениями внутри рекурсии.
Круто! Спасибо, что причесали мой подход! И еще спасибо за челлендж! Один бы не полез в эти задачи.. Интересно самому решить, а после сравнить с другим вариантом.
Эх, любите Вы массивы.. Первая часть классическим способом у меня отработала за
Execution Time: 5.862 ms
Ваш вариант отработал за 160.879 ms
Спасибо за интересные варианты решений.
diff AS
(
SELECT
*,
y - LEAD(y) over(PARTITION BY rn) AS d
FROM
t
),
check_condition AS
(
SELECT
rn
FROM
diff
WHERE
d IS NOT NULL
GROUP BY
rn
HAVING
count(*) = ANY(array[(count(*) filter(WHERE d > 0)) , (count(*) filter(WHERE d < 0))])
AND
count(*) = abs(sum(sign(d)) FILTER(WHERE d BETWEEN 1 AND 3 OR d BETWEEN -3 AND -1))
)
SELECT
count(*)
FROM
check_condition
По crossing_lans, в этом случае порождается куча массив без пересечений и увеличивается время выполнения.
В части 2 предложу такой вариант, у меня выполнился за 0.4 сек.
В части 1, получилось меньше 0.1сек вместо 3.5сек в части 1(снова)
Получилось ~1.5 раза, 9сек вместо 13
Здравствуйте!
В части №2 решение выбрано для демонстрации возможностей оконок? Вроде как более очевидное и быстрое решение, это иметь массив с последними изменениями внутри рекурсии.
Круто! Спасибо, что причесали мой подход!
И еще спасибо за челлендж! Один бы не полез в эти задачи.. Интересно самому решить, а после сравнить с другим вариантом.
Странно, может буквы убежали при редактировании. У меня результаты 1928 и 6241633730082.
По времени:
Execution Time: 283.704 ms
Execution Time: 467.829 ms
Оставлю тут решение по первой части, чуть быстрее решения Маэстро)
WITHtbl AS(SELECTa::int,iFROMregexp_split_to_table('2333133121414131402','')WITH ORDINALITY T(a, i)),encoded AS (SELECT--разворачиваем, вычисляем значения и нумеруем(CASE WHEN i % 2 = 1 THEN ((i-1)/2)::TEXT ELSE '.' END) AS a,ROW_NUMBER() over() nFROMtbl,generate_series(1,a)),swaps AS(SELECT--координаты точекUNNEST(array_agg(n) FILTER (WHERE a = '.') ) AS p,--значения замены с координатами в обратном порядкеUNNEST(array_agg(a::int ORDER BY n DESC) FILTER (WHERE a != '.')) AS dFROMencoded e)SELECT--если требуется перестановка, подставляем значения цифры в соответвствующей позицииsum((CASEWHEN s.p IS NOT NULL THEN s.dELSE u.a::intEND) * (n - 1))FROMencoded AS uLEFT JOIN swaps AS s ON s.p = u.n,--кол-во перестановок(SELECT count(*) AS c FROM swaps WHERE p IS NOT NULL) AS lp,--общее кол-во элементов(SELECT count(*) AS c FROM encoded) AS leWHERE--точки в конце нас не интересуютn <= le.c - lp.cЭх, любите Вы массивы.. Первая часть классическим способом у меня отработала за
Execution Time: 5.862 ms
Ваш вариант отработал за 160.879 ms
Спасибо за интересные варианты решений.
По второй части размножение колонок через union all будет работать немного быстрее массивов. Агрегировать и сортировать (
array_agg) при этом не нужно.