# 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_1211.md mode cockroach statement ok CREATE TABLE input (input TEXT); statement ok INSERT INTO input VALUES ( '#?##..#?.???..##??...??....#....?....#?...#.?..?.#...#....?#..#..##...???.##?...?#####.....##..?.??.?........?.#..#?##..#.###??......??.?#.. .#...#.#?.#...?.#??..##.?##?.#......##.?...?...??#.?.?..?.###??.#.......#...?#.##.##.?#.#?..##?#.###.?..#.#?........?.??##..#?....##...?..?? ?.#..###????#.?.#....?#.?.?.?.#.?..?.#.#.#.?.#.??..?.??#????.?.#.#.?...#.#..?#?#?.#...?..#.#...?.?#?.?...#?..?.?.?##.??.?.#......#.??....##. ..#.....?.??..#?...?##?....#??.###??.#.#.#..?.#?..?##..?.?##..##.##?.#?..??#?..#.?.#....#??.?.?.?.??#?#.#...?.#?.??.#??.?.?#.#...?...??#..?# #.??..#?.?....#.?.?.##.#...???...??.#.#..?..##...?.??.###.???#..#??....?.??.?#?#?...#??....?#.?#?...?..#..#.?..?.?..#.#.#.#...#.??..#.#.?#.. ..##....?....#.??..?.#..?#.?#?..?#?..?....#..??....##?#..##?.#.?.?..??.#......#...#.?.#.#..?...............###?.##.?##..#???##??.?.?###...?. #.#..#####??#??##.###...#.#.#.#.####..?#.?.##...#.##..#.#..#.?.#.#?.#.#...?....??#.#..?#.##..##?......#?.#.#..?.......#?.?.....#..?.#.#??##. .##.?.##..?#.##..?#.#....#...##.?.#?#...##??.#?##.?..?#...???.#..?.#?......?.#?#..##???.#...##.#..#?..?.#...?.?..##..?.??##?..?#??..#..?#.?? #.#.#........?.???..#.###?##.?....?###...#?##?..##..#?.?...#...#??.??.?##...?...????....?.?..#...#...#...#.?.#.....??..???..?#??..?#.#.?.#.? ?.?...#..?.#.#..?..###?.#?#?.##.??...??#...#?#.???.?#?#.#.#?...#....#.?.##...#?##..#..?#.#...??#.#.?..?#.#?#.....#?.......??#.###...#?#..... ..#?...#.#?.#.??..?.?..#.#...?#..#.#......?..#??#...?..#.#...#?..#?.#.#.?.###..????#?..?.??.#..?#?..#........#....?###...#?..#.?#.#?.#??.... .##..#?##..#?...#?.#.?.....#..?..?#.??..#..#.?...?.##.?.#..###.#?.?#.....##?.??#..?..#..??##?..#?#...##.#.?.?#.?..#...##..??.???..??..#.#... ?.#..#.#?....?.?.?.#.?.#.#?#.#......?.#?....#.#.#.?#.##....?....#....#.#?..#.#.?#...?.?..?..###?.?.?.###..#..??#????#.....#...##.?#..#???.#. ?#..?..?#.#.?.?...??.#.......#?#.?..#..?.#.??.#?.#.#?...##..?..?#??.#???......?.?.....#.?#.#?#??.?.##..??.??.#??##?.#....?#.#.#??.?.?.?.?#.? ....#.#.??.??.?..###?#.?..##.???.?.#?#....##?...##..#.#?#.##?.#......#.?#.?.#..??#.#..#?#..?.........##.#.??.??#.##.##?.?#??..#.?#.##.?.?.?# ..??.###....?#?.???..#.....??.??#...##.?..#...##..#.#..?#.....#.???.....#.#??...#......?.?.#.#??##?.#.??#..#...????.#..#.?#..##?..?.?.?..#.. #?.....#.???#..##.#?.?#.?....?#??...?.....##...#.#.#.##?..?..#.#....??.?#?.?#..#?....#.?#???.#?#..?.#.?#.???..?.?..?.#.?#?..###??.?##..#.### ????#.##....?.#.??.?....#?..?#...#..#???....#.##..???.#..##?.#.....#.??.#.....??..?....#....???##??....#....?#.?#...?..?..??....?..#.##.???? ..?#?#??..##??#.....?.?#...??.?#...?#####?.?#.?#?##.#.?#?#??.??..?.?...#.??..#...#.#..##?.#..##?#.?.#??#?.#?.??#...#??.#.?#..??.###.?.#..?.? ..?#??.#?.#.?...##.#..#?.??#?..#...?##.#?.#?...##.#..###....?..#.....#?##.??#.##???.?.###...##.???....?.??.?#?.#?.#?.?#.??..###.?.#.?.....## #..#.....#.#.???.#..??......?.?...?#?.#?.#??.#?#?##..?..??##.#..?..##.#.....##?.??.#..#?.??##?#??.??#??#.#?....?#?....??#..?.??..?#?..##?##. ..?..#??.?.?..?.??....#..#?.???..???.......#?#.?..?....##...#...#..?..?#...?..??.....#.#??#?.###..#?.#.#?.......??..#..?.??..#...##?..#.?..# ?.?....??.#.???.##?.#.?.?.??#.?.###.......?..#...??.#...#.#.?#.?..?...???.##..?.?..####?#....?.#..?...###?...??........#???##..##..??#.#.??. ?#.#?#...?.?....?....?...?.##.....##.##?.....?#####?..#?#.??#??.??#.....?..##..#?.#.#.#?#..#??......#.#?.###.#?#?.?.#.....#...?.#..#?....??. #?...??...?..?#?#......?.....#.????#?.#?##???.#.?..##.#.##.....?..?.##.##.......?.##?......?#.#?.#.##...?..?#??..#..#..#.#?..?#...??#.?#.?.# #..?....?#?#......#...#.........??#............#.?..?#.#....#.?#..#.....#??...#.?.?#??..?..??.#.?.#.....#?....?##.#?##..#?#...?#.??.?.??..?. ..###?...???.?#.##???#?.#?.?.?#.#.#.##.?#.####.#?.???.....##.?...#.##..?....#?.?#.?...#.##.?..#..??#..?#..#?#...?..?..??.....?...?.?...?.#?# #??#.?##.#.?..##?..#.#??#????.?#.?....?...#....??...##?.#.?#?.?.##.#???.?#.?#?..?#.#.#?###?.....##..?..?.#?..?.?.#.#..?.?..?#.?##..#.#..?.#? .?.#.....##..#?#.??...?...?....????.#?##?....#.#.#.?.#??...?.?.##.#.##.?...##.#???#.?.?......???.?.?..?..??..#.?##..###?.##.##?##.?.###??..? ??.#..###..??#.#.#.#.??.....?#??...?...?#.?...?#.#..#?#..?..#?.#.?#..?.#?.#.?#..#?..##.......??.?##?#??#??....#.......#.#...?#.?.?....?#..#. ?.?#..##?..?....??.#..#....#?....?..?..#.#.#.#?...#....##.??#.##.?.???#.#...?.....?.#...?#..?...??..#.#.?..?........###.#..##.?..#.#..??.... .....?.??#.?..#?#.#?.??........#????.......###.......?#??.##..#?####...?#.?.?.##??#?...?#.#...?...?...##..???.#.#.??????....#..#.?.?.##.?..? ??.?.#?..#.??.#.#.#.??.#.#??#.#...?...##......?...?...##..?.#?.?#...?..#....##.#?.#..?.....?...#?.?#.?#...?#??#?...??......?#?.??#.#??...?.? #?.###..#.....#?....#.##...#.##.....#.#.#.#..##.....?..#.....?##...#?.??.......#??##?..###??....?.#?......#.??..#??.#?.#.#.###??.#?..?#?#..# ?.?....?.#??.#....?#?#?.?#.?.....#??#.??.?#?#.#......?.#?...?#..#.....??#.?....??.##...?..#?.#??.#.?.??....#?.?.#...##.?#...##....#.#??..?#. ?#?.?....?.##...??...#?##.#.????##.#..?..?..#..##.??#?.?.??#...?.?...#..?..#..??.?.?#.#.#??..?.#......#...#?.?...?#?.......#.???.#?.##..#?#. ..??.#..??#####.#?.........#.#.?####...?#.?.#??.#??#..?##?#.??#....?.??...?..?..??.#...?..????..#..##?###...#.??.?##..#.#..?.#..##?#.??.?#.? ?.##.?.#.##?.?...#...#?##.#.?.#..?#.?.??##?#??.?.?.#.???...??#.##..?#.??#.??....?..#?..##?#?##???.#..#??.?#???...#?##..#.#..#......??#..###. ###...#...??.#.?..#?..?...#.#?.?.?.?#....#.?#.#..####.?..??##?....?#.?.....#...?#??....??....#.????.?...#.??.#..#..??.?..##..#.?..?..##.#?.. #....#.?.##.?.......#...##?..#...#.?##..###?..#...?....?#????###.?.....?##.##?.#?.###?.#???#..#....?...#?.....#...?..#.?.#???#.?#.??.?#.#.?? #...#??......?..#.......??.?..#....#.?#.#?..#.##..??##..#?#.#?...#...?....?.?.?...#??#?#..####...#..?.#?#..#..#.?.####..#?#.##?#.?#?#.....?. ...#?...#...?#?.##.??..#..#?.?.....#.#?#...#.......#..#....?.??...#???.?...?.#??##.?##?##.#??.#?..##??...#..?.....#?#..##??..###...??.??#?#. .........?.#.?.#?...?..?.??#?#.?.#??......#..#.#.?#?.#??#...#?#?.#?.#..?#...?...##?#.##..?.##......??.?##.?###?.#?##..#.?#?...#..##....?##?# #??#.##.##..#..#???.?.?#.#...##?##?#.#??.?.#.#??.#.#.#.....?#???#??#..?.#.?..??..?.?....?#.....#.?#.??.?.????#..?.#.??###.??#?..#?..??##..?# #.#??..#.?....###.....?#.....##?.#?.?.#.??##...?#?#.?...#..?#.?...?#..?#?#.##.?....##....#..#.##?.??..?.?.?#.?###.?.##?...#...??....#.#..#?. ?..?..?.?.????#???.??.#.???.??..##..#..??##?.#?..?#??##...?????.#?..#...#..?#...?..?#..#.#....?....#.#..?..?#??#??##....#?..?.???...#.#.#.?# ..##?#.#....??...........?.##.....?#?..#..?..#?.?.?...#?#.?###...#.#.?#?..?.#.??#?##...?..?........?.#.....##..?#..?..#.??.?...?.?###.#?#... ..?...#.#?#..#?..#..#..#...#..?.....#.#...#..#?.?.....?..??...#.?.?......?.#?##..?#..#.?..#..?#??...#.#.....?#...?.#...#.#..#.#?.#?.?##?#?## #?.#...##.?.#.####.??.#?.?#?.#...#.?#.??#??.##.#.#..#...#.?.#.#.#.###....?.??.?......?....#????..#.......#..#.###.#.?....?#...#..?.#...#.#.. #...??...??..?.#?...##.?..?#.??.?.#.#..?..###?.????#....#..?.?#.#.#####?##...#.?...??.??...#.#?#.#?..?#..?#??.##.?.?..#....?.#..##.?..?...#. ?..#?##???..?.##??.?....##.??..?.#?....?..?..?....??#.#.??.?...?#?....#.?.#?????#.?#..#?..##...?????##.....#.#.####.?#.?...#?..?.??##?..#.?? ?....?.#.#?..?.?...#..#.#?.#..#...?.#.?#.?.#.##??..#..#?#?#.#??..#.??.?...?.?..?##?...?.?..##.?..?.???...?#.##?#..??..#?#...?..?....#..#.##? #?#.?#......?.#??##...?#.#.##.?...?...?...?#..#?###.##?##..?.#?#.?#..#...#....#?#.#??...?#.#?..#?##?..??..?..#?....?#.#?..#.#.##.?#.?.#..##? .#.....##.##?.?...??..##...#?.#...#...#.??.?...#..?.?.#.##?.?#.#?..#???#?#?#.##..#.#.?...........#.?#..##...##??##..?.?###??#.#........#.?.# ?..#...#.##..?#.?.##..?..?.#....??#...#?..#.#.?.??.?..?#.#.#..??##?.##..?##?#..#?..??#.#.?.?#.?....#.##?#..#....?..##.??###?#...?..#.##.?#?# .??......?..??##?..??...?...?##?.?###?..##?..#?..???#.##.##.?..#..???..???...??#..?##...##.?..?.??#..#####?.#.#..?......##.?.##.#.?#??#..#.. .#?..#.?.#...?.???.?..#...?...?.#....?..#........#.??..?...#.#?..?#....#...#.#...?.?.##???..???..#..??.?..#..#.##?..?#.#..##.??##...?#.....?'); query II WITH MUTUALLY RECURSIVE lines(line TEXT, r 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 ), symbols(symb TEXT, r INT, c INT) as ( SELECT substring(line, j, 1), r, j FROM lines, generate_series(1, length(line)) j ), row_gaps(r INT) AS ( SELECT r FROM symbols GROUP BY r HAVING COUNT(*) FILTER (WHERE symb = '#') = 0 ), col_gaps(c INT) AS ( SELECT c FROM symbols GROUP BY c HAVING COUNT(*) FILTER (WHERE symb = '#') = 0 ), -- Part1: Expand space and restrict to galaxies galaxies(r INT, c INT) AS ( SELECT r + (SELECT COUNT(*) FROM row_gaps WHERE row_gaps.r < symbols.r), c + (SELECT COUNT(*) FROM col_gaps WHERE col_gaps.c < symbols.c) FROM symbols WHERE symb = '#' ), -- Sum of L1 distance between distinct galaxies part1(part1 BIGINT) AS ( SELECT SUM(ABS(g1.r - g2.r) + ABS(g1.c - g2.c)) FROM galaxies g1, galaxies g2 WHERE g1.r < g2.r OR (g1.r = g2.r AND g1.c < g2.c) ), -- Part2: Expand space MORE and restrict to galaxies galaxies2(r INT, c INT) AS ( SELECT r + 999999 * (SELECT COUNT(*) FROM row_gaps WHERE row_gaps.r < symbols.r), c + 999999 * (SELECT COUNT(*) FROM col_gaps WHERE col_gaps.c < symbols.c) FROM symbols WHERE symb = '#' ), -- Sum of L1 distance between distinct galaxies part2(part2 BIGINT) AS ( SELECT SUM(ABS(g1.r - g2.r) + ABS(g1.c - g2.c)) FROM galaxies2 g1, galaxies2 g2 WHERE g1.r < g2.r OR (g1.r = g2.r AND g1.c < g2.c) ) SELECT * FROM part1, part2; ---- 129655908 129655908 query T multiline EXPLAIN OPTIMIZED PLAN WITH(humanized expressions, arity, join implementations) AS VERBOSE TEXT FOR WITH MUTUALLY RECURSIVE lines(line TEXT, r 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 ), symbols(symb TEXT, r INT, c INT) as ( SELECT substring(line, j, 1), r, j FROM lines, generate_series(1, length(line)) j ), row_gaps(r INT) AS ( SELECT r FROM symbols GROUP BY r HAVING COUNT(*) FILTER (WHERE symb = '#') = 0 ), col_gaps(c INT) AS ( SELECT c FROM symbols GROUP BY c HAVING COUNT(*) FILTER (WHERE symb = '#') = 0 ), -- Part1: Expand space and restrict to galaxies galaxies(r INT, c INT) AS ( SELECT r + (SELECT COUNT(*) FROM row_gaps WHERE row_gaps.r < symbols.r), c + (SELECT COUNT(*) FROM col_gaps WHERE col_gaps.c < symbols.c) FROM symbols WHERE symb = '#' ), -- Sum of L1 distance between distinct galaxies part1(part1 BIGINT) AS ( SELECT SUM(ABS(g1.r - g2.r) + ABS(g1.c - g2.c)) FROM galaxies g1, galaxies g2 WHERE g1.r < g2.r OR (g1.r = g2.r AND g1.c < g2.c) ), -- Part2: Expand space MORE and restrict to galaxies galaxies2(r INT, c INT) AS ( SELECT r + 999999 * (SELECT COUNT(*) FROM row_gaps WHERE row_gaps.r < symbols.r), c + 999999 * (SELECT COUNT(*) FROM col_gaps WHERE col_gaps.c < symbols.c) FROM symbols WHERE symb = '#' ), -- Sum of L1 distance between distinct galaxies part2(part2 BIGINT) AS ( SELECT SUM(ABS(g1.r - g2.r) + ABS(g1.c - g2.c)) FROM galaxies2 g1, galaxies2 g2 WHERE g1.r < g2.r OR (g1.r = g2.r AND g1.c < g2.c) ) SELECT * FROM part1, part2; ---- Explained Query: With cte l0 = Project (#0, #2, #3) // { arity: 3 } Map (substr(#1{line}, #2{j}, 1)) // { arity: 4 } FlatMap generate_series(1, char_length(#1{line}), 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 } cte l1 = Project (#0, #1) // { arity: 2 } Filter (#2{symb} = "#") // { arity: 3 } Get l0 // { arity: 3 } cte l2 = Distinct project=[#0, #1] // { arity: 2 } Get l1 // { arity: 2 } cte l3 = Distinct project=[#0] // { arity: 1 } Project (#0) // { arity: 1 } Get l2 // { arity: 2 } cte l4 = Reduce group_by=[#0] aggregates=[count(*)] // { arity: 2 } Project (#0) // { arity: 1 } Filter (#1{r} < #0{r}) // { arity: 2 } CrossJoin type=differential // { arity: 2 } implementation %1[×]ef » %0:l3[×]ef ArrangeBy keys=[[]] // { arity: 1 } Get l3 // { arity: 1 } ArrangeBy keys=[[]] // { arity: 1 } Project (#0) // { arity: 1 } Filter (#1{count} = 0) // { arity: 2 } Reduce group_by=[#0] aggregates=[count((null OR ((#1{symb}) IS NOT NULL AND (#1{symb} = "#"))))] // { arity: 2 } Project (#0, #2) // { arity: 2 } Get l0 // { arity: 3 } cte l5 = Union // { arity: 2 } Get l4 // { arity: 2 } Map (0) // { arity: 2 } Union // { arity: 1 } Negate // { arity: 1 } Project (#0) // { arity: 1 } Get l4 // { arity: 2 } Get l3 // { arity: 1 } cte l6 = Distinct project=[#0] // { arity: 1 } Project (#1) // { arity: 1 } Get l2 // { arity: 2 } cte l7 = Reduce group_by=[#0] aggregates=[count(*)] // { arity: 2 } Project (#0) // { arity: 1 } Filter (#1{c} < #0{c}) // { arity: 2 } CrossJoin type=differential // { arity: 2 } implementation %1[×]ef » %0:l6[×]ef ArrangeBy keys=[[]] // { arity: 1 } Get l6 // { arity: 1 } ArrangeBy keys=[[]] // { arity: 1 } Project (#0) // { arity: 1 } Filter (#1{count} = 0) // { arity: 2 } Reduce group_by=[#0] aggregates=[count((null OR ((#1{symb}) IS NOT NULL AND (#1{symb} = "#"))))] // { arity: 2 } Project (#1, #2) // { arity: 2 } Get l0 // { arity: 3 } cte l8 = Union // { arity: 2 } Get l7 // { arity: 2 } Map (0) // { arity: 2 } Union // { arity: 1 } Negate // { arity: 1 } Project (#0) // { arity: 1 } Get l7 // { arity: 2 } Get l6 // { arity: 1 } cte l9 = Project (#0, #1, #3{count}, #5{count}) // { arity: 4 } Join on=(#0 = #2 AND #1 = #4) type=delta // { arity: 6 } implementation %0:l1 » %1[#0]UK » %2[#0]UK %1 » %0:l1[#0]Kef » %2[#0]UK %2 » %0:l1[#1]Kef » %1[#0]UK ArrangeBy keys=[[#0], [#1]] // { arity: 2 } Get l1 // { arity: 2 } ArrangeBy keys=[[#0]] // { arity: 2 } Union // { arity: 2 } Get l5 // { arity: 2 } Map (null) // { arity: 2 } Union // { arity: 1 } Negate // { arity: 1 } Project (#0) // { arity: 1 } Get l5 // { arity: 2 } Get l3 // { arity: 1 } ArrangeBy keys=[[#0]] // { arity: 2 } Union // { arity: 2 } Get l8 // { arity: 2 } Map (null) // { arity: 2 } Union // { arity: 1 } Negate // { arity: 1 } Project (#0) // { arity: 1 } Get l8 // { arity: 2 } Get l6 // { arity: 1 } cte l10 = ArrangeBy keys=[[]] // { arity: 2 } Project (#4, #5) // { arity: 2 } Map (bigint_to_integer((integer_to_bigint(#0{r}) + #2{count})), bigint_to_integer((integer_to_bigint(#1{c}) + #3{count}))) // { arity: 6 } Get l9 // { arity: 4 } cte l11 = Reduce aggregates=[sum((abs((#0{r} - #2{r})) + abs((#1{c} - #3{c}))))] // { arity: 1 } Filter ((#0{r} < #2{r}) OR ((#0{r} = #2{r}) AND (#1{c} < #3{c}))) // { arity: 4 } CrossJoin type=differential // { arity: 4 } implementation %0:l10[×] » %1:l10[×] Get l10 // { arity: 2 } Get l10 // { arity: 2 } cte l12 = ArrangeBy keys=[[]] // { arity: 2 } Project (#4, #5) // { arity: 2 } Map (bigint_to_integer((integer_to_bigint(#0{r}) + (999999 * #2{count}))), bigint_to_integer((integer_to_bigint(#1{c}) + (999999 * #3{count})))) // { arity: 6 } Get l9 // { arity: 4 } cte l13 = Reduce aggregates=[sum((abs((#0{r} - #2{r})) + abs((#1{c} - #3{c}))))] // { arity: 1 } Filter ((#0{r} < #2{r}) OR ((#0{r} = #2{r}) AND (#1{c} < #3{c}))) // { arity: 4 } CrossJoin type=differential // { arity: 4 } implementation %0:l12[×] » %1:l12[×] Get l12 // { arity: 2 } Get l12 // { arity: 2 } Return // { arity: 2 } CrossJoin type=differential // { arity: 2 } implementation %0[×]U » %1[×]U ArrangeBy keys=[[]] // { arity: 1 } Union // { arity: 1 } Get l11 // { arity: 1 } Map (null) // { arity: 1 } Union // { arity: 0 } Negate // { arity: 0 } Project () // { arity: 0 } Get l11 // { arity: 1 } Constant // { arity: 0 } - () ArrangeBy keys=[[]] // { arity: 1 } Union // { arity: 1 } Get l13 // { arity: 1 } Map (null) // { arity: 1 } Union // { arity: 0 } Negate // { arity: 0 } Project () // { arity: 0 } Get l13 // { arity: 1 } Constant // { arity: 0 } - () Source materialize.public.input Target cluster: quickstart EOF