Materialize/test/sqllogictest/advent-of-code/2023/aoc_1222.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_1222.md

mode cockroach

statement ok
CREATE TABLE input (input TEXT);

statement ok
INSERT INTO input VALUES (
'3,5,62~3,9,62
5,5,623~5,1,623
8,3,176~8,2,176
7,6,17~7,8,17
9,3,821~9,3,163
2,9,71~2,6,71
3,3,514~3,3,390
7,4,494~7,9,494
5,9,842~5,9,840
9,1,41~9,1,296
5,4,276~5,4,94
3,3,838~3,6,838
9,8,425~6,8,425
1,2,55~1,8,55
1,4,249~3,4,249
8,8,541~5,8,541
5,4,634~5,4,365
4,9,745~4,9,293
3,6,621~3,6,287
4,9,645~4,9,389
7,1,712~0,1,712
8,2,69~7,2,69
2,3,374~8,3,374
7,9,495~0,9,495
4,9,200~8,9,200');

query II
WITH MUTUALLY RECURSIVE

    lines(r INT, line TEXT) AS (
        SELECT r, regexp_split_to_array(input, '\n')[r] as line
        FROM input, generate_series(1, array_length(regexp_split_to_array(input, '\n'), 1)) r
    ),

    cells(r INT, x INT, y INT, z INT) AS (
        SELECT xs.r, x, y, z
        FROM (SELECT r, generate_series(regexp_split_to_array(regexp_split_to_array(line, '~')[1], ',')[1]::INT,
                                        regexp_split_to_array(regexp_split_to_array(line, '~')[2], ',')[1]::INT) x FROM lines) xs,
             (SELECT r, generate_series(regexp_split_to_array(regexp_split_to_array(line, '~')[1], ',')[2]::INT,
                                        regexp_split_to_array(regexp_split_to_array(line, '~')[2], ',')[2]::INT) y FROM lines) ys,
             (SELECT r, generate_series(regexp_split_to_array(regexp_split_to_array(line, '~')[1], ',')[3]::INT,
                                        regexp_split_to_array(regexp_split_to_array(line, '~')[2], ',')[3]::INT) z FROM lines) zs
        WHERE xs.r = ys.r
          AND xs.r = zs.r
    ),

    -- Part one: let the pieces fall, with a minimum z value of one.
    parts(r INT, x INT, y INT, z INT) AS (
        SELECT * FROM cells
        EXCEPT ALL SELECT * FROM cells_delayed
        UNION ALL
        SELECT r, x, y, CASE WHEN r IN (SELECT * FROM supported) THEN z ELSE z - 1 END
        FROM parts
    ),
    -- One piece supports a *different* piece if it is directly below a piece of the other.
    supports(r1 INT, r2 INT) AS (
        SELECT DISTINCT p1.r, p2.r
        FROM parts p1, parts p2
        WHERE p1.x = p2.x
          AND p1.y = p2.y
          AND p1.z + 1 = p2.z
          AND p1.r != p2.r
    ),
    supported(r INT) AS (
        SELECT r FROM parts WHERE z = 1
        UNION
        SELECT r2 FROM supports
    ),
    -- A piece is safe to remove if it is does not uniquely support any other piece.
    part1(part1 BIGINT) AS (
        SELECT COUNT(DISTINCT r)
        FROM lines
        WHERE r NOT IN (
            SELECT r1
            FROM supports
            WHERE r2 IN (
                SELECT r2
                FROM supports
                GROUP BY r2
                HAVING COUNT(*) = 1
            )
        )
    ),

    cells_delayed(r INT, x INT, y INT, z INT) AS ( SELECT * FROM cells ),

    -- Part two: for each piece, how many pieces would fall if you removed it?
    -- Extend `supports` to transitive support: if r1 vanished would r2 fall?
    supports_trans(r1 INT, r2 INT) AS (
        -- Uniquely supported pieces would certainly fall.
        SELECT *
        FROM supports
        WHERE r2 IN (SELECT r2 FROM supports GROUP BY r2 HAVING COUNT(*) = 1)
        -- Any piece all of whose supports would fall without 'a' also falls without it.
        UNION
        SELECT st.r1, s1.r2
        FROM supports_trans st, supports s1
        WHERE st.r2 = s1.r1
        GROUP BY st.r1, s1.r2
        HAVING COUNT(*) = (SELECT COUNT(*) FROM supports WHERE supports.r2 = s1.r2)
    ),

    part2(part2 BIGINT) AS (SELECT COUNT(*) FROM supports_trans)

SELECT * FROM part1, part2;
----
23  3

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

    lines(r INT, line TEXT) AS (
        SELECT r, regexp_split_to_array(input, '\n')[r] as line
        FROM input, generate_series(1, array_length(regexp_split_to_array(input, '\n'), 1)) r
    ),

    cells(r INT, x INT, y INT, z INT) AS (
        SELECT xs.r, x, y, z
        FROM (SELECT r, generate_series(regexp_split_to_array(regexp_split_to_array(line, '~')[1], ',')[1]::INT,
                                        regexp_split_to_array(regexp_split_to_array(line, '~')[2], ',')[1]::INT) x FROM lines) xs,
             (SELECT r, generate_series(regexp_split_to_array(regexp_split_to_array(line, '~')[1], ',')[2]::INT,
                                        regexp_split_to_array(regexp_split_to_array(line, '~')[2], ',')[2]::INT) y FROM lines) ys,
             (SELECT r, generate_series(regexp_split_to_array(regexp_split_to_array(line, '~')[1], ',')[3]::INT,
                                        regexp_split_to_array(regexp_split_to_array(line, '~')[2], ',')[3]::INT) z FROM lines) zs
        WHERE xs.r = ys.r
          AND xs.r = zs.r
    ),

    -- Part one: let the pieces fall, with a minimum z value of one.
    parts(r INT, x INT, y INT, z INT) AS (
        SELECT * FROM cells
        EXCEPT ALL SELECT * FROM cells_delayed
        UNION ALL
        SELECT r, x, y, CASE WHEN r IN (SELECT * FROM supported) THEN z ELSE z - 1 END
        FROM parts
    ),
    -- One piece supports a *different* piece if it is directly below a piece of the other.
    supports(r1 INT, r2 INT) AS (
        SELECT DISTINCT p1.r, p2.r
        FROM parts p1, parts p2
        WHERE p1.x = p2.x
          AND p1.y = p2.y
          AND p1.z + 1 = p2.z
          AND p1.r != p2.r
    ),
    supported(r INT) AS (
        SELECT r FROM parts WHERE z = 1
        UNION
        SELECT r2 FROM supports
    ),
    -- A piece is safe to remove if it is does not uniquely support any other piece.
    part1(part1 BIGINT) AS (
        SELECT COUNT(DISTINCT r)
        FROM lines
        WHERE r NOT IN (
            SELECT r1
            FROM supports
            WHERE r2 IN (
                SELECT r2
                FROM supports
                GROUP BY r2
                HAVING COUNT(*) = 1
            )
        )
    ),

    cells_delayed(r INT, x INT, y INT, z INT) AS ( SELECT * FROM cells ),

    -- Part two: for each piece, how many pieces would fall if you removed it?
    -- Extend `supports` to transitive support: if r1 vanished would r2 fall?
    supports_trans(r1 INT, r2 INT) AS (
        -- Uniquely supported pieces would certainly fall.
        SELECT *
        FROM supports
        WHERE r2 IN (SELECT r2 FROM supports GROUP BY r2 HAVING COUNT(*) = 1)
        -- Any piece all of whose supports would fall without 'a' also falls without it.
        UNION
        SELECT st.r1, s1.r2
        FROM supports_trans st, supports s1
        WHERE st.r2 = s1.r1
        GROUP BY st.r1, s1.r2
        HAVING COUNT(*) = (SELECT COUNT(*) FROM supports WHERE supports.r2 = s1.r2)
    ),

    part2(part2 BIGINT) AS (SELECT COUNT(*) FROM supports_trans)

SELECT * FROM part1, part2;
----
Explained Query:
  With
    cte l0 =
      Project (#1, #2) // { arity: 2 }
        Map (array_index(regexp_split_to_array["\n", case_insensitive=false](#0{input}), integer_to_bigint(#1{r}))) // { arity: 3 }
          FlatMap generate_series(1, (regexp_split_to_array["\n", case_insensitive=false](#0{input}) array_length 1), 1) // { arity: 2 }
            ReadStorage materialize.public.input // { arity: 1 }
    cte l1 =
      Project (#0) // { arity: 1 }
        Get l0 // { arity: 2 }
    cte l2 =
      Distinct project=[#0] // { arity: 1 }
        Get l1 // { arity: 1 }
    cte l3 =
      Project (#0, #1, #3, #5) // { arity: 4 }
        Join on=(#0{r} = #2{r} = #4{r}) type=delta // { arity: 6 }
          implementation
            %0 » %1[#0{r}]K » %2[#0{r}]K
            %1 » %0[#0{r}]K » %2[#0{r}]K
            %2 » %0[#0{r}]K » %1[#0{r}]K
          ArrangeBy keys=[[#0{r}]] // { arity: 2 }
            Project (#0, #2) // { arity: 2 }
              FlatMap generate_series(text_to_integer(array_index(regexp_split_to_array[",", case_insensitive=false](array_index(regexp_split_to_array["~", case_insensitive=false](#1{line}), 1)), 1)), text_to_integer(array_index(regexp_split_to_array[",", case_insensitive=false](array_index(regexp_split_to_array["~", case_insensitive=false](#1{line}), 2)), 1)), 1) // { arity: 3 }
                Get l0 // { arity: 2 }
          ArrangeBy keys=[[#0{r}]] // { arity: 2 }
            Project (#0, #2) // { arity: 2 }
              FlatMap generate_series(text_to_integer(array_index(regexp_split_to_array[",", case_insensitive=false](array_index(regexp_split_to_array["~", case_insensitive=false](#1{line}), 1)), 2)), text_to_integer(array_index(regexp_split_to_array[",", case_insensitive=false](array_index(regexp_split_to_array["~", case_insensitive=false](#1{line}), 2)), 2)), 1) // { arity: 3 }
                Get l0 // { arity: 2 }
          ArrangeBy keys=[[#0{r}]] // { arity: 2 }
            Project (#0, #2) // { arity: 2 }
              FlatMap generate_series(text_to_integer(array_index(regexp_split_to_array[",", case_insensitive=false](array_index(regexp_split_to_array["~", case_insensitive=false](#1{line}), 1)), 3)), text_to_integer(array_index(regexp_split_to_array[",", case_insensitive=false](array_index(regexp_split_to_array["~", case_insensitive=false](#1{line}), 2)), 3)), 1) // { arity: 3 }
                Get l0 // { arity: 2 }
  Return // { arity: 2 }
    With Mutually Recursive
      cte l4 =
        Distinct project=[#0] // { arity: 1 }
          Project (#0) // { arity: 1 }
            Get l9 // { arity: 4 }
      cte l5 =
        Reduce group_by=[#0] aggregates=[any((#0{r} = #1{right_col0_0}))] // { arity: 2 }
          CrossJoin type=differential // { arity: 2 }
            implementation
              %0:l4[×] » %1:l12[×]
            ArrangeBy keys=[[]] // { arity: 1 }
              Get l4 // { arity: 1 }
            ArrangeBy keys=[[]] // { arity: 1 }
              Get l12 // { arity: 1 }
      cte l6 =
        ArrangeBy keys=[[#0]] // { arity: 1 }
          Get l4 // { arity: 1 }
      cte l7 =
        Union // { arity: 2 }
          Get l5 // { arity: 2 }
          Project (#0, #2) // { arity: 2 }
            Map (false) // { arity: 3 }
              Join on=(#0 = #1) type=differential // { arity: 2 }
                implementation
                  %1:l6[#0]UK » %0[#0]K
                ArrangeBy keys=[[#0]] // { arity: 1 }
                  Union // { arity: 1 }
                    Negate // { arity: 1 }
                      Project (#0) // { arity: 1 }
                        Get l5 // { arity: 2 }
                    Get l4 // { arity: 1 }
                Get l6 // { arity: 1 }
      cte l8 =
        Union // { arity: 2 }
          Get l7 // { arity: 2 }
          Project (#0, #2) // { arity: 2 }
            FlatMap guard_subquery_size(#1{count}) // { arity: 3 }
              Reduce group_by=[#0] aggregates=[count(*)] // { arity: 2 }
                Project (#0) // { arity: 1 }
                  Get l7 // { arity: 2 }
      cte l9 =
        Union // { arity: 4 }
          Threshold // { arity: 4 }
            Union // { arity: 4 }
              Get l3 // { arity: 4 }
              Negate // { arity: 4 }
                Get l16 // { arity: 4 }
          Project (#0..=#2, #6) // { arity: 4 }
            Map (case when #5{any} then #3{z} else (#3{z} - 1) end) // { arity: 7 }
              Join on=(#0 = #4) type=differential // { arity: 6 }
                implementation
                  %0:l9[#0]K » %1[#0]K
                ArrangeBy keys=[[#0]] // { arity: 4 }
                  Get l9 // { arity: 4 }
                ArrangeBy keys=[[#0]] // { arity: 2 }
                  Union // { arity: 2 }
                    Get l8 // { arity: 2 }
                    Project (#0, #2) // { arity: 2 }
                      Map (null) // { arity: 3 }
                        Join on=(#0 = #1) type=differential // { arity: 2 }
                          implementation
                            %1:l6[#0]UK » %0[#0]K
                          ArrangeBy keys=[[#0]] // { arity: 1 }
                            Union // { arity: 1 }
                              Negate // { arity: 1 }
                                Distinct project=[#0] // { arity: 1 }
                                  Project (#0) // { arity: 1 }
                                    Get l8 // { arity: 2 }
                              Get l4 // { arity: 1 }
                          Get l6 // { arity: 1 }
      cte l10 =
        Distinct project=[#0, #1] // { arity: 2 }
          Project (#0, #4) // { arity: 2 }
            Filter (#0{r} != #4{r}) // { arity: 8 }
              Join on=(#1{x} = #5{x} AND #2{y} = #6{y} AND #7{z} = (#3{z} + 1)) type=differential // { arity: 8 }
                implementation
                  %0:l9[#1{x}, #2{y}, (#3{z} + 1)]KKK » %1:l9[#1{x}..=#3{z}]KKK
                ArrangeBy keys=[[#1{x}, #2{y}, (#3{z} + 1)]] // { arity: 4 }
                  Get l9 // { arity: 4 }
                ArrangeBy keys=[[#1{x}..=#3{z}]] // { arity: 4 }
                  Get l9 // { arity: 4 }
      cte l11 =
        Project (#1) // { arity: 1 }
          Get l10 // { arity: 2 }
      cte l12 =
        Distinct project=[#0] // { arity: 1 }
          Union // { arity: 1 }
            Project (#0) // { arity: 1 }
              Filter (#3{z} = 1) // { arity: 4 }
                Get l9 // { arity: 4 }
            Get l11 // { arity: 1 }
      cte l13 =
        CrossJoin type=differential // { arity: 3 }
          implementation
            %0:l2[×] » %1:l10[×]
          ArrangeBy keys=[[]] // { arity: 1 }
            Get l2 // { arity: 1 }
          ArrangeBy keys=[[]] // { arity: 2 }
            Get l10 // { arity: 2 }
      cte l14 =
        ArrangeBy keys=[[#0]] // { arity: 1 }
          Get l11 // { arity: 1 }
      cte l15 =
        Reduce aggregates=[count(distinct #0{r})] // { arity: 1 }
          Project (#0) // { arity: 1 }
            Join on=(#0 = #1) type=differential // { arity: 2 }
              implementation
                %0:l1[#0]K » %1[#0]K
              ArrangeBy keys=[[#0]] // { arity: 1 }
                Get l1 // { arity: 1 }
              ArrangeBy keys=[[#0]] // { arity: 1 }
                Union // { arity: 1 }
                  Negate // { arity: 1 }
                    Distinct project=[#0] // { arity: 1 }
                      Project (#0) // { arity: 1 }
                        Filter (#3{count} = 1) // { arity: 4 }
                          Join on=(#1 = #2) type=differential // { arity: 4 }
                            implementation
                              %1[#0]UKAef » %0:l13[#1]Kef
                            ArrangeBy keys=[[#1]] // { arity: 2 }
                              Project (#0, #2) // { arity: 2 }
                                Filter (#0 = #1) // { arity: 3 }
                                  Get l13 // { arity: 3 }
                            ArrangeBy keys=[[#0]] // { arity: 2 }
                              Reduce group_by=[#0] aggregates=[count(*)] // { arity: 2 }
                                Project (#0) // { arity: 1 }
                                  Join on=(#0 = #1) type=differential // { arity: 2 }
                                    implementation
                                      %0[#0]UKA » %1:l14[#0]K
                                    ArrangeBy keys=[[#0]] // { arity: 1 }
                                      Distinct project=[#0] // { arity: 1 }
                                        Project (#2) // { arity: 1 }
                                          Get l13 // { arity: 3 }
                                    Get l14 // { arity: 1 }
                  Get l2 // { arity: 1 }
      cte l16 =
        Get l3 // { arity: 4 }
      cte l17 =
        Reduce group_by=[#0, #1] aggregates=[count(*)] // { arity: 3 }
          Project (#0, #3) // { arity: 2 }
            Join on=(#1{r2} = #2{r1}) type=differential // { arity: 4 }
              implementation
                %0:l22[#1{r2}]K » %1:l10[#0{r1}]K
              ArrangeBy keys=[[#1{r2}]] // { arity: 2 }
                Get l22 // { arity: 2 }
              ArrangeBy keys=[[#0{r1}]] // { arity: 2 }
                Get l10 // { arity: 2 }
      cte l18 =
        Distinct project=[#0] // { arity: 1 }
          Project (#1) // { arity: 1 }
            Get l17 // { arity: 3 }
      cte l19 =
        ArrangeBy keys=[[#0{r2}]] // { arity: 1 }
          Get l18 // { arity: 1 }
      cte l20 =
        Reduce group_by=[#0] aggregates=[count(*)] // { arity: 2 }
          Project (#0) // { arity: 1 }
            Join on=(#0{r2} = #1{r2}) type=differential // { arity: 2 }
              implementation
                %0:l19[#0{r2}]UK » %1:l14[#0{r2}]K
              Get l19 // { arity: 1 }
              Get l14 // { arity: 1 }
      cte l21 =
        Union // { arity: 2 }
          Get l20 // { arity: 2 }
          Project (#0, #2) // { arity: 2 }
            Map (0) // { arity: 3 }
              Join on=(#0 = #1) type=differential // { arity: 2 }
                implementation
                  %1:l19[#0]UK » %0[#0]K
                ArrangeBy keys=[[#0]] // { arity: 1 }
                  Union // { arity: 1 }
                    Negate // { arity: 1 }
                      Project (#0) // { arity: 1 }
                        Get l20 // { arity: 2 }
                    Get l18 // { arity: 1 }
                Get l19 // { arity: 1 }
      cte l22 =
        Distinct project=[#0, #1] // { arity: 2 }
          Union // { arity: 2 }
            Project (#0, #1) // { arity: 2 }
              Filter (#3{count} = 1) // { arity: 4 }
                Join on=(#1 = #2) type=differential // { arity: 4 }
                  implementation
                    %1[#0]UKAef » %0:l10[#1]Kef
                  ArrangeBy keys=[[#1]] // { arity: 2 }
                    Get l10 // { arity: 2 }
                  ArrangeBy keys=[[#0]] // { arity: 2 }
                    Reduce group_by=[#0] aggregates=[count(*)] // { arity: 2 }
                      Get l11 // { arity: 1 }
            Project (#0, #1) // { arity: 2 }
              Join on=(#1 = #3 AND #2{count} = #4{count}) type=differential // { arity: 5 }
                implementation
                  %0:l17[#1, #2{"?column?"}]KK » %1[#0, #1]KK
                ArrangeBy keys=[[#1, #2{count}]] // { arity: 3 }
                  Get l17 // { arity: 3 }
                ArrangeBy keys=[[#0, #1{count}]] // { arity: 2 }
                  Union // { arity: 2 }
                    Get l21 // { arity: 2 }
                    Project (#0, #2) // { arity: 2 }
                      FlatMap guard_subquery_size(#1{count}) // { arity: 3 }
                        Reduce group_by=[#0] aggregates=[count(*)] // { arity: 2 }
                          Project (#0) // { arity: 1 }
                            Get l21 // { arity: 2 }
    Return // { arity: 2 }
      With
        cte l23 =
          Reduce aggregates=[count(*)] // { arity: 1 }
            Project () // { arity: 0 }
              Get l22 // { arity: 2 }
      Return // { arity: 2 }
        CrossJoin type=differential // { arity: 2 }
          implementation
            %0[×]U » %1[×]U
          ArrangeBy keys=[[]] // { arity: 1 }
            Union // { arity: 1 }
              Get l15 // { arity: 1 }
              Map (0) // { arity: 1 }
                Union // { arity: 0 }
                  Negate // { arity: 0 }
                    Project () // { arity: 0 }
                      Get l15 // { arity: 1 }
                  Constant // { arity: 0 }
                    - ()
          ArrangeBy keys=[[]] // { arity: 1 }
            Union // { arity: 1 }
              Get l23 // { arity: 1 }
              Map (0) // { arity: 1 }
                Union // { arity: 0 }
                  Negate // { arity: 0 }
                    Project () // { arity: 0 }
                      Get l23 // { arity: 1 }
                  Constant // { arity: 0 }
                    - ()

Source materialize.public.input

Target cluster: quickstart

EOF