# 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