# 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_1215.md

mode cockroach

statement ok
CREATE TABLE input (input TEXT);

statement ok
INSERT INTO input
VALUES ('rn=1,xw-,nn=8,zg=2,lw=4,oo=2,tt-,wv=9,hy=7,rs=8,sm=4,lf-,td=9,zz=1,ca=2,nd-');

query II
WITH MUTUALLY RECURSIVE (RETURN AT RECURSION LIMIT 10)

    strings(r INT, string TEXT) AS (
        SELECT r, regexp_split_to_array(input, ',')[r]
        FROM input, generate_series(1, array_length(regexp_split_to_array(input, ','), 1)) r
    ),

    -- Advance the hash by one character, until all strings are empty.
    hashes(string TEXT, hash BIGINT) AS (
        SELECT string, 0 as hash
        FROM strings
        UNION ALL
        SELECT substring(string, 2), ((hash + ascii(substring(string, 1, 1))) * 17) % 256
        FROM hashes
        WHERE length(string) > 0
    ),

    part1(part1 BIGINT) AS (
        SELECT SUM(hash)
        FROM hashes
        WHERE string = ''
    ),

    -- Parse strings as symbol plus commands; either `-` or `=X`.
    commands(r INT, symb TEXT, op INT) AS (
        SELECT
            r,
            CASE WHEN substring(string, length(string)) = '-'
                 THEN substring(string, 1, length(string)-1)
                 ELSE substring(string, 1, length(string)-2)
            END,
            CASE WHEN substring(string, length(string)) = '-'
                 THEN 0
                 ELSE substring(string, length(string))::INT
            END
        FROM strings
    ),
    -- Operations that happen after a symbol's last delete operation.
    -- All other operations do not matter, and do not affect the state.
    final_ops(r INT, symb TEXT, op INT) AS (
        SELECT *
        FROM commands
        WHERE r > COALESCE(
            (SELECT MAX(r)
            FROM commands c2
            WHERE commands.symb = c2.symb
              AND c2.op = 0), 0)
    ),
    -- Each symbol is summarized by their first final insert time, and the last final operation
    final_state(r INT, symb TEXT, op INT) AS (
        SELECT DISTINCT ON(symb)
            (SELECT MIN(r) FROM final_ops fo2 WHERE fo2.symb = final_ops.symb),
            symb,
            op
        FROM final_ops
        ORDER BY symb, r DESC, op
    ),
    -- Redo the hash computation on symbols rather than commands.
    hashes2(start TEXT, string TEXT, hash BIGINT) AS (
        SELECT symb as start, symb as string, 0 as hash
        FROM final_state
        UNION ALL
        SELECT start, substring(string, 2), ((hash + ascii(substring(string, 1, 1))) * 17) % 256
        FROM hashes2
        WHERE length(string) > 0
    ),
    -- Bin up the state, so's we can tabulate it
    binned(hash BIGINT, r INT, symb TEXT, op INT) AS (
        SELECT hash, final_state.*
        FROM hashes2, final_state
        WHERE hashes2.start = symb
          AND hashes2.string = ''
    ),
    -- Sum the product of 1 + hash, the position in bin by r, and the op.
    part2(part2 BIGINT) AS (
        SELECT SUM(
            (1 + hash) *
            (SELECT COUNT(*) FROM binned b2 WHERE binned.hash = b2.hash AND binned.r >= b2.r) *
            op
        )
        FROM binned
    ),

    potato(x int) as (select 1)

SELECT * FROM part1, part2;
----
2021  6155

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

    strings(r INT, string TEXT) AS (
        SELECT r, regexp_split_to_array(input, ',')[r]
        FROM input, generate_series(1, array_length(regexp_split_to_array(input, ','), 1)) r
    ),

    -- Advance the hash by one character, until all strings are empty.
    hashes(string TEXT, hash BIGINT) AS (
        SELECT string, 0 as hash
        FROM strings
        UNION ALL
        SELECT substring(string, 2), ((hash + ascii(substring(string, 1, 1))) * 17) % 256
        FROM hashes
        WHERE length(string) > 0
    ),

    part1(part1 BIGINT) AS (
        SELECT SUM(hash)
        FROM hashes
        WHERE string = ''
    ),

    -- Parse strings as symbol plus commands; either `-` or `=X`.
    commands(r INT, symb TEXT, op INT) AS (
        SELECT
            r,
            CASE WHEN substring(string, length(string)) = '-'
                 THEN substring(string, 1, length(string)-1)
                 ELSE substring(string, 1, length(string)-2)
            END,
            CASE WHEN substring(string, length(string)) = '-'
                 THEN 0
                 ELSE substring(string, length(string))::INT
            END
        FROM strings
    ),
    -- Operations that happen after a symbol's last delete operation.
    -- All other operations do not matter, and do not affect the state.
    final_ops(r INT, symb TEXT, op INT) AS (
        SELECT *
        FROM commands
        WHERE r > COALESCE(
            (SELECT MAX(r)
            FROM commands c2
            WHERE commands.symb = c2.symb
              AND c2.op = 0), 0)
    ),
    -- Each symbol is summarized by their first final insert time, and the last final operation
    final_state(r INT, symb TEXT, op INT) AS (
        SELECT DISTINCT ON(symb)
            (SELECT MIN(r) FROM final_ops fo2 WHERE fo2.symb = final_ops.symb),
            symb,
            op
        FROM final_ops
        ORDER BY symb, r DESC, op
    ),
    -- Redo the hash computation on symbols rather than commands.
    hashes2(start TEXT, string TEXT, hash BIGINT) AS (
        SELECT symb as start, symb as string, 0 as hash
        FROM final_state
        UNION ALL
        SELECT start, substring(string, 2), ((hash + ascii(substring(string, 1, 1))) * 17) % 256
        FROM hashes2
        WHERE length(string) > 0
    ),
    -- Bin up the state, so's we can tabulate it
    binned(hash BIGINT, r INT, symb TEXT, op INT) AS (
        SELECT hash, final_state.*
        FROM hashes2, final_state
        WHERE hashes2.start = symb
          AND hashes2.string = ''
    ),
    -- Sum the product of 1 + hash, the position in bin by r, and the op.
    part2(part2 BIGINT) AS (
        SELECT SUM(
            (1 + hash) *
            (SELECT COUNT(*) FROM binned b2 WHERE binned.hash = b2.hash AND binned.r >= b2.r) *
            op
        )
        FROM binned
    ),

    potato(x int) as (select 1)

SELECT * FROM part1, part2;
----
Explained Query:
  With
    cte l0 =
      Project (#1, #2) // { arity: 2 }
        Map (array_index(regexp_split_to_array[",", case_insensitive=false](#0{input}), integer_to_bigint(#1{r}))) // { arity: 3 }
          FlatMap generate_series(1, (regexp_split_to_array[",", case_insensitive=false](#0{input}) array_length 1), 1) // { arity: 2 }
            ReadStorage materialize.public.input // { arity: 1 }
    cte l1 =
      Distinct project=[#0] // { arity: 1 }
        Project (#2) // { arity: 1 }
          Map (case when ("-" = substr(#1{string}, char_length(#1{string}))) then substr(#1{string}, 1, (char_length(#1{string}) - 1)) else substr(#1{string}, 1, (char_length(#1{string}) - 2)) end) // { arity: 3 }
            Get l0 // { arity: 2 }
    cte l2 =
      Reduce group_by=[#0] aggregates=[max(#1{r})] // { arity: 2 }
        Project (#0, #1) // { arity: 2 }
          Join on=(#0{symb} = #2{symb}) type=differential // { arity: 3 }
            implementation
              %0:l1[#0{symb}]UKA » %1:l0[#1{symb}]Kef
            ArrangeBy keys=[[#0{symb}]] // { arity: 1 }
              Get l1 // { arity: 1 }
            ArrangeBy keys=[[#1{symb}]] // { arity: 2 }
              Project (#0, #3) // { arity: 2 }
                Filter (#3) IS NOT NULL AND (0 = case when #2 then 0 else text_to_integer(substr(#1{string}, char_length(#1{string}))) end) // { arity: 4 }
                  Map (("-" = substr(#1{string}, char_length(#1{string}))), case when #2 then substr(#1{string}, 1, (char_length(#1{string}) - 1)) else substr(#1{string}, 1, (char_length(#1{string}) - 2)) end) // { arity: 4 }
                    Get l0 // { arity: 2 }
    cte l3 =
      Union // { arity: 2 }
        Get l2 // { arity: 2 }
        Map (null) // { arity: 2 }
          Union // { arity: 1 }
            Negate // { arity: 1 }
              Project (#0) // { arity: 1 }
                Get l2 // { arity: 2 }
            Get l1 // { arity: 1 }
    cte l4 =
      Project (#0..=#2) // { arity: 3 }
        Filter (#0{r} > coalesce(#4{max}, 0)) // { arity: 5 }
          Join on=(#1 = #3) type=differential // { arity: 5 }
            implementation
              %1[#0]UK » %0:l0[#1]K
            ArrangeBy keys=[[#1]] // { arity: 3 }
              Project (#0, #3, #4) // { arity: 3 }
                Map (("-" = substr(#1{string}, char_length(#1{string}))), case when #2 then substr(#1{string}, 1, (char_length(#1{string}) - 1)) else substr(#1{string}, 1, (char_length(#1{string}) - 2)) end, case when #2 then 0 else text_to_integer(substr(#1{string}, char_length(#1{string}))) end) // { arity: 5 }
                  Get l0 // { arity: 2 }
            ArrangeBy keys=[[#0]] // { arity: 2 }
              Union // { arity: 2 }
                Get l3 // { arity: 2 }
                Map (null) // { arity: 2 }
                  Union // { arity: 1 }
                    Negate // { arity: 1 }
                      Project (#0) // { arity: 1 }
                        Get l3 // { arity: 2 }
                    Get l1 // { arity: 1 }
    cte l5 =
      Distinct project=[#0] // { arity: 1 }
        Project (#1) // { arity: 1 }
          Get l4 // { arity: 3 }
    cte l6 =
      Reduce group_by=[#0] aggregates=[min(#1{r})] // { arity: 2 }
        Project (#0, #1) // { arity: 2 }
          Join on=(#0{symb} = #2{symb}) type=differential // { arity: 3 }
            implementation
              %0:l5[#0{symb}]UKA » %1:l4[#1{symb}]K
            ArrangeBy keys=[[#0{symb}]] // { arity: 1 }
              Get l5 // { arity: 1 }
            ArrangeBy keys=[[#1{symb}]] // { arity: 2 }
              Project (#0, #1) // { arity: 2 }
                Filter (#1{symb}) IS NOT NULL // { arity: 3 }
                  Get l4 // { arity: 3 }
    cte l7 =
      Union // { arity: 2 }
        Get l6 // { arity: 2 }
        Map (null) // { arity: 2 }
          Union // { arity: 1 }
            Negate // { arity: 1 }
              Project (#0) // { arity: 1 }
                Get l6 // { arity: 2 }
            Get l5 // { arity: 1 }
    cte l8 =
      Project (#1..=#4) // { arity: 4 }
        TopK group_by=[#1] order_by=[#0 desc nulls_first, #2 asc nulls_last] limit=1 // { arity: 5 }
          Project (#0..=#2, #4{min}, #5) // { arity: 5 }
            Map ((#1) IS NULL) // { arity: 6 }
              Join on=(#1 = #3) type=differential // { arity: 5 }
                implementation
                  %1[#0]UK » %0:l4[#1]K
                ArrangeBy keys=[[#1]] // { arity: 3 }
                  Get l4 // { arity: 3 }
                ArrangeBy keys=[[#0]] // { arity: 2 }
                  Union // { arity: 2 }
                    Get l7 // { arity: 2 }
                    Map (null) // { arity: 2 }
                      Union // { arity: 1 }
                        Negate // { arity: 1 }
                          Project (#0) // { arity: 1 }
                            Get l7 // { arity: 2 }
                        Get l5 // { arity: 1 }
  Return // { arity: 2 }
    With Mutually Recursive
      cte [recursion_limit=10, return_at_limit] l9 =
        Union // { arity: 2 }
          Project (#1, #2) // { arity: 2 }
            Map (0) // { arity: 3 }
              Get l0 // { arity: 2 }
          Project (#2, #3) // { arity: 2 }
            Filter (char_length(#0{string}) > 0) // { arity: 4 }
              Map (substr(#0{string}, 2), (((#1{hash} + integer_to_bigint(ascii(substr(#0{string}, 1, 1)))) * 17) % 256)) // { arity: 4 }
                Get l9 // { arity: 2 }
      cte l10 =
        Reduce aggregates=[sum(#0{hash})] // { arity: 1 }
          Project (#1) // { arity: 1 }
            Filter (#0{string} = "") // { arity: 2 }
              Get l9 // { arity: 2 }
      cte [recursion_limit=10, return_at_limit] l11 =
        Union // { arity: 3 }
          Project (#0, #0, #4) // { arity: 3 }
            Map (0) // { arity: 5 }
              Get l8 // { arity: 4 }
          Project (#0, #3, #4) // { arity: 3 }
            Filter (char_length(#1{string}) > 0) // { arity: 5 }
              Map (substr(#1{string}, 2), (((#2{hash} + integer_to_bigint(ascii(substr(#1{string}, 1, 1)))) * 17) % 256)) // { arity: 5 }
                Get l11 // { arity: 3 }
    Return // { arity: 2 }
      With
        cte l12 =
          Project (#1, #3, #4{min}) // { arity: 3 }
            Join on=(#0{start} = #2{symb}) type=differential // { arity: 5 }
              implementation
                %1:l8[#0{symb}]UKf » %0:l11[#0{start}]Kef
              ArrangeBy keys=[[#0{start}]] // { arity: 2 }
                Project (#0, #2) // { arity: 2 }
                  Filter (#1{string} = "") AND (#0{start}) IS NOT NULL // { arity: 3 }
                    Get l11 // { arity: 3 }
              ArrangeBy keys=[[#0{symb}]] // { arity: 3 }
                Project (#0..=#2{min}) // { arity: 3 }
                  Filter NOT(#3) // { arity: 4 }
                    Get l8 // { arity: 4 }
        cte l13 =
          Project (#0, #2{min}) // { arity: 2 }
            Get l12 // { arity: 3 }
        cte l14 =
          Distinct project=[#0, #1{min}] // { arity: 2 }
            Get l13 // { arity: 2 }
        cte l15 =
          Reduce group_by=[#0, #1{min}] aggregates=[count(*)] // { arity: 3 }
            Project (#0, #1{min}) // { arity: 2 }
              Filter (#1{min} >= #3{min}) // { arity: 4 }
                Join on=(#0{hash} = #2{hash}) type=differential // { arity: 4 }
                  implementation
                    %0:l14[#0{hash}]K » %1:l13[#0{hash}]K
                  ArrangeBy keys=[[#0{hash}]] // { arity: 2 }
                    Get l14 // { arity: 2 }
                  ArrangeBy keys=[[#0{hash}]] // { arity: 2 }
                    Get l13 // { arity: 2 }
        cte l16 =
          Union // { arity: 3 }
            Get l15 // { arity: 3 }
            Map (0) // { arity: 3 }
              Union // { arity: 2 }
                Negate // { arity: 2 }
                  Project (#0, #1{min}) // { arity: 2 }
                    Get l15 // { arity: 3 }
                Get l14 // { arity: 2 }
        cte l17 =
          Reduce aggregates=[sum((((1 + #0{hash}) * #2{count}) * integer_to_bigint(#1{op})))] // { arity: 1 }
            Project (#0, #1, #5{count}) // { arity: 3 }
              Join on=(#0 = #3 AND #2{min} = #4{min}) type=differential // { arity: 6 }
                implementation
                  %1[#0, #1]UKK » %0:l12[#0, #2]KK
                ArrangeBy keys=[[#0, #2{min}]] // { arity: 3 }
                  Get l12 // { arity: 3 }
                ArrangeBy keys=[[#0, #1{min}]] // { arity: 3 }
                  Union // { arity: 3 }
                    Get l16 // { arity: 3 }
                    Map (null) // { arity: 3 }
                      Union // { arity: 2 }
                        Negate // { arity: 2 }
                          Project (#0, #1{min}) // { arity: 2 }
                            Get l16 // { arity: 3 }
                        Get l14 // { arity: 2 }
      Return // { arity: 2 }
        CrossJoin type=differential // { arity: 2 }
          implementation
            %0[×]U » %1[×]U
          ArrangeBy keys=[[]] // { arity: 1 }
            Project (#1) // { arity: 1 }
              Map (numeric_to_bigint(#0{sum})) // { arity: 2 }
                Union // { arity: 1 }
                  Get l10 // { arity: 1 }
                  Map (null) // { arity: 1 }
                    Union // { arity: 0 }
                      Negate // { arity: 0 }
                        Project () // { arity: 0 }
                          Get l10 // { arity: 1 }
                      Constant // { arity: 0 }
                        - ()
          ArrangeBy keys=[[]] // { arity: 1 }
            Project (#1) // { arity: 1 }
              Map (numeric_to_bigint(#0{sum})) // { arity: 2 }
                Union // { arity: 1 }
                  Get l17 // { arity: 1 }
                  Map (null) // { arity: 1 }
                    Union // { arity: 0 }
                      Negate // { arity: 0 }
                        Project () // { arity: 0 }
                          Get l17 // { arity: 1 }
                      Constant // { arity: 0 }
                        - ()

Source materialize.public.input

Target cluster: quickstart

EOF