Comments 8
Это нужно в хаб "ненормальное программирование"! :)
Не стал вчитываться в решение, но заценил размах замысла. Красотища.
Оставлю тут решение по первой части, чуть быстрее решения Маэстро)
WITH
tbl AS
(
SELECT
a::int,
i
FROM
regexp_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() n
FROM
tbl,
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 d
FROM
encoded e
)
SELECT
--если требуется перестановка, подставляем значения цифры в соответвствующей позиции
sum
((CASE
WHEN s.p IS NOT NULL THEN s.d
ELSE u.a::int
END) * (n - 1))
FROM
encoded AS u
LEFT 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 le
WHERE
--точки в конце нас не интересуют
n <= le.c - lp.c
В первом приближении, оно считает неправильно - выдает 2003 на тестовой последовательности вместо 1928 согласно постановке.
Странно, может буквы убежали при редактировании. У меня результаты 1928 и 6241633730082.
По времени:
Execution Time: 283.704 ms
Execution Time: 467.829 ms
Если развить предложенный подход и избавиться от лишних операций со строками, то можно сделать вот так:
WITH map AS (
SELECT
row_number() OVER() pos
, CASE
WHEN n % 2 = 1 THEN n / 2
END fid
FROM
regexp_split_to_table(
'2333133121414131402'
, ''
)
WITH ORDINALITY T(sz, n)
, generate_series(1, sz::integer)
)
, remap AS (
SELECT
u.*
, lim
FROM
(
SELECT
array_agg(pos ORDER BY pos) FILTER(WHERE fid IS NULL) free
, array_agg(fid ORDER BY pos DESC) FILTER(WHERE fid IS NOT NULL) file
FROM
map
) T
, array_length(file, 1) lim
, unnest(free, file) u(pos, fid)
)
SELECT
sum((pos - 1) * coalesce(map.fid, remap.fid))
FROM
map
LEFT JOIN
remap
USING(pos)
WHERE
map.pos <= (SELECT lim FROM remap LIMIT 1);Получается вот такой план - 182ms вместо 326ms, то есть примерно в 2 раза быстрее чем в статье:
Если совсем предельно экономить, можно выжать еще пару процентов:
WITH map AS (
SELECT
row_number() OVER(ORDER BY n) pos
, CASE
WHEN n % 2 = 1 THEN n / 2
END fid
FROM
regexp_split_to_table(
'2333133121414131402'
, ''
)
WITH ORDINALITY T(sz, n)
, generate_series(1, sz::integer)
)
, remap AS (
SELECT
array_agg(fid ORDER BY pos DESC) FILTER(WHERE fid IS NOT NULL) rpl
, count(*) FILTER(WHERE fid IS NOT NULL) lim
FROM
map
)
SELECT
sum((pos - 1) * coalesce(fid, rpl[rplpos]))
FROM
(
SELECT
map.*
, count(*) FILTER(WHERE fid IS NULL) OVER(ORDER BY pos) rplpos
FROM
map
WHERE
pos <= (SELECT lim FROM remap)
) T
, remap;
А если вот так поменять кусочек, то еще 10мс долой:
, remap AS (
SELECT
array_agg(fid ORDER BY pos DESC) rpl
, count(*) lim
FROM
map
WHERE
fid IS NOT NULL
)
SQL HowTo: оптимизируем рекурсию (Advent of Code 2024, Day 9: Disk Fragmenter)