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

mode cockroach

statement ok
CREATE TABLE input (input TEXT);

statement ok
INSERT INTO input VALUES (
'#.###..##
..###..#.
.##.....#
..###....
..##..#..
.##.#..#.
##...##..
..#.#.#.#
#####.###
....#.##.
.#.######
....##...
#..##...#
<EMPTY_LINE>
###.#..###.#....#
...#....#..#..#.#
...#...##.#.#.#..
##.#...##.#.....#
.#..#....##...##.
.##....#...#.#...
..#.##.##.#..##.#
........#.##.#..#
<EMPTY_LINE>
#...#..#.......
.#.###.##.#.###
.#.##..........
##.##.##.###.##
..###.#.....#..
..###.#.....#..
##.##.##.###.##
#....#.##...###
#.#.....##..#..
...###.....#...
..#.....#..#...
##.###.##......
...#.##.#.#.#.#
..........####.
<EMPTY_LINE>
...#.....
...#.....
...#.....
#...##...
..#.....#
...#.####
.##....##
......#..
#.....#..
....#.#.#
##...####
<EMPTY_LINE>
...##.##.#.##
#....#..#..##
##.##....###.
#..###....#.#
###...##..#..
#.#...#.#.##.
###..#.......
..##.#.#...##
##..#..#..#.#
......#...###
..#..#.##....
##.#...#.#...
#..#.....####
....##.##..#.
####......###
<EMPTY_LINE>
#.##..#..##
.#.#####..#
.##.##...##
.#.#..#...#
...####.#..
#..######..
..#....#...
.#####.##.#
..........#
##.#..#.#.#
.......#...
<EMPTY_LINE>
.#.#..#....###...
######..#.###.#..
##..##.#..#..#...
...##...##...#.#.
#...#..####..#.#.
..####.#..#...#.#
####.#......#.#..
##..##...#.#...#.
<EMPTY_LINE>
#..#.##..........
.#....##....#.#.#
.##.....##....###
#####...##...##..
###.....#...###.#
#....#.#......#.#
#..#...###...#..#
#.#......#.###.#.
#..#.##..........
<EMPTY_LINE>
.##.#.#.##..#.#..
...####...##..#..
....##...#...##.#
..###..#..#..####
.#...##...#.###..
...###.....#...##
<EMPTY_LINE>
.#...#.####.#
##..#.#....#.
.#..#...#..#.
..#....#.#.#.
.#...##....#.
#.###.##..###
#..#.#....###
.##..#.#.#...
.##.#.##..#..
#...###..##..');

statement ok
UPDATE input SET input = replace(input, '<EMPTY_LINE>', '');

query II
WITH MUTUALLY RECURSIVE

    blocks(b INT, block TEXT) AS (
        SELECT b, regexp_split_to_array(input, '\n\n')[b] as block
        FROM input, generate_series(1, array_length(regexp_split_to_array(input, '\n\n'), 1)) b
    ),
    lines(b INT, r INT, line TEXT) AS (
        SELECT b, r, regexp_split_to_array(block, '\n')[r] as block
        FROM blocks, generate_series(1, array_length(regexp_split_to_array(block, '\n'), 1)) r
    ),
    cells(b INT, r INT, c INT, symbol TEXT) AS (
        SELECT b, r, c, substring(line, c, 1)
        FROM lines, generate_series(1, length(line)) c
    ),
    columns(b INT, c INT, column TEXT) AS (
        SELECT b, c, string_agg(symbol, '' ORDER BY r) FROM cells GROUP BY b, c
    ),

    row_mirror(b INT, r INT) AS (
        SELECT *
        FROM (SELECT DISTINCT b, r FROM cells) o
        WHERE NOT EXISTS (
            -- We would be upset to find rows at mirrored positions that do not match
            -- Rows that match, or have no mirrored position, are fine.
            SELECT FROM lines
            WHERE o.b = lines.b
            GROUP BY abs(2 * lines.r - (2 * o.r - 1))
            HAVING COUNT(DISTINCT lines.line) > 1
        )
    ),

    col_mirror(b INT, c INT) AS (
        SELECT *
        FROM (SELECT DISTINCT b, c FROM cells) o
        WHERE NOT EXISTS (
            -- We would be upset to find rows at mirrored positions that do not match
            -- Rows that match, or have no mirrored position, are fine.
            SELECT FROM columns
            WHERE o.b = columns.b
            GROUP BY abs(2 * columns.c - (2 * o.c - 1))
            HAVING COUNT(DISTINCT columns.column) > 1
        )
    ),

    part1(part1 BIGINT) AS (
        SELECT COALESCE((SELECT SUM(r-1) FROM row_mirror), 0) * 100
             + COALESCE((SELECT SUM(c-1) FROM col_mirror), 0)
    ),

    row_mirror2(b INT, r INT) AS (
        SELECT *
        FROM (SELECT DISTINCT b, r FROM cells) o
        WHERE 1 = (
            SELECT COUNT(*)
            FROM cells c1, cells c2
            WHERE abs(2 * c1.r - (2 * o.r - 1)) = abs(2 * c2.r - (2 * o.r - 1))
              AND c1.r < c2.r
              AND c1.c = c2.c
              AND c1.b = c2.b
              AND c1.b = o.b
              AND c1.symbol != c2.symbol
        )
    ),

    col_mirror2(b INT, c INT) AS (
        SELECT *
        FROM (SELECT DISTINCT b, c FROM cells) o
        WHERE 1 = (
            SELECT COUNT(*)
            FROM cells c1, cells c2
            WHERE abs(2 * c1.c - (2 * o.c - 1)) = abs(2 * c2.c - (2 * o.c - 1))
              AND c1.c < c2.c
              AND c1.r = c2.r
              AND c1.b = c2.b
              AND c1.b = o.b
              AND c1.symbol != c2.symbol
        )
    ),

    part2(part2 BIGINT) AS (
        SELECT COALESCE((SELECT SUM(r-1) FROM row_mirror2), 0) * 100
             + COALESCE((SELECT SUM(c-1) FROM col_mirror2), 0)
    ),

    potato (x INT) AS ( SELECT 1 )

SELECT * FROM part1, part2;
----
100  16

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

    blocks(b INT, block TEXT) AS (
        SELECT b, regexp_split_to_array(input, '\n\n')[b] as block
        FROM input, generate_series(1, array_length(regexp_split_to_array(input, '\n\n'), 1)) b
    ),
    lines(b INT, r INT, line TEXT) AS (
        SELECT b, r, regexp_split_to_array(block, '\n')[r] as block
        FROM blocks, generate_series(1, array_length(regexp_split_to_array(block, '\n'), 1)) r
    ),
    cells(b INT, r INT, c INT, symbol TEXT) AS (
        SELECT b, r, c, substring(line, c, 1)
        FROM lines, generate_series(1, length(line)) c
    ),
    columns(b INT, c INT, column TEXT) AS (
        SELECT b, c, string_agg(symbol, '' ORDER BY r) FROM cells GROUP BY b, c
    ),

    row_mirror(b INT, r INT) AS (
        SELECT *
        FROM (SELECT DISTINCT b, r FROM cells) o
        WHERE NOT EXISTS (
            -- We would be upset to find rows at mirrored positions that do not match
            -- Rows that match, or have no mirrored position, are fine.
            SELECT FROM lines
            WHERE o.b = lines.b
            GROUP BY abs(2 * lines.r - (2 * o.r - 1))
            HAVING COUNT(DISTINCT lines.line) > 1
        )
    ),

    col_mirror(b INT, c INT) AS (
        SELECT *
        FROM (SELECT DISTINCT b, c FROM cells) o
        WHERE NOT EXISTS (
            -- We would be upset to find rows at mirrored positions that do not match
            -- Rows that match, or have no mirrored position, are fine.
            SELECT FROM columns
            WHERE o.b = columns.b
            GROUP BY abs(2 * columns.c - (2 * o.c - 1))
            HAVING COUNT(DISTINCT columns.column) > 1
        )
    ),

    part1(part1 BIGINT) AS (
        SELECT COALESCE((SELECT SUM(r-1) FROM row_mirror), 0) * 100
             + COALESCE((SELECT SUM(c-1) FROM col_mirror), 0)
    ),

    row_mirror2(b INT, r INT) AS (
        SELECT *
        FROM (SELECT DISTINCT b, r FROM cells) o
        WHERE 1 = (
            SELECT COUNT(*)
            FROM cells c1, cells c2
            WHERE abs(2 * c1.r - (2 * o.r - 1)) = abs(2 * c2.r - (2 * o.r - 1))
              AND c1.r < c2.r
              AND c1.c = c2.c
              AND c1.b = c2.b
              AND c1.b = o.b
              AND c1.symbol != c2.symbol
        )
    ),

    col_mirror2(b INT, c INT) AS (
        SELECT *
        FROM (SELECT DISTINCT b, c FROM cells) o
        WHERE 1 = (
            SELECT COUNT(*)
            FROM cells c1, cells c2
            WHERE abs(2 * c1.c - (2 * o.c - 1)) = abs(2 * c2.c - (2 * o.c - 1))
              AND c1.c < c2.c
              AND c1.r = c2.r
              AND c1.b = c2.b
              AND c1.b = o.b
              AND c1.symbol != c2.symbol
        )
    ),

    part2(part2 BIGINT) AS (
        SELECT COALESCE((SELECT SUM(r-1) FROM row_mirror2), 0) * 100
             + COALESCE((SELECT SUM(c-1) FROM col_mirror2), 0)
    ),

    potato (x INT) AS ( SELECT 1 )

SELECT * FROM part1, part2;
----
Explained Query:
  With
    cte l0 =
      Project (#0, #2, #3) // { arity: 3 }
        Map (array_index(regexp_split_to_array["\n", case_insensitive=false](#1{block}), integer_to_bigint(#2{r}))) // { arity: 4 }
          FlatMap generate_series(1, (regexp_split_to_array["\n", case_insensitive=false](#1{block}) array_length 1), 1) // { arity: 3 }
            Project (#1, #2) // { arity: 2 }
              Map (array_index(regexp_split_to_array["\n\n", case_insensitive=false](#0{input}), integer_to_bigint(#1{b}))) // { arity: 3 }
                FlatMap generate_series(1, (regexp_split_to_array["\n\n", case_insensitive=false](#0{input}) array_length 1), 1) // { arity: 2 }
                  ReadStorage materialize.public.input // { arity: 1 }
    cte l1 =
      Project (#0, #1, #3, #4) // { arity: 4 }
        Map (substr(#2{line}, #3{c}, 1)) // { arity: 5 }
          FlatMap generate_series(1, char_length(#2{line}), 1) // { arity: 4 }
            Get l0 // { arity: 3 }
    cte l2 =
      Distinct project=[#0, #1] // { arity: 2 }
        Project (#0, #1) // { arity: 2 }
          Get l1 // { arity: 4 }
    cte l3 =
      Distinct project=[#0, #1] // { arity: 2 }
        Project (#0, #2) // { arity: 2 }
          Get l1 // { arity: 4 }
    cte l4 =
      ArrangeBy keys=[[#0{b}]] // { arity: 2 }
        Get l2 // { arity: 2 }
    cte l5 =
      Reduce aggregates=[sum((#0{r} - 1))] // { arity: 1 }
        Union // { arity: 1 }
          Negate // { arity: 1 }
            Project (#1) // { arity: 1 }
              Distinct project=[#0, #1] // { arity: 2 }
                Project (#0, #1) // { arity: 2 }
                  Filter (#3{count} > 1) // { arity: 4 }
                    Reduce group_by=[#0, #1, abs(((2 * #2{r}) - ((2 * #1{r}) - 1)))] aggregates=[count(distinct #3{line})] // { arity: 4 }
                      Project (#0, #1, #3, #4) // { arity: 4 }
                        Join on=(#0{b} = #2{b}) type=differential // { arity: 5 }
                          implementation
                            %0:l4[#0{b}]K » %1:l0[#0{b}]K
                          Get l4 // { arity: 2 }
                          ArrangeBy keys=[[#0{b}]] // { arity: 3 }
                            Get l0 // { arity: 3 }
          Project (#1) // { arity: 1 }
            Get l2 // { arity: 2 }
    cte l6 =
      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 }
              - ()
    cte l7 =
      ArrangeBy keys=[[#0{b}]] // { arity: 2 }
        Get l3 // { arity: 2 }
    cte l8 =
      Reduce aggregates=[sum((#0{c} - 1))] // { arity: 1 }
        Union // { arity: 1 }
          Negate // { arity: 1 }
            Project (#1) // { arity: 1 }
              Distinct project=[#0, #1] // { arity: 2 }
                Project (#0, #1) // { arity: 2 }
                  Filter (#3{count_string_agg} > 1) // { arity: 4 }
                    Reduce group_by=[#0, #1, abs(((2 * #2{c}) - ((2 * #1{c}) - 1)))] aggregates=[count(distinct #3{string_agg})] // { arity: 4 }
                      Project (#0, #1, #3, #4{string_agg}) // { arity: 4 }
                        Join on=(#0{b} = #2{b}) type=differential // { arity: 5 }
                          implementation
                            %0:l7[#0{b}]K » %1[#0{b}]K
                          Get l7 // { arity: 2 }
                          ArrangeBy keys=[[#0{b}]] // { arity: 3 }
                            Reduce group_by=[#0, #2] aggregates=[string_agg[order_by=[#0 asc nulls_last]](row(row(#3{symbol}, ""), #1{r}))] // { arity: 3 }
                              Get l1 // { arity: 4 }
          Project (#1) // { arity: 1 }
            Get l3 // { arity: 2 }
    cte l9 =
      Union // { arity: 1 }
        Get l8 // { arity: 1 }
        Map (null) // { arity: 1 }
          Union // { arity: 0 }
            Negate // { arity: 0 }
              Project () // { arity: 0 }
                Get l8 // { arity: 1 }
            Constant // { arity: 0 }
              - ()
    cte l10 =
      Reduce aggregates=[sum((#0{r} - 1))] // { arity: 1 }
        Project (#1) // { arity: 1 }
          Filter (#2{count} = 1) // { arity: 3 }
            Reduce group_by=[#0, #1] aggregates=[count(*)] // { arity: 3 }
              Project (#0, #1) // { arity: 2 }
                Filter (#5{symbol} != #9{symbol}) AND (#3{r} < #7{r}) // { arity: 10 }
                  Join on=(#0{b} = #2{b} = #6{b} AND #4{c} = #8{c} AND abs(((2 * #3{r}) - ((2 * #1{r}) - 1))) = abs(((2 * #7{r}) - ((2 * #1{r}) - 1)))) type=delta // { arity: 10 }
                    implementation
                      %0:l4 » %1:l1[#0{b}]K » %2:l1[#0{b}, #2{c}]KK
                      %1:l1 » %2:l1[#0{b}, #2{c}]KK » %0:l4[#0{b}]K
                      %2:l1 » %1:l1[#0{b}, #2{c}]KK » %0:l4[#0{b}]K
                    Get l4 // { arity: 2 }
                    ArrangeBy keys=[[#0{b}], [#0{b}, #2{c}]] // { arity: 4 }
                      Get l1 // { arity: 4 }
                    ArrangeBy keys=[[#0{b}, #2{c}]] // { arity: 4 }
                      Get l1 // { arity: 4 }
    cte l11 =
      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 }
              - ()
    cte l12 =
      Reduce aggregates=[sum((#0{c} - 1))] // { arity: 1 }
        Project (#1) // { arity: 1 }
          Filter (#2{count} = 1) // { arity: 3 }
            Reduce group_by=[#0, #1] aggregates=[count(*)] // { arity: 3 }
              Project (#0, #1) // { arity: 2 }
                Filter (#5{symbol} != #9{symbol}) AND (#4{c} < #8{c}) // { arity: 10 }
                  Join on=(#0{b} = #2{b} = #6{b} AND #3{r} = #7{r} AND abs(((2 * #4{c}) - ((2 * #1{c}) - 1))) = abs(((2 * #8{c}) - ((2 * #1{c}) - 1)))) type=delta // { arity: 10 }
                    implementation
                      %0:l7 » %1:l1[#0{b}]K » %2:l1[#0{b}, #1{r}]KK
                      %1:l1 » %2:l1[#0{b}, #1{r}]KK » %0:l7[#0{b}]K
                      %2:l1 » %1:l1[#0{b}, #1{r}]KK » %0:l7[#0{b}]K
                    Get l7 // { arity: 2 }
                    ArrangeBy keys=[[#0{b}], [#0{b}, #1{r}]] // { arity: 4 }
                      Get l1 // { arity: 4 }
                    ArrangeBy keys=[[#0{b}, #1{r}]] // { arity: 4 }
                      Get l1 // { arity: 4 }
    cte l13 =
      Union // { arity: 1 }
        Get l12 // { arity: 1 }
        Map (null) // { arity: 1 }
          Union // { arity: 0 }
            Negate // { arity: 0 }
              Project () // { arity: 0 }
                Get l12 // { arity: 1 }
            Constant // { arity: 0 }
              - ()
  Return // { arity: 2 }
    Project (#4, #5) // { arity: 2 }
      Map (((coalesce(#0{sum}, 0) * 100) + coalesce(#1{sum}, 0)), ((coalesce(#2{sum}, 0) * 100) + coalesce(#3{sum}, 0))) // { arity: 6 }
        CrossJoin type=delta // { arity: 4 }
          implementation
            %0 » %1[×]U » %2[×]U » %3[×]U
            %1 » %0[×]U » %2[×]U » %3[×]U
            %2 » %0[×]U » %1[×]U » %3[×]U
            %3 » %0[×]U » %1[×]U » %2[×]U
          ArrangeBy keys=[[]] // { 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 }
                    - ()
          ArrangeBy keys=[[]] // { arity: 1 }
            Union // { arity: 1 }
              Get l9 // { arity: 1 }
              Map (null) // { arity: 1 }
                Union // { arity: 0 }
                  Negate // { arity: 0 }
                    Project () // { arity: 0 }
                      Get l9 // { arity: 1 }
                  Constant // { arity: 0 }
                    - ()
          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