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

mode cockroach

statement ok
CREATE TABLE input (input TEXT);

statement ok
INSERT INTO input VALUES (
'-............./...\................\......-.......\....|...--....................\.............\...\.-........
/\...............\.........|....|..../...-....\...\../...........\..\..................................|......
.\..........\..../....../............-.-.........|........../.............|.............-......./..........\..
.\.......\..........\.......\.\........................\.....|...\.../........|..............\\...........|..-
.\...........\.....\../...-\..|....-.................-.|.....|/\...\................././.........\.\.../......
./....\...\..............|...\.......\...-.....|..|...../...../..-.....................\.......\...../...|..|.
...........|.-.........|.....-.../......\./.........\\....\...\..|./...-.............\........................
-.......................\.............\........\.\...........-....................../...........\....|.-......
-............\..........-./.....\\......\.......|.....-..................-.-\\.....|............-....\........
..............-....|..................-......|....-.../....................-....\...........\.................
................\.......\../.............../......|.....\............-.....\...\....................|..-.../.-
|\.............-......./...........-........../......\-.........-.....................................|\......
.....\.....||.........-............../............|....-...........\.\.....................................|\.
......................./...\......\......./|...\..........|...\.../...........\....\./..-..........\..........
.....\................\.\..............\./.\..-......|........../.....\..\.........|....\....\.....\..........
...\...\...\.......|.....\\.\..\........\.-.....\.|..................................|......-.................
\|...../............................|.../.\......\......-.............|....|...|...-.......|.....\............
.\/..........-..........|........./...................\.........../\.......-.............../............./\.-.
.......\.......\...\............\.-.../.......\....................|.../..............\./.........-......\.-..
../...\...-...|.|../......\......\...\...-................................\.........-........-............./..
...\.../..|........\...|...../../...|............-..........|/...............|..........\|................./..
......\/.\......|..................-...\.......\..|........./.-......-...........-...\......|..........-|/-...
.\.........-........./........................|...........\/....\-......\...\../\.............................
|.....\.\.....|-.............|.......|...........\..|\..........\..|........................|....-.......\//..
..........-.............\.........|......\.......\.../..../.\.-..........\....../........................\....');

query II
WITH MUTUALLY RECURSIVE

    lines(r INT, line TEXT) AS (
        SELECT r, regexp_split_to_array(input, '\n')[r] as block
        FROM input, generate_series(1, array_length(regexp_split_to_array(input, '\n'), 1)) r
    ),
    cells(r INT, c INT, symbol TEXT) AS (
        SELECT r, c, substring(line, c, 1)
        FROM lines, generate_series(1, length(line)) c
    ),

    shift(dir TEXT, symbol TEXT, dr INT, dc INT, new_dir TEXT) AS (
        VALUES
            ('r', '.',  0,  1, 'r'),
            ('r', '-',  0,  1, 'r'),
            ('r', '|',  1,  0, 'd'),
            ('r', '|', -1,  0, 'u'),
            ('r', '/', -1,  0, 'u'),
            ('r', '\',  1,  0, 'd'),
            ('l', '.',  0, -1, 'l'),
            ('l', '-',  0, -1, 'l'),
            ('l', '|',  1,  0, 'd'),
            ('l', '|', -1,  0, 'u'),
            ('l', '/',  1,  0, 'd'),
            ('l', '\', -1,  0, 'u'),
            ('u', '.', -1,  0, 'u'),
            ('u', '-',  0,  1, 'r'),
            ('u', '-',  0, -1, 'l'),
            ('u', '|', -1,  0, 'u'),
            ('u', '/',  0,  1, 'r'),
            ('u', '\',  0, -1, 'l'),
            ('d', '.',  1,  0, 'd'),
            ('d', '-',  0,  1, 'r'),
            ('d', '-',  0, -1, 'l'),
            ('d', '|',  1,  0, 'd'),
            ('d', '/',  0, -1, 'l'),
            ('d', '\',  0,  1, 'r')
    ),

    -- Light is in a location, and has a direction.
    light(r INT, c INT, dir TEXT) AS (
        SELECT 1, 1, 'r'
        UNION
        SELECT light.r + dr, light.c + dc, new_dir
        FROM light, cells, shift
        WHERE light.r = cells.r
            AND light.c = cells.c
            AND light.dir = shift.dir
            AND cells.symbol = shift.symbol
    ),

    part1(part1 BIGINT) AS (
        SELECT COUNT(*) FROM (
            SELECT DISTINCT light.r, light.c
            FROM light, cells
            WHERE light.r = cells.r
                AND light.c = cells.c
        )
    ),

    -- Light is in a location, a direction, and an origin.
    light2(r INT, c INT, dir TEXT, source TEXT) AS (
        SELECT DISTINCT * FROM (SELECT r, (SELECT MIN(c) FROM cells), 'r', 'r' || r FROM cells) UNION
        SELECT DISTINCT * FROM (SELECT r, (SELECT MAX(c) FROM cells), 'l', 'l' || r FROM cells) UNION
        SELECT DISTINCT * FROM (SELECT (SELECT MIN(r) FROM cells), c, 'd', 'd' || c FROM cells) UNION
        SELECT DISTINCT * FROM (SELECT (SELECT MAX(c) FROM cells), c, 'u', 'u' || c FROM cells) UNION
        SELECT light2.r + dr, light2.c + dc, new_dir, source
        FROM light2, cells, shift
        WHERE light2.r = cells.r
            AND light2.c = cells.c
            AND light2.dir = shift.dir
            AND cells.symbol = shift.symbol
    ),

    part2(part2 BIGINT) AS (
        SELECT MAX(count) FROM (
            SELECT source, COUNT(*) FROM (
                SELECT DISTINCT light2.r, light2.c, source
                FROM light2, cells
                WHERE light2.r = cells.r
                    AND light2.c = cells.c
            )
            GROUP BY source
        )
    )

SELECT * FROM part1, part2;
----
15  613

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

    lines(r INT, line TEXT) AS (
        SELECT r, regexp_split_to_array(input, '\n')[r] as block
        FROM input, generate_series(1, array_length(regexp_split_to_array(input, '\n'), 1)) r
    ),
    cells(r INT, c INT, symbol TEXT) AS (
        SELECT r, c, substring(line, c, 1)
        FROM lines, generate_series(1, length(line)) c
    ),

    shift(dir TEXT, symbol TEXT, dr INT, dc INT, new_dir TEXT) AS (
        VALUES
            ('r', '.',  0,  1, 'r'),
            ('r', '-',  0,  1, 'r'),
            ('r', '|',  1,  0, 'd'),
            ('r', '|', -1,  0, 'u'),
            ('r', '/', -1,  0, 'u'),
            ('r', '\',  1,  0, 'd'),
            ('l', '.',  0, -1, 'l'),
            ('l', '-',  0, -1, 'l'),
            ('l', '|',  1,  0, 'd'),
            ('l', '|', -1,  0, 'u'),
            ('l', '/',  1,  0, 'd'),
            ('l', '\', -1,  0, 'u'),
            ('u', '.', -1,  0, 'u'),
            ('u', '-',  0,  1, 'r'),
            ('u', '-',  0, -1, 'l'),
            ('u', '|', -1,  0, 'u'),
            ('u', '/',  0,  1, 'r'),
            ('u', '\',  0, -1, 'l'),
            ('d', '.',  1,  0, 'd'),
            ('d', '-',  0,  1, 'r'),
            ('d', '-',  0, -1, 'l'),
            ('d', '|',  1,  0, 'd'),
            ('d', '/',  0, -1, 'l'),
            ('d', '\',  0,  1, 'r')
    ),

    -- Light is in a location, and has a direction.
    light(r INT, c INT, dir TEXT) AS (
        SELECT 1, 1, 'r'
        UNION
        SELECT light.r + dr, light.c + dc, new_dir
        FROM light, cells, shift
        WHERE light.r = cells.r
            AND light.c = cells.c
            AND light.dir = shift.dir
            AND cells.symbol = shift.symbol
    ),

    part1(part1 BIGINT) AS (
        SELECT COUNT(*) FROM (
            SELECT DISTINCT light.r, light.c
            FROM light, cells
            WHERE light.r = cells.r
                AND light.c = cells.c
        )
    ),

    -- Light is in a location, a direction, and an origin.
    light2(r INT, c INT, dir TEXT, source TEXT) AS (
        SELECT DISTINCT * FROM (SELECT r, (SELECT MIN(c) FROM cells), 'r', 'r' || r FROM cells) UNION
        SELECT DISTINCT * FROM (SELECT r, (SELECT MAX(c) FROM cells), 'l', 'l' || r FROM cells) UNION
        SELECT DISTINCT * FROM (SELECT (SELECT MIN(r) FROM cells), c, 'd', 'd' || c FROM cells) UNION
        SELECT DISTINCT * FROM (SELECT (SELECT MAX(c) FROM cells), c, 'u', 'u' || c FROM cells) UNION
        SELECT light2.r + dr, light2.c + dc, new_dir, source
        FROM light2, cells, shift
        WHERE light2.r = cells.r
            AND light2.c = cells.c
            AND light2.dir = shift.dir
            AND cells.symbol = shift.symbol
    ),

    part2(part2 BIGINT) AS (
        SELECT MAX(count) FROM (
            SELECT source, COUNT(*) FROM (
                SELECT DISTINCT light2.r, light2.c, source
                FROM light2, cells
                WHERE light2.r = cells.r
                    AND light2.c = cells.c
            )
            GROUP BY source
        )
    )

SELECT * FROM part1, part2;
----
Explained Query:
  With
    cte l0 =
      Project (#0, #2, #3) // { arity: 3 }
        Map (substr(#1{line}, #2{c}, 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{r}))) // { 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 (#1) // { arity: 1 }
        Get l0 // { arity: 3 }
    cte l2 =
      Reduce aggregates=[min(#0{c})] // { arity: 1 }
        Get l1 // { arity: 1 }
    cte l3 =
      Union // { arity: 1 }
        Get l2 // { arity: 1 }
        Map (null) // { arity: 1 }
          Union // { arity: 0 }
            Negate // { arity: 0 }
              Project () // { arity: 0 }
                Get l2 // { arity: 1 }
            Constant // { arity: 0 }
              - ()
    cte l4 =
      Reduce aggregates=[max(#0{c})] // { arity: 1 }
        Get l1 // { arity: 1 }
    cte l5 =
      Union // { arity: 1 }
        Get l4 // { arity: 1 }
        Map (null) // { arity: 1 }
          Union // { arity: 0 }
            Negate // { arity: 0 }
              Project () // { arity: 0 }
                Get l4 // { arity: 1 }
            Constant // { arity: 0 }
              - ()
    cte l6 =
      Project (#0) // { arity: 1 }
        Get l0 // { arity: 3 }
    cte l7 =
      Reduce aggregates=[min(#0{r})] // { arity: 1 }
        Get l6 // { arity: 1 }
    cte l8 =
      Union // { arity: 1 }
        Get l7 // { arity: 1 }
        Map (null) // { arity: 1 }
          Union // { arity: 0 }
            Negate // { arity: 0 }
              Project () // { arity: 0 }
                Get l7 // { arity: 1 }
            Constant // { arity: 0 }
              - ()
    cte l9 =
      Project (#0, #1) // { arity: 2 }
        Get l0 // { arity: 3 }
    cte l10 =
      CrossJoin type=differential // { arity: 3 }
        implementation
          %1[×]U » %0:l9[×]
        ArrangeBy keys=[[]] // { arity: 2 }
          Get l9 // { arity: 2 }
        ArrangeBy keys=[[]] // { arity: 1 }
          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 l11 =
      ArrangeBy keys=[[#0{r}, #1{c}]] // { arity: 3 }
        Filter (#2{symbol}) IS NOT NULL // { arity: 3 }
          Get l0 // { arity: 3 }
    cte l12 =
      ArrangeBy keys=[[#0{dir}, #1{symbol}]] // { arity: 5 }
        Constant // { arity: 5 }
          total_rows (diffs absed): 24
          first_rows:
            - ("d", "-", 0, -1, "l")
            - ("d", "/", 0, -1, "l")
            - ("l", "-", 0, -1, "l")
            - ("l", ".", 0, -1, "l")
            - ("l", "\", -1, 0, "u")
            - ("l", "|", -1, 0, "u")
            - ("r", "/", -1, 0, "u")
            - ("r", "|", -1, 0, "u")
            - ("u", "-", 0, -1, "l")
            - ("u", ".", -1, 0, "u")
            - ("u", "\", 0, -1, "l")
            - ("u", "|", -1, 0, "u")
            - ("d", "-", 0, 1, "r")
            - ("d", ".", 1, 0, "d")
            - ("d", "\", 0, 1, "r")
            - ("d", "|", 1, 0, "d")
            - ("l", "/", 1, 0, "d")
            - ("l", "|", 1, 0, "d")
            - ("r", "-", 0, 1, "r")
            - ("r", ".", 0, 1, "r")
  Return // { arity: 2 }
    With Mutually Recursive
      cte l13 =
        Distinct project=[#0..=#2] // { arity: 3 }
          Union // { arity: 3 }
            Project (#11, #12, #10) // { arity: 3 }
              Map ((#0{r} + #8{dr}), (#1{c} + #9{dc})) // { arity: 13 }
                Join on=(#0{r} = #3{r} AND #1{c} = #4{c} AND #2{dir} = #6{dir} AND #5{symbol} = #7{symbol}) type=differential // { arity: 11 }
                  implementation
                    %0:l13[#0{r}, #1{c}]KK » %1:l11[#0{r}, #1{c}]KK » %2:l12[#0{dir}, #1{symbol}]KK
                  ArrangeBy keys=[[#0{r}, #1{c}]] // { arity: 3 }
                    Get l13 // { arity: 3 }
                  Get l11 // { arity: 3 }
                  Get l12 // { arity: 5 }
            Constant // { arity: 3 }
              - (1, 1, "r")
      cte l14 =
        Reduce aggregates=[count(*)] // { arity: 1 }
          Project () // { arity: 0 }
            Join on=(#0{r} = #2{r} AND #1{c} = #3{c}) type=differential // { arity: 4 }
              implementation
                %0[#0, #1]UKKA » %1[#0, #1]UKKA
              ArrangeBy keys=[[#0{r}, #1{c}]] // { arity: 2 }
                Distinct project=[#0{r}, #1{c}] // { arity: 2 }
                  Project (#0, #1) // { arity: 2 }
                    Get l13 // { arity: 3 }
              ArrangeBy keys=[[#0{r}, #1{c}]] // { arity: 2 }
                Distinct project=[#0{r}, #1{c}] // { arity: 2 }
                  Get l9 // { arity: 2 }
      cte l15 =
        Distinct project=[#0{min}..=#3] // { arity: 4 }
          Union // { arity: 4 }
            Project (#0, #1{min}, #3, #2) // { arity: 4 }
              Map (("r" || integer_to_text(#0{r})), "r") // { arity: 4 }
                CrossJoin type=differential // { arity: 2 }
                  implementation
                    %1[×]U » %0:l6[×]
                  ArrangeBy keys=[[]] // { arity: 1 }
                    Get l6 // { arity: 1 }
                  ArrangeBy keys=[[]] // { arity: 1 }
                    Union // { arity: 1 }
                      Get l3 // { arity: 1 }
                      Map (null) // { arity: 1 }
                        Union // { arity: 0 }
                          Negate // { arity: 0 }
                            Project () // { arity: 0 }
                              Get l3 // { arity: 1 }
                          Constant // { arity: 0 }
                            - ()
            Project (#0, #2{max}, #4, #3) // { arity: 4 }
              Map (("l" || integer_to_text(#0{r})), "l") // { arity: 5 }
                Get l10 // { arity: 3 }
            Project (#1{min}, #0, #3, #2) // { arity: 4 }
              Map (("d" || integer_to_text(#0{c})), "d") // { arity: 4 }
                CrossJoin type=differential // { arity: 2 }
                  implementation
                    %1[×]U » %0:l1[×]
                  ArrangeBy keys=[[]] // { arity: 1 }
                    Get l1 // { arity: 1 }
                  ArrangeBy keys=[[]] // { arity: 1 }
                    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 }
                            - ()
            Project (#2{max}, #1, #4, #3) // { arity: 4 }
              Map (("u" || integer_to_text(#1{c})), "u") // { arity: 5 }
                Get l10 // { arity: 3 }
            Project (#12, #13, #11, #3) // { arity: 4 }
              Map ((#0{r} + #9{dr}), (#1{c} + #10{dc})) // { arity: 14 }
                Join on=(#0{r} = #4{r} AND #1{c} = #5{c} AND #2{dir} = #7{dir} AND #6{symbol} = #8{symbol}) type=differential // { arity: 12 }
                  implementation
                    %0:l15[#0{r}, #1{c}]KK » %1:l11[#0{r}, #1{c}]KK » %2:l12[#0{dir}, #1{symbol}]KK
                  ArrangeBy keys=[[#0{min}, #1{min}]] // { arity: 4 }
                    Filter (#0{min}) IS NOT NULL AND (#1{min}) IS NOT NULL // { arity: 4 }
                      Get l15 // { arity: 4 }
                  Get l11 // { arity: 3 }
                  Get l12 // { arity: 5 }
    Return // { arity: 2 }
      With
        cte l16 =
          Reduce aggregates=[max(#0{count})] // { arity: 1 }
            Project (#1{count}) // { arity: 1 }
              Reduce group_by=[#0] aggregates=[count(*)] // { arity: 2 }
                Project (#2) // { arity: 1 }
                  Join on=(#0{min} = #3{r} AND #1{min} = #4{c}) type=differential // { arity: 5 }
                    implementation
                      %1[#0, #1]UKKA » %0[#0, #1]KK
                    ArrangeBy keys=[[#0{min}, #1{min}]] // { arity: 3 }
                      Distinct project=[#0{min}..=#2] // { arity: 3 }
                        Project (#0{min}, #1{min}, #3) // { arity: 3 }
                          Filter (#0{min}) IS NOT NULL AND (#1{min}) IS NOT NULL // { arity: 4 }
                            Get l15 // { arity: 4 }
                    ArrangeBy keys=[[#0{r}, #1{c}]] // { arity: 2 }
                      Distinct project=[#0{r}, #1{c}] // { arity: 2 }
                        Project (#0, #1) // { arity: 2 }
                          Get l0 // { arity: 3 }
      Return // { arity: 2 }
        CrossJoin type=differential // { arity: 2 }
          implementation
            %0[×]U » %1[×]U
          ArrangeBy keys=[[]] // { arity: 1 }
            Union // { arity: 1 }
              Get l14 // { arity: 1 }
              Map (0) // { arity: 1 }
                Union // { arity: 0 }
                  Negate // { arity: 0 }
                    Project () // { arity: 0 }
                      Get l14 // { arity: 1 }
                  Constant // { arity: 0 }
                    - ()
          ArrangeBy keys=[[]] // { arity: 1 }
            Union // { arity: 1 }
              Get l16 // { arity: 1 }
              Map (null) // { arity: 1 }
                Union // { arity: 0 }
                  Negate // { arity: 0 }
                    Project () // { arity: 0 }
                      Get l16 // { arity: 1 }
                  Constant // { arity: 0 }
                    - ()

Source materialize.public.input

Target cluster: quickstart

EOF