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

mode cockroach

statement ok
CREATE TABLE input (input TEXT);

# no data

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

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

    numbers(value INT, line_no INT, col_no INT) AS (
        SELECT regexp_split_to_array(line, ' ')[j]::INT, line_no, j
        FROM lines, generate_series(1, array_length(regexp_split_to_array(line, ' '), 1)) j
    ),

    -- Contains non-zero values of differences after each round.
    derivatives(value INT, line_no INT, col_no INT, round INT) AS (
        SELECT numbers.*, 1
        FROM numbers
        UNION
        SELECT
            COALESCE(i2.value, 0) - COALESCE(i1.value, 0),
            COALESCE(i1.line_no, i2.line_no),
            COALESCE(i1.col_no + 1, i2.col_no),
            COALESCE(i1.round, i2.round) + 1
        FROM derivatives i1 FULL OUTER JOIN derivatives i2 ON (i1.line_no = i2.line_no AND i1.round = i2.round AND i1.col_no + 1 = i2.col_no)
        WHERE COALESCE(i2.value, 0) - COALESCE(i1.value, 0) != 0
          AND COALESCE(i1.col_no + 1, i2.col_no) > COALESCE(i1.round, i2.round)
          AND COALESCE(i1.col_no + 1, i2.col_no) <= 21
    ),

    -- Accumulate the derivatives at the leading edge
    part1(part1 BIGINT) AS (
        SELECT SUM(value)
        FROM derivatives
        WHERE col_no = 21
    ),

    -- Accumulate the derivatives at the preceding edge
    part2(part2 BIGINT) AS (
        SELECT SUM(pow(-1, round + 1) * value)
        FROM derivatives
        WHERE col_no = round
    )

-- SELECT * FROM derivatives WHERE line_no = 1 ORDER BY round, col_no;
SELECT * FROM part1, part2;
----
Explained Query:
  With Mutually Recursive
    cte l0 =
      Map ((#2{col_no} + 1)) // { arity: 5 }
        Get l3 // { arity: 4 }
    cte l1 =
      Project (#0..=#4, #6) // { arity: 6 }
        Join on=(#1{line_no} = #5{line_no} AND #3{round} = #7{round} AND #6{col_no} = (#2{col_no} + 1)) type=differential // { arity: 8 }
          implementation
            %0:l0[#1{line_no}, (#2{col_no} + 1), #3{round}]KKKif » %1:l3[#1{line_no}..=#3{round}]KKKiif
          ArrangeBy keys=[[#1{line_no}, (#2{col_no} + 1), #3{round}]] // { arity: 4 }
            Project (#0..=#3) // { arity: 4 }
              Filter (#4 <= 21) AND (#1{line_no}) IS NOT NULL AND (#4 > #3{round}) // { arity: 5 }
                Get l0 // { arity: 5 }
          ArrangeBy keys=[[#1{line_no}..=#3{round}]] // { arity: 4 }
            Filter (#2{col_no} <= 21) AND (#1{line_no}) IS NOT NULL AND (#2{col_no} > #3{round}) // { arity: 4 }
              Get l3 // { arity: 4 }
    cte l2 =
      Distinct project=[#0..=#2] // { arity: 3 }
        Project (#1, #3, #5) // { arity: 3 }
          Get l1 // { arity: 6 }
    cte [recursion_limit=30, return_at_limit] l3 =
      Distinct project=[#0..=#3] // { arity: 4 }
        Union // { arity: 4 }
          Project (#3, #0, #2, #4) // { arity: 4 }
            Map (text_to_integer(array_index(regexp_split_to_array[" ", case_insensitive=false](#1{line}), integer_to_bigint(#2{j}))), 1) // { arity: 5 }
              FlatMap generate_series(1, (regexp_split_to_array[" ", case_insensitive=false](#1{line}) array_length 1), 1) // { arity: 3 }
                Project (#1, #2) // { arity: 2 }
                  Map (array_index(regexp_split_to_array["\n", case_insensitive=false](#0{input}), integer_to_bigint(#1{i}))) // { 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 }
          Project (#8..=#11) // { arity: 4 }
            Map ((coalesce(#4{value}, 0) - coalesce(#0{value}, 0)), coalesce(#1{line_no}, #5{line_no}), coalesce((#2{col_no} + 1), #6{col_no}), (coalesce(#3{round}, #7{round}) + 1)) // { arity: 12 }
              Union // { arity: 8 }
                Project (#4..=#7, #0..=#3) // { arity: 8 }
                  Map (null, null, null, null) // { arity: 8 }
                    Union // { arity: 4 }
                      Negate // { arity: 4 }
                        Project (#0..=#3) // { arity: 4 }
                          Join on=(#1{line_no} = #4 AND #2{col_no} = #6 AND #3{round} = #5) type=differential // { arity: 7 }
                            implementation
                              %1:l2[#0, #2, #1]UKKK » %0:l3[#1{line_no}..=#3{round}]KKKif
                            ArrangeBy keys=[[#1{line_no}..=#3{round}]] // { arity: 4 }
                              Filter (#2{col_no} <= 21) AND (#1{line_no}) IS NOT NULL AND (#2{col_no} > #3{round}) AND (0 != (coalesce(#0{value}, 0) - 0)) // { arity: 4 }
                                Get l3 // { arity: 4 }
                            ArrangeBy keys=[[#0, #2, #1]] // { arity: 3 }
                              Get l2 // { arity: 3 }
                      Filter (#2{col_no} <= 21) AND (#2{col_no} > #3{round}) AND (0 != (coalesce(#0{value}, 0) - 0)) // { arity: 4 }
                        Get l3 // { arity: 4 }
                Map (null, null, null, null) // { arity: 8 }
                  Union // { arity: 4 }
                    Negate // { arity: 4 }
                      Project (#0..=#3) // { arity: 4 }
                        Join on=(#1{line_no} = #4 AND #3{round} = #5 AND #6 = (#2{col_no} + 1)) type=differential // { arity: 7 }
                          implementation
                            %1:l2[#0..=#2]UKKK » %0:l0[#1{line_no}, #3{round}, (#2{col_no} + 1)]KKKif
                          ArrangeBy keys=[[#1{line_no}, #3{round}, (#2{col_no} + 1)]] // { arity: 4 }
                            Project (#0..=#3) // { arity: 4 }
                              Filter (#4 <= 21) AND (#1{line_no}) IS NOT NULL AND (#4 > #3{round}) AND (0 != (0 - coalesce(#0{value}, 0))) // { arity: 5 }
                                Get l0 // { arity: 5 }
                          ArrangeBy keys=[[#0..=#2]] // { arity: 3 }
                            Get l2 // { arity: 3 }
                    Project (#0..=#3) // { arity: 4 }
                      Filter (#4 <= 21) AND (#4 > #3{round}) AND (0 != (0 - coalesce(#0{value}, 0))) // { arity: 5 }
                        Get l0 // { arity: 5 }
                Project (#0..=#4, #1, #5, #3) // { arity: 8 }
                  Filter (0 != (coalesce(#4{value}, 0) - coalesce(#0{value}, 0))) // { arity: 6 }
                    Get l1 // { arity: 6 }
  Return // { arity: 2 }
    With
      cte l4 =
        Reduce aggregates=[sum(#0{value})] // { arity: 1 }
          Project (#0) // { arity: 1 }
            Filter (#2{col_no} = 21) // { arity: 4 }
              Get l3 // { arity: 4 }
      cte l5 =
        Reduce aggregates=[sum((power(-1, integer_to_double((#1{col_no} + 1))) * integer_to_double(#0{value})))] // { arity: 1 }
          Project (#0, #2) // { arity: 2 }
            Filter (#2{col_no} = #3{round}) // { arity: 4 }
              Get l3 // { arity: 4 }
    Return // { arity: 2 }
      CrossJoin type=differential // { arity: 2 }
        implementation
          %0[×]U » %1[×]U
        ArrangeBy keys=[[]] // { arity: 1 }
          Union // { arity: 1 }
            Get l4 // { arity: 1 }
            Map (null) // { arity: 1 }
              Union // { arity: 0 }
                Negate // { arity: 0 }
                  Project () // { arity: 0 }
                    Get l4 // { arity: 1 }
                Constant // { arity: 0 }
                  - ()
        ArrangeBy keys=[[]] // { arity: 1 }
          Project (#1) // { arity: 1 }
            Map (f64toi64(#0{sum})) // { arity: 2 }
              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