Materialize/test/sqllogictest/advent-of-code/2023/aoc_1219.slt

# Copyright Materialize, Inc. and contributors. All rights reserved.
#
# Use of this software is governed by the Business Source License
# included in the LICENSE file at the root of this repository.
#
# As of the Change Date specified in that file, in accordance with
# the Business Source License, use of this software will be governed
# by the Apache License, Version 2.0.

# https://github.com/MaterializeInc/advent-of-code-2023/blob/main/week1/aoc_1219.md

mode cockroach

statement ok
CREATE TABLE input (input TEXT);

statement ok
INSERT INTO input VALUES (
'in{x<1164:zoz,s>1473:A,a<8576:ask,A}
ask{m<2275:rsx,zoz}
rsx{a>8922:A,s>4213:A,R}
zoz{m>5813:A,s>4522:A,x<245:R,krw}
krw{a>3747:dqu,a>299:R,a<927:A,A}
ton{a<8226:ktx,m>1965:ktx,s>3591:uhu,dqu}
dqu{m<6866:uhu,s>4649:A,R}
uhu{a<6293:A,lel}
lel{a<6145:ktx,A}
ktx{s>8889:R,a>3215:R,R}
<EMPTY_LINE>
{x=61,m=818,a=525,s=29}
{x=225,m=7722,a=964,s=466}
{x=528,m=3628,a=914,s=8823}
{x=13,m=675,a=5933,s=9}
{x=9693,m=8583,a=125,s=787}');

statement ok
UPDATE input SET input = replace(input, '<EMPTY_LINE>', '');

query II
WITH MUTUALLY RECURSIVE

    blocks(block1 TEXT, block2 TEXT) AS (
        SELECT
            trim(regexp_split_to_array(input, '\n\n')[1]) block1,
            trim(regexp_split_to_array(input, '\n\n')[2]) block2
        FROM input
    ),
    states(state TEXT, trans TEXT) AS (
        SELECT
            regexp_split_to_array(line, '\{')[1] state,
            trim('}' FROM regexp_split_to_array(line, '\{')[2]) trans
        FROM (SELECT regexp_split_to_table(block1, '\n') line FROM blocks)
    ),
    steps(state TEXT, priority INT, rule TEXT) AS (
        SELECT
            state,
            priority,
            regexp_split_to_array(trans, ',')[priority]
        FROM states, generate_series(1, array_length(regexp_split_to_array(trans, ','), 1)) priority
    ),

    starts(x INT, m INT, a INT, s INT) AS (
        SELECT
            substring(regexp_split_to_array(trimmed, ',')[1], 3)::INT,
            substring(regexp_split_to_array(trimmed, ',')[2], 3)::INT,
            substring(regexp_split_to_array(trimmed, ',')[3], 3)::INT,
            substring(regexp_split_to_array(trimmed, ',')[4], 3)::INT
        FROM (SELECT trim('\{' FROM trim('\}' FROM regexp_split_to_table(block2, '\n'))) trimmed FROM blocks)
    ),

    --
    rules(state TEXT, priority INT, field TEXT, cmp TEXT, val INT, next TEXT) AS (
        SELECT
            state,
            priority,
            CASE WHEN substring(rule, 2, 1) = '<' OR substring(rule, 2, 1) = '>'
                THEN substring(rule, 1, 1)
                ELSE 'x'
            END,
            CASE WHEN substring(rule, 2, 1) = '<' OR substring(rule, 2, 1) = '>'
                THEN substring(rule, 2, 1)
                ELSE '>'
            END,
            CASE WHEN substring(rule, 2, 1) = '<' OR substring(rule, 2, 1) = '>'
                THEN regexp_split_to_array(substring(rule, 3), ':')[1]::INT
                ELSE '0'
            END,
            CASE WHEN substring(rule, 2, 1) = '<' OR substring(rule, 2, 1) = '>'
                THEN regexp_split_to_array(substring(rule, 3), ':')[2]
                ELSE rule
            END
        FROM steps
    ),

    -- PART 1: iterate folks forward from `in`
    movement(state TEXT, x INT, m INT, a INT, s INT) AS (
        SELECT 'in' state, * FROM starts
        UNION ALL
        SELECT next, x, m, a, s
        FROM (
            SELECT DISTINCT ON (state, x, m, a, s) state, x, m, a, s, priority, next
            FROM (
                SELECT movement.*, rules.next, rules.priority
                FROM movement, rules
                WHERE movement.state = rules.state
                AND CASE WHEN rules.cmp = '<'
                         THEN CASE WHEN rules.field = 'x' THEN x < val
                                   WHEN rules.field = 'm' THEN m < val
                                   WHEN rules.field = 'a' THEN a < val
                                   WHEN rules.field = 's' THEN s < val
                                   ELSE false
                              END
                         WHEN rules.cmp = '>'
                         THEN CASE WHEN rules.field = 'x' THEN x > val
                                   WHEN rules.field = 'm' THEN m > val
                                   WHEN rules.field = 'a' THEN a > val
                                   WHEN rules.field = 's' THEN s > val
                                   ELSE false
                              END
                         ELSE false
                    END
            )
            ORDER BY state, x, m, a, s, priority
        )
    ),

    part1(part1 BIGINT) AS (
        SELECT SUM(x + m + a + s)
        FROM movement
        WHERE state = 'A'
    ),

    -- PART 2: just find all the bounding regions and label them 'A' or 'R'.
    region(state TEXT, priority INT, xl INT, xu INT, ml INT, mu INT, al INT, au INT, sl INT, su INT) AS (
        SELECT 'in', 1, 1, 4000, 1, 4000, 1, 4000, 1, 4000
        -- Could satisfy the rule, and transition to the next state ..
        UNION ALL
        SELECT
            next,
            1,
            CASE WHEN rules.field = 'x' AND rules.cmp = '>' THEN GREATEST(val+1, xl) ELSE xl END,
            CASE WHEN rules.field = 'x' AND rules.cmp = '<' THEN LEAST(val-1, xu) ELSE xu END,
            CASE WHEN rules.field = 'm' AND rules.cmp = '>' THEN GREATEST(val+1, ml) ELSE ml END,
            CASE WHEN rules.field = 'm' AND rules.cmp = '<' THEN LEAST(val-1, mu) ELSE mu END,
            CASE WHEN rules.field = 'a' AND rules.cmp = '>' THEN GREATEST(val+1, al) ELSE al END,
            CASE WHEN rules.field = 'a' AND rules.cmp = '<' THEN LEAST(val-1, au) ELSE au END,
            CASE WHEN rules.field = 's' AND rules.cmp = '>' THEN GREATEST(val+1, sl) ELSE sl END,
            CASE WHEN rules.field = 's' AND rules.cmp = '<' THEN LEAST(val-1, su) ELSE su END
        FROM region, rules
        WHERE region.state = rules.state
          AND region.priority = rules.priority
        -- .. or could fail the rule, and advance to the next priority.
        UNION ALL
        SELECT
            region.state,
            region.priority + 1,
            CASE WHEN rules.field = 'x' AND rules.cmp = '<' THEN GREATEST(val, xl) ELSE xl END,
            CASE WHEN rules.field = 'x' AND rules.cmp = '>' THEN LEAST(val, xu) ELSE xu END,
            CASE WHEN rules.field = 'm' AND rules.cmp = '<' THEN GREATEST(val, ml) ELSE ml END,
            CASE WHEN rules.field = 'm' AND rules.cmp = '>' THEN LEAST(val, mu) ELSE mu END,
            CASE WHEN rules.field = 'a' AND rules.cmp = '<' THEN GREATEST(val, al) ELSE al END,
            CASE WHEN rules.field = 'a' AND rules.cmp = '>' THEN LEAST(val, au) ELSE au END,
            CASE WHEN rules.field = 's' AND rules.cmp = '<' THEN GREATEST(val, sl) ELSE sl END,
            CASE WHEN rules.field = 's' AND rules.cmp = '>' THEN LEAST(val, su) ELSE su END
        FROM region, rules
        WHERE region.state = rules.state
          AND region.priority = rules.priority
    ),

    part2(part2 NUMERIC) AS (
        SELECT SUM((1 + xu - xl)::BIGINT * (1 + mu - ml)::BIGINT * (1 + au - al)::BIGINT * (1 + su - sl)::BIGINT)
        FROM region
        WHERE state = 'A'
    ),

    potato(x INT) AS (SELECT 1)

SELECT * FROM part1, part2;
----
42458  -257636238955235

query T multiline
EXPLAIN OPTIMIZED PLAN WITH(humanized expressions, arity, join implementations) AS VERBOSE TEXT FOR
WITH MUTUALLY RECURSIVE

    blocks(block1 TEXT, block2 TEXT) AS (
        SELECT
            regexp_split_to_array(input, '\n\n')[1] block1,
            regexp_split_to_array(input, '\n\n')[2] block2
        FROM input
    ),
    states(state TEXT, trans TEXT) AS (
        SELECT
            regexp_split_to_array(line, '\{')[1] state,
            trim('}' FROM regexp_split_to_array(line, '\{')[2]) trans
        FROM (SELECT regexp_split_to_table(block1, '\n') line FROM blocks)
    ),
    steps(state TEXT, priority INT, rule TEXT) AS (
        SELECT
            state,
            priority,
            regexp_split_to_array(trans, ',')[priority]
        FROM states, generate_series(1, array_length(regexp_split_to_array(trans, ','), 1)) priority
    ),

    starts(x INT, m INT, a INT, s INT) AS (
        SELECT
            substring(regexp_split_to_array(trimmed, ',')[1], 3)::INT,
            substring(regexp_split_to_array(trimmed, ',')[2], 3)::INT,
            substring(regexp_split_to_array(trimmed, ',')[3], 3)::INT,
            substring(regexp_split_to_array(trimmed, ',')[4], 3)::INT
        FROM (SELECT trim('\{' FROM trim('\}' FROM regexp_split_to_table(block2, '\n'))) trimmed FROM blocks)
    ),

    --
    rules(state TEXT, priority INT, field TEXT, cmp TEXT, val INT, next TEXT) AS (
        SELECT
            state,
            priority,
            CASE WHEN substring(rule, 2, 1) = '<' OR substring(rule, 2, 1) = '>'
                THEN substring(rule, 1, 1)
                ELSE 'x'
            END,
            CASE WHEN substring(rule, 2, 1) = '<' OR substring(rule, 2, 1) = '>'
                THEN substring(rule, 2, 1)
                ELSE '>'
            END,
            CASE WHEN substring(rule, 2, 1) = '<' OR substring(rule, 2, 1) = '>'
                THEN regexp_split_to_array(substring(rule, 3), ':')[1]::INT
                ELSE '0'
            END,
            CASE WHEN substring(rule, 2, 1) = '<' OR substring(rule, 2, 1) = '>'
                THEN regexp_split_to_array(substring(rule, 3), ':')[2]
                ELSE rule
            END
        FROM steps
    ),

    -- PART 1: iterate folks forward from `in`
    movement(state TEXT, x INT, m INT, a INT, s INT) AS (
        SELECT 'in' state, * FROM starts
        UNION ALL
        SELECT next, x, m, a, s
        FROM (
            SELECT DISTINCT ON (state, x, m, a, s) state, x, m, a, s, priority, next
            FROM (
                SELECT movement.*, rules.next, rules.priority
                FROM movement, rules
                WHERE movement.state = rules.state
                AND CASE WHEN rules.cmp = '<'
                         THEN CASE WHEN rules.field = 'x' THEN x < val
                                   WHEN rules.field = 'm' THEN m < val
                                   WHEN rules.field = 'a' THEN a < val
                                   WHEN rules.field = 's' THEN s < val
                                   ELSE false
                              END
                         WHEN rules.cmp = '>'
                         THEN CASE WHEN rules.field = 'x' THEN x > val
                                   WHEN rules.field = 'm' THEN m > val
                                   WHEN rules.field = 'a' THEN a > val
                                   WHEN rules.field = 's' THEN s > val
                                   ELSE false
                              END
                         ELSE false
                    END
            )
            ORDER BY state, x, m, a, s, priority
        )
    ),

    part1(part1 BIGINT) AS (
        SELECT SUM(x + m + a + s)
        FROM movement
        WHERE state = 'A'
    ),

    -- PART 2: just find all the bounding regions and label them 'A' or 'R'.
    region(state TEXT, priority INT, xl INT, xu INT, ml INT, mu INT, al INT, au INT, sl INT, su INT) AS (
        SELECT 'in', 1, 1, 4000, 1, 4000, 1, 4000, 1, 4000
        -- Could satisfy the rule, and transition to the next state ..
        UNION ALL
        SELECT
            next,
            1,
            CASE WHEN rules.field = 'x' AND rules.cmp = '>' THEN GREATEST(val+1, xl) ELSE xl END,
            CASE WHEN rules.field = 'x' AND rules.cmp = '<' THEN LEAST(val-1, xu) ELSE xu END,
            CASE WHEN rules.field = 'm' AND rules.cmp = '>' THEN GREATEST(val+1, ml) ELSE ml END,
            CASE WHEN rules.field = 'm' AND rules.cmp = '<' THEN LEAST(val-1, mu) ELSE mu END,
            CASE WHEN rules.field = 'a' AND rules.cmp = '>' THEN GREATEST(val+1, al) ELSE al END,
            CASE WHEN rules.field = 'a' AND rules.cmp = '<' THEN LEAST(val-1, au) ELSE au END,
            CASE WHEN rules.field = 's' AND rules.cmp = '>' THEN GREATEST(val+1, sl) ELSE sl END,
            CASE WHEN rules.field = 's' AND rules.cmp = '<' THEN LEAST(val-1, su) ELSE su END
        FROM region, rules
        WHERE region.state = rules.state
          AND region.priority = rules.priority
        -- .. or could fail the rule, and advance to the next priority.
        UNION ALL
        SELECT
            region.state,
            region.priority + 1,
            CASE WHEN rules.field = 'x' AND rules.cmp = '<' THEN GREATEST(val, xl) ELSE xl END,
            CASE WHEN rules.field = 'x' AND rules.cmp = '>' THEN LEAST(val, xu) ELSE xu END,
            CASE WHEN rules.field = 'm' AND rules.cmp = '<' THEN GREATEST(val, ml) ELSE ml END,
            CASE WHEN rules.field = 'm' AND rules.cmp = '>' THEN LEAST(val, mu) ELSE mu END,
            CASE WHEN rules.field = 'a' AND rules.cmp = '<' THEN GREATEST(val, al) ELSE al END,
            CASE WHEN rules.field = 'a' AND rules.cmp = '>' THEN LEAST(val, au) ELSE au END,
            CASE WHEN rules.field = 's' AND rules.cmp = '<' THEN GREATEST(val, sl) ELSE sl END,
            CASE WHEN rules.field = 's' AND rules.cmp = '>' THEN LEAST(val, su) ELSE su END
        FROM region, rules
        WHERE region.state = rules.state
          AND region.priority = rules.priority
    ),

    part2(part2 NUMERIC) AS (
        SELECT SUM((1 + xu - xl)::BIGINT * (1 + mu - ml)::BIGINT * (1 + au - al)::BIGINT * (1 + su - sl)::BIGINT)
        FROM region
        WHERE state = 'A'
    ),

    potato(x INT) AS (SELECT 1)

SELECT * FROM part1, part2;
----
Explained Query:
  With
    cte l0 =
      Project (#0, #2, #6..=#9) // { arity: 6 }
        Map (array_index(regexp_split_to_array[",", case_insensitive=false](#1{trans}), integer_to_bigint(#2{priority})), substr(#3{rule}, 2, 1), ((#4 = "<") OR (#4 = ">")), case when #5 then substr(#3, 1, 1) else "x" end, case when #5 then substr(#3, 2, 1) else ">" end, case when #5 then text_to_integer(array_index(regexp_split_to_array[":", case_insensitive=false](substr(#3, 3)), 1)) else 0 end, case when #5 then array_index(regexp_split_to_array[":", case_insensitive=false](substr(#3, 3)), 2) else #3 end) // { arity: 10 }
          FlatMap generate_series(1, (regexp_split_to_array[",", case_insensitive=false](#1{trans}) array_length 1), 1) // { arity: 3 }
            Project (#3, #4) // { arity: 2 }
              Filter (#3) IS NOT NULL // { arity: 5 }
                Map (regexp_split_to_array["\{", case_insensitive=false](#1{line}), array_index(#2, 1), btrim(array_index(#2, 2), "}")) // { arity: 5 }
                  FlatMap unnest_array(regexp_split_to_array["\n", case_insensitive=false](#0{block1})) // { arity: 2 }
                    Project (#1) // { arity: 1 }
                      Map (array_index(regexp_split_to_array["\n\n", case_insensitive=false](#0{input}), 1)) // { arity: 2 }
                        ReadStorage materialize.public.input // { arity: 1 }
  Return // { arity: 2 }
    With Mutually Recursive
      cte l1 =
        Union // { arity: 5 }
          Project (#7, #3..=#6) // { arity: 5 }
            Map (regexp_split_to_array[",", case_insensitive=false](btrim(btrim(#1{unnest}, "\}"), "\{")), text_to_integer(substr(array_index(#2, 1), 3)), text_to_integer(substr(array_index(#2, 2), 3)), text_to_integer(substr(array_index(#2, 3), 3)), text_to_integer(substr(array_index(#2, 4), 3)), "in") // { arity: 8 }
              FlatMap unnest_array(regexp_split_to_array["\n", case_insensitive=false](#0{block2})) // { arity: 2 }
                Project (#1) // { arity: 1 }
                  Map (array_index(regexp_split_to_array["\n\n", case_insensitive=false](#0{input}), 2)) // { arity: 2 }
                    ReadStorage materialize.public.input // { arity: 1 }
          Project (#6, #1..=#4) // { arity: 5 }
            TopK group_by=[#0, #1, #2, #3, #4] order_by=[#5 asc nulls_last] limit=1 // { arity: 7 }
              Project (#0..=#4, #6, #10) // { arity: 7 }
                Filter case when (#8{cmp} = "<") then case when (#7{field} = "x") then (#1{x} < #9{val}) else case when (#7{field} = "m") then (#2{m} < #9{val}) else case when (#7{field} = "a") then (#3{a} < #9{val}) else case when (#7{field} = "s") then (#4{s} < #9{val}) else false end end end end else case when (#8{cmp} = ">") then case when (#7{field} = "x") then (#1{x} > #9{val}) else case when (#7{field} = "m") then (#2{m} > #9{val}) else case when (#7{field} = "a") then (#3{a} > #9{val}) else case when (#7{field} = "s") then (#4{s} > #9{val}) else false end end end end else false end end // { arity: 11 }
                  Join on=(#0{state} = #5{state}) type=differential // { arity: 11 }
                    implementation
                      %0:l1[#0{state}]K » %1:l0[#0{state}]K
                    ArrangeBy keys=[[#0{state}]] // { arity: 5 }
                      Filter (#0{state}) IS NOT NULL // { arity: 5 }
                        Get l1 // { arity: 5 }
                    ArrangeBy keys=[[#0{state}]] // { arity: 6 }
                      Get l0 // { arity: 6 }
      cte l2 =
        Reduce aggregates=[sum((((#0{x} + #1{m}) + #2{a}) + #3{s}))] // { arity: 1 }
          Project (#1..=#4) // { arity: 4 }
            Filter (#0{state} = "A") // { arity: 5 }
              Get l1 // { arity: 5 }
      cte l3 =
        Project (#0..=#9, #12..=#15) // { arity: 14 }
          Join on=(#0{state} = #10{state} AND #1{priority} = #11{priority}) type=differential // { arity: 16 }
            implementation
              %0:l4[#0{state}, #1{priority}]KK » %1:l0[#0{state}, #1{priority}]KK
            ArrangeBy keys=[[#0{state}, #1{priority}]] // { arity: 10 }
              Filter (#0{state}) IS NOT NULL // { arity: 10 }
                Get l4 // { arity: 10 }
            ArrangeBy keys=[[#0{state}, #1{priority}]] // { arity: 6 }
              Get l0 // { arity: 6 }
      cte l4 =
        Union // { arity: 10 }
          Project (#13, #28, #16, #18, #20, #21, #23, #24, #26, #27) // { arity: 10 }
            Map ((#10{field} = "x"), (#11{cmp} = ">"), case when (#14 AND #15) then greatest((#12{val} + 1), #2{xl}) else #2{xl} end, (#11{cmp} = "<"), case when (#14 AND #17) then least((#12{val} - 1), #3{xu}) else #3{xu} end, (#10{field} = "m"), case when (#15 AND #19) then greatest((#12{val} + 1), #4{ml}) else #4{ml} end, case when (#17 AND #19) then least((#12{val} - 1), #5{mu}) else #5{mu} end, (#10{field} = "a"), case when (#15 AND #22) then greatest((#12{val} + 1), #6{al}) else #6{al} end, case when (#17 AND #22) then least((#12{val} - 1), #7{au}) else #7{au} end, (#10{field} = "s"), case when (#15 AND #25) then greatest((#12{val} + 1), #8{sl}) else #8{sl} end, case when (#17 AND #25) then least((#12{val} - 1), #9{su}) else #9{su} end, 1) // { arity: 29 }
              Get l3 // { arity: 14 }
          Project (#0, #14, #17, #19, #21, #22, #24, #25, #27, #28) // { arity: 10 }
            Map ((#1{priority} + 1), (#10{field} = "x"), (#11{cmp} = "<"), case when (#15 AND #16) then greatest(#12{val}, #2{xl}) else #2{xl} end, (#11{cmp} = ">"), case when (#15 AND #18) then least(#12{val}, #3{xu}) else #3{xu} end, (#10{field} = "m"), case when (#16 AND #20) then greatest(#12{val}, #4{ml}) else #4{ml} end, case when (#18 AND #20) then least(#12{val}, #5{mu}) else #5{mu} end, (#10{field} = "a"), case when (#16 AND #23) then greatest(#12{val}, #6{al}) else #6{al} end, case when (#18 AND #23) then least(#12{val}, #7{au}) else #7{au} end, (#10{field} = "s"), case when (#16 AND #26) then greatest(#12{val}, #8{sl}) else #8{sl} end, case when (#18 AND #26) then least(#12{val}, #9{su}) else #9{su} end) // { arity: 29 }
              Get l3 // { arity: 14 }
          Constant // { arity: 10 }
            - ("in", 1, 1, 4000, 1, 4000, 1, 4000, 1, 4000)
    Return // { arity: 2 }
      With
        cte l5 =
          Reduce aggregates=[sum((((integer_to_bigint(((1 + #1{xu}) - #0{xl})) * integer_to_bigint(((1 + #3{mu}) - #2{ml}))) * integer_to_bigint(((1 + #5{au}) - #4{al}))) * integer_to_bigint(((1 + #7{su}) - #6{sl}))))] // { arity: 1 }
            Project (#2..=#9) // { arity: 8 }
              Filter (#0{state} = "A") // { arity: 10 }
                Get l4 // { arity: 10 }
      Return // { arity: 2 }
        CrossJoin type=differential // { arity: 2 }
          implementation
            %0[×]U » %1[×]U
          ArrangeBy keys=[[]] // { arity: 1 }
            Union // { arity: 1 }
              Get l2 // { arity: 1 }
              Map (null) // { arity: 1 }
                Union // { arity: 0 }
                  Negate // { arity: 0 }
                    Project () // { arity: 0 }
                      Get l2 // { arity: 1 }
                  Constant // { arity: 0 }
                    - ()
          ArrangeBy keys=[[]] // { arity: 1 }
            Union // { arity: 1 }
              Get l5 // { arity: 1 }
              Map (null) // { arity: 1 }
                Union // { arity: 0 }
                  Negate // { arity: 0 }
                    Project () // { arity: 0 }
                      Get l5 // { arity: 1 }
                  Constant // { arity: 0 }
                    - ()

Source materialize.public.input

Target cluster: quickstart

EOF