# 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