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

mode cockroach

statement ok
CREATE TABLE aoc_1204 (input TEXT);

statement ok
INSERT INTO aoc_1204 VALUES (
'Card   1: 91 58 89  8 19 64 92 28 22  1 |  6 94 21 70 81 59  5 35 24 31 43 69 91 12 51 53 98 50 70 98 47  6  9 49 50
Card   2: 49 56 57 80 28  9  3 19 55  6 | 35 25 76 45 35 73 12 93 29 23 50 33 75 36  4 33 90 84  1  9 44 62 99 80 85
Card   3: 97 29 93 95 66 40 97  9 58 11 | 22 56 90 13 40 84 83 70 65 80 73 84 58 93 98 79 46 51 47 70  8 50 43    70
Card   4: 62 79 90 45 63 70 75 26 14 92 | 70  5 69 58 80 64 72  4 36 24 40 76 79 16 79 11 80 88 49 92 15 24  5 49 22
Card   5: 54 26 80 65 14 46 77 59 12 20 | 96 89 95 25 19 22 34  9 24 86 87 63 16 31  5 22 91 71  8 80 33  2 65 67 78
Card   6: 22 10 58 44  5 97 97 57 88  8 | 54 50 79 45  2 40 90 30 82 37 29 99 50 90 51 84 97 62  8  4 89 82 86 59 65
Card   7: 65 94 76  4 41 40  1  6 50 96 | 82 90 42 92 22 18 29 96 47 91 71  2  5  3 42 73 45 26 15 13 29 37  7 63 81
Card   8: 73 19 52 43 47 54  6 86 12 34 | 25 70 26 15 35 10 65 81 48 72 98 48 18 94  8 34  6 44 79 25 77 27 78 61 28
Card   9: 32 51 38 86 17 56 42  4 67 38 | 55  5 26 91 98 11 52  1 48 13 55 95 60 15 16 51 54 22 91  8 26 70 26 35 92
Card  10:  6 40 74  5 31 63  1  5 12 64 | 88  7 91 54  4 62 37 66  5 69 59 78 17 47 61  2  6 56 36 59  2 71 63 87 72');

statement ok
CREATE VIEW input (input) AS SELECT * FROM aoc_1204;

query I
WITH parsed AS (
  SELECT regexp_split_to_table(input, '\n') AS line FROM aoc_1204
),
numbers AS (
  SELECT split_part(line,':',1) AS card_id,
         replace(split_part(line,':',2),'|','') AS nrs
  FROM parsed
),
arr AS (
  SELECT card_id,
         nrs,
         regexp_split_to_array(ltrim(rtrim(nrs)),'\s') AS nrs_arr
  FROM numbers
),
winning AS (
  SELECT card_id,
         unnest(array_remove(nrs_arr,'')) nr,
         ROW_NUMBER() OVER (PARTITION BY card_id) AS row_num
  FROM arr
  GROUP BY card_id, nr HAVING COUNT(*)>1
  ORDER BY card_id
),
winning_points AS (
  SELECT ROUND(EXP(SUM(LN(CASE WHEN row_num = 1 THEN row_num ELSE 2 END)))) AS points
  FROM winning
  GROUP BY card_id
)
SELECT SUM(points)
FROM winning_points;
----
184

query T multiline
EXPLAIN OPTIMIZED PLAN WITH(humanized expressions, arity, join implementations) AS VERBOSE TEXT FOR
WITH parsed AS (
  SELECT regexp_split_to_table(input, '\n') AS line FROM aoc_1204
),
numbers AS (
  SELECT split_part(line,':',1) AS card_id,
         replace(split_part(line,':',2),'|','') AS nrs
  FROM parsed
),
arr AS (
  SELECT card_id,
         nrs,
         regexp_split_to_array(ltrim(rtrim(nrs)),'\s') AS nrs_arr
  FROM numbers
),
winning AS (
  SELECT card_id,
         unnest(array_remove(nrs_arr,'')) nr,
         ROW_NUMBER() OVER (PARTITION BY card_id) AS row_num
  FROM arr
  GROUP BY card_id, nr HAVING COUNT(*)>1
  ORDER BY card_id
),
winning_points AS (
  SELECT ROUND(EXP(SUM(LN(CASE WHEN row_num = 1 THEN row_num ELSE 2 END)))) AS points
  FROM winning
  GROUP BY card_id
)
SELECT SUM(points)
FROM winning_points;
----
Explained Query:
  With
    cte l0 =
      Reduce aggregates=[sum(roundf64(expf64(#0{sum})))] // { arity: 1 }
        Project (#1{sum}) // { arity: 1 }
          Reduce group_by=[record_get[0](record_get[1](#0))] aggregates=[sum(lnf64(bigint_to_double(case when (1 = record_get[0](#0)) then record_get[0](#0) else 2 end)))] // { arity: 2 }
            Project (#1) // { arity: 1 }
              FlatMap unnest_list(#0{row_number}) // { arity: 2 }
                Project (#1{row_number}) // { arity: 1 }
                  Reduce group_by=[#0] aggregates=[row_number[order_by=[]](row(list[row(#0, #1, #2{count})]))] // { arity: 2 }
                    Filter (#2{count} > 1) // { arity: 3 }
                      Reduce group_by=[#0, #1] aggregates=[count(*)] // { arity: 3 }
                        Project (#0, #2) // { arity: 2 }
                          FlatMap unnest_array(array_remove(#1{nrs_arr}, "")) // { arity: 3 }
                            Project (#2, #3) // { arity: 2 }
                              Map (split_string(#1{line}, ":", 1), regexp_split_to_array["\s", case_insensitive=false](ltrim(rtrim(replace(split_string(#1{line}, ":", 2), "|", ""))))) // { arity: 4 }
                                FlatMap unnest_array(regexp_split_to_array["\n", case_insensitive=false](#0{input})) // { arity: 2 }
                                  ReadStorage materialize.public.aoc_1204 // { arity: 1 }
  Return // { arity: 1 }
    Union // { arity: 1 }
      Get l0 // { arity: 1 }
      Map (null) // { arity: 1 }
        Union // { arity: 0 }
          Negate // { arity: 0 }
            Project () // { arity: 0 }
              Get l0 // { arity: 1 }
          Constant // { arity: 0 }
            - ()

Source materialize.public.aoc_1204

Target cluster: quickstart

EOF

query I
WITH MUTUALLY RECURSIVE
lines(line string) AS (
    SELECT
        regexp_split_to_table(input, '\n') AS line
    FROM
        aoc_1204
),
cards(match string[]) AS (
    SELECT
        regexp_match(line, 'Card +(\d+): (.*)') AS match
    FROM
        lines
),
card_parts(card_id int, parts string[]) AS (
    SELECT
        match[1]::int AS card_id,
        regexp_split_to_array(match[2], ' \| ') AS parts
    FROM
        cards
),
winners(card_id int, val int) AS (
    SELECT
        card_id,
        regexp_split_to_table(trim(parts[1]), '\s+')::int AS val
    FROM
        card_parts
),
ours(card_id int, val int) AS (
    SELECT
        card_id,
        regexp_split_to_table(trim(parts[2]), '\s+')::int AS val
    FROM
        card_parts
),
count_winning_numbers(card_id int, count int) AS (
    SELECT
        ours.card_id,
        count(winners.val)::int AS count
    FROM
        ours LEFT OUTER JOIN winners ON (
            ours.card_id = winners.card_id AND
            ours.val = winners.val
        )
    GROUP BY ours.card_id
),
prizes(card_id int, prize_id int) AS (
    SELECT
        card_id,
        prize_id
    FROM
        count_winning_numbers CROSS JOIN generate_series(card_id + 1, card_id + count) AS prize_id
    UNION
    SELECT
        0 AS card_id,
        ours.card_id AS prize_id
    FROM
        ours
),
multipliers(card_id int, multiplier int) AS (
    SELECT
        prizes.prize_id AS card_id,
        SUM(coalesce(multipliers.multiplier, 1))::int AS multiplier
    FROM
        prizes left outer JOIN multipliers ON (
            prizes.card_id = multipliers.card_id
        )
    GROUP BY prizes.prize_id
)
SELECT
    SUM(multiplier) AS answer
FROM
    multipliers;
----
978

query T multiline
EXPLAIN OPTIMIZED PLAN WITH(humanized expressions, arity, join implementations) AS VERBOSE TEXT FOR
WITH MUTUALLY RECURSIVE
lines(line string) AS (
    SELECT
        regexp_split_to_table(input, '\n') AS line
    FROM
        aoc_1204
),
cards(match string[]) AS (
    SELECT
        regexp_match(line, 'Card +(\d+): (.*)') AS match
    FROM
        lines
),
card_parts(card_id int, parts string[]) AS (
    SELECT
        match[1]::int AS card_id,
        regexp_split_to_array(match[2], ' \| ') AS parts
    FROM
        cards
),
winners(card_id int, val int) AS (
    SELECT
        card_id,
        regexp_split_to_table(trim(parts[1]), '\s+')::int AS val
    FROM
        card_parts
),
ours(card_id int, val int) AS (
    SELECT
        card_id,
        regexp_split_to_table(trim(parts[2]), '\s+')::int AS val
    FROM
        card_parts
),
count_winning_numbers(card_id int, count int) AS (
    SELECT
        ours.card_id,
        count(winners.val)::int AS count
    FROM
        ours LEFT OUTER JOIN winners ON (
            ours.card_id = winners.card_id AND
            ours.val = winners.val
        )
    GROUP BY ours.card_id
),
prizes(card_id int, prize_id int) AS (
    SELECT
        card_id,
        prize_id
    FROM
        count_winning_numbers CROSS JOIN generate_series(card_id + 1, card_id + count) AS prize_id
    UNION
    SELECT
        0 AS card_id,
        ours.card_id AS prize_id
    FROM
        ours
),
multipliers(card_id int, multiplier int) AS (
    SELECT
        prizes.prize_id AS card_id,
        SUM(coalesce(multipliers.multiplier, 1))::int AS multiplier
    FROM
        prizes left outer JOIN multipliers ON (
            prizes.card_id = multipliers.card_id
        )
    GROUP BY prizes.prize_id
)
SELECT
    SUM(multiplier) AS answer
FROM
    multipliers;
----
Explained Query:
  With
    cte l0 =
      Project (#3, #4) // { arity: 2 }
        Map (regexp_match["Card +(\d+): (.*)", case_insensitive=false](#1{line}), text_to_integer(array_index(#2{match}, 1)), regexp_split_to_array[" \| ", case_insensitive=false](array_index(#2{match}, 2))) // { arity: 5 }
          FlatMap unnest_array(regexp_split_to_array["\n", case_insensitive=false](#0{input})) // { arity: 2 }
            ReadStorage materialize.public.aoc_1204 // { arity: 1 }
    cte l1 =
      Project (#0, #3) // { arity: 2 }
        Map (text_to_integer(#2{unnest})) // { arity: 4 }
          FlatMap unnest_array(regexp_split_to_array["\s+", case_insensitive=false](btrim(array_index(#1{parts}, 2)))) // { arity: 3 }
            Get l0 // { arity: 2 }
    cte l2 =
      ArrangeBy keys=[[#0{card_id}, #1{val}]] // { arity: 2 }
        Filter (#0{card_id}) IS NOT NULL AND (#1{val}) IS NOT NULL // { arity: 2 }
          Get l1 // { arity: 2 }
    cte l3 =
      Project (#0, #1) // { arity: 2 }
        Join on=(#0{card_id} = #2{card_id} AND #1{val} = #3{val}) type=differential // { arity: 4 }
          implementation
            %0:l2[#0{card_id}, #1{val}]KK » %1[#0{card_id}, #1{val}]KK
          Get l2 // { arity: 2 }
          ArrangeBy keys=[[#0{card_id}, #1{val}]] // { arity: 2 }
            Project (#0, #3) // { arity: 2 }
              Filter (#2{unnest}) IS NOT NULL // { arity: 4 }
                Map (text_to_integer(#2{unnest})) // { arity: 4 }
                  FlatMap unnest_array(regexp_split_to_array["\s+", case_insensitive=false](btrim(array_index(#1{parts}, 1)))) // { arity: 3 }
                    Filter (#0{card_id}) IS NOT NULL // { arity: 2 }
                      Get l0 // { arity: 2 }
    cte l4 =
      Distinct project=[#0, #1] // { arity: 2 }
        Union // { arity: 2 }
          Project (#0, #2) // { arity: 2 }
            FlatMap generate_series((#0{card_id} + 1), (#0{card_id} + #1{count}), 1) // { arity: 3 }
              Project (#0, #2) // { arity: 2 }
                Map (bigint_to_integer(#1{count})) // { arity: 3 }
                  Reduce group_by=[#0] aggregates=[count(#1{val})] // { arity: 2 }
                    Union // { arity: 2 }
                      Map (null) // { arity: 2 }
                        Union // { arity: 1 }
                          Negate // { arity: 1 }
                            Project (#0) // { arity: 1 }
                              Join on=(#0{card_id} = #2 AND #1{val} = #3) type=differential // { arity: 4 }
                                implementation
                                  %1[#0, #1]UKKA » %0:l2[#0{card_id}, #1{val}]KK
                                Get l2 // { arity: 2 }
                                ArrangeBy keys=[[#0, #1]] // { arity: 2 }
                                  Distinct project=[#0, #1] // { arity: 2 }
                                    Get l3 // { arity: 2 }
                          Project (#0) // { arity: 1 }
                            Get l1 // { arity: 2 }
                      Get l3 // { arity: 2 }
          Project (#2, #0) // { arity: 2 }
            Map (0) // { arity: 3 }
              Get l1 // { arity: 2 }
  Return // { arity: 1 }
    With Mutually Recursive
      cte l5 =
        Project (#1, #3) // { arity: 2 }
          Join on=(#0{card_id} = #2) type=differential // { arity: 4 }
            implementation
              %1:l6[#0]UK » %0:l4[#0{card_id}]K
            ArrangeBy keys=[[#0{card_id}]] // { arity: 2 }
              Filter (#0{card_id}) IS NOT NULL // { arity: 2 }
                Get l4 // { arity: 2 }
            ArrangeBy keys=[[#0]] // { arity: 2 }
              Filter (#0{card_id}) IS NOT NULL // { arity: 2 }
                Get l6 // { arity: 2 }
      cte l6 =
        Project (#0, #2) // { arity: 2 }
          Map (bigint_to_integer(#1{sum})) // { arity: 3 }
            Reduce group_by=[#0] aggregates=[sum(coalesce(#1{multiplier}, 1))] // { arity: 2 }
              Union // { arity: 2 }
                Map (null) // { arity: 2 }
                  Union // { arity: 1 }
                    Negate // { arity: 1 }
                      Project (#0) // { arity: 1 }
                        Get l5 // { arity: 2 }
                    Project (#1) // { arity: 1 }
                      Get l4 // { arity: 2 }
                Get l5 // { arity: 2 }
    Return // { arity: 1 }
      With
        cte l7 =
          Reduce aggregates=[sum(#0{multiplier})] // { arity: 1 }
            Project (#1) // { arity: 1 }
              Get l6 // { arity: 2 }
      Return // { arity: 1 }
        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 }
                - ()

Source materialize.public.aoc_1204

Target cluster: quickstart

EOF

query II
WITH MUTUALLY RECURSIVE
    -- PART 0
    -- Parse the input as lines of text with line numbers.
    lines(line TEXT) AS (
        SELECT regexp_split_to_table(input, '\n')
        FROM   input
    ),
    blocks(card TEXT, wins TEXT, have TEXT) AS (
        SELECT
            TRIM (regexp_split_to_array(line, '(:|\|)')[1]),
            TRIM (regexp_split_to_array(line, '(:|\|)')[2]),
            TRIM (regexp_split_to_array(line, '(:|\|)')[3])
        FROM
            lines
    ),
    parsed(card INT, wins TEXT[], have TEXT[]) AS (
        SELECT
            regexp_match(card, '[0-9]+')[1]::INT,
            regexp_split_to_array(wins, ' '),
            regexp_split_to_array(have, ' ')
        FROM blocks
    ),

    -- PART 1
    -- Count "have"s in "wins" for each row, exponentiate, sum.
    matches(card INT, score BIGINT) AS (
        SELECT card, (
            SELECT COUNT(*)
            FROM (
                SELECT unnest(wins) w
                INTERSECT
                SELECT unnest(have) w
            )
            WHERE w != ''
        )
        FROM parsed
    ),
    part1(part1 NUMERIC) AS (
        SELECT SUM(pow(2, score - 1))::NUMERIC
        FROM matches
        WHERE score > 0
    ),

    -- PART 2
    -- Each card provides a copy of the next `score` cards.
    -- This could be prefix sum if we want to be clever ...
    expanded(card INT, score BIGINT) AS (
        SELECT * FROM matches
        UNION ALL
        SELECT
            matches.card,
            matches.score
        FROM
            expanded,
            matches,
            generate_series(1, expanded.score) as step
        WHERE
            expanded.card + step = matches.card
    ),
    part2(part2 BIGINT) AS ( SELECT COUNT(*) FROM expanded)

select * from part1, part2;
----
23  314

query T multiline
EXPLAIN OPTIMIZED PLAN WITH(humanized expressions, arity, join implementations) AS VERBOSE TEXT FOR
WITH MUTUALLY RECURSIVE
    -- PART 0
    -- Parse the input as lines of text with line numbers.
    lines(line TEXT) AS (
        SELECT regexp_split_to_table(input, '\n')
        FROM   input
    ),
    blocks(card TEXT, wins TEXT, have TEXT) AS (
        SELECT
            TRIM (regexp_split_to_array(line, '(:|\|)')[1]),
            TRIM (regexp_split_to_array(line, '(:|\|)')[2]),
            TRIM (regexp_split_to_array(line, '(:|\|)')[3])
        FROM
            lines
    ),
    parsed(card INT, wins TEXT[], have TEXT[]) AS (
        SELECT
            regexp_match(card, '[0-9]+')[1]::INT,
            regexp_split_to_array(wins, ' '),
            regexp_split_to_array(have, ' ')
        FROM blocks
    ),

    -- PART 1
    -- Count "have"s in "wins" for each row, exponentiate, sum.
    matches(card INT, score BIGINT) AS (
        SELECT card, (
            SELECT COUNT(*)
            FROM (
                SELECT unnest(wins) w
                INTERSECT
                SELECT unnest(have) w
            )
            WHERE w != ''
        )
        FROM parsed
    ),
    part1(part1 NUMERIC) AS (
        SELECT SUM(pow(2, score - 1))::NUMERIC
        FROM matches
        WHERE score > 0
    ),

    -- PART 2
    -- Each card provides a copy of the next `score` cards.
    -- This could be prefix sum if we want to be clever ...
    expanded(card INT, score BIGINT) AS (
        SELECT * FROM matches
        UNION ALL
        SELECT
            matches.card,
            matches.score
        FROM
            expanded,
            matches,
            generate_series(1, expanded.score) as step
        WHERE
            expanded.card + step = matches.card
    ),
    part2(part2 BIGINT) AS ( SELECT COUNT(*) FROM expanded)

select * from part1, part2;
----
Explained Query:
  With
    cte l0 =
      Project (#3..=#5) // { arity: 3 }
        Map (regexp_split_to_array["(:|\|)", case_insensitive=false](#1{line}), text_to_integer(array_index(regexp_match["[0-9]+", case_insensitive=false](btrim(array_index(#2, 1))), 1)), regexp_split_to_array[" ", case_insensitive=false](btrim(array_index(#2, 2))), regexp_split_to_array[" ", case_insensitive=false](btrim(array_index(#2, 3)))) // { arity: 6 }
          FlatMap unnest_array(regexp_split_to_array["\n", case_insensitive=false](#0{input})) // { arity: 2 }
            ReadStorage materialize.public.aoc_1204 // { arity: 1 }
    cte l1 =
      Distinct project=[#0, #1] // { arity: 2 }
        Project (#1, #2) // { arity: 2 }
          Get l0 // { arity: 3 }
    cte l2 =
      Filter (#2 != "") // { arity: 3 }
        FlatMap unnest_array(#0{wins}) // { arity: 3 }
          Get l1 // { arity: 2 }
    cte l3 =
      Reduce group_by=[#0, #1] aggregates=[count(*)] // { arity: 3 }
        Project (#0, #1) // { arity: 2 }
          Distinct project=[#0..=#2] // { arity: 3 }
            Union // { arity: 3 }
              Get l2 // { arity: 3 }
              Negate // { arity: 3 }
                Threshold // { arity: 3 }
                  Union // { arity: 3 }
                    Get l2 // { arity: 3 }
                    Negate // { arity: 3 }
                      Filter (#2 != "") // { arity: 3 }
                        FlatMap unnest_array(#1{have}) // { arity: 3 }
                          Get l1 // { arity: 2 }
    cte l4 =
      Union // { arity: 3 }
        Get l3 // { arity: 3 }
        Map (0) // { arity: 3 }
          Union // { arity: 2 }
            Negate // { arity: 2 }
              Project (#0, #1) // { arity: 2 }
                Get l3 // { arity: 3 }
            Get l1 // { arity: 2 }
    cte l5 =
      Project (#0, #5{count}) // { arity: 2 }
        Join on=(#1 = #3 AND #2 = #4) type=differential // { arity: 6 }
          implementation
            %1[#0, #1]UKK » %0:l0[#1, #2]KK
          ArrangeBy keys=[[#1, #2]] // { arity: 3 }
            Get l0 // { arity: 3 }
          ArrangeBy keys=[[#0, #1]] // { arity: 3 }
            Union // { arity: 3 }
              Get l4 // { arity: 3 }
              Map (null) // { arity: 3 }
                Union // { arity: 2 }
                  Negate // { arity: 2 }
                    Project (#0, #1) // { arity: 2 }
                      Get l4 // { arity: 3 }
                  Get l1 // { arity: 2 }
    cte l6 =
      Reduce aggregates=[sum(power(2, bigint_to_double((#0{count} - 1))))] // { arity: 1 }
        Project (#1{count}) // { arity: 1 }
          Filter (#1{count} > 0) // { arity: 2 }
            Get l5 // { arity: 2 }
  Return // { arity: 2 }
    With Mutually Recursive
      cte l7 =
        Union // { arity: 2 }
          Get l5 // { arity: 2 }
          Project (#2, #3{count}) // { arity: 2 }
            Filter (integer_to_bigint(#2{card}) = (integer_to_bigint(#0{card}) + #4{step})) // { arity: 5 }
              FlatMap generate_series(1, #1{score}, 1) // { arity: 5 }
                CrossJoin type=differential // { arity: 4 }
                  implementation
                    %0:l7[×] » %1:l5[×]
                  ArrangeBy keys=[[]] // { arity: 2 }
                    Get l7 // { arity: 2 }
                  ArrangeBy keys=[[]] // { arity: 2 }
                    Get l5 // { arity: 2 }
    Return // { arity: 2 }
      With
        cte l8 =
          Reduce aggregates=[count(*)] // { arity: 1 }
            Project () // { arity: 0 }
              Get l7 // { arity: 2 }
      Return // { arity: 2 }
        CrossJoin type=differential // { arity: 2 }
          implementation
            %0[×]U » %1[×]U
          ArrangeBy keys=[[]] // { arity: 1 }
            Project (#1) // { arity: 1 }
              Map (double_to_numeric(#0{sum})) // { arity: 2 }
                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 l8 // { arity: 1 }
              Map (0) // { arity: 1 }
                Union // { arity: 0 }
                  Negate // { arity: 0 }
                    Project () // { arity: 0 }
                      Get l8 // { arity: 1 }
                  Constant // { arity: 0 }
                    - ()

Source materialize.public.aoc_1204

Target cluster: quickstart

EOF