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

mode cockroach

statement ok
CREATE TABLE input (input TEXT);

# no input data

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

    lines(r INT, characters TEXT, springs TEXT) AS (
        SELECT
            row_id,
            regexp_split_to_array(regexp_split_to_array(input, '\n')[row_id], ' ')[1] || '.',
            regexp_split_to_array(regexp_split_to_array(input, '\n')[row_id], ' ')[2]
        FROM
            input,
            generate_series(1, array_length(regexp_split_to_array(input, '\n'), 1)) row_id
    ),
    characters(r INT, pos INT, symb TEXT) AS (
        SELECT
            r,
            pos,
            substring(characters, pos, 1)
        FROM
            lines,
            generate_series(1, length(characters)) pos
    ),
    springs(r INT, pos INT, len INT) AS (
        SELECT
            r,
            pos,
            regexp_split_to_array(springs, ',')[pos]::INT
        FROM
            lines,
            generate_series(1, array_length(regexp_split_to_array(springs, ','), 1)) pos
    ),

    -- How many ways can we pack row `r`'s first `spring` springs (plus a space) into the first `chars` characters?
    -- Importantly, the "plus a space" applies to the last spring also! Each of these should admit the immediate appending of a new spring.
    fits(r INT, chars INT, spring INT) AS (
        -- We can pack no springs into no characters.
        SELECT r, 0, 0
        FROM lines
        -- We can extend any fits with a blank, as long as there are no '#' observations.
        UNION ALL
        SELECT fits.r, fits.chars + 1, fits.spring
        FROM fits, characters
        WHERE fits.r = characters.r
          AND fits.chars + 1 = characters.pos
          AND characters.symb != '#'
        -- We can extend any fits with the next spring and a blank, as long as no '.' in the spring and no '#' in the blank.
        UNION ALL
        SELECT fits.r, fits.chars + springs.len + 1, fits.spring + 1
        FROM
            fits,
            springs,
            characters
        WHERE fits.r = springs.r
          AND fits.spring + 1 = springs.pos
          AND fits.r = characters.r
          AND fits.chars + springs.len + 1 = characters.pos
          AND characters.symb != '#'
          AND NOT EXISTS (SELECT FROM characters c WHERE c.r = fits.r AND c.symb = '.' AND c.pos BETWEEN fits.chars + 1 AND fits.chars + springs.len)
    ),

    fit_counts(r INT, chars INT, spring INT, count BIGINT) AS (
        SELECT r, chars, spring, COUNT(*) AS count
        FROM fits
        GROUP BY r, chars, spring
    ),
    counts(r INT, chars INT, spring INT, count BIGINT) AS (
        SELECT DISTINCT ON (r) r, chars, spring, count
        FROM fit_counts
        ORDER BY r, chars DESC, spring DESC
    ),

    potato (x INT) AS ( SELECT 1 )

SELECT SUM(count) FROM counts;
----
Explained Query:
  With
    cte l0 =
      Project (#1, #3, #4) // { arity: 3 }
        Map (regexp_split_to_array[" ", case_insensitive=false](array_index(regexp_split_to_array["\n", case_insensitive=false](#0{input}), integer_to_bigint(#1{row_id}))), (array_index(#2, 1) || "."), array_index(#2, 2)) // { arity: 5 }
          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, #2, #3) // { arity: 3 }
        Map (substr(#1{characters}, #2{pos}, 1)) // { arity: 4 }
          FlatMap generate_series(1, char_length(#1{characters}), 1) // { arity: 3 }
            Project (#0, #1) // { arity: 2 }
              Get l0 // { arity: 3 }
    cte l2 =
      ArrangeBy keys=[[#0{r}, #1{pos}]] // { arity: 2 }
        Project (#0, #1) // { arity: 2 }
          Filter (#2{symb} != "#") // { arity: 3 }
            Get l1 // { arity: 3 }
  Return // { arity: 1 }
    With Mutually Recursive
      cte l3 =
        Project (#0..=#2, #5) // { arity: 4 }
          Join on=(#0{r} = #3{r} = #6{r} AND #4{pos} = (#2{spring} + 1) AND #7{pos} = ((#1{chars} + #5{len}) + 1)) type=delta // { arity: 8 }
            implementation
              %0:l5 » %1[#0{r}, #1{pos}]KK » %2:l2[#0{r}, #1{pos}]KKf
              %1 » %0:l5[#0{r}, (#2{spring} + 1)]KK » %2:l2[#0{r}, #1{pos}]KKf
              %2:l2 » %0:l5[#0{r}]K » %1[#0{r}, #1{pos}]KK
            ArrangeBy keys=[[#0{r}], [#0{r}, (#2{spring} + 1)]] // { arity: 3 }
              Get l5 // { arity: 3 }
            ArrangeBy keys=[[#0{r}, #1{pos}]] // { arity: 3 }
              Project (#0, #2, #3) // { arity: 3 }
                Map (text_to_integer(array_index(regexp_split_to_array[",", case_insensitive=false](#1{springs}), integer_to_bigint(#2{pos})))) // { arity: 4 }
                  FlatMap generate_series(1, (regexp_split_to_array[",", case_insensitive=false](#1{springs}) array_length 1), 1) // { arity: 3 }
                    Project (#0, #2) // { arity: 2 }
                      Get l0 // { arity: 3 }
            Get l2 // { arity: 2 }
      cte l4 =
        Distinct project=[#0..=#2] // { arity: 3 }
          Project (#0, #1, #3) // { arity: 3 }
            Get l3 // { arity: 4 }
      cte l5 =
        Union // { arity: 3 }
          Project (#0, #3, #4) // { arity: 3 }
            Map (0, 0) // { arity: 5 }
              Get l0 // { arity: 3 }
          Project (#0, #5, #2) // { arity: 3 }
            Map ((#1{chars} + 1)) // { arity: 6 }
              Join on=(#0{r} = #3{r} AND #4{pos} = (#1{chars} + 1)) type=differential // { arity: 5 }
                implementation
                  %1:l2[#0{r}, #1{pos}]KKf » %0:l5[#0{r}, (#1{chars} + 1)]KKf
                ArrangeBy keys=[[#0{r}, (#1{chars} + 1)]] // { arity: 3 }
                  Get l5 // { arity: 3 }
                Get l2 // { arity: 2 }
          Project (#0, #7, #8) // { arity: 3 }
            Map (((#1{chars} + #3{len}) + 1), (#2{spring} + 1)) // { arity: 9 }
              Join on=(#0 = #4 AND #1 = #5 AND #3 = #6) type=differential // { arity: 7 }
                implementation
                  %0:l3[#0, #1, #3]KKK » %1[#0..=#2]KKK
                ArrangeBy keys=[[#0, #1, #3]] // { arity: 4 }
                  Get l3 // { arity: 4 }
                ArrangeBy keys=[[#0..=#2]] // { arity: 3 }
                  Union // { arity: 3 }
                    Negate // { arity: 3 }
                      Distinct project=[#0..=#2] // { arity: 3 }
                        Project (#0..=#2) // { arity: 3 }
                          Filter (#4{pos} >= (#1{chars} + 1)) AND (#4{pos} <= (#1{chars} + #2{len})) // { arity: 5 }
                            Join on=(#0{r} = #3{r}) type=differential // { arity: 5 }
                              implementation
                                %1:l1[#0{r}]Kef » %0:l4[#0{r}]Kef
                              ArrangeBy keys=[[#0{r}]] // { arity: 3 }
                                Get l4 // { arity: 3 }
                              ArrangeBy keys=[[#0{r}]] // { arity: 2 }
                                Project (#0, #1) // { arity: 2 }
                                  Filter (#2{symb} = ".") // { arity: 3 }
                                    Get l1 // { arity: 3 }
                    Get l4 // { arity: 3 }
    Return // { arity: 1 }
      With
        cte l6 =
          Reduce aggregates=[sum(#0{count})] // { arity: 1 }
            Project (#3{count}) // { arity: 1 }
              TopK group_by=[#0] order_by=[#1 desc nulls_first, #2 desc nulls_first] limit=1 // { arity: 4 }
                Reduce group_by=[#0..=#2] aggregates=[count(*)] // { arity: 4 }
                  Get l5 // { arity: 3 }
      Return // { arity: 1 }
        Union // { arity: 1 }
          Get l6 // { arity: 1 }
          Map (null) // { arity: 1 }
            Union // { arity: 0 }
              Negate // { arity: 0 }
                Project () // { arity: 0 }
                  Get l6 // { arity: 1 }
              Constant // { arity: 0 }
                - ()

Source materialize.public.input

Target cluster: quickstart

EOF