Materialize/test/sqllogictest/advent-of-code/2023/aoc_1224.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_1224.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, line TEXT) AS (
        SELECT r, regexp_split_to_array(input, '\n')[r] as line
        FROM input, generate_series(1, array_length(regexp_split_to_array(input, '\n'), 1)) r
    ),

    observation(r INT, x NUMERIC, y NUMERIC, z NUMERIC, dx NUMERIC, dy NUMERIC, dz NUMERIC) AS (
        SELECT
            r,
            trim(',' FROM regexp_split_to_array(line, ' ')[1])::NUMERIC,
            trim(',' FROM regexp_split_to_array(line, ' ')[2])::NUMERIC,
            trim(',' FROM regexp_split_to_array(line, ' ')[3])::NUMERIC,
            trim(',' FROM regexp_split_to_array(line, ' ')[5])::NUMERIC,
            trim(',' FROM regexp_split_to_array(line, ' ')[6])::NUMERIC,
            trim(',' FROM regexp_split_to_array(line, ' ')[7])::NUMERIC
        FROM
            lines
    ),

    -- Part one: for each pair, solve for a future (x,y) intersection of their traced paths.
    -- https://en.wikipedia.org/wiki/Line–line_intersection#Given_two_points_on_each_line_segment
    meeting(r1 INT, r2 INT, x NUMERIC, y NUMERIC, t1 NUMERIC, t2 NUMERIC) AS (
        SELECT
            o1.r,
            o2.r,
            o1.x + o1.dx * (((o2.x - o1.x) * o2.dy) - ((o2.y - o1.y) * o2.dx)) / (o1.dx * o2.dy - o1.dy * o2.dx),
            o1.y + o1.dy * (((o2.x - o1.x) * o2.dy) - ((o2.y - o1.y) * o2.dx)) / (o1.dx * o2.dy - o1.dy * o2.dx),
            (((o2.x - o1.x) * o2.dy) - ((o2.y - o1.y) * o2.dx)) / (o1.dx * o2.dy - o1.dy * o2.dx),
            (((o2.x - o1.x) * o1.dy) - ((o2.y - o1.y) * o1.dx)) / (o1.dx * o2.dy - o1.dy * o2.dx)
        FROM observation o1, observation o2
        WHERE o1.dx * o2.dy != o1.dy * o2.dx
          AND o1.r < o2.r
    ),
    part1(part1 BIGINT) AS (
        SELECT COUNT(*)
        FROM meeting
        WHERE t1 >= 0
          AND t2 >= 0
          AND x BETWEEN 200000000000000 AND 400000000000000
          AND y BETWEEN 200000000000000 AND 400000000000000
    ),

    -- Part two: find an initial x, y, z, dx, dy, dz such that you intersect every observation in the future.
    -- Hypothesize dx and dy, subtract them, and assses the number of coincidences.
    hypotheses(r INT, x NUMERIC, y NUMERIC, dx NUMERIC, dy NUMERIC, ox NUMERIC, oy NUMERIC) AS (
        SELECT
            r, x, y, dx - ox, dy - oy, ox, oy
        FROM
            observation,
            generate_series(-500, 500) ox,
            generate_series(-500, 500) oy
        WHERE r < 10
          AND 5 * (ox + 21) = 16 * (oy + 39)    -- derived from input pair with same (dx, dy).
    ),
    coincidence(r1 INT, r2 INT, x NUMERIC, y NUMERIC, ox NUMERIC, oy NUMERIC) AS (
        SELECT
            o1.r,
            o2.r,
            o1.x + o1.dx * (((o2.x - o1.x) * o2.dy) - ((o2.y - o1.y) * o2.dx)) / (o1.dx * o2.dy - o1.dy * o2.dx),
            o1.y + o1.dy * (((o2.x - o1.x) * o2.dy) - ((o2.y - o1.y) * o2.dx)) / (o1.dx * o2.dy - o1.dy * o2.dx),
            o1.ox,
            o1.oy
        FROM hypotheses o1, hypotheses o2
        WHERE o1.dx * o2.dy != o1.dy * o2.dx
          AND o1.r < o2.r
          AND o1.ox = o2.ox
          AND o1.oy = o2.oy
    ),

    hypotheses_xz(r INT, x NUMERIC, y NUMERIC, dx NUMERIC, dy NUMERIC, ox NUMERIC, oy NUMERIC) AS (
        SELECT
            r, x, z, dx - ox, dz - oz, ox, oz
        FROM
            observation,
            generate_series(-117, -117) ox,
            generate_series(-500, 500) oz
        WHERE r < 10
    ),
    coincidence_xz(r1 INT, r2 INT, x NUMERIC, y NUMERIC, ox NUMERIC, oy NUMERIC) AS (
        SELECT
            o1.r,
            o2.r,
            o1.x + o1.dx * (((o2.x - o1.x) * o2.dy) - ((o2.y - o1.y) * o2.dx)) / (o1.dx * o2.dy - o1.dy * o2.dx),
            o1.y + o1.dy * (((o2.x - o1.x) * o2.dy) - ((o2.y - o1.y) * o2.dx)) / (o1.dx * o2.dy - o1.dy * o2.dx),
            o1.ox,
            o1.oy
        FROM hypotheses_xz o1, hypotheses_xz o2
        WHERE o1.dx * o2.dy != o1.dy * o2.dx
          AND o1.r < o2.r
          AND o1.ox = o2.ox
          AND o1.oy = o2.oy
    ),

    potato (x INT) AS ( SELECT 1 )

-- SELECT x, y, ox, oy, COUNT(*) FROM coincidence GROUP BY x, y, ox, oy HAVING COUNT(*) > 1;
SELECT x, y, ox, oy, COUNT(*) FROM coincidence_xz GROUP BY x, y, ox, oy HAVING COUNT(*) > 1;
----
Explained Query:
  With
    cte l0 =
      ArrangeBy keys=[[#5{oy}]] // { arity: 6 }
        Project (#0..=#2, #6, #8, #7) // { arity: 6 }
          Map ((#3{dx} - -117), integer_to_numeric(#5{oz}), (#4{dz} - #7)) // { arity: 9 }
            CrossJoin type=differential // { arity: 6 }
              implementation
                %0[×]if » %1[×]if
              ArrangeBy keys=[[]] // { arity: 5 }
                Project (#1, #3..=#6) // { arity: 5 }
                  Filter (#1{r} < 10) // { arity: 7 }
                    Map (regexp_split_to_array[" ", case_insensitive=false](array_index(regexp_split_to_array["\n", case_insensitive=false](#0{input}), integer_to_bigint(#1{r}))), text_to_numeric(btrim(array_index(#2, 1), ",")), text_to_numeric(btrim(array_index(#2, 3), ",")), text_to_numeric(btrim(array_index(#2, 5), ",")), text_to_numeric(btrim(array_index(#2, 7), ","))) // { arity: 7 }
                      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 }
              ArrangeBy keys=[[]] // { arity: 1 }
                Constant // { arity: 1 }
                  total_rows (diffs absed): 1001
                  first_rows:
                    - (0)
                    - (-1)
                    - (1)
                    - (2)
                    - (3)
                    - (4)
                    - (5)
                    - (6)
                    - (7)
                    - (8)
                    - (9)
                    - (10)
                    - (11)
                    - (12)
                    - (13)
                    - (14)
                    - (15)
                    - (16)
                    - (17)
                    - (18)
  Return // { arity: 5 }
    Project (#0, #1, #4, #2, #3{count}) // { arity: 5 }
      Filter (#3{count} > 1) // { arity: 5 }
        Map (-117) // { arity: 5 }
          Reduce group_by=[(#0{x} + ((#2{dx} * (((#5{x} - #0{x}) * #8{dy}) - ((#6{y} - #1{y}) * #7{dx}))) / ((#2{dx} * #8{dy}) - (#3{dy} * #7{dx})))), (#1{y} + ((#3{dy} * (((#5{x} - #0{x}) * #8{dy}) - ((#6{y} - #1{y}) * #7{dx}))) / ((#2{dx} * #8{dy}) - (#3{dy} * #7{dx})))), #4] aggregates=[count(*)] // { arity: 4 }
            Project (#1..=#5, #7..=#10) // { arity: 9 }
              Filter (#0{r} < #6{r}) AND ((#3{dx} * #10{dy}) != (#4{dy} * #9{dx})) // { arity: 12 }
                Join on=(#5{oy} = #11{oy}) type=differential // { arity: 12 }
                  implementation
                    %0:l0[#5{oy}]K » %1:l0[#5{oy}]K
                  Get l0 // { arity: 6 }
                  Get l0 // { arity: 6 }

Source materialize.public.input

Target cluster: quickstart

EOF