## day 1

with recursive origin as (
    select row_number() over () as rn, substring(line, 1, 1) as rotation, substring(line, 2) :: integer as distance
    from lance_input
), steps as (
    select 50 as pos, 0 as step

    UNION ALL

    SELECT case when new_pos < 0 then new_pos + 100
                when new_pos >= 100 then new_pos - 100
                else new_pos 
            end as pos, step
    FROM (
        select case when rotation = 'L' then pos - (distance % 100) else pos + (distance % 100) end as new_pos, step + 1 as step
        from steps s 
        join origin t
        on s.step + 1 = t.rn
    ) t
)
select * From steps where pos = 0;


with recursive origin as (
    select row_number() over () as rn, substring(line, 1, 1) as rotation, substring(line, 2) :: integer as distance
    from lance_input
), steps as (
    select 50 as pos, 0 as step, 0 as points

    UNION ALL

    SELECT case when new_pos < 0 then new_pos + 100
                when new_pos >= 100 then new_pos - 100
                else new_pos 
            end as pos, step,
           case when old_pos > 0 and new_pos < 0 then laps + 1
                when new_pos >= 100 then laps + 1
                when old_pos != 0 and new_pos = 0 then laps + 1
                else laps 
            end as laps
    FROM (
        select pos as old_pos, case when rotation = 'L' then pos - (distance % 100) else pos + (distance % 100) end as new_pos, step + 1 as step, distance / 100 as laps
        from steps s 
        join origin t
        on s.step + 1 = t.rn
    ) t
)
select sum(points) From steps;


## day 2

SELECT SUM(id :: BIGINT)
FROM (
    SELECT generate_series(split_part(line, '-', 1) :: BIGINT, split_part(line, '-', 2) :: BIGINT) :: text as id
    FROM (
        SELECT REGEXP_SPLIT_TO_TABLE(line, ',') as line
        FROM lance_input
    ) t
) t
WHERE length(id) % 2 = 0
AND substring(id, 1, length(id) / 2) = substring(id, length(id) / 2 + 1);




SELECT SUM(id :: BIGINT)
FROM (
    SELECT generate_series(split_part(line, '-', 1) :: BIGINT, split_part(line, '-', 2) :: BIGINT) :: text as id
    FROM (
        SELECT REGEXP_SPLIT_TO_TABLE(line, ',') as line
        FROM lance_input
    ) t
) t
WHERE (length(id) % 2 = 0 AND repeat(substring(id, 1, length(id) / 2), 2) = id)
OR (length(id) % 3 = 0 AND repeat(substring(id, 1, length(id) / 3), 3) = id)
OR (length(id) % 5 = 0 AND repeat(substring(id, 1, length(id) / 5), 5) = id)
OR (length(id) % 7 = 0 AND repeat(substring(id, 1, length(id) / 7), 7) = id)
OR (length(id) % 11 = 0 AND repeat(substring(id, 1, length(id) / 11), 11) = id)
OR (length(id) % 13 = 0 AND repeat(substring(id, 1, length(id) / 13), 13) = id)


## day 3
with origin as (
    SELECT row_number() over () as rn, line, length(line) as len FROM lance_input
), splits as (
    SELECT rn, len, x.pos :: integer as num, idx
    FROM origin, regexp_split_to_table(line, '') with ordinality as x(pos, idx)
), first_num AS (
    SELECT rn, row_number() over (partition by rn order by case when idx != len then num else -1 end desc, idx) as first_rk, num, idx
    FROM splits
), second_num AS (
    SELECT rn, first_rk, row_number() over (partition by rn order by case when idx > t.first_idx then num else -1 end desc) as second_rk, num, idx
    FROM first_num
    JOIN (SELECT rn as first_rn, max(case when first_rk = 1 then idx end) as first_idx FROM first_num GROUP BY rn) t
    ON rn = t.first_rn
), filter_num AS (
    SELECT rn, first_rk, second_rk, num
    FROM second_num
    WHERE first_rk = 1
    OR second_rk = 1
)
SELECT sum(num)
FROM (
    SELECT rn, concat(max(case when first_rk = 1 then num end), max(case when second_rk = 1 then num end)) :: integer as num
    FROM filter_num
    GROUP BY rn
) t;


with recursive origin AS (
    SELECT row_number() over () as rn, line, length(line) as len FROM lance_input
), walkthrough AS (
    SELECT 0 as num, 12 as left_nums, rn, line, len
    FROM origin

    UNION ALL

    SELECT num, left_nums, rn, line, len
    FROM (
        with inner_tbl as (
            select * From walkthrough where left_nums > 0
        ), splits as (
            SELECT left_nums, rn, len, x.pos :: integer as num, idx :: integer as idx
            FROM inner_tbl, regexp_split_to_table(line, '') with ordinality as x(pos, idx)
        ), max_valid as (
            SELECT rn, num, idx
            FROM (
                SELECT rn, num, idx, row_number() over (partition by rn order by num desc, idx) as num_rk
                FROM (
                    SELECT rn, num, idx
                    FROM splits
                    WHERE idx <= len - left_nums + 1
                ) t
            ) t
            WHERE num_rk = 1
        )
        SELECT b.num, left_nums - 1 as left_nums, a.rn, substring(line, b.idx + 1) as line, a.len - b.idx as len
        FROM inner_tbl a
        JOIN max_valid b
        ON a.rn = b.rn
        WHERE a.left_nums > 0
    ) t
)
select sum(num) from (
    select rn,string_agg(num::text, '' order by left_nums desc) :: bigint as num 
    from walkthrough 
    where left_nums < 12 
    group by rn
) t;


## day 4
with 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)
)
SELECT COUNT(*)
FROM (
    SELECT a._row, a._col
    FROM matrix a
    JOIN matrix b
    ON abs(a._row - b._row) <= 1
    AND abs(a._col - b._col) <= 1
    AND a.pos = '@'
    AND b.pos = '@'
    AND NOT (a._row = b._row AND a._col = b._col)
    GROUP BY a._row, a._col
    HAVING count(*) < 4
) t;




with 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)
), matrix_neighbours AS (
    SELECT _row, _col, pos,
        lead(pos) over (partition by _col order by _row) as down_pos,
        lag(pos) over (partition by _col order by _row) as up_pos,
        lead(pos) over (partition by _row order by _col) as right_pos,
        lag(pos) over (partition by _row order by _col) as left_pos,
        lead(pos) over (partition by _row - _col order by _row) as se_pos,
        lag(pos) over (partition by _row - _col order by _row) as nw_pos,
        lead(pos) over (partition by _row + _col order by _col) as ne_pos,
        lag(pos) over (partition by _row + _col order by _col) as sw_pos
    FROM matrix
)
SELECT COUNT(*)
FROM matrix_neighbours
WHERE concat(down_pos, up_pos, right_pos, left_pos, se_pos, nw_pos, ne_pos, sw_pos) not like '%@%@%@%@%'
AND pos = '@';






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)
), matrix_neighbours AS (
    SELECT 1 as step, _row, _col, pos, true as forklift
    FROM matrix

    UNION ALL

    SELECT *
    FROM (
        WITH inner_tbl AS (select * from matrix_neighbours)
        SELECT step + 1 as step, _row, _col, case when pos = '@' and neighbours not like '%@%@%@%@%' then 'x' else pos end as pos,
               pos = '@' and neighbours not like '%@%@%@%@%' as forklift
        FROM (
            SELECT step, _row, _col, pos, concat(
                lead(pos) over (partition by _col order by _row),
                lag(pos) over (partition by _col order by _row),
                lead(pos) over (partition by _row order by _col),
                lag(pos) over (partition by _row order by _col),
                lead(pos) over (partition by _row - _col order by _row),
                lag(pos) over (partition by _row - _col order by _row),
                lead(pos) over (partition by _row + _col order by _col),
                lag(pos) over (partition by _row + _col order by _col)
                ) as neighbours
            FROM inner_tbl
        ) t
        WHERE exists (select * from inner_tbl where forklift)
    ) t
)
SELECT count(*) from matrix_neighbours where step = 69 and pos = 'x';




## day 5

with origin AS (
    SELECT row_number() over () as rn, line
    FROM lance_input
), empty AS (
    SELECT rn
    FROM origin
    WHERE line is null
), range AS (
    SELECT split_part(line, '-', 1) :: BIGINT as min_num, split_part(line, '-', 2) :: BIGINT as max_num
    FROM origin, empty
    WHERE origin.rn < empty.rn
)
SELECT count(distinct case when origin.line :: BIGINT between range.min_num and range.max_num then origin.line end)
FROM origin, empty, range
WHERE origin.rn > empty.rn;


with origin AS (
    SELECT row_number() over () as rn, line
    FROM lance_input
), empty AS (
    SELECT rn
    FROM origin
    WHERE line is null
), range AS (
    SELECT split_part(line, '-', 1) :: BIGINT as min_num, split_part(line, '-', 2) :: BIGINT as max_num
    FROM origin, empty
    WHERE origin.rn < empty.rn
)
SELECT COUNT(distinct num)
FROM (
    SELECT generate_series(min_num, max_num) as num
    FROM range
) t;



with recursive origin AS (
    SELECT row_number() over () as rn, line
    FROM lance_input
), empty AS (
    SELECT rn
    FROM origin
    WHERE line is null
), range AS (
    SELECT row_number() over () as rn, split_part(line, '-', 1) :: BIGINT as min_num, split_part(line, '-', 2) :: BIGINT as max_num
    FROM origin, empty
    WHERE origin.rn < empty.rn
), merge_range AS (
    SELECT 1 as step, rn, min_num, max_num
    FROM range

    UNION ALL

    SELECT step + 1 as step, row_number() over () as rn, min_num, max_num
    FROM (
        WITH inner_tbl AS (select * from merge_range),
        larger_range AS (
            SELECT distinct a.step, least(a.min_num, b.min_num) as min_num, greatest(a.max_num, b.max_num) as max_num
            FROM inner_tbl a
            JOIN inner_tbl b
            ON a.min_num <= b.max_num
            AND a.max_num >= b.max_num
            AND a.rn != b.rn
        )
        SELECT step, min_num, max_num
        FROM (
            SELECT step, min_num, max_num
            FROM larger_range
            UNION ALL
            SELECT step, min_num, max_num
            FROM (
                SELECT s.step, s.min_num, s.max_num
                FROM inner_tbl s
                LEFT JOIN larger_range t
                ON s.min_num >= t.min_num and s.max_num <= t.max_num
                WHERE t.min_num is null
            ) s
        ) t
        WHERE exists (
            SELECT 1 FROM inner_tbl a
            JOIN inner_tbl b
            ON a.min_num <= b.max_num
            AND a.max_num >= b.max_num
            AND a.rn != b.rn
        )
    ) t
)
select * from merge_range;




## day 6

CREATE AGGREGATE mul(bigint) ( SFUNC = int8mul, STYPE=bigint );

with 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(trim(line), '\s+') with ordinality as x(pos, idx)
), operator AS (
    SELECT _row, _col, pos
    FROM matrix
    WHERE _row = (select max(_row) from matrix)
)
SELECT sum(case when b.pos = '+' then sum when b.pos = '*' then mul end)
FROM (
    SELECT _col, SUM(pos :: BIGINT) as sum, mul(pos :: BIGINT) as mul
    FROM matrix
    WHERE _row != (select max(_row) from matrix)
    GROUP BY _col
) a
JOIN operator b
ON a._col = b._col;


with rows as (
    SELECT (row_number() over ()) :: INTEGER as _row, line
    FROM lance_input
), operator AS (
    SELECT _row :: INTEGER, x.idx :: INTEGER as _col, x.pos
    FROM rows, regexp_split_to_table(trim(line), '\s+') with ordinality as x(pos, idx)
    WHERE _row = (select max(_row) from rows)
), split_num AS (
    SELECT _col, string_agg(pos, '' order by _row) as num
    FROM (
        SELECT _row :: INTEGER, x.idx :: INTEGER as _col, x.pos
        FROM rows, regexp_split_to_table(line, '') with ordinality as x(pos, idx)
        WHERE _row != (select max(_row) from rows)
    ) t
    GROUP by _col
), empty_line AS (
    SELECT _col, coalesce(lag(_col) over (order by _col), 0) as pre_col, row_number() over (order by _col) as rn
    FROM (
        SELECT _col
        FROM split_num
        WHERE trim(num) = ''

        UNION ALL

        SELECT max(_col) + 1 as _col
        FROM split_num
    )t
), group_num AS (
    SELECT b.rn, a.num :: bigint
    FROM split_num a
    JOIN empty_line b
    ON a._col > b.pre_col
    AND a._col < b._col
)
SELECT sum(case when b.pos = '+' then sum when b.pos = '*' then mul end)
FROM (
    SELECT rn, SUM(num :: BIGINT) as sum, mul(num :: BIGINT) as mul
    FROM group_num
    GROUP BY rn
) a
JOIN operator b
ON a.rn = b._col;



## day 7

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(trim(line), '') with ordinality as x(pos, idx)
), walkthrough AS (
    SELECT _row, _col
    FROM matrix
    WHERE pos = 'S'

    UNION ALL

    SELECT DISTINCT t._row, x._col :: integer
    FROM (
        SELECT b._row, case when b.pos = '.' then b._col :: text when b.pos = '^' then concat(b._col - 1, ',' , b._col + 1) end as next_col
        FROM walkthrough a 
        JOIN matrix b
        ON a._row + 1 = b._row
        AND a._col = b._col
    ) t, regexp_split_to_table(next_col, ',') as x(_col)
    WHERE x._col :: integer > 0 
    AND x._col :: integer < 16
) 
select count(*)
FROM walkthrough a
JOIN matrix b
ON a._row + 1 = b._row
AND a._col = b._col
AND b.pos = '^';


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(trim(line), '') with ordinality as x(pos, idx)
), walkthrough AS (
    SELECT _row, _col, array[_col::text] as path
    FROM matrix
    WHERE pos = 'S'

    UNION ALL

    SELECT _row, x._col :: integer, path || x._col as path
    FROM (
        SELECT b._row, a.path, case when b.pos = '.' then b._col :: text when b.pos = '^' then concat(b._col - 1, ',' , b._col + 1) end as next_col
        FROM walkthrough a 
        JOIN matrix b
        ON a._row + 1 = b._row
        AND a._col = b._col
    ) t, regexp_split_to_table(next_col, ',') as x(_col)
    WHERE x._col :: integer > 0 
    AND x._col :: integer < 16
) 
SELECT * FROM walkthrough where _row = 16;


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(trim(line), '') with ordinality as x(pos, idx)
), walkthrough AS (
    SELECT _row, _col, array[_col::text] as path
    FROM matrix
    WHERE pos = 'S'

    UNION ALL

    SELECT _row, x._col :: integer, path || x._col as path
    FROM (
        SELECT b._row, a.path, case when b.pos = '.' then b._col :: text when b.pos = '^' then concat(b._col - 1, ',' , b._col + 1) end as next_col
        FROM walkthrough a 
        JOIN matrix b
        ON a._row + 1 = b._row
        AND a._col = b._col
    ) t, regexp_split_to_table(next_col, ',') as x(_col)
    WHERE x._col :: integer > 0 
    AND x._col :: integer < 16
) 
SELECT * FROM walkthrough where _row = 16;


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(trim(line), '') with ordinality as x(pos, idx)
), walkthrough AS (
    SELECT _row, _col, 1 :: BIGINTas timeline
    FROM matrix
    WHERE pos = 'S'

    UNION ALL

    SELECT t._row, x._col :: integer, sum(timeline) :: BIGINT as timeline
    FROM (
        SELECT b._row, a.timeline, case when b.pos = '.' then b._col :: text when b.pos = '^' then concat(b._col - 1, ',' , b._col + 1) end as next_col
        FROM walkthrough a 
        JOIN matrix b
        ON a._row + 1 = b._row
        AND a._col = b._col
    ) t, regexp_split_to_table(next_col, ',') as x(_col)
    WHERE x._col :: integer > 0 
    AND x._col :: integer < 142
    GROUP by t._row, x._col :: integer
) 
select sum(timeline)
FROM walkthrough a
WHERE _row = 142;

## day 8

drop table num_distance;
create table num_distance
AS
with rows AS (
    SELECT (row_number() over ()) :: INTEGER as rn, line
    FROM lance_input
), nums AS (
    SELECT rn,
           split_part(line, ',', 1) :: integer as x,
           split_part(line, ',', 2) :: integer as y,
           split_part(line, ',', 3) :: integer as z
    FROM rows
)
SELECT a.rn as rn1, b.rn as rn2, power(a.x-b.x, 2) + power(a.y-b.y, 2) + power(a.z-b.z, 2) as distance,
       row_number() over (order by power(a.x-b.x, 2) + power(a.y-b.y, 2) + power(a.z-b.z, 2)) as rn, null :: integer as group_num
FROM nums a, nums b 
WHERE a.rn < b.rn;

create index idx_rn on num_distance(rn);
create index idx_rn1 on num_distance(rn1);
create index idx_rn2 on num_distance(rn2);
create index idx_group_num on num_distance(group_num);



CREATE OR REPLACE FUNCTION merge_num(_num integer)
RETURNS VOID AS $$
DECLARE
    valid_group INTEGER[];
BEGIN
    valid_group := (
        SELECT array_agg(DISTINCT s.group_num) as group_num
        FROM (
            SELECT *
            FROM num_distance
            WHERE rn = _num
        ) t
        LEFT JOIN (
            SELECT *
            FROM num_distance
            WHERE group_num is not null
        ) s
        ON t.rn1 = s.rn1
        OR t.rn1 = s.rn2
        OR t.rn2 = s.rn1
        OR t.rn2 = s.rn2
        WHERE s.group_num is not null
    );

    IF valid_group is null THEN
        raise notice 'group:null';
        UPDATE num_distance SET group_num = _num WHERE rn = _num;
    ELSIF #valid_group = 1 THEN
        raise notice 'group:%,%', valid_group[1], _num;
        UPDATE num_distance SET group_num = valid_group[1] WHERE rn = _num;
    ELSE
        raise notice 'groups:%', valid_group;
        UPDATE num_distance SET group_num = _num
        WHERE rn = _num
        OR group_num = ANY(valid_group);
    END IF;
END;
$$ LANGUAGE plpgsql;

select merge_num(t.id)
FROM (select generate_series(1, 10) as id) t;


SELECT group_num, COUNT(distinct num) as cnt
FROM (
    SELECT group_num, rn1 as num
    FROM num_distance
    WHERE group_num is not null

    UNION ALL

    SELECT group_num, rn2 as num
    FROM num_distance
    WHERE group_num is not null
)t
GROUP BY group_num order by 2 desc;


# day 9

with matrix as (
    SELECT split_part(line, ',', 1)::integer as _row, split_part(line, ',', 2)::integer as _col
    FROM lance_input
)
SELECT (abs(a._row - b._row)+1)::bigint * (abs(a._col - b._col)+1)
FROM matrix a
JOIN matrix b
ON a._row != b._row
OR a._col != b._col
order by 1 desc limit 1;

with matrix as (
    SELECT row_number() over() as rn, 
           split_part(line, ',', 1)::integer as _row, 
           split_part(line, ',', 2)::integer as _col
    FROM lance_input
), pre_next as (
    SELECT x._row, x._col,
            coalesce(pre_row, z._row) as pre_row,
            coalesce(pre_col, z._col) as pre_col,
            coalesce(next_row, y._row) as next_row,
            coalesce(next_col, y._col) as next_col
    FROM (
        SELECT _row, _col,
            lag(_row) over (order by rn) as pre_row,
            lag(_col) over (order by rn) as pre_col,
            lead(_row) over (order by rn) as next_row,
            lead(_col) over (order by rn) as next_col
        FROM matrix a
    ) x, (
        SELECT _row, _col FROM matrix where rn = 1
    ) y, (
        SELECT _row, _col FROM matrix where rn = (select max(rn) from matrix)
    ) z
), vertex as (
    SELECT _row, _col,
           case when pre_row < _row and next_col < _col then 'J'
                when pre_col < _col and next_row < _row then 'J'
                when pre_col > _col and next_row < _row then 'L'
                when pre_row < _row and next_col > _col then 'L'
                when pre_col < _col and next_row > _row then '7'
                when pre_row > _row and next_col < _col then '7'
                when pre_col > _col and next_row > _row then 'F'
                when pre_row > _row and next_col > _col then 'F'
            end as type
    FROM pre_next
), edge as (
    SELECT least(a.pre_row, a._row) as start_row,
           least(a.pre_col, a._col) as start_col,
           greatest(a.pre_row, a._row) as end_row,
           greatest(a.pre_col, a._col) as end_col,
           case when a.pre_row = a._row then 'H'
                when a.pre_col = a._col then 'V'
            end as direction,
           case when b.type = 'F' and c.type = '7' THEN 'U'
                when b.type = '7' and c.type = 'F' THEN 'U'
                when b.type = 'L' and c.type = 'J' THEN 'U'
                when b.type = 'J' and c.type = 'L' THEN 'U'
                when b.type = 'F' and c.type = 'J' THEN 'Z'
                when b.type = 'J' and c.type = 'F' THEN 'Z'
                when b.type = 'L' and c.type = '7' THEN 'Z'
                when b.type = '7' and c.type = 'L' THEN 'Z'
            end as type
    FROM pre_next a
    JOIN vertex b
    ON a._row = b._row
    AND a._col = b._col
    JOIN vertex c
    ON a.pre_row = c._row
    AND a.pre_col = c._col
), candidates 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 matrix a
    JOIN matrix b
    ON a._row < b._row
    AND a._col != b._col
), candidate_stats as (
    SELECT a.start_row, a.start_col, a.end_row, a.end_col,
           max(case when (b.direction = 'V' and a.start_col = b.start_col and a.start_row between b.start_row and b.end_row)
           OR (b.direction = 'H' and a.start_row = b.start_row and a.start_col between b.start_col and b.end_col) then 1 end) as NW_edge,
           max(case when (b.direction = 'V' and a.end_col = b.start_col and a.start_row between b.start_row and b.end_row)
           OR (b.direction = 'H' and a.start_row = b.start_row and a.end_col between b.start_col and b.end_col) then 1 end) as NE_edge,
           max(case when (b.direction = 'V' and a.start_col = b.start_col and a.end_row between b.start_row and b.end_row)
           OR (b.direction = 'H' and a.end_row = b.start_row and a.start_col between b.start_col and b.end_col) then 1 end) as SW_edge,
           max(case when (b.direction = 'V' and a.end_col = b.start_col and a.end_row between b.start_row and b.end_row)
           OR (b.direction = 'H' and a.end_row = b.start_row and a.end_col between b.start_col and b.end_col) then 1 end) as SE_edge,

           count(case when b.direction = 'V' and b.start_col > a.start_col and a.start_row > b.start_row and a.start_row < b.end_row then 1 end)
           + count(case when b.direction = 'H' and b.type = 'Z' and b.start_col > a.start_col and a.start_row = b.start_row then 1 end) as NW_E_CNT,
           count(case when b.direction = 'V' and b.start_col < a.start_col and a.start_row > b.start_row and a.start_row < b.end_row then 1 end) 
           + count(case when b.direction = 'H' and b.type = 'Z' and b.start_col < a.start_col and a.start_row = b.start_row then 1 end) as NW_W_CNT,
           
           count(case when b.direction = 'V' and b.start_col > a.end_col and a.start_row > b.start_row and a.start_row < b.end_row then 1 end) 
           + count(case when b.direction = 'H' and b.type = 'Z' and b.start_col > a.end_col and a.start_row = b.start_row then 1 end) as NE_E_CNT,
           count(case when b.direction = 'V' and b.start_col < a.end_col and a.start_row > b.start_row and a.start_row < b.end_row then 1 end) 
           + count(case when b.direction = 'H' and b.type = 'Z' and b.start_col < a.end_col and a.start_row = b.start_row then 1 end) as NE_W_CNT,

           count(case when b.direction = 'V' and b.start_col > a.start_col and a.end_row > b.start_row and a.end_row < b.end_row then 1 end) 
           + count(case when b.direction = 'H' and b.type = 'Z' and b.start_col > a.start_col and a.end_row = b.end_row then 1 end) as SW_E_CNT,
           count(case when b.direction = 'V' and b.start_col < a.start_col and a.end_row > b.start_row and a.end_row < b.end_row then 1 end)
           + count(case when b.direction = 'H' and b.type = 'Z' and b.start_col < a.start_col and a.end_row = b.end_row then 1 end) as SW_W_CNT,

           count(case when b.direction = 'V' and b.start_col > a.end_col and a.end_row > b.start_row and a.end_row < b.end_row then 1 end) 
           + count(case when b.direction = 'H' and b.type = 'Z' and b.start_col > a.end_col and a.end_row = b.end_row then 1 end) as SE_E_CNT,
           count(case when b.direction = 'V' and b.start_col < a.end_col and a.end_row > b.start_row and a.end_row < b.end_row then 1 end) 
           + count(case when b.direction = 'H' and b.type = 'Z' and b.start_col < a.end_col and a.end_row = b.end_row then 1 end) as SE_W_CNT,
           
           count(case when b.direction = 'V' and b.start_col > a.start_col and b.start_col < a.end_col and a.start_row > b.start_row and a.start_row < b.end_row then 1 end) as n_cnt,
           count(case when b.direction = 'V' and b.start_col > a.start_col and b.start_col < a.end_col and a.end_row > b.start_row and a.end_row < b.end_row then 1 end) as s_cnt,
           count(case when b.direction = 'H' and b.start_row > a.start_row and b.start_row < a.end_row and a.start_col > b.start_col and a.start_col < b.end_col then 1 end) as w_cnt,
           count(case when b.direction = 'H' and b.start_row > a.start_row and b.start_row < a.end_row and a.end_col > b.start_col and a.end_col < b.end_col then 1 end) as e_cnt

    FROM candidates a
    JOIN edge b
    ON 1 = 1
    GROUP BY a.start_row, a.start_col, a.end_row, a.end_col
), candidate_coordinates as (
    SELECT a.start_row, a.start_col, a.end_row, a.end_col,
            case when NW_edge = 1 then TRUE
                when NW_E_CNT % 2 = 1 AND NW_W_CNT % 2 = 1 THEN TRUE
                else false
            end as nw_inside,
            case when NE_edge = 1 then TRUE
                when NE_E_CNT % 2 = 1 AND NE_W_CNT % 2 = 1 THEN TRUE
                else false
            end as ne_inside,
            case when SW_edge = 1 then TRUE
                when SW_E_CNT % 2 = 1 AND SW_W_CNT % 2 = 1 THEN TRUE
                else false
            end as sw_inside,
            case when SE_edge = 1 then TRUE
                when SE_E_CNT % 2 = 1 AND SE_W_CNT % 2 = 1 THEN TRUE
                else false
            end as se_inside,
            n_cnt + s_cnt + w_cnt + e_cnt as intersect_cnt
    FROM candidate_stats a
)
select (end_row - start_row + 1)::bigint * (end_col - start_col + 1)
from candidate_coordinates 
where nw_inside and ne_inside and sw_inside and se_inside and intersect_cnt = 0
order by 1 desc limit 1;


# day 10

with origin as (
    SELECT row_number() over () as rn,
           substring(split_part(line, '] ', 1), 2) as target, 
           split_part(split_part(line, '] ', 2), ' {', 1) as schematics
    FROM lance_input
), split_schematics as (
    SELECT rn, button, idx
    FROM origin, regexp_split_to_table(schematics, ' ') with ordinality as x(button, idx)
), button_cnt as (
    SELECT rn, count(*) as total
    FROM split_schematics
    GROUP BY rn
), power_seq as (
    SELECT generate_series(1, power(2, max(total))::integer) - 1 as seq
    FROM button_cnt
), cross_join as (
    SELECT a.rn, substring(a.button, 2, length(a.button) - 2) as buttons, b.seq
    FROM split_schematics a
    JOIN button_cnt c
    ON a.rn = c.rn
    JOIN power_seq b
    ON power(2, a.idx - 1)::integer & b.seq = power(2, a.idx - 1)::integer
    AND power(2, c.total)::integer > b.seq 
), button_agg as (
    SELECT rn, seq, string_agg(button, '' order by button::integer) as buttons
    FROM (
        SELECT rn, seq, button
        FROM cross_join a, regexp_split_to_table(buttons, ',') as x(button)
        GROUP BY rn, seq, button
        HAVING count(*) % 2 = 1
    ) t
    GROUP BY rn, seq
), origin_result as (
    SELECT rn, string_agg((idx - 1)::text, '' order by idx) as buttons
    FROM origin, regexp_split_to_table(target, '') with ordinality as x(button, idx)
    WHERE x.button = '#'
    GROUP BY rn
)
SELECT sum(len)
FROM(
    SELECT b.rn, min(length(replace(b.seq::bit(32)::text, '0', ''))::integer) as len
    FROM origin_result a
    JOIN button_agg b
    ON a.rn = b.rn
    AND a.buttons = b.buttons
    GROUP BY b.rn
) t;




CREATE OR REPLACE FUNCTION calculate_joltage(buttons text[], targets integer[])
RETURNS INTEGER AS $$
DECLARE
    ROW_LEN integer;
    COL_LEN integer;
    BUTTON integer[];
    BUTTON_CURR integer[];
    BUTTON_ALL integer[][];
    MATRIX integer[];
    LINEAR_RESULT linear_system_solution;
    SOLVED variable_solution;
    MAX_COEFF integer;
    CURR_COEFF DOUBLE PRECISION;
    MIN_VAL integer := 0;
    VAR_SOLUTION integer[];
    eps DOUBLE PRECISION := 1e-3;
BEGIN
    ROW_LEN := array_length(targets, 1);
    COL_LEN := array_length(buttons, 1);
    MAX_COEFF := (SELECT max(x) FROM unnest(targets) as x);

    FOR i IN 1..ROW_LEN LOOP
        FOR j IN 1..COL_LEN LOOP
            button := replace(replace(buttons[j], '(', '{'), ')', '}') :: INTEGER[];
            IF i - 1 = ANY(button) THEN
                matrix := matrix || 1;
            ELSE
                matrix := matrix || 0;
            END IF;
        END LOOP;
    END LOOP;

    FOR i IN 1..COL_LEN LOOP
        BUTTON_CURR := '{}' :: integer[];
        button := replace(replace(buttons[i], '(', '{'), ')', '}') :: INTEGER[];

        FOR j IN 1..ROW_LEN LOOP
            IF j - 1 = ANY(button) THEN
                BUTTON_CURR := BUTTON_CURR || 1;
            ELSE
                BUTTON_CURR := BUTTON_CURR || 0;
            END IF;
        END LOOP;

        BUTTON_ALL := BUTTON_ALL || array[BUTTON_CURR];
    END LOOP;

    LINEAR_RESULT := solve_linear_system(matrix, targets, ROW_LEN, COL_LEN);

    raise info 'free:%', array_length(LINEAR_RESULT.free_variables, 1);

    IF LINEAR_RESULT.status = 'unique' THEN
        FOR i IN 1..array_length(LINEAR_RESULT.solved_variables, 1) LOOP
            SOLVED := LINEAR_RESULT.solved_variables[i];
            min_val := min_val + SOLVED.constant;
        END LOOP;
    ELSE 
        -- 最小解，初始化为最大系数 * 变量数
        MIN_VAL := MAX_COEFF * COL_LEN;

        <<outer_loop>>
        FOR i IN 1..power(MAX_COEFF, array_length(LINEAR_RESULT.free_variables, 1)) LOOP
            -- 初始化变量解
            VAR_SOLUTION := array_fill(0, array[COL_LEN]);

            FOR j IN 1..array_length(LINEAR_RESULT.free_variables, 1) LOOP
                CURR_COEFF := floor((i % power(MAX_COEFF, j) :: BIGINT) / power(MAX_COEFF, j - 1));
                VAR_SOLUTION[LINEAR_RESULT.free_variables[j]] := CURR_COEFF;
            END LOOP;

            FOR k IN 1..array_length(LINEAR_RESULT.solved_variables, 1) LOOP
                SOLVED := LINEAR_RESULT.solved_variables[k];
                CURR_COEFF := SOLVED.constant;
                IF array_length(SOLVED.free_var_indices, 1) > 0 THEN
                    FOR m IN 1..array_length(SOLVED.free_var_indices, 1) LOOP
                        CURR_COEFF := CURR_COEFF - VAR_SOLUTION[SOLVED.free_var_indices[m]] * SOLVED.free_var_coeffs[m];
                    END LOOP;
                    VAR_SOLUTION[SOLVED.var_index] := round(CURR_COEFF);
                END IF;

                -- 不能为小数
                IF abs(CURR_COEFF - round(CURR_COEFF)) > eps THEN
                    continue outer_loop;
                END IF;

                IF round(CURR_COEFF) >= 0 THEN
                    VAR_SOLUTION[SOLVED.var_index] := round(CURR_COEFF);
                ELSE
                    continue outer_loop;
                END IF;

            END LOOP;

            IF (SELECT sum(x) FROM unnest(VAR_SOLUTION) as x) > 0 THEN
                MIN_VAL := least(MIN_VAL, (SELECT sum(x) FROM unnest(VAR_SOLUTION) as x));
            END IF;

        END LOOP;

    END IF;
    return MIN_VAL;
END;
$$ LANGUAGE plpgsql;


with origin as (
    SELECT row_number() over () as rn,
           '{' || split_part(line, ' {', 2) as targets, 
           split_part(split_part(line, '] ', 2), ' {', 1) as schematics
    FROM lance_input
), origin_input as (
    SELECT rn, string_to_array(schematics, ' ') as buttons, targets :: integer[]
    FROM origin
)
select sum(calculate_joltage(buttons, targets)) from origin_input;



CREATE OR REPLACE FUNCTION calculate_joltage_fast(buttons text[], targets integer[])
RETURNS INTEGER AS $$
DECLARE
    target_trans text := '';
    candidate_list integer[];
    tmp_targets integer[];
    index_array integer[];
    min_press integer := 10000000;
    current_press integer;
    cache_candidate integer[];
BEGIN
    -- all zero
    IF 0 = all(targets) THEN
        RETURN 0;
    END IF;

    -- tranform target numbers to .#
    FOR i IN 1..array_length(targets, 1) LOOP
        IF targets[i] % 2 = 0 THEN
            target_trans := target_trans || '.';
        ELSE
            target_trans := target_trans || '#';
        END IF;
    END LOOP;

    -- all even numbers
    IF target_trans not like '%#%' THEN
        tmp_targets := targets;
        FOR j in 1..array_length(tmp_targets, 1) LOOP
            tmp_targets[j] := tmp_targets[j] / 2;
        END LOOP;

        RETURN 2 * calculate_joltage_fast(buttons, tmp_targets);
    END IF;

    candidate_list := (
        with origin as (
            SELECT target_trans as target
        ), power_seq as (
            SELECT generate_series(1, power(2, array_length(buttons, 1))::integer) - 1 as seq
        ), cross_join as (
            SELECT substring(a.button, 2, length(a.button) - 2) as button_list, b.seq
            FROM (SELECT * FROM unnest(buttons) WITH ORDINALITY AS t(button, idx)) a
            JOIN power_seq b
            ON power(2, a.idx - 1)::integer & b.seq = power(2, a.idx - 1)::integer
            AND power(2, array_length(buttons, 1))::integer > b.seq 
        ), button_agg as (
            SELECT seq, string_agg(button, '' order by button::integer) as button_list
            FROM (
                SELECT seq, button
                FROM cross_join a, regexp_split_to_table(button_list, ',') as x(button)
                GROUP BY seq, button
                HAVING count(*) % 2 = 1
            ) t
            GROUP BY seq
        ), origin_result as (
            SELECT string_agg((idx - 1)::text, '' order by idx) as button_list
            FROM origin, regexp_split_to_table(target, '') with ordinality as x(button, idx)
            WHERE x.button = '#'
        )
        SELECT array_agg(seq order by seq)
        FROM (
            SELECT b.seq
            FROM origin_result a
            JOIN button_agg b
            ON a.button_list = b.button_list
        ) t
    ) :: integer[];

    -- no candidate found
    IF candidate_list is null THEN
        RETURN 1000000;
    END IF;

    -- filter validate candidate
    <<outer_loop>>
    FOR i in 1..array_length(candidate_list, 1) LOOP
        current_press := 0;
        tmp_targets := targets;
        FOR j in 1..array_length(buttons, 1) LOOP
            IF power(2, j - 1)::integer & candidate_list[i] = power(2, j - 1)::integer THEN
                current_press := current_press + 1;
                index_array := string_to_array(substring(buttons[j], 2, length(buttons[j])- 2), ',');
                FOR k IN 1..array_length(index_array, 1) LOOP
                    -- invalid candidate
                    IF tmp_targets[index_array[k] + 1] = 0 THEN
                        continue outer_loop;
                    END IF;
                    tmp_targets[index_array[k] + 1] := tmp_targets[index_array[k] + 1] - 1;
                END LOOP;
            END IF;
        END LOOP;

        -- divided by 2
        FOR j in 1..array_length(tmp_targets, 1) LOOP
            tmp_targets[j] := tmp_targets[j] / 2;
        END LOOP;

        -- iteration
        current_press := current_press + 2 * calculate_joltage_fast(buttons, tmp_targets);

        IF current_press < min_press THEN
            min_press := current_press;
        END IF;
    END LOOP;

    RETURN min_press;
END;
$$ LANGUAGE plpgsql;





# day 11
with recursive origin as (
    SELECT t.device, s.target
    FROM (
        SELECT split_part(line, ': ', 1) as device, 
               split_part(line, ': ', 2) as targets
        FROM lance_input
    ) t, regexp_split_to_table(targets, ' ') as s(target) 
), all_path as (
    SELECT device, target, array[device, target] as path
    FROM origin 
    WHERE device = 'you'

    UNION ALL

    SELECT a.device, b.target, path || b.target as path
    FROM all_path a
    JOIN origin b
    ON a.target = b.device
    AND b.target != ANY(path)
    AND a.target != 'out'
)
SELECT * from all_path;



with recursive origin as (
    SELECT t.device, s.target
    FROM (
        SELECT split_part(line, ': ', 1) as device, 
               split_part(line, ': ', 2) as targets
        FROM lance_input
    ) t, regexp_split_to_table(targets, ' ') as s(target) 
), all_path as (
    SELECT target, device, array[target, device] as path
    FROM origin 
    WHERE target = 'fft'

    UNION ALL

    SELECT a.target, b.device, path || b.device as path
    FROM all_path a
    JOIN origin b
    ON a.device = b.target
    AND b.device != ANY(path)
    AND a.device != 'svr'
)
SELECT * from all_path;


drop table if exists device_path;
create table device_path as 
with origin as (
    SELECT t.device, s.target, 1 :: bigint as path
    FROM (
        SELECT split_part(line, ': ', 1) as device, 
               split_part(line, ': ', 2) as targets
        FROM lance_input
    ) t, regexp_split_to_table(targets, ' ') as s(target) 
)
select * from origin;

create index idx_device_path on device_path(device, target);

CREATE OR REPLACE FUNCTION calculate_device_path(_source text, _target text)
RETURNS BIGINT AS $$
DECLARE
    _path bigint;
    _targets varchar[];
BEGIN
    -- find from cache
    _path := (select path from device_path where device = _source and target = _target);

    IF _path IS NULL THEN
        _targets := (
            SELECT array_agg(target) from device_path where device = _source and path > 0
        );

        IF _targets IS NULL THEN
            _path := 0;
        ELSE
            _path := 0;
            FOR i in 1..array_length(_targets, 1) LOOP
                _path := _path + calculate_device_path(_targets[i], _target);
            END LOOP;
        END IF;

        -- insert into cache
        INSERT INTO device_path values(_source, _target, _path);
    ELSE
        RETURN _path;
    END IF;

    RETURN _path;
END;
$$ LANGUAGE plpgsql;




# day 12

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 origin
    WHERE line = ''
), shapes AS (
    SELECT empty.rn / 5 as idx, sum(length(origin.line) - length(replace(origin.line, '#', ''))) as size
    FROM origin, empty
    WHERE origin.rn between empty.pre_rn and empty.rn
    group by empty.rn / 5
), regions AS (
    SELECT split_part(size, 'x', 1) :: integer * split_part(size, 'x', 2) :: integer as total,
           split_part(targets, ' ', 1) :: integer * (select size From shapes where idx = 1) +
           split_part(targets, ' ', 2) :: integer * (select size From shapes where idx = 2) +
           split_part(targets, ' ', 3) :: integer * (select size From shapes where idx = 3) +
           split_part(targets, ' ', 4) :: integer * (select size From shapes where idx = 4) +
           split_part(targets, ' ', 5) :: integer * (select size From shapes where idx = 5) +
           split_part(targets, ' ', 6) :: integer * (select size From shapes where idx = 6) as shape_sum
    FROM (
        SELECT split_part(line, ': ', 1) as size, split_part(line, ': ', 2) as targets
        FROM origin
        WHERE rn > (select max(rn) from empty)
    ) t
)
select * From regions;