## day 2
with origin as (
    SELECT row_number() over () as rn, line
    FROM lance_input
), splits AS (
    SELECT rn :: INTEGER, x.idx :: INTEGER as seq, x.num :: INTEGER
    FROM origin, regexp_split_to_table(line, ' ') with ordinality as x(num, idx)
    WHERE rn not in (select id from lance_test)
    AND x.idx :: INTEGER != 1
), splits_with_diff AS (
    SELECT rn, seq, num, lag(num) over(partition by rn order by seq) as pre_num
    FROM splits
)
insert into lance_test SELECT rn
FROM splits_with_diff
GROUP BY rn
HAVING (count(case when pre_num < num then 1 end) = count(1) - 1 
OR count(case when pre_num > num then 1 end) = count(1) - 1 )
AND min(abs(pre_num - num)) >= 1
AND max(abs(pre_num - num)) <= 3;




## day 3
with dont as (
    SELECT x.txt, idx = 1 as safe
    FROM lance_input, regexp_split_to_table(line, 'don''t\(\)') with ordinality as x(txt, idx)
), dos as (
    SELECT x.txt, case when dont.safe then true else x.idx != 1 end safe
    FROM dont, regexp_split_to_table(txt, 'do\(\)') with ordinality as x(txt, idx)
)
SELECT sum(num[1]::integer * num[2]::integer)
FROM (
    SELECT regexp_matches(mul[1], '(\d+),(\d+)') as num
    FROM (
        SELECT regexp_matches(txt, '(mul\(\d+,\d+\))', 'g') as mul
        FROM dos
        WHERE safe
    ) t
) s



## day 4
with origin as (
    SELECT row_number() over () as rn, line
    FROM lance_input
), splits AS (
    SELECT rn :: INTEGER as _row, x.idx :: INTEGER as _col, x.pos
    FROM origin, regexp_split_to_table(line, '') with ordinality as x(pos, idx)
), top_down as (
    SELECT string_agg(pos, '' order by _row) as line
    FROM splits
    GROUP by _col
), left_right as (
    SELECT string_agg(pos, '' order by _col) as line
    FROM splits
    GROUP by _row
), slash as (
    SELECT string_agg(pos, '' order by _row) as line
    FROM splits
    GROUP by _row + _col
), backslash as (
    SELECT string_agg(pos, '' order by _row) as line
    FROM splits
    GROUP by _row - _col
), allstr as (
    SELECT line from top_down
    union all
    SELECT line from left_right
    union all
    SELECT line from slash
    union all
    SELECT line from backslash
) 
SELECT regexp_matches(line, 'XMAS', 'g')
FROM allstr
UNION ALL
SELECT regexp_matches(reverse(line), 'XMAS', 'g')
FROM allstr


with origin as (
    SELECT row_number() over () as rn, line
    FROM lance_input
), splits AS (
    SELECT rn :: INTEGER as _row, x.idx :: INTEGER as _col, x.pos
    FROM origin, regexp_split_to_table(line, '') with ordinality as x(pos, idx)
), slash as (
    SELECT _row + _col as _group, string_agg(pos, '' order by _row) as line
    FROM splits
    GROUP by _row + _col
), backslash as (
    SELECT _row - _col as _group, string_agg(pos, '' order by _row) as line
    FROM splits
    GROUP by _row - _col
), slash_mas_pos as (
    SELECT _group, case when _group > 140 + 1 then _group - 140 - 1 + a_pos else a_pos end as a_row
    FROM (
        SELECT _group, length(line) as total, sum(length(pos) + 3) over (partition by _group order by idx) - 1 as a_pos
        FROM slash, regexp_split_to_table(line, 'MAS') with ordinality as x(pos, idx)
    ) t
    WHERE a_pos < total 
), slash_sam_pos as (
    SELECT _group, case when _group > 140 + 1 then _group - 140 - 1 + a_pos else a_pos end as a_row
    FROM (
        SELECT _group, length(line) as total, sum(length(pos) + 3) over (partition by _group order by idx) - 1 as a_pos
        FROM slash, regexp_split_to_table(line, 'SAM') with ordinality as x(pos, idx)
    ) t
    WHERE a_pos < total 
), backslash_mas_pos as (
    SELECT _group, case when _group > 0 then a_pos + _group else a_pos end as a_row
    FROM (
        SELECT _group, length(line) as total, sum(length(pos) + 3) over (partition by _group order by idx) - 1 as a_pos
        FROM backslash, regexp_split_to_table(line, 'MAS') with ordinality as x(pos, idx)
    ) t
    WHERE a_pos < total 
), backslash_sam_pos as (
    SELECT _group, case when _group > 0 then a_pos + _group else a_pos end as a_row
    FROM (
        SELECT _group, length(line) as total, sum(length(pos) + 3) over (partition by _group order by idx) - 1 as a_pos
        FROM backslash, regexp_split_to_table(line, 'SAM') with ordinality as x(pos, idx)
    ) t
    WHERE a_pos < total 
)
SELECT a.*
FROM (
    SELECT a_row, _group - a_row as a_col
    FROM slash_mas_pos
    UNION ALL
    SELECT a_row, _group - a_row as a_col
    FROM slash_sam_pos
) a 
JOIN (
    SELECT a_row, a_row - _group as a_col
    FROM backslash_mas_pos
    UNION ALL
    SELECT a_row, a_row - _group as a_col
    FROM backslash_sam_pos
) b
ON a.a_row = b.a_row
AND a.a_col = b.a_col;




## day 5
with origin as (
    SELECT row_number() over () as rn, line
    FROM lance_input
), ordering_rule as (
    SELECT rn, split_part(line, '|', 1) :: INTEGER as l, split_part(line, '|', 2) :: INTEGER as r
    FROM origin
    WHERE rn < (select rn from origin where line is null)
), updating_record as (
    SELECT rn, x.item :: INTEGER, x.idx
    FROM origin, regexp_split_to_table(line, ',') with ordinality as x(item, idx)
    WHERE rn > (select rn from origin where line is null)
), correct_order as (
    SELECT *
    FROM updating_record
    WHERE rn not in (
        SELECT b.rn
        FROM ordering_rule a
        JOIN updating_record b
        ON a.l = b.item
        JOIN updating_record c
        ON a.r = c.item
        WHERE b.rn = c.rn
        AND b.idx > c.idx
    )
)
SELECT sum(path[((#path) + 1) / 2])
FROM (
    SELECT array_agg(item) as path
    FROM correct_order
    GROUP BY rn
) t

with recursive origin as (
    SELECT row_number() over () as rn, line
    FROM lance_input
), ordering_rule as (
    SELECT rn, split_part(line, '|', 1) :: INTEGER as l, split_part(line, '|', 2) :: INTEGER as r
    FROM origin
    WHERE rn < (select rn from origin where line is null)
), sub_ordering_rule as (
    SELECT *
    FROM ordering_rule
    WHERE r IN (81,74,28,18,98,82,55,29,53,86,24,65,37)
)
SELECT r
FROM sub_ordering_rule
GROUP BY r
HAVING NOT array_agg(l) && ARRAY[81,74,28,18,98,82,55,29,53,86,24,65,37]

with recursive origin as (
    SELECT row_number() over () as rn, line
    FROM lance_input
), ordering_rule as (
    SELECT rn, split_part(line, '|', 1) :: INTEGER as l, split_part(line, '|', 2) :: INTEGER as r
    FROM origin
    WHERE rn < (select rn from origin where line is null)
), updating_record as (
    SELECT rn, x.item :: INTEGER, x.idx
    FROM origin, regexp_split_to_table(line, ',') with ordinality as x(item, idx)
    WHERE rn > (select rn from origin where line is null)
), wrong_record as (
    SELECT *
    FROM updating_record
    WHERE rn in (
        SELECT b.rn
        FROM ordering_rule a
        JOIN updating_record b
        ON a.l = b.item
        JOIN updating_record c
        ON a.r = c.item
        WHERE b.rn = c.rn
        AND b.idx > c.idx
    )
), parent_agg as (
    SELECT b.rn, b.item, array_agg(a.item) as parent_items
    FROM wrong_record a
    JOIN wrong_record b
    ON a.rn = b.rn
    JOIN ordering_rule c
    ON a.item = c.l
    AND b.item = c.r
    GROUP by b.rn, b.item
), correct_order as (
    SELECT a.rn, array[a.item] as path
    FROM wrong_record a
    LEFT JOIN parent_agg b
    ON a.rn = b.rn
    AND a.item = b.item
    WHERE b.rn is null

    UNION ALL

    SELECT a.rn, path || b.item as path
    FROM correct_order a
    JOIN parent_agg b
    ON a.rn = b.rn
    AND a.path @> b.parent_items
    AND NOT b.item = ANY(path)
) 
SELECT sum(path[((#path) + 1) / 2])
FROM (
    SELECT rn, path, row_number() over(partition by rn order by #path desc) as rn
    FROM correct_order
) t
WHERE rn = 1;



## day 6

with recursive rows as (
    SELECT row_number() over () as _row, line
    FROM lance_input
), matrix AS (
    SELECT _row :: INTEGER, x.idx :: INTEGER as _col, x.pos
    FROM rows, regexp_split_to_table(line, '') with ordinality as x(pos, idx)
), cols AS (
    SELECT _col, string_agg(pos, '' order by _row) as line
    FROM matrix
    GROUP BY _col
), route AS (
    SELECT _row, _col, 'N' as direction, 1 as step
    FROM matrix
    WHERE pos = '^'

    UNION ALL

    SELECT _row + row_shift as _row,
           _col + col_shift as _col,
           direction,
           step
    FROM (
        SELECT CASE WHEN direction IN ('N') THEN 1 - position('#' IN reverse(substring(cols.line, 1, route._row - 1)) || '#')
                    WHEN direction IN ('S') THEN position('#' IN substring(cols.line, route._row + 1) || '#') - 1
                    ELSE 0
                END as row_shift,
               CASE WHEN direction IN ('E') THEN position('#' IN substring(rows.line, route._col + 1) || '#') - 1
                    WHEN direction IN ('W') THEN 1 - position('#' IN reverse(substring(rows.line, 1, route._col - 1)) || '#')
                    ELSE 0
                END as col_shift,
               route._row,
               route._col,
               CASE WHEN direction = 'N' THEN 'E'
                    WHEN direction = 'E' THEN 'S'
                    WHEN direction = 'S' THEN 'W'
                    WHEN direction = 'W' THEN 'N'
                END as direction,
               step + 1 as step
        FROM route 
        LEFT JOIN rows
        ON route._row = rows._row
        AND direction IN ('E', 'W')
        LEFT JOIN cols
        ON route._col = cols._col
        AND direction IN ('N', 'S')
        WHERE route._row between 2 and 129
        AND route._col between 2 and 129
    ) t
), path AS (
    SELECT least(a._row, b._row) as start_row, 
           least(a._col, b._col) as start_col,
           greatest(a._row, b._row) as end_row, 
           greatest(a._col, b._col) as end_col
    FROM route a
    JOIN route b
    ON a.step + 1 = b.step
)
SELECT DISTINCT x, y
FROM path, generate_series(1, 130) x, generate_series(1, 130) y
WHERE x.id between start_row AND end_row
AND y.id between start_col AND end_col;




with recursive rows as (
    SELECT row_number() over () as _row, line
    FROM lance_input
), matrix AS (
    SELECT _row :: INTEGER, x.idx :: INTEGER as _col, x.pos
    FROM rows, regexp_split_to_table(line, '') with ordinality as x(pos, idx)
), cols AS (
    SELECT _col, string_agg(pos, '' order by _row) as line
    FROM matrix
    GROUP BY _col
), route AS (
    SELECT _row, _col, 'N' as direction, 1 as step
    FROM matrix
    WHERE pos = '^'

    UNION ALL

    SELECT _row + row_shift as _row,
           _col + col_shift as _col,
           direction,
           step
    FROM (
        SELECT CASE WHEN direction IN ('N') THEN 1 - position('#' IN reverse(substring(cols.line, 1, route._row - 1)) || '#')
                    WHEN direction IN ('S') THEN position('#' IN substring(cols.line, route._row + 1) || '#') - 1
                    ELSE 0
                END as row_shift,
               CASE WHEN direction IN ('E') THEN position('#' IN substring(rows.line, route._col + 1) || '#') - 1
                    WHEN direction IN ('W') THEN 1 - position('#' IN reverse(substring(rows.line, 1, route._col - 1)) || '#')
                    ELSE 0
                END as col_shift,
               route._row,
               route._col,
               CASE WHEN direction = 'N' THEN 'E'
                    WHEN direction = 'E' THEN 'S'
                    WHEN direction = 'S' THEN 'W'
                    WHEN direction = 'W' THEN 'N'
                END as direction,
               step + 1 as step
        FROM route 
        LEFT JOIN rows
        ON route._row = rows._row
        AND direction IN ('E', 'W')
        LEFT JOIN cols
        ON route._col = cols._col
        AND direction IN ('N', 'S')
        WHERE route._row between 2 and 129
        AND route._col between 2 and 129
    ) t
), path AS (
    SELECT least(a._row, b._row) as start_row, 
           least(a._col, b._col) as start_col,
           greatest(a._row, b._row) as end_row, 
           greatest(a._col, b._col) as end_col
    FROM route a
    JOIN route b
    ON a.step + 1 = b.step
), new_pos AS (
    SELECT row_number() over () as rn, _row, _col
    FROM (
        SELECT distinct x as _row, y as _col
        FROM path a, 
             generate_series(1, 130) as x,
             generate_series(1, 130) as y,
             matrix b
        WHERE x between start_row and end_row
        AND y between start_col and end_col
        AND x = b._row
        AND y = b._col
        AND b.pos = '.'
    ) t
), new_route AS (
    SELECT rn, matrix._row, matrix._col, 'N' as direction, array[matrix._row * 1000 + matrix._col] as path, false as cycle
    FROM matrix, new_pos
    WHERE pos = '^'

    UNION ALL

    SELECT rn, _row, _col, 
           CASE WHEN direction = 'N' THEN 'E'
                WHEN direction = 'E' THEN 'S'
                WHEN direction = 'S' THEN 'W'
                WHEN direction = 'W' THEN 'N'
            END as direction,
           CASE WHEN (_row * 1000 + _col) = path[#path] THEN path ELSE path || (_row * 1000 + _col) END as path,
           (_row * 1000 + _col) = ANY(path[1 : (#path) - 1]) as cycle
    FROM (
        SELECT _row + CASE WHEN direction = 'N' THEN greatest(row_shift, new_row_shift)
                           WHEN direction = 'S' THEN least(row_shift, new_row_shift) 
                           ELSE 0
                       END as _row,
               _col + CASE WHEN direction = 'E' THEN least(col_shift, new_col_shift)
                           WHEN direction = 'W' THEN greatest(col_shift, new_col_shift) 
                           ELSE 0
                       END as _col,
               direction, path, rn
        FROM (
            SELECT CASE WHEN direction IN ('N') THEN 1 - position('#' IN reverse(substring(cols.line, 1, new_route._row - 1)) || '#')
                        WHEN direction IN ('S') THEN position('#' IN substring(cols.line, new_route._row + 1) || '#') - 1
                        ELSE 0
                    END as row_shift,
                   CASE WHEN direction IN ('E') THEN position('#' IN substring(rows.line, new_route._col + 1) || '#') - 1
                        WHEN direction IN ('W') THEN 1 - position('#' IN reverse(substring(rows.line, 1, new_route._col - 1)) || '#')
                        ELSE 0
                    END as col_shift,
                   CASE WHEN direction IN ('N') AND new_pos._col = new_route._col AND new_pos._row < new_route._row THEN new_pos._row - new_route._row + 1 
                        WHEN direction IN ('S') AND new_pos._col = new_route._col AND new_pos._row > new_route._row THEN new_pos._row - new_route._row - 1 
                    END as new_row_shift,
                   CASE WHEN direction IN ('E') AND new_pos._row = new_route._row AND new_pos._col > new_route._col THEN new_pos._col - new_route._col - 1 
                        WHEN direction IN ('W') AND new_pos._row = new_route._row AND new_pos._col < new_route._col THEN new_pos._col - new_route._col + 1 
                    END as new_col_shift,
                   new_route._row,
                   new_route._col,
                   new_route.direction,
                   new_route.path,
                   new_route.rn
            FROM new_route 
            JOIN new_pos
            ON new_route.rn = new_pos.rn
            LEFT JOIN rows
            ON new_route._row = rows._row
            AND direction IN ('E', 'W')
            LEFT JOIN cols
            ON new_route._col = cols._col
            AND direction IN ('N', 'S')
            WHERE new_route._row between 2 and 129
            AND new_route._col between 2 and 129
            AND NOT cycle
        ) t
    ) s
)
select rn From new_route where cycle;



# day 7 

with recursive origin AS (
    SELECT row_number() over () as rn, 
           split_part(line, ': ', 1) :: bigint as expected,
           regexp_split_to_array(split_part(line, ': ', 2), ' ') :: int[] as numbers
    FROM lance_input
), calc as (
    SELECT rn, numbers, numbers[1] :: bigint as result, 1 as index, expected, array[] :: text[] as operators
    FROM origin

    UNION ALL

    SELECT rn, numbers,
           CASE WHEN operator = '+' THEN result + numbers[index + 1]
                WHEN operator = '*' THEN result * numbers[index + 1]
                WHEN operator = '|' THEN (result :: text || numbers[index + 1] :: text) :: bigint
            END as result,
           index + 1 as index,
           expected,
           operators || operator as operators
    FROM calc
    JOIN regexp_split_to_table('+*|','') as x(operator)
    ON calc.result <= expected
    AND index < #numbers
)
select sum(expected) from origin where rn in (SELECT distinct rn from calc where result = expected and index = #numbers);


# day 8

with rows as (
    SELECT row_number() over () as _row, line
    FROM lance_input
), matrix AS (
    SELECT _row :: INTEGER, x.idx :: INTEGER as _col, x.pos
    FROM rows, regexp_split_to_table(line, '') with ordinality as x(pos, idx)
), antinodes AS (
    SELECT CASE WHEN a._row <= b._row THEN a._row - (b._row - a._row) 
                ELSE a._row + (a._row - b._row) 
            END as _row,
           CASE WHEN a._col <= b._col THEN a._col - (b._col - a._col) 
                ELSE a._col + (a._col - b._col) 
            END as _col
    FROM matrix a
    JOIN matrix b
    ON a.pos != '.'
    AND b.pos != '.'
    AND a.pos = b.pos
    AND (a._row, a._col) != (b._row, b._col)
)
SELECT distinct _row, _col
FROM antinodes
WHERE _row between 1 AND (select max(_row) from matrix)
AND _col between 1 AND (select max(_col) from matrix);



with recursive rows as (
    SELECT row_number() over () as _row, line
    FROM lance_input
), matrix AS (
    SELECT _row :: INTEGER, x.idx :: INTEGER as _col, x.pos
    FROM rows, regexp_split_to_table(line, '') with ordinality as x(pos, idx)
), antinodes AS (
    SELECT _row, _col, delta_row, delta_col
    FROM (
        SELECT CASE WHEN a._row <= b._row THEN a._row - (b._row - a._row) 
                    ELSE a._row + (a._row - b._row) 
                END as _row,
               CASE WHEN a._col <= b._col THEN a._col - (b._col - a._col) 
                    ELSE a._col + (a._col - b._col) 
                END as _col,
               CASE WHEN a._row <= b._row THEN a._row - b._row
                    ELSE a._row - b._row
                END as delta_row,
               CASE WHEN a._col <= b._col THEN a._col - b._col
                    ELSE a._col - b._col
                END as delta_col
        FROM matrix a
        JOIN matrix b
        ON a.pos != '.'
        AND b.pos != '.'
        AND a.pos = b.pos
        AND (a._row, a._col) != (b._row, b._col)
    ) t
    WHERE _row between 1 AND (select max(_row) from matrix)
    AND _col between 1 AND (select max(_col) from matrix)

    UNION ALL

    SELECT _row + delta_row as _row,
           _col + delta_col as _col,
           delta_row, delta_col
    FROM antinodes
    WHERE (_row + delta_row) between 1 AND (select max(_row) from matrix)
    AND (_col + delta_col) between 1 AND (select max(_col) from matrix)
)
SELECT _row, _col
FROM antinodes

UNION

SELECT a._row, a._col
FROM matrix a
JOIN matrix b
ON a.pos != '.'
AND b.pos != '.'
AND a.pos = b.pos
AND (a._row, a._col) != (b._row, b._col)


# day 9

with origin AS (
    SELECT idx, case when mod(idx, 2) = 1 then ((idx - 1) / 2) :: VARCHAR  else '.' end as pos
    FROM (
        SELECT x.idx :: INTEGER, x.pos
        FROM lance_input, regexp_split_to_table(line, '') with ordinality as x(pos, idx)
    ) t, generate_series(1, 9) as id
    WHERE pos :: INTEGER >= id
    ORDER BY idx
), group_a AS (
    SELECT idx, pos, 
           row_number() over (partition by case when pos = '.' then 1 else 2 end order by idx) as rn
    FROM origin
), group_b AS (
    SELECT idx, pos, 
           row_number() over (partition by case when pos = '.' then 1 else 2 end order by idx desc) as rn
    FROM origin
), move AS (
    SELECT pos, row_number() over (order by idx, rn) as rn
    FROM (
        SELECT a.idx, a.rn, coalesce(b.pos, a.pos) as pos
        FROM group_a a
        LEFT JOIN group_b b 
        ON a.rn = b.rn
        AND a.pos = '.'
        AND b.pos != '.'
    ) t
)
SELECT sum((rn - 1) * pos :: INTEGER)
FROM move
WHERE rn <= (select count(*) from group_a where pos != '.');




with recursive origin AS (
    SELECT idx, pos :: INTEGER as length, case when mod(idx, 2) = 1 then ((idx - 1) / 2) :: VARCHAR else '.' end as file_id
    FROM (
        SELECT x.idx :: INTEGER, x.pos
        FROM lance_input, regexp_split_to_table(line, '') with ordinality as x(pos, idx)
    ) t
    ORDER BY idx
), num_pos AS (
    SELECT start_pos, length, file_id :: INTEGER
    FROM (
        SELECT sum(length) over (order by idx) - length as start_pos, length, file_id
        FROM origin
    ) t
    WHERE file_id != '.'
), mv_pos AS (
    SELECT start_pos, length, file_id, (SELECT max(file_id) FROM num_pos) as current_file
    FROM num_pos

    UNION ALL

    SELECT start_pos, length, file_id, current_file
    FROM (
        WITH t AS (
            SELECT * FROM mv_pos
        ), free AS (
            SELECT a.start_pos + a.length as start_pos,
                   b.start_pos - a.start_pos - a.length as length
            FROM t a
            JOIN (
                SELECT start_pos, 
                       lag(start_pos) over (order by start_pos) as pre_pos
                FROM t
            ) b
            ON a.start_pos = b.pre_pos
            AND a.start_pos + a.length < b.start_pos 
        ), mv_idx AS (
            SELECT a.start_pos
            FROM free a
            JOIN t b
            ON a.length >= b.length
            AND b.file_id = b.current_file
            AND a.start_pos < b.start_pos
            ORDER BY a.start_pos
            LIMIT 1
        )
        SELECT CASE WHEN t.file_id = current_file AND a.start_pos IS NOT null THEN a.start_pos
                    ELSE t.start_pos
                END as start_pos,
               t.length, 
               t.file_id,
               t.current_file - 1 as current_file
        FROM t LEFT JOIN mv_idx a
        ON 1 = 1
        WHERE t.current_file >= 0
    ) s
)
SELECT sum(t.file_id * (t.start_pos + id - 1)) as result
FROM (
    SELECT * 
    FROM mv_pos
    WHERE current_file = -1
) t
JOIN generate_series(1, 9) as id
ON t.length >= id;


CREATE OR REPLACE FUNCTION move_file(idx_array INTEGER[], position_array INTEGER[], length_array INTEGER[], current_file INTEGER)
RETURNS RECORD AS $$
DECLARE
  file_position INTEGER;
  file_length INTEGER;
  insert_index INTEGER;
BEGIN
    file_position := position_array[current_file];
    file_length := length_array[current_file];

    insert_index := 0;
    FOR i IN 1..#idx_array LOOP
        -- last position
        CONTINUE WHEN i = #idx_array;
        -- no free space left
        CONTINUE WHEN position_array[idx_array[i]] + length_array[idx_array[i]] = position_array[idx_array[i + 1]];
        -- beyond current file position
        EXIT WHEN position_array[idx_array[i]] >= file_position;
        -- not enough free space
        CONTINUE WHEN position_array[idx_array[i + 1]] - (position_array[idx_array[i]] + length_array[idx_array[i]]) < file_length;
        -- calculate start position of the free space
        insert_index := i;
        EXIT;
    END LOOP;

    IF insert_index > 0 THEN
        position_array[current_file] := position_array[idx_array[insert_index]] + length_array[idx_array[insert_index]];
        RETURN (idx_array[1:insert_index] || current_file || (idx_array[insert_index + 1:#idx_array] - current_file), position_array);
    ELSE
        RETURN (idx_array, position_array);
    END IF;
  
END;
$$ LANGUAGE plpgsql;

with recursive origin AS (
    SELECT idx, pos :: INTEGER as length, case when mod(idx, 2) = 1 then ((idx - 1) / 2) :: VARCHAR else '.' end as file_id
    FROM (
        SELECT x.idx :: INTEGER, x.pos
        FROM lance_input, regexp_split_to_table(line, '') with ordinality as x(pos, idx)
    ) t
    ORDER BY idx
), num_pos AS (
    SELECT start_pos, length, file_id :: INTEGER + 1 as file_id
    FROM (
        SELECT sum(length) over (order by idx) - length as start_pos, length, file_id
        FROM origin
    ) t
    WHERE file_id != '.'
), mv_pos AS (
    SELECT array_agg(file_id order by file_id) :: int[] as idx_array, 
           array_agg(start_pos order by file_id) :: int[] as pos_array,
           array_agg(length order by file_id) :: int[] as length_array, 
           max(file_id) as current_file
    FROM num_pos

    UNION ALL

    SELECT t.idx_array, t.pos_array, s.length_array, s.current_file - 1 as current_file
    FROM mv_pos s, move_file(idx_array, pos_array, length_array, current_file) as t(idx_array int[], pos_array int[])
    WHERE s.current_file >0
)
SELECT sum(file_id * (t.pos + id - 1)) as result
FROM (
    SELECT x.id - 1 as file_id, y.pos, z.length
    FROM (
        SELECT id.*
        FROM mv_pos, unnest(idx_array) WITH ORDINALITY id
        WHERE current_file = 0
    ) x
    JOIN (
        SELECT pos.*
        FROM mv_pos, unnest(pos_array) WITH ORDINALITY pos
        WHERE current_file = 0
    ) y
    ON x.id = y.ORDINALITY
    JOIN (
        SELECT length.*
        FROM mv_pos, unnest(length_array) WITH ORDINALITY length
        WHERE current_file = 0
    ) z
    ON x.id = z.ORDINALITY
) t
JOIN generate_series(1, 9) as id
ON t.length >= id;



# day 10
with recursive origin as (
    SELECT row_number() over () as rn, line
    FROM lance_input
), matrix AS (
    SELECT rn :: INTEGER as _row, x.idx :: INTEGER as _col, x.num :: INTEGER
    FROM origin, regexp_split_to_table(line, '') with ordinality as x(num, idx)
), walk AS (
    SELECT _row, _col, num, _row as current_row, _col as current_col
    FROM matrix
    WHERE num = 0

    UNION ALL

    SELECT DISTINCT a._row, a._col, b.num, b._row as current_row, b._col as current_col
    FROM walk a
    JOIN matrix b
    ON a.num + 1 = b.num
    AND abs(a.current_row - b._row) + abs(a.current_col - b._col) = 1
)
SELECT SUM(cnt)
FROM (
    SELECT _row, _col, count(*) as cnt
    FROM walk
    WHERE num = 9
    GROUP BY _row, _col
) t


# day 11
with recursive stones AS (
    SELECT line, 0 as blink
    FROM lance_input

    UNION ALL

    SELECT string_agg(num, ' ') as line, blink + 1
    FROM (
        SELECT blink, 
               CASE WHEN num = '0' then '1'
                    WHEN length(num) % 2 = 0 THEN substr(num, 1, length(num) / 2) :: BIGINT || ' ' || 
                         substr(num, length(num) / 2 + 1, length(num) / 2) :: BIGINT
                    ELSE (num :: BIGINT * 2024) :: VARCHAR
                END as num
        FROM (
            SELECT x.pos as num, blink
            FROM stones, regexp_split_to_table(line, ' ') with ordinality as x(pos, idx)
        ) t
    ) t
    WHERE blink < 25
    GROUP BY blink
)
SELECT * FROM stones;




CREATE OR REPLACE FUNCTION count_stones(num bigint, blink_left integer)
RETURNS BIGINT AS $$
DECLARE
  query_num BIGINT;
  stone_num BIGINT;
BEGIN
    IF blink_left = 0 THEN
        RETURN 1;
    END IF;

    query_num := (SELECT cache_stone FROM cache WHERE cache_num = num AND cache_blink = blink_left);

    IF query_num IS NOT NULL THEN
        return query_num;
    END IF;

    IF num = 0 THEN
        stone_num := count_stones(1, blink_left - 1);
    ELSE 
        IF length(num :: VARCHAR) % 2 = 0 THEN
            stone_num := count_stones(substr(num :: VARCHAR, 1, length(num :: VARCHAR) / 2) :: BIGINT, blink_left - 1) 
                       + count_stones(substr(num :: VARCHAR, length(num :: VARCHAR) / 2 + 1, length(num :: VARCHAR) / 2) :: BIGINT, blink_left - 1);
        ELSE
            stone_num := count_stones(num * 2024, blink_left - 1);
        END IF;
    END IF;

    query_num := (SELECT cache_stone FROM cache WHERE cache_num = num AND cache_blink = blink_left);
    IF query_num IS NULL THEN
        INSERT INTO cache values(num, blink_left, stone_num);
        RAISE NOTICE 'add map: %', (num || ' ' || blink_left);
    END IF;
    
    RETURN stone_num;
END;
$$ LANGUAGE plpgsql;


# day 12
with rows as (
    SELECT row_number() over () as _row, line
    FROM lance_input
), matrix AS (
    SELECT _row :: INTEGER, x.idx :: INTEGER as _col, x.pos as plant
    FROM rows, regexp_split_to_table(line, '') with ordinality as x(pos, idx)
), plant_cnt AS (
    SELECT plant, count(*) as cnt
    FROM matrix
    GROUP BY plant
), plant_neighbour AS (
    SELECT a.plant, count(*) as CNT
    FROM matrix a, matrix b
    WHERE a.plant = b.plant
    AND ((a._row + 1 = b._row AND a._col = b._col) OR (a._col + 1 = b._col AND a._row = b._row))
    GROUP BY a.plant
)
SELECT sum(a.cnt * (a.cnt * 4 - coalesce(b.cnt, 0) * 2))
FROM plant_cnt a 
LEFT JOIN plant_neighbour b
ON a.plant = b.plant;


with recursive rows as (
    SELECT row_number() over () as _row, line
    FROM lance_input
), matrix AS (
    SELECT _row :: INTEGER, x.idx :: INTEGER as _col, x.pos as plant
    FROM rows, regexp_split_to_table(line, '') with ordinality as x(pos, idx)
), region AS (
    SELECT _row, _col, plant, 
           rn = 1 as find,
           0 as region_seq,
           1 as round
    FROM (
        SELECT _row, _col, plant,
               row_number() over (partition by plant order by _row, _col) as rn
        FROM matrix
    ) t

    UNION ALL

    SELECT _row, _col, plant, find, region_seq, round
    FROM (
        WITH _region AS (SELECT * FROM region)
        SELECT a._row, a._col, a.plant, 
               a.find OR b._row is not null as find,
               coalesce(b.region_seq, a.region_seq) as region_seq,
               a.round + 1 as round
        FROM _region a
        LEFT JOIN (
            SELECT DISTINCT _row, _col, plant, region_seq
            FROM (
                SELECT _row, _col, plant, region_seq,
                       rank() over (partition by plant order by case when neighbour then '1' else '0' || lpad(_row::varchar, 3, '0') || lpad(_col::varchar, 3, '0') end desc, region_seq desc) as rn
                FROM (
                    SELECT b._row, b._col, b.plant,
                           abs(a._row - b._row) + abs(a._col - b._col) = 1 as neighbour,
                           case when abs(a._row - b._row) + abs(a._col - b._col) = 1 then a.region_seq else a.region_seq + 1 end as region_seq
                    FROM _region a
                    JOIN _region b
                    ON a.plant = b.plant
                    AND a.find
                    AND NOT b.find
                ) t
            ) t
            WHERE rn = 1
        ) b
        ON a._row = b._row
        AND a._col = b._col
        WHERE exists (select * From _region where not find limit 1)
    ) t
), final_round AS (
    SELECT *
    FROM region
    WHERE round = (select max(round) from region)
), plant_cnt AS (
    SELECT plant, region_seq, count(*) as cnt
    FROM final_round
    GROUP BY plant, region_seq
), plant_neighbour AS (
    SELECT a.plant, a.region_seq, count(*) as CNT
    FROM final_round a, final_round b
    WHERE a.plant = b.plant
    AND ((a._row + 1 = b._row AND a._col = b._col) OR (a._col + 1 = b._col AND a._row = b._row))
    GROUP BY a.plant, a.region_seq
)
SELECT sum(a.cnt * (a.cnt * 4 - coalesce(b.cnt, 0) * 2))
FROM plant_cnt a 
LEFT JOIN plant_neighbour b
ON a.plant = b.plant
AND a.region_seq = b.region_seq;


with recursive rows as (
    SELECT row_number() over () as _row, line
    FROM lance_input
), matrix AS (
    SELECT _row :: INTEGER, x.idx :: INTEGER as _col, x.pos as plant
    FROM rows, regexp_split_to_table(line, '') with ordinality as x(pos, idx)
), region AS (
    SELECT _row, _col, plant, 
           rn = 1 as find,
           rn = 1 as active,
           0 as region_seq,
           1 as round
    FROM (
        SELECT _row, _col, plant,
               row_number() over (partition by plant order by _row, _col) as rn
        FROM matrix
    ) t

    UNION ALL

    SELECT _row, _col, plant, find, active, region_seq, round
    FROM (
        WITH _region AS (SELECT * FROM region)
        SELECT a._row, a._col, a.plant, 
               a.find OR b._row is not null as find,
               b._row is not null as active,
               coalesce(b.region_seq, a.region_seq) as region_seq,
               a.round + 1 as round
        FROM _region a
        LEFT JOIN (
            SELECT DISTINCT _row, _col, plant, region_seq
            FROM (
                SELECT _row, _col, plant, region_seq,
                       rank() over (partition by plant order by case when neighbour then '1' else '0' || lpad(_row::varchar, 3, '0') || lpad(_col::varchar, 3, '0') end desc, region_seq desc) as rn
                FROM (
                    SELECT b._row, b._col, b.plant,
                           abs(a._row - b._row) + abs(a._col - b._col) = 1 as neighbour,
                           case when abs(a._row - b._row) + abs(a._col - b._col) = 1 then a.region_seq else a.region_seq + 1 end as region_seq
                    FROM _region a
                    JOIN _region b
                    ON a.plant = b.plant
                    AND a.active
                    AND NOT b.find
                ) t
            ) t
            WHERE rn = 1
        ) b
        ON a._row = b._row
        AND a._col = b._col
        WHERE exists (select * From _region where not find limit 1)
    ) t
), final_round AS (
    SELECT *
    FROM region
    WHERE round = (select max(round) from region)
), plant_cnt AS (
    SELECT plant, region_seq, count(*) as cnt
    FROM final_round
    GROUP BY plant, region_seq
), plant_neighbour AS (
    SELECT a.plant, a.region_seq, count(*) as CNT
    FROM final_round a, final_round b
    WHERE a.plant = b.plant
    AND ((a._row + 1 = b._row AND a._col = b._col) OR (a._col + 1 = b._col AND a._row = b._row))
    GROUP BY a.plant, a.region_seq
)
SELECT sum(a.cnt * (a.cnt * 4 - coalesce(b.cnt, 0) * 2))
FROM plant_cnt a 
LEFT JOIN plant_neighbour b
ON a.plant = b.plant
AND a.region_seq = b.region_seq;

with recursive rows as (
    SELECT row_number() over () as _row, line
    FROM lance_input
), matrix AS (
    SELECT _row :: INTEGER, x.idx :: INTEGER as _col, x.pos as plant
    FROM rows, regexp_split_to_table(line, '') with ordinality as x(pos, idx)
), region AS (
    SELECT _row, _col, plant, 
           rn = 1 as find,
           rn = 1 as active,
           0 as region_seq,
           1 as round
    FROM (
        SELECT _row, _col, plant,
               row_number() over (partition by plant order by _row, _col) as rn
        FROM matrix
    ) t

    UNION ALL

    SELECT _row, _col, plant, find, active, region_seq, round
    FROM (
        WITH _region AS (SELECT * FROM region)
        SELECT a._row, a._col, a.plant, 
               a.find OR b._row is not null as find,
               b._row is not null as active,
               coalesce(b.region_seq, a.region_seq) as region_seq,
               a.round + 1 as round
        FROM _region a
        LEFT JOIN (
            SELECT DISTINCT _row, _col, plant, region_seq
            FROM (
                SELECT _row, _col, plant, region_seq,
                       rank() over (partition by plant order by case when neighbour then '1' else '0' || lpad(_row::varchar, 3, '0') || lpad(_col::varchar, 3, '0') end desc, region_seq desc) as rn
                FROM (
                    SELECT b._row, b._col, b.plant,
                           abs(a._row - b._row) + abs(a._col - b._col) = 1 as neighbour,
                           case when abs(a._row - b._row) + abs(a._col - b._col) = 1 then a.region_seq else a.region_seq + 1 end as region_seq
                    FROM _region a
                    JOIN _region b
                    ON a.plant = b.plant
                    AND a.active
                    AND NOT b.find
                ) t
            ) t
            WHERE rn = 1
        ) b
        ON a._row = b._row
        AND a._col = b._col
        WHERE exists (select * From _region where not find limit 1)
    ) t
), final_round AS (
    SELECT _row, _col, plant, find, active, region_seq, round
    FROM region
    WHERE round = (select max(round) from region)
), plant_cnt AS (
    SELECT plant, region_seq, count(*) as cnt
    FROM final_round
    GROUP BY plant, region_seq
), plant_stats AS (
    SELECT a._row, a._col, a.plant, a.region_seq, 
           max(case when b._row = a._row - 1 then 1 else 0 end) as has_up,
           max(case when b._row = a._row + 1 then 1 else 0 end) as has_down,
           max(case when b._col = a._col - 1 then 1 else 0 end) as has_left,
           max(case when b._col = a._col + 1 then 1 else 0 end) as has_right
    FROM final_round a
    LEFT JOIN final_round b
    ON a.plant = b.plant
    AND abs(a._row - b._row) + abs(a._col - b._col) = 1
    GROUP BY a._row, a._col, a.plant, a.region_seq
), plant_neighbour AS (
    SELECT a.plant, a.region_seq, count(*) as cnt
    FROM final_round a, final_round b
    WHERE a.plant = b.plant
    AND ((a._row + 1 = b._row AND a._col = b._col) OR (a._col + 1 = b._col AND a._row = b._row))
    GROUP BY a.plant, a.region_seq
), plant_straight AS (
    SELECT a.plant, a.region_seq,
           sum(case when a._col + 1 = b._col AND a.has_up = 0 AND b.has_up = 0 then 1 else 0 end) as up_trim,
           sum(case when a._col + 1 = b._col AND a.has_down = 0 AND b.has_down = 0 then 1 else 0 end) as down_trim,
           sum(case when a._row + 1 = b._row AND a.has_left = 0 AND b.has_left = 0 then 1 else 0 end) as left_trim,
           sum(case when a._row + 1 = b._row AND a.has_right = 0 AND b.has_right = 0 then 1 else 0 end) as right_trim
    FROM plant_stats a, plant_stats b
    WHERE a.plant = b.plant
    AND ((a._row + 1 = b._row AND a._col = b._col) OR (a._col + 1 = b._col AND a._row = b._row))
    GROUP BY a.plant, a.region_seq
)
SELECT sum(a.cnt * (a.cnt * 4 - coalesce(b.cnt, 0) * 2 - coalesce(c.up_trim, 0) - coalesce(c.down_trim, 0) - coalesce(c.left_trim, 0) - coalesce(c.right_trim, 0)))
FROM plant_cnt a 
LEFT JOIN plant_neighbour b
ON a.plant = b.plant
AND a.region_seq = b.region_seq
LEFT JOIN plant_straight c
ON a.plant = c.plant
AND a.region_seq = c.region_seq;


# day 13
with origin as (
    SELECT row_number() over () as rn, line
    FROM lance_input
), splitter AS (
    SELECT 0 as rn
    UNION ALL
    SELECT rn
    FROM origin
    WHERE line is null
), inputs AS (
    SELECT substring(b.line, position('X+' IN b.line) + 2, position(',' IN b.line) - position('X+' IN b.line) - 2) :: BIGINT as button_a_x,
           substring(b.line, position('Y+' IN b.line) + 2) :: BIGINT as button_a_y,
           substring(c.line, position('X+' IN c.line) + 2, position(',' IN c.line) - position('X+' IN c.line) - 2) :: BIGINT as button_b_x,
           substring(c.line, position('Y+' IN c.line) + 2) :: BIGINT as button_b_y,
           substring(d.line, position('X=' IN d.line) + 2, position(',' IN d.line) - position('X=' IN d.line) - 2) :: BIGINT as prize_x,
           substring(d.line, position('Y=' IN d.line) + 2) :: BIGINT as prize_y
    FROM splitter a 
    JOIN origin b 
    ON a.rn + 1 = b.rn
    JOIN origin c
    ON a.rn + 2 = c.rn
    JOIN origin d
    ON a.rn + 3 = d.rn
)
SELECT sum((prize_x - button_b * button_b_x) / button_a_x * 3+ button_b)
FROM (
    SELECT *, (prize_x * button_a_y - prize_y * button_a_x) / (button_b_x * button_a_y - button_b_y * button_a_x) as button_b
    FROM inputs
    WHERE (prize_x * button_a_y - prize_y * button_a_x) % (button_b_x * button_a_y - button_b_y * button_a_x) = 0
) t
where (prize_x - button_b * button_b_x) % button_a_x = 0;

# day 14
with origin as (
    SELECT row_number() over () as rn, line
    FROM lance_input
), robots as (
    SELECT split_part(p, ',', 1) :: integer as p_x, 
           split_part(p, ',', 2) :: integer as p_y,
           split_part(v, ',', 1) :: integer as v_x,
           split_part(v, ',', 2) :: integer as v_y
    FROM (
        SELECT split_part(split_part(line, ' ', 1), '=', 2) as p, 
               split_part(split_part(line, ' ', 2), '=', 2) as v
        FROM origin
    ) t
), robots_trans as (
    SELECT p_x, p_y,
           CASE WHEN v_x < 0 THEN v_x + 101 ELSE v_x END as v_x,
           CASE WHEN v_y < 0 THEN v_y + 103 ELSE v_y END as v_y
    FROM robots
)
SELECT final_x < 50, final_y < 51, count(*)
FROM (
    SELECT (p_x + 100 * v_x) % 101 as final_x,
           (p_y + 100 * v_y) % 103 as final_y
    FROM robots_trans
) t
WHERE final_x != 50
AND final_y != 51
GROUP BY final_x < 50, final_y < 51;

with origin as (
    SELECT row_number() over () as rn, line
    FROM lance_input
), robots as (
    SELECT split_part(p, ',', 1) :: integer as p_x, 
           split_part(p, ',', 2) :: integer as p_y,
           split_part(v, ',', 1) :: integer as v_x,
           split_part(v, ',', 2) :: integer as v_y
    FROM (
        SELECT split_part(split_part(line, ' ', 1), '=', 2) as p, 
               split_part(split_part(line, ' ', 2), '=', 2) as v
        FROM origin
    ) t
), robots_trans as (
    SELECT p_x, p_y,
           CASE WHEN v_x < 0 THEN v_x + 101 ELSE v_x END as v_x,
           CASE WHEN v_y < 0 THEN v_y + 103 ELSE v_y END as v_y
    FROM robots
)
select id, pos_y, string_agg(case when final_x is not null THEN 'x' ELSE '.' END, '' order by pos_x)
FROM (
    SELECT (p_x + id * v_x) % 101 as final_x,
           (p_y + id * v_y) % 103 as final_y, 
           id
    FROM robots_trans, (select generate_series(1, 1, 1) as id) x
) x 
RIGHT JOIN (
    SELECT z.id as id, x.id as pos_x, y.id as pos_y
    FROM (select generate_series(0, 100, 1) as id) x, (select generate_series(0, 102, 1) as id) y,  (select generate_series(1, 10000, 1) as id) z
) y
ON x.final_x = y.pos_x
AND x.final_y = y.pos_y
AND x.id = y.id
GROUP BY id, pos_y;

# day 15
drop table matrix;
create table matrix as 
with origin as (
    SELECT row_number() over () as rn, line
    FROM lance_input
)
SELECT rn as _row, idx as _col, pos
FROM origin, regexp_split_to_table(line, '') with ordinality as x(pos, idx)
WHERE rn < (select rn from origin where line is null);

create index idx_row on matrix(_row);

create index idx_col on matrix(_col);

create index idx_pos on matrix(pos);


CREATE OR REPLACE FUNCTION move_robot(direction VARCHAR)
RETURNS VOID AS $$
DECLARE
    robot_row INTEGER;
    robot_col INTEGER;
    target_row INTEGER;
    target_col INTEGER;
    empty_pos INTEGER;
    next_pos VARCHAR;
    move_pos VARCHAR;
BEGIN

    SELECT _row, _col INTO robot_row, robot_col FROM matrix WHERE pos = '@';

    target_row := robot_row;
    target_col := robot_col;

    IF direction = '>' THEN
        target_col := robot_col + 1;
    END IF;

    IF direction = '<' THEN
        target_col := robot_col - 1;
    END IF;

    IF direction = '^' THEN
        target_row := robot_row - 1;
    END IF;

    IF direction = 'v' THEN
        target_row := robot_row + 1;
    END IF;

    empty_pos := (select count(*) from matrix where _row = target_row AND _col = target_col AND pos = '.');

    IF empty_pos = 1 THEN
        IF direction = '>' THEN
            UPDATE matrix SET _col = (CASE WHEN _col = robot_col THEN _col + 1 ELSE _col - 1 END) 
            WHERE _row = robot_row AND _col IN (robot_col, robot_col + 1);
        END IF;

        IF direction = '<' THEN
            UPDATE matrix SET _col = (CASE WHEN _col = robot_col THEN _col - 1 ELSE _col + 1 END) 
            WHERE _row = robot_row AND _col IN (robot_col, robot_col - 1);
        END IF;

        IF direction = '^' THEN
            UPDATE matrix SET _row = (CASE WHEN _row = robot_row THEN _row - 1 ELSE _row + 1 END) 
            WHERE _row IN (robot_row, robot_row - 1) AND _col = robot_col;
        END IF;

        IF direction = 'v' THEN
            UPDATE matrix SET _row = (CASE WHEN _row = robot_row THEN _row + 1 ELSE _row - 1 END) 
            WHERE _row IN (robot_row, robot_row + 1) AND _col = robot_col;
        END IF;
    ELSE
        IF direction = '>' THEN
            next_pos := (select substring(string_agg(pos, '' order by _col), robot_col + 1) from matrix where _row = robot_row);
        END IF;

        IF direction = '<' THEN
            next_pos := (select reverse(substring(string_agg(pos, '' order by _col), 1, robot_col - 1)) from matrix where _row = robot_row);
        END IF;

        IF direction = '^' THEN
            next_pos := (select reverse(substring(string_agg(pos, '' order by _row), 1, robot_row - 1)) from matrix where _col = robot_col);
        END IF;

        IF direction = 'v' THEN
            next_pos := (select substring(string_agg(pos, '' order by _row), robot_row + 1) from matrix where _col = robot_col);
        END IF;

        move_pos := (select (regexp_matches(next_pos, '^(O+\.)'))[1]);

        IF move_pos IS NULL THEN
            RETURN; 
        END IF;

        IF direction = '>' THEN
            UPDATE matrix set _col = (case when _col = robot_col + length(move_pos) THEN robot_col ELSE _col + 1 END)
            WHERE _row = robot_row
            AND _col between robot_col AND robot_col + length(move_pos);
        END IF;

        IF direction = '<' THEN
            UPDATE matrix set _col = (case when _col = robot_col - length(move_pos) THEN robot_col ELSE _col - 1 END)
            WHERE _row = robot_row
            AND _col between robot_col - length(move_pos) AND robot_col;
        END IF;

        IF direction = '^' THEN
            UPDATE matrix set _row = (case when _row = robot_row - length(move_pos) THEN robot_row ELSE _row - 1 END)
            WHERE _col = robot_col
            AND _row between robot_row - length(move_pos) AND robot_row;
        END IF;

        IF direction = 'v' THEN
            UPDATE matrix set _row = (case when _row = robot_row + length(move_pos) THEN robot_row ELSE _row + 1 END)
            WHERE _col = robot_col
            AND _row between robot_row AND robot_row + length(move_pos);
        END IF;
    END IF;
END;
$$ LANGUAGE plpgsql;




with origin as (
    SELECT row_number() over () as rn, line
    FROM lance_input
)
SELECT move_robot(pos)
FROM origin, regexp_split_to_table(line, '') with ordinality as x(pos, idx)
WHERE rn > (select rn from origin where line is null);

select sum((_row - 1) * 100 + _col - 1) from matrix where pos = 'O';



drop table matrix;
create table matrix as 
with origin as (
    SELECT row_number() over () as rn, replace(replace(replace(replace(line, '#', '##'), 'O', '[]'), '.', '..'), '@', '@.') as line
    FROM lance_input
)
SELECT rn as _row, idx as _col, pos
FROM origin, regexp_split_to_table(line, '') with ordinality as x(pos, idx)
WHERE rn < (select rn from origin where line is null);

create index idx_row on matrix(_row);

create index idx_col on matrix(_col);

create index idx_pos on matrix(pos);



CREATE OR REPLACE FUNCTION move_robot(direction VARCHAR)
RETURNS VOID AS $$
DECLARE
    robot_row INTEGER;
    robot_col INTEGER;
    target_row INTEGER;
    target_col INTEGER;
    empty_pos INTEGER;
    next_pos VARCHAR;
    move_pos VARCHAR;
BEGIN

    SELECT _row, _col INTO robot_row, robot_col FROM matrix WHERE pos = '@';

    target_row := robot_row;
    target_col := robot_col;

    IF direction = '>' THEN
        target_col := robot_col + 1;
    END IF;

    IF direction = '<' THEN
        target_col := robot_col - 1;
    END IF;

    IF direction = '^' THEN
        target_row := robot_row - 1;
    END IF;

    IF direction = 'v' THEN
        target_row := robot_row + 1;
    END IF;

    empty_pos := (select count(*) from matrix where _row = target_row AND _col = target_col AND pos = '.');

    IF empty_pos = 1 THEN
        IF direction = '>' THEN
            UPDATE matrix SET _col = (CASE WHEN _col = robot_col THEN _col + 1 ELSE _col - 1 END) 
            WHERE _row = robot_row AND _col IN (robot_col, robot_col + 1);
        END IF;

        IF direction = '<' THEN
            UPDATE matrix SET _col = (CASE WHEN _col = robot_col THEN _col - 1 ELSE _col + 1 END) 
            WHERE _row = robot_row AND _col IN (robot_col, robot_col - 1);
        END IF;

        IF direction = '^' THEN
            UPDATE matrix SET _row = (CASE WHEN _row = robot_row THEN _row - 1 ELSE _row + 1 END) 
            WHERE _row IN (robot_row, robot_row - 1) AND _col = robot_col;
        END IF;

        IF direction = 'v' THEN
            UPDATE matrix SET _row = (CASE WHEN _row = robot_row THEN _row + 1 ELSE _row - 1 END) 
            WHERE _row IN (robot_row, robot_row + 1) AND _col = robot_col;
        END IF;
    ELSE
        IF direction = '>' THEN
            next_pos := (select replace(substring(string_agg(pos, '' order by _col), robot_col + 1), '[]', 'O') from matrix where _row = robot_row);
            move_pos := (select (regexp_matches(next_pos, '^(O+\.)'))[1]);
            move_pos := replace(move_pos, 'O', '[]');
        END IF;

        IF direction = '<' THEN
            next_pos := (select reverse(replace(substring(string_agg(pos, '' order by _col), 1, robot_col - 1), '[]', 'O')) from matrix where _row = robot_row);
            move_pos := (select (regexp_matches(next_pos, '^(O+\.)'))[1]);
            move_pos := replace(move_pos, 'O', '[]');
        END IF;

        IF direction = '^' THEN
            next_pos := (select reverse(substring(string_agg(pos, '' order by _row), 1, robot_row - 1)) from matrix where _col = robot_col);
            move_pos := (select (regexp_matches(next_pos, '^((\[|\])+\.)'))[1]);
        END IF;

        IF direction = 'v' THEN
            next_pos := (select substring(string_agg(pos, '' order by _row), robot_row + 1) from matrix where _col = robot_col);
            move_pos := (select (regexp_matches(next_pos, '^((\[|\])+\.)'))[1]);
        END IF;

        IF move_pos IS NULL THEN
            RETURN; 
        END IF;

        IF direction = '>' THEN
            UPDATE matrix set _col = (case when _col = robot_col + length(move_pos) THEN robot_col ELSE _col + 1 END)
            WHERE _row = robot_row
            AND _col between robot_col AND robot_col + length(move_pos);
        END IF;

        IF direction = '<' THEN
            UPDATE matrix set _col = (case when _col = robot_col - length(move_pos) THEN robot_col ELSE _col - 1 END)
            WHERE _row = robot_row
            AND _col between robot_col - length(move_pos) AND robot_col;
        END IF;

        IF direction = '^' THEN
            UPDATE matrix set pos = t.pos
            FROM (
                with recursive boxes AS (
                    SELECT _row, _col,
                           CASE WHEN up_pos like '%#%' THEN 0
                                WHEN up_pos like '%[%' OR up_pos like '%]%' THEN 1
                                ELSE 2
                            END as flag
                    FROM (
                        SELECT _row, _col,
                              (select string_agg(pos, '' order by _col) from matrix where _row = t._row - 1 and _col in (t._col, t._col + 1)) as up_pos
                        FROM (
                            SELECT _row, case when pos = '[' then _col else _col - 1 end as _col
                            FROM matrix 
                            WHERE _row = robot_row - 1 
                            AND _col = robot_col
                        ) t
                    ) t

                    UNION ALL

                    SELECT _row, _col,
                           CASE WHEN up_pos like '%#%' THEN 0
                                WHEN up_pos like '%[%' OR up_pos like '%]%' THEN 1
                                ELSE 2
                            END as flag
                    FROM (
                        SELECT b._row, b._col,
                               (select string_agg(pos, '' order by _col) from matrix where _row = b._row - 1 and _col in (b._col, b._col + 1)) as up_pos
                        FROM boxes a
                        JOIN matrix b 
                        ON b._row = a._row - 1
                        AND b.pos = '['
                        AND (b._col = a._col OR b._col = a._col - 1 OR b._col = a._col + 1)
                        AND flag = 1
                    ) t
                ), moved_boxes AS (
                    SELECT _row, _col, '[' as pos
                    FROM boxes b
                    WHERE not exists (select * From boxes where flag = 0)

                    UNION ALL 

                    SELECT _row, _col + 1, ']' as pos
                    FROM boxes b
                    WHERE not exists (select * From boxes where flag = 0)

                    UNION ALL

                    SELECT robot_row, robot_col, '@' as pos
                    WHERE not exists (select * From boxes where flag = 0)
                )
                SELECT coalesce(a._row, b._row) as _row,
                       coalesce(a._col, b._col) as _col,
                       coalesce(a.pos, '.') as pos
                FROM (select _row - 1 as _row, _col, pos from moved_boxes) a
                FULL OUTER JOIN moved_boxes b
                ON a._row = b._row
                AND a._col = b._col
                
            ) t
            WHERE matrix._row = t._row
            AND matrix._col = t._col;
        END IF;

        IF direction = 'v' THEN
            UPDATE matrix set pos = t.pos
            FROM (
                with recursive boxes AS (
                    SELECT _row, _col,
                           CASE WHEN up_pos like '%#%' THEN 0
                                WHEN up_pos like '%[%' OR up_pos like '%]%' THEN 1
                                ELSE 2
                            END as flag
                    FROM (
                        SELECT _row, _col,
                              (select string_agg(pos, '' order by _col) from matrix where _row = t._row + 1 and _col in (t._col, t._col + 1)) as up_pos
                        FROM (
                            SELECT _row, case when pos = '[' then _col else _col - 1 end as _col
                            FROM matrix 
                            WHERE _row = robot_row + 1 
                            AND _col = robot_col
                        ) t
                    ) t

                    UNION ALL

                    SELECT _row, _col,
                           CASE WHEN up_pos like '%#%' THEN 0
                                WHEN up_pos like '%[%' OR up_pos like '%]%' THEN 1
                                ELSE 2
                            END as flag
                    FROM (
                        SELECT b._row, b._col,
                               (select string_agg(pos, '' order by _col) from matrix where _row = b._row + 1 and _col in (b._col, b._col + 1)) as up_pos
                        FROM boxes a
                        JOIN matrix b 
                        ON b._row = a._row + 1
                        AND b.pos = '['
                        AND (b._col = a._col OR b._col = a._col - 1 OR b._col = a._col + 1)
                        AND flag = 1
                    ) t
                ), moved_boxes AS (
                    SELECT _row, _col, '[' as pos
                    FROM boxes b
                    WHERE not exists (select * From boxes where flag = 0)

                    UNION ALL 

                    SELECT _row, _col + 1, ']' as pos
                    FROM boxes b
                    WHERE not exists (select * From boxes where flag = 0)

                    UNION ALL

                    SELECT robot_row, robot_col, '@' as pos
                    WHERE not exists (select * From boxes where flag = 0)
                )
                SELECT coalesce(a._row, b._row) as _row,
                       coalesce(a._col, b._col) as _col,
                       coalesce(a.pos, '.') as pos
                FROM (select _row + 1 as _row, _col, pos from moved_boxes) a
                FULL OUTER JOIN moved_boxes b
                ON a._row = b._row
                AND a._col = b._col
                
            ) t
            WHERE matrix._row = t._row
            AND matrix._col = t._col;
        END IF;


    END IF;
END;
$$ LANGUAGE plpgsql;


# day 16

CREATE OR REPLACE FUNCTION find_dot_ranges(input_str text)
RETURNS TABLE(start_pos int, end_pos int) AS $$
DECLARE
    i int := 1;
    n int := length(input_str);
    in_dot_sequence boolean := false;
    current_start int;
BEGIN
    WHILE i <= n LOOP
        -- 当遇到点且不在点序列中时，开始新的序列
        IF substring(input_str FROM i FOR 1) IN ('.', 'S', 'E') AND NOT in_dot_sequence THEN
            current_start := i;
            in_dot_sequence := true;
        -- 当遇到非点且正在点序列中时，结束当前序列
        ELSIF substring(input_str FROM i FOR 1) NOT IN ('.', 'S', 'E') AND in_dot_sequence THEN
            start_pos := current_start;
            end_pos := i - 1;
            RETURN NEXT;
            in_dot_sequence := false;
        END IF;
        
        i := i + 1;
    END LOOP;
    
    -- 处理字符串以点结尾的情况
    IF in_dot_sequence THEN
        start_pos := current_start;
        end_pos := n;
        RETURN NEXT;
    END IF;
    
    RETURN;
END;
$$ LANGUAGE plpgsql;

CREATE OR REPLACE FUNCTION split_range(low int, high int, splits int[])
RETURNS TABLE(start_pos int, end_pos int) AS $$
DECLARE
    current_value int := low;
BEGIN
    IF splits is null THEN
        start_pos := low;
        end_pos := high;
        RETURN NEXT;
    ELSE
        FOR i IN 1..#splits LOOP
            IF splits[i] > current_value THEN
                start_pos := current_value;
                end_pos := splits[i];
                current_value = splits[i];
                RETURN NEXT;
            END IF;
        END LOOP;

        IF high > current_value THEN
            start_pos := current_value;
            end_pos := high;
            RETURN NEXT;
        END IF;
    END IF;
END;
$$ LANGUAGE plpgsql;


with recursive rows as (
    SELECT (row_number() over ()) :: INTEGER as _row, line
    FROM lance_input
), matrix AS (
    SELECT _row :: INTEGER, x.idx :: INTEGER as _col, x.pos
    FROM rows, regexp_split_to_table(line, '') with ordinality as x(pos, idx)
), cols AS (
    SELECT _col, string_agg(pos, '' order by _row) as line
    FROM matrix
    GROUP BY _col
), rows_range AS (
    SELECT _row, start_pos, end_pos
    FROM rows, find_dot_ranges(line) t
    WHERE t.start_pos < t.end_pos
), cols_range AS (
    SELECT _col, start_pos, end_pos
    FROM cols, find_dot_ranges(line) t
    WHERE t.start_pos < t.end_pos
), rows_new_range AS (
    SELECT t._row, s.start_pos as _col, s.end_pos as next_col
    FROM (
        SELECT a._row, a.start_pos, a.end_pos, b.pos_array
        FROM rows_range a
        LEFT JOIN (
            SELECT a._row, a.start_pos, a.end_pos, array_agg(b._col order by b._col) as pos_array
            FROM rows_range a
            JOIN cols_range b
            ON a._row between b.start_pos and b.end_pos
            AND b._col between a.start_pos and a.end_pos
            GROUP BY a._row, a.start_pos, a.end_pos
        ) b
        ON a._row = b._row
        AND a.start_pos = b.start_pos
        AND a.end_pos = b.end_pos
    ) t, split_range(start_pos, end_pos, pos_array) s
), cols_new_range AS (
    SELECT t._col, s.start_pos as _row, s.end_pos as next_row
    FROM (
        SELECT a._col, a.start_pos, a.end_pos, b.pos_array
        FROM cols_range a
        LEFT JOIN (
            SELECT b._col, b.start_pos, b.end_pos, array_agg(a._row order by a._row) as pos_array
            FROM rows_range a
            JOIN cols_range b
            ON a._row between b.start_pos and b.end_pos
            AND b._col between a.start_pos and a.end_pos
            GROUP BY b._col, b.start_pos, b.end_pos
        ) b
        ON a._col = b._col
        AND a.start_pos = b.start_pos
        AND a.end_pos = b.end_pos
    ) t, split_range(start_pos, end_pos, pos_array) s
), all_range AS (
    SELECT _row as start_row, _col as start_col, _row as end_row, next_col as end_col, 'E' as direction
    FROM rows_new_range

    UNION ALL

    SELECT _row as start_row, next_col as start_col, _row as end_row, _col as end_col, 'W' as direction
    FROM rows_new_range

    UNION ALL

    SELECT _row as start_row, _col as start_col, next_row as end_row, _col as end_col, 'S' as direction
    FROM cols_new_range

    UNION ALL

    SELECT next_row as start_row, _col as start_col, _row as end_row, _col as end_col, 'N' as direction
    FROM cols_new_range
), walkthrough AS (
    SELECT _row, _col, 'E' as direction, 0 as steps, 0 as turns, array[_row * 10000 + _col] as path
    FROM matrix
    WHERE pos = 'S'

    UNION ALL

    SELECT *
    FROM (
        WITH walkthrough_inner as (select * From walkthrough)
        SELECT b.end_row as _row, 
               b.end_col as _col, 
               b.direction, 
               a.steps + abs(b.end_row - b.start_row) + abs(b.end_col - b.start_col) as steps,
               case when a.direction != b.direction then turns + 1 else turns end as turns,
               path || (b.end_row * 10000 + b.end_col) as path
        FROM walkthrough_inner a
        JOIN all_range b
        ON a._row = b.start_row
        AND a._col = b.start_col
        AND NOT (b.end_row * 10000 + b.end_col) = ANY(a.path)
        WHERE NOT EXISTS (select * From walkthrough_inner where _row = 2 and _col = 16)
    ) t

)
SELECT * FROM walkthrough;




with recursive rows as (
    SELECT (row_number() over ()) :: INTEGER as _row, line
    FROM lance_input
), matrix AS (
    SELECT _row :: INTEGER, x.idx :: INTEGER as _col, x.pos
    FROM rows, regexp_split_to_table(line, '') with ordinality as x(pos, idx)
), cols AS (
    SELECT _col, string_agg(pos, '' order by _row) as line
    FROM matrix
    GROUP BY _col
), rows_range AS (
    SELECT _row, start_pos, end_pos
    FROM rows, find_dot_ranges(line) t
    WHERE t.start_pos < t.end_pos
), cols_range AS (
    SELECT _col, start_pos, end_pos
    FROM cols, find_dot_ranges(line) t
    WHERE t.start_pos < t.end_pos
), rows_new_range AS (
    SELECT t._row, s.start_pos as _col, s.end_pos as next_col
    FROM (
        SELECT a._row, a.start_pos, a.end_pos, b.pos_array
        FROM rows_range a
        LEFT JOIN (
            SELECT a._row, a.start_pos, a.end_pos, array_agg(b._col order by b._col) as pos_array
            FROM rows_range a
            JOIN cols_range b
            ON a._row between b.start_pos and b.end_pos
            AND b._col between a.start_pos and a.end_pos
            GROUP BY a._row, a.start_pos, a.end_pos
        ) b
        ON a._row = b._row
        AND a.start_pos = b.start_pos
        AND a.end_pos = b.end_pos
    ) t, split_range(start_pos, end_pos, pos_array) s
), cols_new_range AS (
    SELECT t._col, s.start_pos as _row, s.end_pos as next_row
    FROM (
        SELECT a._col, a.start_pos, a.end_pos, b.pos_array
        FROM cols_range a
        LEFT JOIN (
            SELECT b._col, b.start_pos, b.end_pos, array_agg(a._row order by a._row) as pos_array
            FROM rows_range a
            JOIN cols_range b
            ON a._row between b.start_pos and b.end_pos
            AND b._col between a.start_pos and a.end_pos
            GROUP BY b._col, b.start_pos, b.end_pos
        ) b
        ON a._col = b._col
        AND a.start_pos = b.start_pos
        AND a.end_pos = b.end_pos
    ) t, split_range(start_pos, end_pos, pos_array) s
), all_range AS (
    SELECT _row as start_row, _col as start_col, _row as end_row, next_col as end_col, 'E' as direction
    FROM rows_new_range

    UNION ALL

    SELECT _row as start_row, next_col as start_col, _row as end_row, _col as end_col, 'W' as direction
    FROM rows_new_range

    UNION ALL

    SELECT _row as start_row, _col as start_col, next_row as end_row, _col as end_col, 'S' as direction
    FROM cols_new_range

    UNION ALL

    SELECT next_row as start_row, _col as start_col, _row as end_row, _col as end_col, 'N' as direction
    FROM cols_new_range
), walkthrough AS (
    SELECT _row, _col, 'E' as direction, 0 as steps, 0 as turns, array[_row * 10000 + _col] as path
    FROM matrix
    WHERE pos = 'S'

    UNION ALL


    SELECT _row, _col, direction, steps, turns, path
    FROM (
        WITH walkthrough_inner as (
            SELECT _row, _col, direction, steps, turns, path
            FROM (
                SELECT *, rank() over (partition by _row, _col, direction order by turns * 1000 + steps) as rn
                From walkthrough
            ) t
            WHERE rn = 1
        )
        SELECT b.end_row as _row, 
               b.end_col as _col, 
               b.direction, 
               a.steps + abs(b.end_row - b.start_row) + abs(b.end_col - b.start_col) as steps,
               case when a.direction != b.direction then turns + 1 else turns end as turns,
               path || (b.end_row * 10000 + b.end_col) as path
        FROM walkthrough_inner a
        JOIN all_range b
        ON a._row = b.start_row
        AND a._col = b.start_col
        AND NOT (b.end_row * 10000 + b.end_col) = ANY(a.path)
    ) t
)
SELECT * FROM walkthrough;






WITH top_path AS (
    select path from (select rank() over (order by turns * 1000 + steps) as rn, path from lance_test where _row = 2 and _col = 140) t where rn = 1
), all_route AS (
    SELECT DISTINCT 
        path[i] AS first,
        path[i + 1] AS next
    FROM 
        top_path,
        generate_series(
            array_lower(path, 1),
            array_upper(path, 1) - 1
        ) AS i
), all_coordinates AS (
    SELECT first / 10000 as first_row, 
           first % 10000 as first_col, 
           next / 10000 as next_row, 
           next % 10000 as next_col
    FROM all_route
)
SELECT sum(case when first_row = next_row then abs(first_col - next_col) - 1 else abs(first_row - next_row) - 1 end)
FROM all_coordinates

UNION ALL

SELECT COUNT(DISTINCT coordinate)
FROM (
    SELECT first as coordinate
    FROM all_route
    UNION ALL
    SELECT next as coordinate
    FROM all_route
) t


# day 18

with recursive matrix AS (
    SELECT m._row, m._col, case when n._col is not null then '#' else '.' end as pos
    FROM (
        SELECT _row, _col
        FROM generate_series(1, 71) _row, generate_series(1, 71) _col
    ) m
    LEFT JOIN (select split_part(line, ',', 2) :: integer + 1 as _row, split_part(line, ',', 1) :: integer + 1 as _col from lance_input limit 1024) n
    ON m._row = n._row
    AND m._col = n._col
), rows AS (
    SELECT _row, string_agg(pos, '' order by _col) as line
    FROM matrix
    GROUP BY _row
), cols AS (
    SELECT _col, string_agg(pos, '' order by _row) as line
    FROM matrix
    GROUP BY _col
), rows_range AS (
    SELECT _row, start_pos, end_pos
    FROM rows, find_dot_ranges(line) t
    WHERE t.start_pos < t.end_pos
), cols_range AS (
    SELECT _col, start_pos, end_pos
    FROM cols, find_dot_ranges(line) t
    WHERE t.start_pos < t.end_pos
), rows_new_range AS (
    SELECT t._row, s.start_pos as _col, s.end_pos as next_col
    FROM (
        SELECT a._row, a.start_pos, a.end_pos, b.pos_array
        FROM rows_range a
        LEFT JOIN (
            SELECT a._row, a.start_pos, a.end_pos, array_agg(b._col order by b._col) as pos_array
            FROM rows_range a
            JOIN cols_range b
            ON a._row between b.start_pos and b.end_pos
            AND b._col between a.start_pos and a.end_pos
            GROUP BY a._row, a.start_pos, a.end_pos
        ) b
        ON a._row = b._row
        AND a.start_pos = b.start_pos
        AND a.end_pos = b.end_pos
    ) t, split_range(start_pos, end_pos, pos_array) s
), cols_new_range AS (
    SELECT t._col, s.start_pos as _row, s.end_pos as next_row
    FROM (
        SELECT a._col, a.start_pos, a.end_pos, b.pos_array
        FROM cols_range a
        LEFT JOIN (
            SELECT b._col, b.start_pos, b.end_pos, array_agg(a._row order by a._row) as pos_array
            FROM rows_range a
            JOIN cols_range b
            ON a._row between b.start_pos and b.end_pos
            AND b._col between a.start_pos and a.end_pos
            GROUP BY b._col, b.start_pos, b.end_pos
        ) b
        ON a._col = b._col
        AND a.start_pos = b.start_pos
        AND a.end_pos = b.end_pos
    ) t, split_range(start_pos, end_pos, pos_array) s
), all_range AS (
    SELECT _row as start_row, _col as start_col, _row as end_row, next_col as end_col, 'E' as direction
    FROM rows_new_range

    UNION ALL

    SELECT _row as start_row, next_col as start_col, _row as end_row, _col as end_col, 'W' as direction
    FROM rows_new_range

    UNION ALL

    SELECT _row as start_row, _col as start_col, next_row as end_row, _col as end_col, 'S' as direction
    FROM cols_new_range

    UNION ALL

    SELECT next_row as start_row, _col as start_col, _row as end_row, _col as end_col, 'N' as direction
    FROM cols_new_range
), walkthrough AS (
    SELECT _row, _col, 0 as steps, array[_row * 10000 + _col] as path
    FROM matrix
    WHERE _row = 1 and _col = 1

    UNION ALL


    SELECT _row, _col, steps, path
    FROM (
        WITH walkthrough_inner as (
            SELECT _row, _col, steps, path
            FROM (
                SELECT *, row_number() over (partition by _row, _col order by steps) as rn
                From walkthrough
            ) t
            WHERE rn = 1
        )
        SELECT b.end_row as _row, 
               b.end_col as _col, 
               a.steps + abs(b.end_row - b.start_row) + abs(b.end_col - b.start_col) as steps,
               path || (b.end_row * 10000 + b.end_col) as path
        FROM walkthrough_inner a
        JOIN all_range b
        ON a._row = b.start_row
        AND a._col = b.start_col
        AND NOT (b.end_row * 10000 + b.end_col) = ANY(a.path)
    ) t
)
SELECT * FROM walkthrough;


# day 19
with recursive rows as (
    SELECT row_number() over () as _row, line
    FROM lance_input
), towels as (
    SELECT replace(line, ', ', '|') as line
    FROM rows
    where _row = 1
), design as (
    SELECT _row, line
    FROM rows
    WHERE _row > 2
)
SELECT string_agg(distinct result::text, '') 
FROM (
    SELECT a._row, unnest(regexp_split_to_array(a.line, b.line)) as result
    FROM design a, towels b
) t 
GROUP BY _row;



with recursive rows as (
    SELECT row_number() over () as _row, line
    FROM lance_input
), towels as (
    SELECT regexp_split_to_table(line, ', ') as line
    FROM rows
    where _row = 1
), design as (
    SELECT _row, line
    FROM rows
    WHERE _row > 2
), trim_design as (
    SELECT 1 as step, _row, line
    FROM design 

    UNION ALL

    SELECT * 
    FROM (
        WITH trim_design_inner as (select * From trim_design)
        SELECT step + 1 as step, _row, substring(a.line, length(b.line) + 1) as line
        FROM trim_design_inner a, towels b
        WHERE starts_with(a.line, b.line)
        AND length(a.line) > 0
        AND not exists (select * from trim_design_inner where line = '')
    ) t
    
)
SELECT * FROM trim_design;


CREATE OR REPLACE FUNCTION is_valid(design varchar, towels text[])
RETURNS BOOLEAN AS $$
DECLARE
  check_result BOOLEAN;
BEGIN
    -- empy string
    IF design = '' THEN
        RETURN TRUE;
    END IF;

    -- read from table
    check_result := (SELECT _result FROM results WHERE _design = design);
    IF check_result is not null THEN
        return check_result;
    END IF;

    FOR i IN 1..array_length(towels, 1) LOOP
        CONTINUE WHEN NOT starts_with(design, towels[i]);

        check_result := is_valid(substring(design, length(towels[i]) + 1), towels);
        INSERT INTO results VALUES(substring(design, length(towels[i]) + 1), check_result) on conflict(_design) do nothing;

        CONTINUE WHEN NOT check_result;
        
        RETURN TRUE;
    END LOOP;

    -- insert false result
    INSERT INTO results VALUES(design, FALSE) on conflict(_design) do nothing;
    RETURN FALSE;
END;
$$ LANGUAGE plpgsql;


with rows as (
    SELECT row_number() over () as _row, line
    FROM lance_input
), towels as (
    SELECT line
    FROM rows
    where _row = 1
), design as (
    SELECT _row, line
    FROM rows
    WHERE _row > 2
)
SELECT COUNT(*)
FROM (
    SELECT design.line, is_valid(design.line, regexp_split_to_array(towels.line, ', ')) as is_valid
    FROM design, towels
) t
WHERE is_valid;


CREATE OR REPLACE FUNCTION is_valid_cnt(design varchar, towels text[])
RETURNS BIGINT AS $$
DECLARE
  check_result BIGINT;
  find_result BIGINT;
BEGIN
    -- empy string
    IF design = '' THEN
        RETURN 1;
    END IF;

    -- read from table
    check_result := (SELECT _result FROM results WHERE _design = design);
    IF check_result is not null THEN
        return check_result;
    END IF;

    -- init result
    check_result := 0;
    FOR i IN 1..array_length(towels, 1) LOOP
        CONTINUE WHEN NOT starts_with(design, towels[i]);

        find_result := is_valid_cnt(substring(design, length(towels[i]) + 1), towels);
        check_result := check_result + find_result;
    END LOOP;

    -- insert result
    INSERT INTO results VALUES(design, check_result) on conflict(_design) do nothing;
    RETURN check_result;
END;
$$ LANGUAGE plpgsql;


with rows as (
    SELECT row_number() over () as _row, line
    FROM lance_input
), towels as (
    SELECT line
    FROM rows
    where _row = 1
), design as (
    SELECT _row, line
    FROM rows
    WHERE _row > 2
)
SELECT SUM(is_valid_cnt)
FROM (
    SELECT design.line, is_valid_cnt(design.line, regexp_split_to_array(towels.line, ', ')) as is_valid_cnt
    FROM design, towels
) t


# day 20
with recursive rows as (
    SELECT (row_number() over ()) :: INTEGER as _row, line
    FROM lance_input
), matrix AS (
    SELECT _row :: INTEGER, x.idx :: INTEGER as _col, x.pos
    FROM rows, regexp_split_to_table(line, '') with ordinality as x(pos, idx)
), cols AS (
    SELECT _col, string_agg(pos, '' order by _row) as line
    FROM matrix
    GROUP BY _col
), rows_range AS (
    SELECT _row, start_pos, end_pos
    FROM rows, find_dot_ranges(line) t
    WHERE t.start_pos < t.end_pos
), cols_range AS (
    SELECT _col, start_pos, end_pos
    FROM cols, find_dot_ranges(line) t
    WHERE t.start_pos < t.end_pos
), rows_new_range AS (
    SELECT t._row, s.start_pos as _col, s.end_pos as next_col
    FROM (
        SELECT a._row, a.start_pos, a.end_pos, b.pos_array
        FROM rows_range a
        LEFT JOIN (
            SELECT a._row, a.start_pos, a.end_pos, array_agg(b._col order by b._col) as pos_array
            FROM rows_range a
            JOIN cols_range b
            ON a._row between b.start_pos and b.end_pos
            AND b._col between a.start_pos and a.end_pos
            GROUP BY a._row, a.start_pos, a.end_pos
        ) b
        ON a._row = b._row
        AND a.start_pos = b.start_pos
        AND a.end_pos = b.end_pos
    ) t, split_range(start_pos, end_pos, pos_array) s
), cols_new_range AS (
    SELECT t._col, s.start_pos as _row, s.end_pos as next_row
    FROM (
        SELECT a._col, a.start_pos, a.end_pos, b.pos_array
        FROM cols_range a
        LEFT JOIN (
            SELECT b._col, b.start_pos, b.end_pos, array_agg(a._row order by a._row) as pos_array
            FROM rows_range a
            JOIN cols_range b
            ON a._row between b.start_pos and b.end_pos
            AND b._col between a.start_pos and a.end_pos
            GROUP BY b._col, b.start_pos, b.end_pos
        ) b
        ON a._col = b._col
        AND a.start_pos = b.start_pos
        AND a.end_pos = b.end_pos
    ) t, split_range(start_pos, end_pos, pos_array) s
), all_range AS (
    SELECT _row as start_row, _col as start_col, _row as end_row, next_col as end_col, 'E' as direction
    FROM rows_new_range

    UNION ALL

    SELECT _row as start_row, next_col as start_col, _row as end_row, _col as end_col, 'W' as direction
    FROM rows_new_range

    UNION ALL

    SELECT _row as start_row, _col as start_col, next_row as end_row, _col as end_col, 'S' as direction
    FROM cols_new_range

    UNION ALL

    SELECT next_row as start_row, _col as start_col, _row as end_row, _col as end_col, 'N' as direction
    FROM cols_new_range
), walkthrough AS (
    SELECT _row, _col, 'E' as direction, 0 as steps, array[_row * 10000 + _col] as path
    FROM matrix
    WHERE pos = 'S'

    UNION ALL

    SELECT *
    FROM (
        WITH walkthrough_inner as (select * From walkthrough)
        SELECT b.end_row as _row, 
               b.end_col as _col, 
               b.direction, 
               a.steps + abs(b.end_row - b.start_row) + abs(b.end_col - b.start_col) as steps,
               path || (b.end_row * 10000 + b.end_col) as path
        FROM walkthrough_inner a
        JOIN all_range b
        ON a._row = b.start_row
        AND a._col = b.start_col
        AND NOT (b.end_row * 10000 + b.end_col) = ANY(a.path)
    ) t

), all_steps AS (
    SELECT CASE WHEN last_row is null THEN current_row
                WHEN last_row < current_row THEN last_row + seq
                WHEN last_row > current_row THEN last_row - seq
                ELSE current_row
            END as _row,
           CASE WHEN last_col is null THEN current_col
                WHEN last_col < current_col THEN last_col + seq
                WHEN last_col > current_col THEN last_col - seq
                ELSE current_col
            END as _col,
           row_number() over (order by rn, seq) as rn
    FROM (
        SELECT row_number() over () as rn,
               lag(_row) over() as last_row, 
               lag(_col) over() as last_col,
               _row as current_row,
               _col as current_col
        FROM walkthrough
    ) s, generate_series(1, 15) as seq
    WHERE seq <= abs(last_row - current_row)
    OR seq <= abs(last_col - current_col)
    OR (last_row is null AND seq = 1)
)
SELECT save_steps, count(*) 
FROM (
    SELECT s._row as start_row, s._col as start_col,
           t._row as end_row, t._col as end_col,
           t.rn - s.rn - 2 as save_steps 
    FROM all_steps s
    JOIN all_steps t
    ON s.rn < t.rn
    AND ((abs(s._row - t._row) = 2 AND s._col = t._col)
    OR (abs(s._col - t._col) = 2 AND s._row = t._row)) 
) t 
GROUP BY save_steps;


SELECT save_steps, count(*)  as cnt
FROM (
    SELECT s._row as start_row, s._col as start_col,
           t._row as end_row, t._col as end_col,
           t.rn - s.rn - (abs(s._row - t._row) + abs(s._col - t._col)) as save_steps 
    FROM all_steps s
    JOIN all_steps t
    ON s.rn < t.rn
    AND abs(s._row - t._row) + abs(s._col - t._col) <= 20 
) t 
GROUP BY save_steps

# day 21

    +---+---+
    | ^ | A |
+---+---+---+
| < | v | > |
+---+---+---+

create table direct_keypad(direction varchar(1), _row integer, _col integer);
insert into direct_keypad values('^', 1, 2);
insert into direct_keypad values('A', 1, 3);
insert into direct_keypad values('<', 2, 1);
insert into direct_keypad values('v', 2, 2);
insert into direct_keypad values('>', 2, 3);

+---+---+---+
| 7 | 8 | 9 |
+---+---+---+
| 4 | 5 | 6 |
+---+---+---+
| 1 | 2 | 3 |
+---+---+---+
    | 0 | A |
    +---+---+

create table numeric_keypad(num varchar(1), _row integer, _col integer);
insert into numeric_keypad values('1', 3, 1);
insert into numeric_keypad values('2', 3, 2);
insert into numeric_keypad values('3', 3, 3);
insert into numeric_keypad values('4', 2, 1);
insert into numeric_keypad values('5', 2, 2);
insert into numeric_keypad values('6', 2, 3);
insert into numeric_keypad values('7', 1, 1);
insert into numeric_keypad values('8', 1, 2);
insert into numeric_keypad values('9', 1, 3);
insert into numeric_keypad values('0', 4, 2);
insert into numeric_keypad values('A', 4, 3);



WITH numeric_path AS (
    SELECT start_num, end_num, path || 'A' as path
    FROM (
        SELECT a.num as start_num, b.num as end_num,
               CASE WHEN a._row <= b._row and a._col <= b._col THEN repeat('>', b._col - a._col) || repeat('v', b._row - a._row)
                    WHEN a._row >= b._row and a._col <= b._col THEN repeat('>', b._col - a._col) || repeat('^', a._row - b._row)
                    WHEN a._row <= b._row and a._col >= b._col THEN repeat('v', b._row - a._row) || repeat('<', a._col - b._col)
                    WHEN a._row >= b._row and a._col >= b._col THEN repeat('^', a._row - b._row) || repeat('<', a._col - b._col)
                END as path
        FROM numeric_keypad a
        JOIN numeric_keypad b
        ON a.num != b.num
    ) t
), direction_path AS (
    SELECT start_direction, end_direction, path || 'A' as path
    FROM (
        SELECT a.direction as start_direction, b.direction as end_direction,
               CASE WHEN a._row <= b._row and a._col <= b._col THEN repeat('>', b._col - a._col) || repeat('v', b._row - a._row)
                    WHEN a._row >= b._row and a._col <= b._col THEN repeat('>', b._col - a._col) || repeat('^', a._row - b._row)
                    WHEN a._row <= b._row and a._col >= b._col THEN repeat('v', b._row - a._row) || repeat('<', a._col - b._col)
                    WHEN a._row >= b._row and a._col >= b._col THEN repeat('^', a._row - b._row) || repeat('<', a._col - b._col)
                END as path
        FROM direct_keypad a
        JOIN direct_keypad b
        ON a.direction != b.direction
    ) t
), origin AS (
    SELECT row_number() over () as rn, line
    FROM lance_input
), move AS (
    SELECT rn, coalesce(lag(button) over (partition by rn order by idx), 'A') as pre_button, button, idx
    FROM origin, regexp_split_to_table(line, '') with ordinality as x(button, idx)
), path_1 AS (
    SELECT a.rn, string_agg(b.path, '' order by idx) as path
    FROM move a
    JOIN numeric_path b
    ON a.pre_button = b.start_num
    AND a.button = b.end_num
    GROUP by a.rn
), robot_move AS (
    SELECT rn, coalesce(lag(button) over (partition by rn order by idx), 'A') as pre_button, button, idx
    FROM path_1, regexp_split_to_table(path, '') with ordinality as x(button, idx)
), path_2 AS (
    SELECT a.rn, string_agg(coalesce(b.path, 'A'), '' order by idx) as path
    FROM robot_move a
    LEFT JOIN direction_path b
    ON a.pre_button = b.start_direction
    AND a.button = b.end_direction
    GROUP by a.rn
), robot_move_2 AS (
    SELECT rn, coalesce(lag(button) over (partition by rn order by idx), 'A') as pre_button, button, idx
    FROM path_2, regexp_split_to_table(path, '') with ordinality as x(button, idx)
), path_3 AS (
    SELECT a.rn, string_agg(coalesce(b.path, 'A'), '' order by idx) as path
    FROM robot_move_2 a
    LEFT JOIN direction_path b
    ON a.pre_button = b.start_direction
    AND a.button = b.end_direction
    GROUP by a.rn
)
SELECT substring(line, 1, 3) :: INTEGER as num, length(path) as path_len
FROM path_3 a
JOIN origin b
ON a.rn = b.rn;



WITH numeric_path AS (
    SELECT start_num, end_num, path || 'A' as path
    FROM (
        SELECT a.num as start_num, b.num as end_num,
               CASE WHEN a.num in ('1','4','7') AND b.num in ('0','A') THEN repeat('>', b._col - a._col) || repeat('v', b._row - a._row)
                    WHEN b.num in ('1','4','7') AND a.num in ('0','A') THEN repeat('^', a._row - b._row) || repeat('<', a._col - b._col)
                    WHEN a._row <= b._row and a._col <= b._col THEN repeat('v', b._row - a._row) || repeat('>', b._col - a._col)
                    WHEN a._row >= b._row and a._col <= b._col THEN repeat('^', a._row - b._row) || repeat('>', b._col - a._col)
                    WHEN a._row <= b._row and a._col >= b._col THEN repeat('<', a._col - b._col) || repeat('v', b._row - a._row)
                    WHEN a._row >= b._row and a._col >= b._col THEN repeat('<', a._col - b._col) || repeat('^', a._row - b._row)
                END as path
        FROM numeric_keypad a
        JOIN numeric_keypad b
        ON a.num != b.num
    ) t
), direction_path AS (
    SELECT start_direction, end_direction, path || 'A' as path
    FROM (
        SELECT a.direction as start_direction, b.direction as end_direction,
               CASE WHEN a.direction in ('^','A') AND b.direction in ('<') THEN repeat('v', b._row - a._row) || repeat('<', a._col - b._col)
                    WHEN b.direction in ('^','A') AND a.direction in ('<') THEN repeat('>', b._col - a._col) || repeat('^', a._row - b._row)
                    WHEN a._row <= b._row and a._col <= b._col THEN repeat('v', b._row - a._row) || repeat('>', b._col - a._col)
                    WHEN a._row >= b._row and a._col <= b._col THEN repeat('^', a._row - b._row) || repeat('>', b._col - a._col)
                    WHEN a._row <= b._row and a._col >= b._col THEN repeat('<', a._col - b._col) || repeat('v', b._row - a._row)
                    WHEN a._row >= b._row and a._col >= b._col THEN repeat('<', a._col - b._col) || repeat('^', a._row - b._row)
                END as path
        FROM direct_keypad a
        JOIN direct_keypad b
        ON a.direction != b.direction
    ) t
), origin AS (
    SELECT row_number() over () as rn, line
    FROM lance_input
), move AS (
    SELECT rn, coalesce(lag(button) over (partition by rn order by idx), 'A') as pre_button, button, idx
    FROM origin, regexp_split_to_table(line, '') with ordinality as x(button, idx)
), path_1 AS (
    SELECT a.rn, string_agg(b.path, '' order by idx) as path
    FROM move a
    JOIN numeric_path b
    ON a.pre_button = b.start_num
    AND a.button = b.end_num
    GROUP by a.rn
), robot_move AS (
    SELECT rn, coalesce(lag(button) over (partition by rn order by idx), 'A') as pre_button, button, idx
    FROM path_1, regexp_split_to_table(path, '') with ordinality as x(button, idx)
), path_2 AS (
    SELECT a.rn, string_agg(coalesce(b.path, 'A'), '' order by idx) as path
    FROM robot_move a
    LEFT JOIN direction_path b
    ON a.pre_button = b.start_direction
    AND a.button = b.end_direction
    GROUP by a.rn
), robot_move_2 AS (
    SELECT rn, coalesce(lag(button) over (partition by rn order by idx), 'A') as pre_button, button, idx
    FROM path_2, regexp_split_to_table(path, '') with ordinality as x(button, idx)
), path_3 AS (
    SELECT a.rn, string_agg(coalesce(b.path, 'A'), '' order by idx) as path
    FROM robot_move_2 a
    LEFT JOIN direction_path b
    ON a.pre_button = b.start_direction
    AND a.button = b.end_direction
    GROUP by a.rn
)
SELECT substring(line, 1, 3) :: INTEGER as num, length(path) as path_len
FROM path_3 a
JOIN origin b
ON a.rn = b.rn;




WITH recursive numeric_path AS (
    SELECT start_num, end_num, path || 'A' as path
    FROM (
        SELECT a.num as start_num, b.num as end_num,
               CASE WHEN a.num in ('1','4','7') AND b.num in ('0','A') THEN repeat('>', b._col - a._col) || repeat('v', b._row - a._row)
                    WHEN b.num in ('1','4','7') AND a.num in ('0','A') THEN repeat('^', a._row - b._row) || repeat('<', a._col - b._col)
                    WHEN a._row <= b._row and a._col <= b._col THEN repeat('v', b._row - a._row) || repeat('>', b._col - a._col)
                    WHEN a._row >= b._row and a._col <= b._col THEN repeat('^', a._row - b._row) || repeat('>', b._col - a._col)
                    WHEN a._row <= b._row and a._col >= b._col THEN repeat('<', a._col - b._col) || repeat('v', b._row - a._row)
                    WHEN a._row >= b._row and a._col >= b._col THEN repeat('<', a._col - b._col) || repeat('^', a._row - b._row)
                END as path
        FROM numeric_keypad a
        JOIN numeric_keypad b
        ON a.num != b.num
    ) t
), direction_path AS (
    SELECT start_direction, end_direction, path || 'A' as path
    FROM (
        SELECT a.direction as start_direction, b.direction as end_direction,
               CASE WHEN a.direction in ('^','A') AND b.direction in ('<') THEN repeat('v', b._row - a._row) || repeat('<', a._col - b._col)
                    WHEN b.direction in ('^','A') AND a.direction in ('<') THEN repeat('>', b._col - a._col) || repeat('^', a._row - b._row)
                    WHEN a._row <= b._row and a._col <= b._col THEN repeat('v', b._row - a._row) || repeat('>', b._col - a._col)
                    WHEN a._row >= b._row and a._col <= b._col THEN repeat('^', a._row - b._row) || repeat('>', b._col - a._col)
                    WHEN a._row <= b._row and a._col >= b._col THEN repeat('<', a._col - b._col) || repeat('v', b._row - a._row)
                    WHEN a._row >= b._row and a._col >= b._col THEN repeat('<', a._col - b._col) || repeat('^', a._row - b._row)
                END as path
        FROM direct_keypad a
        JOIN direct_keypad b
        ON a.direction != b.direction
    ) t
), origin AS (
    SELECT row_number() over () as rn, line
    FROM lance_input
), move AS (
    SELECT rn, coalesce(lag(button) over (partition by rn order by idx), 'A') as pre_button, button, idx
    FROM origin, regexp_split_to_table(line, '') with ordinality as x(button, idx)
), robot_path AS (
    SELECT 0 as step, a.rn, string_agg(b.path, '' order by idx) as path
    FROM move a
    JOIN numeric_path b
    ON a.pre_button = b.start_num
    AND a.button = b.end_num
    GROUP by a.rn

    UNION ALL

    SELECT a.step + 1 as step, a.rn, string_agg(coalesce(b.path, 'A'), '' order by idx) as path
    FROM (
        SELECT step, rn, coalesce(lag(button) over (partition by rn order by idx), 'A') as pre_button, button, idx
        FROM robot_path, regexp_split_to_table(path, '') with ordinality as x(button, idx)
    ) a
    LEFT JOIN direction_path b
    ON a.pre_button = b.start_direction
    AND a.button = b.end_direction
    WHERE a.step < 2
    GROUP by a.step, a.rn
)
SELECT substring(line, 1, 3) :: INTEGER as num, length(path) as path_len
FROM robot_path a
JOIN origin b
ON a.rn = b.rn;


CREATE OR REPLACE FUNCTION count_path(start_button text, end_button text, robots_left integer)
RETURNS BIGINT AS $$
DECLARE
  query_num BIGINT;
  origin_path TEXT;
BEGIN
    -- same button
    IF start_button = end_button THEN
        RETURN 1;
    END IF;

    -- get path length from direction_path
    origin_path := (select path from direction_path where start_direction = start_button and end_direction = end_button);
    IF robots_left = 0 THEN
        RETURN length(origin_path);
    END IF;
 
    -- get length from cache
    query_num := (SELECT path_length FROM cache_path WHERE cache_start = start_button AND cache_end = end_button AND robot_num = robots_left);
 
    IF query_num IS NOT NULL THEN
        return query_num;
    END IF;
 
    query_num := (
    SELECT SUM(CASE WHEN b.start_direction IS NULL THEN 1 ELSE count_path(pre_button, button, robots_left - 1) END) 
    FROM (
        SELECT coalesce(lag(button) over (order by idx), 'A') as pre_button, button, idx
        FROM regexp_split_to_table(origin_path, '') with ordinality as x(button, idx)
    ) a
    LEFT JOIN direction_path b
    ON a.pre_button = b.start_direction
    AND a.button = b.end_direction
    );
 
    INSERT INTO cache_path values(start_button, end_button, robots_left, query_num);
    RAISE NOTICE 'add map: %', (query_num || ' ' || robots_left);
     
    RETURN query_num;
END;
$$ LANGUAGE plpgsql;


WITH numeric_path AS (
    SELECT start_num, end_num, path || 'A' as path
    FROM (
        SELECT a.num as start_num, b.num as end_num,
               CASE WHEN a.num in ('1','4','7') AND b.num in ('0','A') THEN repeat('>', b._col - a._col) || repeat('v', b._row - a._row)
                    WHEN b.num in ('1','4','7') AND a.num in ('0','A') THEN repeat('^', a._row - b._row) || repeat('<', a._col - b._col)
                    WHEN a._row <= b._row and a._col <= b._col THEN repeat('v', b._row - a._row) || repeat('>', b._col - a._col)
                    WHEN a._row >= b._row and a._col <= b._col THEN repeat('^', a._row - b._row) || repeat('>', b._col - a._col)
                    WHEN a._row <= b._row and a._col >= b._col THEN repeat('<', a._col - b._col) || repeat('v', b._row - a._row)
                    WHEN a._row >= b._row and a._col >= b._col THEN repeat('<', a._col - b._col) || repeat('^', a._row - b._row)
                END as path
        FROM numeric_keypad a
        JOIN numeric_keypad b
        ON a.num != b.num
    ) t
), direction_path AS (
    SELECT start_direction, end_direction, path || 'A' as path
    FROM (
        SELECT a.direction as start_direction, b.direction as end_direction,
               CASE WHEN a.direction in ('^','A') AND b.direction in ('<') THEN repeat('v', b._row - a._row) || repeat('<', a._col - b._col)
                    WHEN b.direction in ('^','A') AND a.direction in ('<') THEN repeat('>', b._col - a._col) || repeat('^', a._row - b._row)
                    WHEN a._row <= b._row and a._col <= b._col THEN repeat('v', b._row - a._row) || repeat('>', b._col - a._col)
                    WHEN a._row >= b._row and a._col <= b._col THEN repeat('^', a._row - b._row) || repeat('>', b._col - a._col)
                    WHEN a._row <= b._row and a._col >= b._col THEN repeat('<', a._col - b._col) || repeat('v', b._row - a._row)
                    WHEN a._row >= b._row and a._col >= b._col THEN repeat('<', a._col - b._col) || repeat('^', a._row - b._row)
                END as path
        FROM direct_keypad a
        JOIN direct_keypad b
        ON a.direction != b.direction
    ) t
), origin AS (
    SELECT row_number() over () as rn, line
    FROM lance_input
), move AS (
    SELECT rn, coalesce(lag(button) over (partition by rn order by idx), 'A') as pre_button, button, idx
    FROM origin, regexp_split_to_table(line, '') with ordinality as x(button, idx)
), path_1 AS (
    SELECT a.rn, string_agg(b.path, '' order by idx) as path
    FROM move a
    JOIN numeric_path b
    ON a.pre_button = b.start_num
    AND a.button = b.end_num
    GROUP by a.rn
), robot_move AS (
    SELECT rn, coalesce(lag(button) over (partition by rn order by idx), 'A') as pre_button, button, idx
    FROM path_1, regexp_split_to_table(path, '') with ordinality as x(button, idx)
)
SELECT substring(line, 1, 3) :: INTEGER as num, sum(count_path(pre_button, button, 2)) as path_length 
FROM robot_move a
JOIN origin b
ON a.rn = b.rn
GROUP BY substring(line, 1, 3)

# day 22


CREATE OR REPLACE FUNCTION calculate(secret_number bigint)
RETURNS BIGINT AS $$
DECLARE
  result BIGINT;
  current_secret BIGINT;
BEGIN
    current_secret := (secret_number * 64) # secret_number;
    current_secret := current_secret % 16777216;
    current_secret := (current_secret / 32) # current_secret;
    current_secret := current_secret % 16777216;
    current_secret := (current_secret * 2048) # current_secret;
    current_secret := current_secret % 16777216;
    RETURN current_secret;
END;
$$ LANGUAGE plpgsql;

CREATE OR REPLACE FUNCTION calculate(secret_number bigint)
RETURNS BIGINT AS $$
DECLARE
  result BIGINT;
  current_secret BIGINT;
BEGIN
    current_secret := (secret_number << 6) # secret_number;
    current_secret := current_secret & 16777215;
    current_secret := (current_secret >> 5) # current_secret;
    current_secret := current_secret & 16777215;
    current_secret := (current_secret << 11) # current_secret;
    current_secret := current_secret & 16777215;
    RETURN current_secret;
END;
$$ LANGUAGE plpgsql;

with recursive result AS (
    SELECT 0 as step, line :: BIGINT as id
    FROM lance_input

    UNION ALL

    SELECT step + 1 as step, calculate(id) as id
    FROM result
    WHERE step < 2000
)
select sum(id) From result WHERE step = 2000;


with recursive result AS (
    SELECT row_number() over () as seq, 0 as step, line :: BIGINT as id
    FROM lance_input

    UNION ALL

    SELECT seq, step + 1 as step, calculate(id) as id
    FROM result
    WHERE step <= 2000
), prices AS (
    SELECT seq, step, id, price,  price - lag(price) over (partition by seq order by step) as diff
    FROM (
        SELECT seq, step, id, right(id :: text, 1) :: integer as price
        FROM result
    ) t
), price_list AS (
    SELECT seq, step, id, price, 
           lag(diff, 3) over (partition by seq order by step) as pre_3_diff,
           lag(diff, 2) over (partition by seq order by step) as pre_2_diff,
           lag(diff, 1) over (partition by seq order by step) as pre_1_diff,
           diff
    FROM prices
)
SELECT sum(price) FROM (
    SELECT seq, pre_3_diff, pre_2_diff, pre_1_diff, diff, price, 
           row_number() over (partition by seq, pre_3_diff, pre_2_diff, pre_1_diff, diff order by step) as rn 
    FROM price_list 
    WHERE pre_3_diff is not null 
    AND pre_2_diff is not null 
    AND pre_1_diff is not null 
    AND diff is not null
) t 
WHERE rn = 1 
GROUP BY pre_3_diff, pre_2_diff, pre_1_diff, diff 
ORDER BY 1 desc 
LIMIT 3;


# day 23

with origin AS (
    SELECT least(split_part(line, '-', 1), split_part(line, '-', 2)) as l, 
           greatest(split_part(line, '-', 1), split_part(line, '-', 2)) as r
    FROM lance_input
)
SELECT count(*)
FROM (
    SELECT distinct a.l, a.r, c.r
    FROM origin a
    JOIN origin b
    ON a.r = b.l
    JOIN origin c
    ON a.l = c.l
    AND b.r = c.r
    WHERE left(a.l, 1) = 't' 
    OR left(a.r, 1) = 't' 
    OR left(c.r, 1) = 't'
) t;

with recursive origin AS (
    SELECT least(split_part(line, '-', 1), split_part(line, '-', 2)) as l, 
           greatest(split_part(line, '-', 1), split_part(line, '-', 2)) as r
    FROM lance_input
), all_paths AS (
    SELECT l, r, array[l, r] as path
    FROM origin

    UNION ALL

    SELECT *
    FROM (
        WITH all_paths_inner AS (select * from all_paths)
        SELECT a.l, c.r, a.path || c.r as path
        FROM all_paths_inner a
        JOIN all_paths_inner b
        ON a.path[2:] = b.path[1:array_length(b.path,1) - 1]
        JOIN origin c
        ON a.l = c.l
        AND b.r = c.r
    ) t
) 
SELECT * FROM all_paths; 


# day 24

with recursive origin AS (
    SELECT row_number() over () as rn, line
    FROM lance_input
), input AS (
    SELECT split_part(line, ': ', 1) as key, split_part(line, ': ', 2) :: INTEGER as value
    FROM origin
    WHERE rn < (select rn from origin where line is null)
), gate AS (
    SELECT split_part(line, ' ', 1) as l, 
           split_part(line, ' ', 2) as op,
           split_part(line, ' ', 3) as r,
           split_part(line, ' ', 5) as output
    FROM origin
    WHERE rn > (select rn from origin where line is null)
), gate_output AS (
    SELECT key, value
    FROM input

    UNION ALL

    SELECT key, value
    FROM (
        WITH inner_gate AS (select * from gate_output),
        new_output as (
            SELECT key, value from inner_gate

            UNION ALL

            SELECT output as key,
                   CASE WHEN op = 'AND' THEN b.value & c.value
                        WHEN op = 'OR' THEN b.value | c.value
                        WHEN op = 'XOR' THEN b.value # c.value
                    END as value
            FROM gate a
            JOIN inner_gate b
            ON a.l = b.key
            JOIN inner_gate c
            ON a.r = c.key
            LEFT JOIN inner_gate d
            ON a.output = d.key
            WHERE d.value is null
        )
        SELECT key, value
        FROM new_output
        WHERE exists (
            SELECT 1 
            FROM gate 
            LEFT JOIN inner_gate 
            ON gate.output = inner_gate.key 
            WHERE inner_gate.value is null
        )
    ) t
)
SELECT sum(value * power(2, substring(key, 2) :: integer)) 
FROM (
    select distinct key, value
    from gate_output 
    where key like 'z%'
) t;



with recursive origin AS (
    SELECT row_number() over () as rn, line
    FROM lance_input
), input AS (
    SELECT split_part(line, ': ', 1) as key, split_part(line, ': ', 2) :: INTEGER as value
    FROM origin
    WHERE rn < (select rn from origin where line is null)
), gate AS (
    SELECT split_part(line, ' ', 1) as l, 
           split_part(line, ' ', 2) as op,
           split_part(line, ' ', 3) as r,
           split_part(line, ' ', 5) as output
    FROM origin
    WHERE rn > (select rn from origin where line is null)
), bit_calc AS (
    SELECT 0 as bit_seq, 
           max(case when op = 'XOR' then output end) as bit_val,
           max(case when op = 'AND' then output end) as bit_carry
    FROM gate
    WHERE least(l, r) = 'x00' and greatest(l, r) = 'y00'

    UNION ALL

    SELECT bit_seq, bit_val, bit_carry
    FROM (
        WITH inner_bit AS (select * From bit_calc)
        SELECT a.bit_seq, c.output as bit_val, e.output as bit_carry
        FROM (
            SELECT b.bit_seq + 1 as bit_seq,
                   max(case when op = 'XOR' then output end) as bit_xor,
                   max(case when op = 'AND' then output end) as bit_and
            FROM gate a
            JOIN inner_bit b
            ON least(l, r) = 'x' || lpad((b.bit_seq + 1)::text, 2, '0') and greatest(l, r) = 'y' || lpad((b.bit_seq + 1)::text, 2, '0')
            GROUP BY b.bit_seq
        ) a
        JOIN inner_bit b
        ON a.bit_seq = b.bit_seq + 1
        JOIN gate c
        ON ((c.l = a.bit_xor and c.r = b.bit_carry) OR (c.l = b.bit_carry and c.r = a.bit_xor))
        AND c.op = 'XOR'
        LEFT JOIN gate d
        ON ((d.l = a.bit_xor and d.r = b.bit_carry) OR (d.l = b.bit_carry and d.r = a.bit_xor))
        AND d.op = 'AND'
        LEFT JOIN gate e
        ON ((e.l = a.bit_and and e.r = d.output) OR (e.l = d.output and e.r = a.bit_and))
        AND e.op = 'OR'
    ) t
)
select * from bit_calc;


mvb z08

rds jss

wss z18

bmn z23

bmn,jss,mvb,rds,wss,z08,z18,z23

# day 25
with origin AS (
    SELECT row_number() over () as rn, line
    FROM lance_input
), empty AS (
    SELECT coalesce(lag(rn) over (order by rn), 0) as pre_rn, rn 
    FROM (
        SELECT rn
        FROM origin
        WHERE line is null
 
        UNION ALL
 
        SELECT max(rn) + 1 as rn
        FROM origin
    ) t
), matrix AS (
    SELECT empty.pre_rn as rn, origin.rn :: INTEGER as _row, x.idx :: INTEGER as _col, x.pos
    FROM origin, regexp_split_to_table(line, '') with ordinality as x(pos, idx), empty
    WHERE origin.rn between empty.pre_rn and empty.rn
), rows AS (
    SELECT rn, _row, string_agg(pos, '' order by _col) as line
    FROM matrix
    GROUP BY rn, _row
), cols AS (
    SELECT rn, _col, string_agg(pos, '' order by _row) as line
    FROM matrix
    GROUP BY rn, _col
), lock_key AS (
    SELECT rn, CASE WHEN line like '%.%' THEN 'key' ELSE 'lock' END as type
    FROM (
        SELECT rn, row_number() over (partition by rn order by _row) as seq, line
        FROM rows
    ) t
    WHERE t.seq = 1
)
SELECT COUNT(*)
FROM (
    SELECT b.rn as lock, d.rn as key, min(case when length(replace(a.line, '.', '')) + length(replace(c.line, '.', '')) - 2 <= 5 then 1 else 0 end) as result
    FROM cols a
    JOIN lock_key b 
    ON a.rn = b.rn
    AND b.type = 'lock'
    JOIN cols c
    ON a._col = c._col
    JOIN lock_key d
    ON c.rn = d.rn
    AND d.type = 'key'
    GROUP BY b.rn, d.rn
) t
WHERE result = 1