Materialize and Advent of Code: Using SQL to solve your puzzles!

Frank McSherry

January 19, 2024

This past year Team Materialize struck out to do each day of 2023's Advent of Code, an annual programming event with thought-provoking problems that you are encouraged to approach from non-standard directions. We figured we'd try and use SQL for the whole thing.

SQL is a bold choice because it is meant for querying data, and not as much for general computation. Several of the problems call for interesting algorithms, specific data structures, and some flexibility. However, Materialize's core thesis is that you can do so much more with SQL that just query your data. If you want to move operational logic from bespoke code into SQL, you'll need to be able to express that logic. And so, Advent of Code was a great opportunity to stretch our legs, and fingers, and see just how much logic fits into SQL.

Preliminaries

There's a lot of content in the month's problems. There are 49 problems, and although there is some overlap really there is too much to say about all of them. We aren't going to recount each of the problems, the whimsical backstories, and the shape of the problem inputs. We'll try and flag some surprising moments, though, and you should dive into those problems if you are keen (they can each be done on their own).

I (Frank) wrote all of my solutions using Materialize's WITH MUTUALLY RECURSIVE even when recursion was not required. This just helped me start writing, as the blocks allow you to just start naming subqueries and writing SQL.

My solutions all had the same skeletal structure:

WITH MUTUALLY RECURSIVE 

 
   -- Parse the problem input into tabular form. 
   lines(line TEXT) AS ( .. ), 

 
   -- SQL leading up to part 1. 
   part1(part1 BIGINT) AS ( .. ), 

 
   -- SQL leading up to part 2. 
   part2(part2 BIGINT) AS ( .. )  

 
SELECT * FROM part1, part2; 

 
 sql

As mentioned, we won't always need recursion. However, we often do use recursion, and may even need it. We'll call this out, as the use (and ease) of recursion in SQL was one of the main unlocks.

Week one

Day one was largely about text manipulation, specifically extracting numbers from text, and was well-addressed by using regular expressions to manipulate and search the text.

See the solution

Link to puzzle(s) 🟢 🟢

Part one

The newly-improved calibration document consists of lines of text; each line originally contained a specific calibration value that the Elves now need to recover. On each line, the calibration value can be found by combining the first digit and the last digit (in that order) to form a single two-digit number.
Consider your entire calibration document. What is the sum of all of the calibration values?

SELECT SUM(LEFT(r, 1)::int * 10 + RIGHT(r, 1)::int) AS part1 
FROM ( 
SELECT regexp_replace(input, '[^\d]', '', 'g') AS r 
FROM aoc_1201 
); 

 
 sql

Part two

Your calculation isn't quite right. It looks like some of the digits are actually spelled out with letters: one, two, three, four, five, six, seven, eight, and nine also count as valid "digits".
Equipped with this new information, you now need to find the real first and last digit on each line.

WITH 
   lines AS ( 
       SELECT regexp_split_to_table(input, '\n') AS line 
       FROM aoc_1201 
   ), 
   slices AS ( 
       SELECT line, index, substring(line, index, width) AS slice 
       FROM 
           lines, 
           generate_series(1, length(line)) AS index, 
           generate_series(1, 5) AS width 
   ), 
   numbers (t, n) AS ( 
       VALUES ('0', 0), ('1', 1), ('2', 2), ('3', 3), ('4', 4), ('5', 5), ('6', 6), ('7', 7), ('8', 8), ('9', 9), 
              ('zero', 0), ('one', 1), ('two', 2), ('three', 3), ('four', 4), ('five', 5), ('six', 6), ('seven', 7), ('eight', 8), ('nine', 9) 
   ), 
   findings AS ( 
       SELECT line, index, n AS number 
       FROM slices, numbers 
       WHERE slices.slice = numbers.t 
   ), 
   first AS ( SELECT DISTINCT ON (line) line, number AS f FROM findings ORDER BY line, index ), 
   last AS ( SELECT DISTINCT ON (line) line, number AS l FROM findings ORDER BY line, index DESC ) 
SELECT SUM(f * 10 + l) 
FROM first, last 
WHERE first.line = last.line 

 
 sql

Contributors

Day 1 was brought to you by: @chass, @def-, @doy-materialize, @frankmcsherry, @josharenberg, @morsapaes, @nrainer-materialize

Day two was largely about aggregation: rolling up counts and maxima for games involving numbers of colored cubes; SQL did great here.

See the solution

Link to puzzle(s) 🟢 🟢

Part one

Given a table with the following format:

game_id   | set_id | green_cnt | red_cnt | blue_cnt 
----------+--------+-----------+---------+---------- 
Game 4   | set_2  |        12 |       0 |        0 
... 

 sql

WITH game_cnt AS ( 
SELECT split_part(game_id,' ', 2)::int AS game_id, 
      COUNT(set_id) AS total_set_cnt, 
      COUNT(set_id) FILTER (WHERE (green_cnt <= 13) AND (red_cnt <= 12) AND (blue_cnt <= 14)) AS possible_set_cnt 
FROM aoc_1202 
GROUP BY game_id 
) 
SELECT SUM(game_id) FROM game_cnt WHERE total_set_cnt = possible_set_cnt; 

 
 sql

Part two

WITH game_min AS ( 
SELECT split_part(game_id,' ', 2)::int AS game_id, 
      MAX(green_cnt) AS green_min, 
      MAX(red_cnt) AS red_min, 
      MAX(blue_cnt) AS blue_min 
FROM aoc_1202 
GROUP BY split_part(game_id,' ', 2)::int 
) 
SELECT SUM(green_min*red_min*blue_min) FROM game_min; 

 
 sql

Part one + two in one go!

-- Pre-supposes a view `input(input TEXT)` containing the string from AOC 
with mutually recursive 
   -- Parse the input up 
   lines(line TEXT) as (select regexp_split_to_table(input, '\n') as line from input), 
   games(game TEXT, report TEXT) as (select regexp_split_to_array(line, ':')[1], regexp_split_to_array(line, ':')[2] from lines), 
   round(game TEXT, visible TEXT) as (select game, regexp_split_to_table(report, ';') from games), 
   bacon(game TEXT, color TEXT) as (select game, regexp_split_to_table(visible, ',') from round), 
   parsed(game INT, color TEXT, number INT) as ( 
       select 
           substring(game, 5)::INT as game, 
           regexp_split_to_array(color, ' ')[3] as color, 
           regexp_split_to_array(color, ' ')[2]::INT as number 
       from bacon 
   ), 
   -- PART 1 
   limits(color TEXT, number INT) as (SELECT * FROM (VALUES ('red', 12), ('green', 13), ('blue', 14))), 
   bad_news(game INT) as ( 
       select game 
       from parsed, limits 
       where parsed.color = limits.color 
         AND parsed.number > limits.number 
   ), 
   plausible(game INT) as (select distinct parsed.game from parsed left join bad_news on(parsed.game = bad_news.game) where bad_news.game IS NULL), 
   part1(part1 BIGINT) as (select SUM(game) from plausible), 
   -- PART 2 
   maximum(game INT, color TEXT, number INT) as (select game, color, max(number) from parsed GROUP BY game, color), 
   red(game INT) as (select game from maximum, generate_series(1, number) where color = 'red'), 
   blue(game INT) as (select game from maximum, generate_series(1, number) where color = 'blue'), 
   green(game INT) as (select game from maximum, generate_series(1, number) where color = 'green'), 
   power(game INT, product BIGINT) as (SELECT red.game, count(*) from red, blue, green where red.game = blue.game and blue.game = green.game GROUP BY red.game), 
   part2(part2 BIGINT) as (select sum(product)::BIGINT from power) 
select * from part1, part2; 

 
 sql

Contributors

Day 2 was brought to you by: @def-, @frankmcsherry, @morsapaes

Day three has inputs in grid form, where there can be interaction between multiple lines (with symbols above or below others). You are looking for runs of numerals, and I used WMR to track these down; reportedly you can also use regular expressions, but I was not clever enough for that!

See the solution

Link to puzzle(s) 🟢 🟢

Part one + two in one go!

-- Pre-supposes a view `input(input TEXT)` containing the string from AOC 
   WITH MUTUALLY RECURSIVE 
       -- PART 0 
       -- Parse the input as lines of text with line numbers. 
       lines(line TEXT, row_idx INT) AS ( 
           SELECT 
              regexp_split_to_array(input, '\n')[row_idx], 
              row_idx 
            FROM 
               input, 
               generate_series(1, (SELECT COUNT(*)::INT FROM (SELECT regexp_split_to_table(input, '\n') FROM input))) as row_idx 
       ), 
       chars(symbol TEXT, row_idx INT, col_idx INT) AS ( 
           SELECT 
               substring(line, start, 1), 
               row_idx, 
               start 
           FROM 
               lines, 
               generate_series(1, length(line)) as start 
           WHERE 
               substring(line, start, 1) != '.' 
       ), 
       numerals(number TEXT, row_idx INT, col_idx INT) AS ( 
           SELECT symbol, row_idx, col_idx 
           FROM chars 
           WHERE symbol IN ( VALUES ('0'), ('1'), ('2'), ('3'), ('4'), ('5'), ('6'), ('7'), ('8'), ('9') ) 
       ), 
       symbols(symbol TEXT, row_idx INT, col_idx INT) AS ( 
           SELECT symbol, row_idx, col_idx 
           FROM chars 
           WHERE symbol NOT IN ( VALUES ('0'), ('1'), ('2'), ('3'), ('4'), ('5'), ('6'), ('7'), ('8'), ('9') ) 
       ), 
       -- PART 1 
       -- Recursively build up ranges of numerals that are "active", in the sense of being adjacent to a symbol. 
       -- Each range has an accumulated number (as a string), a row index, a column index and length of the run. 
       active(number TEXT, row_idx INT, col_idx INT, length INT) AS ( 
           -- Base case: numerals adjacent to a symbol 
           SELECT numerals.*, 1 
           FROM 
               numerals, 
               symbols, 
               generate_series(-1, 1) row_off, 
               generate_series(-1, 1) col_off 
           WHERE numerals.row_idx = symbols.row_idx + row_off 
             AND numerals.col_idx = symbols.col_idx + col_off 
           UNION 
           -- Inductive case 1: Join to the left 
           SELECT numerals.number || active.number, numerals.row_idx, numerals.col_idx, active.length + 1 
           FROM numerals, active 
           WHERE numerals.row_idx = active.row_idx 
             AND numerals.col_idx = active.col_idx - 1 
           UNION 
           -- Inductive case 2: Join to the right 
           SELECT active.number || numerals.number, numerals.row_idx, active.col_idx, active.length + 1 
           FROM numerals, active 
           WHERE numerals.row_idx = active.row_idx 
             AND numerals.col_idx = active.col_idx + active.length 
       ), 
       parts(number INT, row_idx INT, col_idx INT, length INT) AS ( 
           SELECT active.number::INT, row_idx, col_idx, length 
           FROM active 
           WHERE (active.row_idx, active.col_idx-1) NOT IN (SELECT row_idx, col_idx FROM numerals) 
             AND (active.row_idx, active.col_idx+length) NOT IN (SELECT row_idx, col_idx FROM numerals) 
       ), 
       part1(part1 BIGINT) AS ( SELECT SUM(parts.number::INT) FROM parts ), 
       -- PART 2 
       -- A "gear" is a `*` adjacent to exactly two part numbers. We want the sum over gears of their product. 
       -- A gear is identified by a location, which we will want to attempt to join with part numbers. 
       gear_adjacent(row_idx INT, col_idx INT, number INT, part_row INT, part_col INT) AS ( 
           SELECT DISTINCT symbols.row_idx, symbols.col_idx, parts.number, parts.row_idx, parts.col_idx 
           FROM 
               symbols, 
               generate_series(-1, 1) gear_r_off, 
               generate_series(-1, 1) gear_c_off, 
               parts, 
               generate_series(parts.col_idx, parts.col_idx + parts.length - 1) part_col 
           WHERE symbols.symbol = '*' 
             AND symbols.row_idx + gear_r_off = parts.row_idx 
             AND symbols.col_idx + gear_c_off = part_col 
       ), 
       gears(row_idx INT, col_idx INT) AS ( 
           SELECT row_idx, col_idx 
           FROM gear_adjacent 
           GROUP BY row_idx, col_idx 
           HAVING COUNT(*) = 2 
       ), 
       gear_products(row_idx INT, col_idx INT, product INT) AS ( 
           SELECT DISTINCT gears.row_idx, gears.col_idx, p1.number * p2.number 
           FROM gears, gear_adjacent p1, gear_adjacent p2 
           WHERE gears.row_idx = p1.row_idx 
             AND gears.col_idx = p1.col_idx 
             AND gears.row_idx = p2.row_idx 
             AND gears.col_idx = p2.col_idx 
             AND (p1.part_row != p2.part_row OR p1.part_col != p2.part_col) 
       ), 
       part2(part2 BIGINT) AS ( SELECT SUM(product) FROM gear_products) 

 
   SELECT * FROM part1, part2; 

 
 sql

Contributors

Day 3 was brought to you by: @frankmcsherry, @morsapaes

Day four introduced scratch cards where each line of input has some winners and losers. This was easy SQL until part two, in which winners give you other scratch cards, which have winners that give you other scratch cards, which .. you can see the recursion. Despite being wordy and complicated, the SQL isn't so bad:

   -- PART 2 
   -- Each card provides a copy of the next `score` cards. 
   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) 

 
 sql

This would be tricky to do with non-recursive SQL, as the data itself tells us how to unfold the results. Hooray for recursion!

See the solution

Link to puzzle(s) 🟢 🟢

Part one

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; 

 
 sql

Part two

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; 

 
 sql

Part one + two in one go!

-- Pre-supposes a view `input(input TEXT)` containing the string FROM AOC 
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; 

 
 sql

Contributors

Day 4 was brought to you by: @chass, @doy-materialize, @frankmcsherry, @morsapaes

Day five was a bit of a bear. It was the same day we were doing a Materialize on-site and we were all a bit distracted, but also it was pretty beefy. You first have to "route" various elements through a sequence of remappings, whose length is defined in the data. You then have to expand that out to routing whole intervals (rather than elements), and .. there is just lots of potential for error. I used recursive SQL to handle all the remapping, but other folks just expanded out their SQL for each of the (ten-ish) remappings.

See the solution

Link to puzzle(s) 🟢 🟢

Part one

WITH seeds AS ( 
   SELECT 
       regexp_split_to_table( 
           regexp_split_to_array( 
               regexp_split_to_array(input, '\n')[1], 
               ': ' 
           )[2], 
           ' ' 
       )::bigint AS seed 
   FROM 
       input 
), 
seed_to_soil_lines AS ( 
   SELECT 
       regexp_split_to_array( 
           regexp_split_to_table( 
               regexp_match(input, 'seed-to-soil map:\n([0-9 \n]*?)\n\n')[1], 
               '\n' 
           ), 
           ' ' 
       )::bigint[] AS line 
   FROM 
       input 
), 
seed_to_soil AS ( 
   SELECT 
       line[1] AS dst_base, 
       line[2] AS src_base, 
       line[3] AS len 
   FROM 
       seed_to_soil_lines 
), 
soil_to_fertilizer_lines AS ( 
   SELECT 
       regexp_split_to_array( 
           regexp_split_to_table( 
               regexp_match(input, 'soil-to-fertilizer map:\n([0-9 \n]*?)\n\n')[1], 
               '\n' 
           ), 
           ' ' 
       )::bigint[] AS line 
   FROM 
       input 
), 
soil_to_fertilizer AS ( 
   SELECT 
       line[1] AS dst_base, 
       line[2] AS src_base, 
       line[3] AS len 
   FROM 
       soil_to_fertilizer_lines 
), 
fertilizer_to_water_lines AS ( 
   SELECT 
       regexp_split_to_array( 
           regexp_split_to_table( 
               regexp_match(input, 'fertilizer-to-water map:\n([0-9 \n]*?)\n\n')[1], 
               '\n' 
           ), 
           ' ' 
       )::bigint[] AS line 
   FROM 
       input 
), 
fertilizer_to_water AS ( 
   SELECT 
       line[1] AS dst_base, 
       line[2] AS src_base, 
       line[3] AS len 
   FROM 
       fertilizer_to_water_lines 
), 
water_to_light_lines AS ( 
   SELECT 
       regexp_split_to_array( 
           regexp_split_to_table( 
               regexp_match(input, 'water-to-light map:\n([0-9 \n]*?)\n\n')[1], 
               '\n' 
           ), 
           ' ' 
       )::bigint[] AS line 
   FROM 
       input 
), 
water_to_light AS ( 
   SELECT 
       line[1] AS dst_base, 
       line[2] AS src_base, 
       line[3] AS len 
   FROM 
       water_to_light_lines 
), 
light_to_temperature_lines AS ( 
   SELECT 
       regexp_split_to_array( 
           regexp_split_to_table( 
               regexp_match(input, 'light-to-temperature map:\n([0-9 \n]*?)\n\n')[1], 
               '\n' 
           ), 
           ' ' 
       )::bigint[] AS line 
   FROM 
       input 
), 
light_to_temperature AS ( 
   SELECT 
       line[1] AS dst_base, 
       line[2] AS src_base, 
       line[3] AS len 
   FROM 
       light_to_temperature_lines 
), 
temperature_to_humidity_lines AS ( 
   SELECT 
       regexp_split_to_array( 
           regexp_split_to_table( 
               regexp_match(input, 'temperature-to-humidity map:\n([0-9 \n]*?)\n\n')[1], 
               '\n' 
           ), 
           ' ' 
       )::bigint[] AS line 
   FROM 
       input 
), 
temperature_to_humidity AS ( 
   SELECT 
       line[1] AS dst_base, 
       line[2] AS src_base, 
       line[3] AS len 
   FROM 
       temperature_to_humidity_lines 
), 
humidity_to_location_lines AS ( 
   SELECT 
       regexp_split_to_array( 
           regexp_split_to_table( 
               regexp_match(input, 'humidity-to-location map:\n([0-9 \n]*)')[1], 
               '\n' 
           ), 
           ' ' 
       )::bigint[] AS line 
   FROM 
       input 
), 
humidity_to_location AS ( 
   SELECT 
       line[1] AS dst_base, 
       line[2] AS src_base, 
       line[3] AS len 
   FROM 
       humidity_to_location_lines 
), 
soil AS ( 
   SELECT 
       seed, 
       coalesce( 
           MAX( 
               CASE 
                   WHEN seed >= src_base AND seed < src_base + len 
                   THEN dst_base + (seed - src_base) 
                   ELSE null 
               END 
           ), 
           seed 
       ) AS soil 
   FROM 
       seeds, seed_to_soil 
   GROUP BY seed 
), 
fertilizer AS ( 
   SELECT 
       soil, 
       coalesce( 
           MAX( 
               CASE 
                   WHEN soil >= src_base AND soil < src_base + len 
                   THEN dst_base + (soil - src_base) 
                   ELSE null 
               END 
           ), 
           soil 
       ) AS fertilizer 
   FROM 
       soil, soil_to_fertilizer 
   GROUP BY soil 
), 
water AS ( 
   SELECT 
       fertilizer, 
       coalesce( 
           MAX( 
               CASE 
                   when fertilizer >= src_base AND fertilizer < src_base + len 
                   then dst_base + (fertilizer - src_base) 
                   else null 
               END 
           ), 
           fertilizer 
       ) AS water 
   FROM 
       fertilizer, fertilizer_to_water 
   GROUP BY fertilizer 
), 
light AS ( 
   SELECT 
       water, 
       coalesce( 
           MAX( 
               CASE 
                   WHEN water >= src_base AND water < src_base + len 
                   THEN dst_base + (water - src_base) 
                   ELSE null 
               END 
           ), 
           water 
       ) AS light 
   FROM 
       water, water_to_light 
   GROUP BY water 
), 
temperature AS ( 
   SELECT 
       light, 
       coalesce( 
           MAX( 
               CASE 
                   WHEN light >= src_base AND light < src_base + len 
                   THEN dst_base + (light - src_base) 
                   ELSE null 
               END 
           ), 
           light 
       ) AS temperature 
   FROM 
       light, light_to_temperature 
   GROUP BY light 
), 
humidity AS ( 
   SELECT 
       temperature, 
       coalesce( 
           MAX( 
               CASE 
                   WHEN temperature >= src_base AND temperature < src_base + len 
                   THEN dst_base + (temperature - src_base) 
                   ELSE null 
               END 
           ), 
           temperature 
       ) AS humidity 
   FROM 
       temperature, temperature_to_humidity 
   GROUP BY temperature 
), 
location AS ( 
   SELECT 
       humidity, 
       coalesce( 
           MAX( 
               CASE 
                   WHEN humidity >= src_base AND humidity < src_base + len 
                   THEN dst_base + (humidity - src_base) 
                   ELSE null 
               END 
           ), 
           humidity 
       ) AS location 
   FROM 
       humidity, humidity_to_location 
   GROUP BY humidity 
) 
SELECT 
   MIN(location) AS answer 
FROM 
   location; 

 
 sql

Part one + two in one go!

WITH MUTUALLY RECURSIVE 
   blocks(head TEXT, body TEXT) AS ( 
       SELECT 
           split_part(regexp_split_to_table(input, '\n\n'), ':', 1), 
           split_part(regexp_split_to_table(input, '\n\n'), ':', 2) 
       FROM 
           input 
   ), 
   seeds(seed BIGINT) AS ( 
       SELECT regexp_split_to_table(trim(body), ' ')::BIGINT 
       FROM blocks 
       WHERE head = 'seeds' 
   ), 
   entry0(src_name TEXT, dst_name TEXT, dst_idx TEXT, src_idx TEXT, len TEXT) AS ( 
       SELECT 
           split_part(split_part(head, ' ', 1), '-', 1), 
           split_part(split_part(head, ' ', 1), '-', 3), 
           split_part(regexp_split_to_table(body, '\n'), ' ', 1), 
           split_part(regexp_split_to_table(body, '\n'), ' ', 2), 
           split_part(regexp_split_to_table(body, '\n'), ' ', 3) 
       FROM 
           blocks 
       WHERE 
           head != 'seeds' 
   ), 
   entry(src_name TEXT, dst_name TEXT, src_idx BIGINT, dst_idx BIGINT, len BIGINT) AS ( 
       SELECT 
           src_name, 
           dst_name, 
           src_idx::BIGINT, 
           dst_idx::BIGINT, 
           len::BIGINT 
       FROM 
           entry0 
       WHERE 
           src_idx != '' 
   ), 

 
   -- PART 1 
   -- Our active inventory of .. "stuff" 
   active(name TEXT, idx BIGINT) AS ( 
       SELECT 'seed', seed FROM seeds 
       UNION ALL 
       SELECT 
           intent.dst_name, 
           COALESCE(intent.idx + (entry.dst_idx - entry.src_idx), idx) 
       FROM intent LEFT JOIN entry ON ( 
           intent.src_name = entry.src_name AND 
           intent.dst_name = entry.dst_name AND 
           intent.idx BETWEEN entry.src_idx AND entry.src_idx + len - 1) 
   ), 
   -- We would like to perform this mapping, but must find a range. 
   intent(src_name TEXT, dst_name TEXT, idx BIGINT) AS ( 
       SELECT DISTINCT entry.src_name, dst_name, idx 
       FROM active, entry 
       WHERE active.name = entry.src_name 
   ), 
   part1(part1 BIGINT) AS ( 
       SELECT MIN(idx) FROM active WHERE name = 'location' 
   ), 

 
   -- PART 2 
   -- Now we are doing *ranges* of seeds, rather than seed identifiers. 
   -- They are big ranges, so we'll need to be smarter! 
   seeds2(start_idx BIGINT, end_idx BIGINT) AS ( 
       SELECT 
           regexp_split_to_array(trim(body), ' ')[2*x-1]::BIGINT, 
           regexp_split_to_array(trim(body), ' ')[2*x-1]::BIGINT + regexp_split_to_array(trim(body), ' ')[2*x]::BIGINT 
       FROM 
           blocks, 
           generate_series(1, array_length(regexp_split_to_array(trim(body), ' '), 1)/2) x 
       WHERE head = 'seeds' 
   ), 
   active2(name TEXT, start_idx BIGINT, end_idx BIGINT) AS ( 
       SELECT 'seed', start_idx, end_idx 
       FROM seeds2 
       UNION 
       SELECT 
           dst_name, 
           clipped_start + (entry_dst - entry_start), 
           clipped_end   + (entry_dst - entry_start) 
       FROM intersection 
       UNION 
       SELECT 
           name, 
           start_idx, 
           end_idx 
       FROM hole 
   ), 
   -- We would like to perform this mapping, but must find a range. 
   intent2(src_name TEXT, dst_name TEXT, start_idx BIGINT, end_idx BIGINT) AS ( 
       SELECT DISTINCT entry.src_name, dst_name, start_idx, end_idx 
       FROM active2, entry 
       WHERE active2.name = entry.src_name 
   ), 
   -- Each mapping has a potential intersection with a requested range. 
   intersection(src_name TEXT, dst_name TEXT, start_idx BIGINT, end_idx BIGINT, entry_start BIGINT, entry_end BIGINT, clipped_start BIGINT, clipped_end BIGINT, entry_dst BIGINT) AS ( 
       SELECT 
           intent2.src_name, 
           intent2.dst_name, 
           intent2.start_idx, 
           intent2.end_idx, 
           entry.src_idx, 
           entry.src_idx + entry.len, 
           GREATEST(start_idx, entry.src_idx), 
           LEAST(end_idx, entry.src_idx + entry.len), 
           entry.dst_idx 
       FROM intent2, entry 
       WHERE intent2.src_name = entry.src_name 
         AND intent2.dst_name = entry.dst_name 
         AND GREATEST(intent2.start_idx, entry.src_idx) 
           < LEAST(intent2.end_idx, entry.src_idx + entry.len) 
   ), 
   -- We may have holes in our intervals. Each intersection's start and end is the end and 
   -- start, respectively, of some hole we may have that needs to remain the identity. 
   hole(name TEXT, start_idx BIGINT, end_idx BIGINT) AS ( 
       SELECT * FROM ( 
           SELECT 
               dst_name, 
               clipped_end start_idx, 
               ( 
                   SELECT COALESCE(MIN(i2.clipped_start), i1.end_idx) 
                   FROM intersection i2 
                   WHERE i2.clipped_start >= i1.clipped_end 
                   AND i2.clipped_start < i1.end_idx 
                   AND i1.src_name = i2.src_name 
                   AND i1.dst_name = i2.dst_name 
                   AND i1.start_idx = i2.start_idx 
                   AND i1.end_idx = i2.end_idx 
               ) end_idx 
           FROM intersection i1 
           UNION 
           SELECT DISTINCT 
               dst_name, 
               start_idx, 
               ( 
                   SELECT COALESCE(MIN(i2.clipped_start), i1.end_idx) 
                   FROM intersection i2 
                   WHERE i2.clipped_start >= i1.start_idx 
                   AND i2.clipped_start < i1.end_idx 
                   AND i1.src_name = i2.src_name 
                   AND i1.dst_name = i2.dst_name 
                   AND i1.start_idx = i2.start_idx 
                   AND i1.end_idx = i2.end_idx 
               ) 
           FROM intent2 i1 
       ) 
       WHERE start_idx < end_idx 
   ), 
   part2(part2 BIGINT) AS ( SELECT MIN(start_idx) FROM active2 WHERE name = 'location') 

 
SELECT * FROM part1, part2; 

 
 sql

Contributors

Day 5 was brought to you by: @doy-materialize, @frankmcsherry, @nrainer-materialize

Day six was about whether you knew (or were willing to learn about) the quadratic formula.

See the solution

Link to puzzle(s) 🟢 🟢

Part one

WITH options AS 
( 
SELECT 
  (floor((time - sqrt(time * time - 4 * record)) / 2) + 1)::int low, 
  (ceil((time + sqrt(time * time - 4 * record)) / 2) - 1)::int hi, 
FROM input 
) 
SELECT exp(sum(ln(hi - low + 1)))::int 
FROM options; 

 
 sql

Part one + two in one go!

WITH MUTUALLY RECURSIVE 

 
   ties(slower NUMERIC, faster NUMERIC) AS ( 
       SELECT 
           (time + sqrt(time * time - 4 * distance)) / 2 as slower, 
           (time - sqrt(time * time - 4 * distance)) / 2 as faster 
       FROM input 
   ), 
   options(choices NUMERIC) AS ( 
       SELECT 1 + FLOOR(slower)::NUMERIC - CEIL(faster)::NUMERIC FROM ties 
   ), 
   part12(part12 NUMERIC) AS ( 
       SELECT pow(10.0, SUM(log(choices))) FROM options 
   ) 

 
SELECT * FROM part12; 

 
 sql

Contributors

Day 6 was brought to you by: @doy-materialize, @frankmcsherry, @nrainer-materialize, @petrosagg

Day seven is about scoring poker hands, using some new rules for tie breaking. This was mostly SQL aggregation, as the numbers of each card in each hand largely determine the outcome, other than tie-breaking where I learned about the translate function.

See the solution

Link to puzzle(s) 🟢 🟢

Part one + two in one go!

   -- Hands of cards (e.g. 'AKJQT') and integer bids. 
   WITH MUTUALLY RECURSIVE 
       lines(line TEXT) AS ( SELECT regexp_split_to_table(input, '\n') FROM input ), 
       hands(hand TEXT, bid INT) as ( 
           SELECT regexp_split_to_array(line, ' ')[1], 
                  regexp_split_to_array(line, ' ')[2]::INT 
           FROM lines 
       ), 
       cards(hand TEXT, value TEXT, position INT) AS ( 
           SELECT hand, substring(hand, pos, 1), pos 
           FROM hands, generate_series(1, 5) pos 
       ), 

 
       -- Part1 
       counts(hand TEXT, value TEXT, count INT) AS ( 
           SELECT hand, value, COUNT(*) 
           FROM cards 
           GROUP BY hand, value 
       ), 
       ranked(hand TEXT, bid INT, rank INT, score TEXT) AS ( 
           SELECT 
               hand, 
               bid, 
               CASE WHEN hand IN (SELECT hand FROM counts WHERE count = 5) THEN 1 
                    WHEN hand IN (SELECT hand FROM counts WHERE count = 4) THEN 2 
                    WHEN hand IN (SELECT hand FROM counts WHERE count = 3) 
                     AND hand IN (SELECT hand FROM counts WHERE count = 2) THEN 3 
                    WHEN hand IN (SELECT hand FROM counts WHERE count = 3) THEN 4 
                    WHEN hand IN (SELECT hand FROM (SELECT hand FROM counts WHERE count = 2) GROUP BY hand HAVING COUNT(*) = 2) THEN 5 
                    WHEN hand IN (SELECT hand FROM counts WHERE count = 2) THEN 6 
                    ELSE 7 
               END, 
               translate(hand, 'AKQJT98765432', 'ABCDEFGHIJKLM') 
           FROM 
               hands 
       ), 
       part1(part1 INT) AS ( 
           SELECT SUM(r1.bid) 
           FROM ranked r1, ranked r2 
           WHERE r1.rank < r2.rank OR (r1.rank = r2.rank AND r1.score <= r2.score) 
       ), 

 
       -- Part2: J are now wild for determining rank, but last for score. 
       wild(hand TEXT, value TEXT, position INT) AS ( 
           SELECT * FROM cards 
           UNION 
           SELECT c1.hand, c2.value, c1.position 
           FROM cards c1, cards c2 
           WHERE c1.hand = c2.hand 
             AND c1.value = 'J' 
       ), 
       wild_hands(hand TEXT, new_hand TEXT) AS ( 
           SELECT DISTINCT w1.hand, w1.value || w2.value || w3.value || w4.value || w5.value 
           FROM (SELECT * FROM wild w1 WHERE position = 1) w1, 
                (SELECT * FROM wild w2 WHERE position = 2) w2, 
                (SELECT * FROM wild w3 WHERE position = 3) w3, 
                (SELECT * FROM wild w4 WHERE position = 4) w4, 
                (SELECT * FROM wild w5 WHERE position = 5) w5 
           WHERE w1.hand = w2.hand 
             AND w1.hand = w3.hand 
             AND w1.hand = w4.hand 
             AND w1.hand = w5.hand 
       ), 
       wild_cards(hand TEXT, value TEXT, position INT) AS ( 
           SELECT DISTINCT new_hand, substring(new_hand, pos, 1), pos 
           FROM wild_hands, generate_series(1, 5) pos 
       ), 
       wild_counts(hand TEXT, value TEXT, count INT) AS ( 
           SELECT hand, value, COUNT(*) 
           FROM wild_cards 
           GROUP BY hand, value 
       ), 
       wild_ranked(hand TEXT, new_hand TEXT, rank INT, score TEXT) AS ( 
           SELECT 
               hand, 
               new_hand, 
               CASE WHEN new_hand IN (SELECT hand FROM wild_counts WHERE count = 5) THEN 1 
                    WHEN new_hand IN (SELECT hand FROM wild_counts WHERE count = 4) THEN 2 
                    WHEN new_hand IN (SELECT hand FROM wild_counts WHERE count = 3) 
                     AND new_hand IN (SELECT hand FROM wild_counts WHERE count = 2) THEN 3 
                    WHEN new_hand IN (SELECT hand FROM wild_counts WHERE count = 3) THEN 4 
                    WHEN new_hand IN (SELECT hand FROM (SELECT hand FROM wild_counts WHERE count = 2) GROUP BY hand HAVING COUNT(*) = 2) THEN 5 
                    WHEN new_hand IN (SELECT hand FROM wild_counts WHERE count = 2) THEN 6 
                    ELSE 7 
               END, 
               translate(hand, 'AKQT98765432J', 'ABCDEFGHIJKLM') 
           FROM 
               wild_hands 
       ), 
       best_hands(hand TEXT, new_hand TEXT, rank INT, score TEXT) AS ( 
           SELECT DISTINCT ON (hand) hand, new_hand, rank, score 
           FROM wild_ranked 
           ORDER BY hand, rank, score 
       ), 
       wild_bids(hand TEXT, bid INT, rank INT, score TEXT) AS ( 
           SELECT hands.hand, hands.bid, rank, score 
           FROM hands, best_hands 
           WHERE hands.hand = best_hands.hand 
       ), 
       part2(part2 INT) AS ( 
           SELECT SUM(r1.bid) 
           FROM wild_bids r1, wild_bids r2 
           WHERE r1.rank < r2.rank OR (r1.rank = r2.rank AND r1.score <= r2.score) 
       ) 

 
   SELECT * FROM part1, part2; 

 
 sql

Contributors

Day 7 was brought to you by: @frankmcsherry, @nrainer-materialize

Week two

Day eight involved some graph navigation (recursion), and some mathematics. The mathematics were of the form "notice that various things are relatively prime", and it was important to rely on SQL as a tool to support reasoning, as opposed to directly attacking the specified computation. In this case, my problem called for 14,935,034,899,483 steps, and no tool is going to make direct simulation be the right answer.

See the solution

Link to puzzle(s) 🟢 🟢

Part one + two in one go!

   WITH MUTUALLY RECURSIVE 

 
       route(step TEXT, steps INT) AS ( 
           SELECT substring(input, steps, 1), steps 
           FROM steps_input, generate_series(1, length(input)) steps 
       ), 

 
       -- Part 1: Start at 'AAA` and go until `ZZZ`. 
       pos1(state TEXT, steps INT) AS ( 
           SELECT 'AAA', 0 
           UNION ALL 
           SELECT 
               CASE WHEN route.step = 'L' THEN paths.left 
                    WHEN route.step = 'R' THEN paths.right 
                    ELSE '???' 
               END, 
               pos1.steps + 1 
           FROM paths, pos1, route 
           WHERE pos1.state = paths.state 
             AND 1 + (pos1.steps % 263) = route.steps 
             AND pos1.state != 'ZZZ' 
             AND pos1.state != '???' 
       ) 
       part1(part1 INT) AS (SELECT steps FROM pos1 WHERE pos1.state = 'ZZZ'), 

 
       -- Part 2: Start at all '**A` and go until all at '**Z' 
       pos2(start TEXT, state TEXT, steps INT) AS ( 
           SELECT state, state, 0 
           FROM paths 
           WHERE substring(state, 3, 1) = 'A' 
           UNION ALL 
           SELECT 
               pos2.start, 
               CASE WHEN route.step = 'L' THEN paths.left 
                    WHEN route.step = 'R' THEN paths.right 
                    ELSE '???' 
               END, 
               pos2.steps + 1 
           FROM paths, pos2, route 
           WHERE pos2.state = paths.state 
             AND 1 + (pos2.steps % 263) = route.steps 
             AND substring(pos2.state, 3, 1) != 'Z' 
       ) 

 
   SELECT * FROM pos2 WHERE substring(state, 3, 1) = 'Z'; 

 
 sql

Contributors

Day 8 was brought to you by: @doy-materialize, @frankmcsherry, @nrainer-materialize

Day nine was a refreshing introduction to polynomials, and how if you take enough derivatives of them they end up at zero. The task was to do this, repeatedly difference adjacent measurements, or adjacent differences, etc., until you get all zeros. Then, integrate back up to get projections in the forward and reverse direction. I used recursion here to accommodate the unknown degree of the polynomial (somewhere in the twenties).

See the solution

Link to puzzle(s) 🟢 🟢

Part one + two in one go!

WITH MUTUALLY RECURSIVE (RETURN AT RECURSION LIMIT 30) 

 
       lines (line TEXT, line_no INT) AS ( 
           SELECT regexp_split_to_array(input, '\n')[i], i 
           FROM input, generate_series(1, array_length(regexp_split_to_array(input, '\n'), 1)) i 
       ), 

 
       numbers(value INT, line_no INT, col_no INT) AS ( 
           SELECT regexp_split_to_array(line, ' ')[j]::INT, line_no, j 
           FROM lines, generate_series(1, array_length(regexp_split_to_array(line, ' '), 1)) j 
       ), 

 
       -- Contains non-zero values of differences after each round. 
       derivatives(value INT, line_no INT, col_no INT, round INT) AS ( 
           SELECT numbers.*, 1 
           FROM numbers 
           UNION 
           SELECT 
               COALESCE(i2.value, 0) - COALESCE(i1.value, 0), 
               COALESCE(i1.line_no, i2.line_no), 
               COALESCE(i1.col_no + 1, i2.col_no), 
               COALESCE(i1.round, i2.round) + 1 
           FROM derivatives i1 FULL OUTER JOIN derivatives i2 ON (i1.line_no = i2.line_no AND i1.round = i2.round AND i1.col_no + 1 = i2.col_no) 
           WHERE COALESCE(i2.value, 0) - COALESCE(i1.value, 0) != 0 
             AND COALESCE(i1.col_no + 1, i2.col_no) > COALESCE(i1.round, i2.round) 
             AND COALESCE(i1.col_no + 1, i2.col_no) <= 21 
       ), 

 
       -- Accumulate the derivatives at the leading edge 
       part1(part1 BIGINT) AS ( 
           SELECT SUM(value) 
           FROM derivatives 
           WHERE col_no = 21 
       ), 

 
       -- Accumulate the derivatives at the preceding edge 
       part2(part2 BIGINT) AS ( 
           SELECT SUM(pow(-1, round + 1) * value) 
           FROM derivatives 
           WHERE col_no = round 
       ) 

 
   -- SELECT * FROM derivatives WHERE line_no = 1 ORDER BY round, col_no; 
   SELECT * FROM part1, part2; 

 
 sql

Contributors

Day 9 was brought to you by: @frankmcsherry, @nrainer-materialize

Day ten presents you with a grid of pipe (symbols |, -, J, 7, F, and L), and questions about how long a loop of pipe is, and then how many cells are contained within it. The first part involved recursion, and I used it again for a dynamic programming solution to the second part.

See the solution

Link to puzzle(s) 🟢 🟢

Part one + two in one go!

   WITH MUTUALLY RECURSIVE 

 
       lines(line TEXT, row_no INT) AS ( 
           SELECT regexp_split_to_array(input, '\n')[i], i 
           FROM input, generate_series(1, array_length(regexp_split_to_array(input, '\n'), 1)) i 
       ), 

 
       symbols(symb TEXT, row_no INT, col_no INT) as ( 
           SELECT substring(line, j, 1), row_no, j 
           FROM lines, generate_series(1, length(line)) j 
       ), 

 
       -- Each location that is pipe has two neighbors 
       edge1(r1 INT, c1 INT, r2 INT, c2 INT) AS ( 
           SELECT 
               row_no, 
               col_no, 
               CASE WHEN symb = '-' THEN row_no 
                    WHEN symb = '|' THEN row_no - 1 
                    WHEN symb = 'F' THEN row_no + 1 
                    WHEN symb = 'L' THEN row_no - 1 
                    WHEN symb = 'J' THEN row_no 
                    WHEN symb = '7' THEN row_no 
                    ELSE NULL 
               END, 
               CASE WHEN symb = '-' THEN col_no - 1 
                    WHEN symb = '|' THEN col_no 
                    WHEN symb = 'F' THEN col_no 
                    WHEN symb = 'L' THEN col_no 
                    WHEN symb = 'J' THEN col_no - 1 
                    WHEN symb = '7' THEN col_no - 1 
                    ELSE NULL 
               END 
           FROM symbols 
           WHERE symb != '.' AND symb != 'S' 
       ), 
       edge2(r1 INT, c1 INT, r2 INT, c2 INT) AS ( 
           SELECT 
               row_no, 
               col_no, 
               CASE WHEN symb = '-' THEN row_no 
                    WHEN symb = '|' THEN row_no + 1 
                    WHEN symb = 'F' THEN row_no 
                    WHEN symb = 'L' THEN row_no 
                    WHEN symb = 'J' THEN row_no - 1 
                    WHEN symb = '7' THEN row_no + 1 
                    ELSE NULL 
               END, 
               CASE WHEN symb = '-' THEN col_no + 1 
                    WHEN symb = '|' THEN col_no 
                    WHEN symb = 'F' THEN col_no + 1 
                    WHEN symb = 'L' THEN col_no + 1 
                    WHEN symb = 'J' THEN col_no 
                    WHEN symb = '7' THEN col_no 
                    ELSE NULL 
               END 
           FROM symbols 
           WHERE symb != '.' AND symb != 'S' 
       ), 
       -- Symmetrized graph 
       symm(r1 INT, c1 INT, r2 INT, c2 INT) AS ( 
           SELECT r1, c1, r2, c2 
           FROM ( 
               SELECT * FROM edge1 
               UNION ALL 
               SELECT * FROM edge2 
               UNION ALL 
               SELECT r2, c2, r1, c1 FROM edge1 
               UNION ALL 
               SELECT r2, c2, r1, c1 FROM edge2 
               UNION ALL 
               SELECT row_no, col_no, row_no + 1, col_no FROM symbols WHERE symb = 'S' 
               UNION ALL 
               SELECT row_no, col_no, row_no, col_no + 1 FROM symbols WHERE symb = 'S' 
               UNION ALL 
               SELECT row_no, col_no, row_no - 1, col_no FROM symbols WHERE symb = 'S' 
               UNION ALL 
               SELECT row_no, col_no, row_no, col_no - 1 FROM symbols WHERE symb = 'S' 
           ) 
           GROUP BY r1, c1, r2, c2 
           HAVING COUNT(*) = 2 
       ), 
       reach(r INT, c INT) AS ( 
           SELECT row_no, col_no 
           FROM symbols 
           WHERE symb = 'S' 
           UNION 
           SELECT r2, c2 
           FROM reach, symm 
           WHERE r = r1 AND c = c1 
       ), 
       part1(part1 BIGINT) AS ( 
           SELECT COUNT(*)/2 FROM reach 
       ), 

 
       -- Part 2: how many cells are *inside* the loop? 
       -- All (1, *) and (*, 1) cells have their upper left outside the loop (outer edge of the diagram). 
       -- Each cell inherits from its UL neighbor, toggled by any pipe except '7' and 'L' pipe. 
       -- Rewrite the pipe to have symbols, and resolve 'S' to actual oriented pipe. 
       pipe(r INT, c INT, symb TEXT) AS ( 
           SELECT r, c, symb 
           FROM reach, symbols 
           WHERE r = row_no AND c = col_no AND symb != 'S' 
           UNION 
           SELECT 
               row_no, 
               col_no, 
               CASE WHEN row_no = s1.r1 AND col_no = s1.c1 + 1 AND row_no = s2.r2 + 1 AND col_no = s2.c2 THEN 'J' -- toggle 
                    WHEN row_no = s1.r1 AND col_no = s1.c1 + 1 AND row_no = s2.r2 AND col_no = s2.c2 - 1 THEN '-' -- toggle 
                    WHEN row_no = s1.r1 AND col_no = s1.c1 + 1 AND row_no = s2.r2 - 1 AND col_no = s2.c2 THEN '7' -- no toggle 
                    WHEN row_no = s1.r1 + 1 AND col_no = s1.c1 AND row_no = s2.r2 AND col_no = s2.c2 - 1 THEN 'L' -- no toggle 
                    WHEN row_no = s1.r1 + 1 AND col_no = s1.c1 AND row_no = s2.r2 - 1 AND col_no = s2.c2 THEN '|' -- toggle 
                    WHEN row_no = s1.r1 AND col_no = s1.c1 - 1 AND row_no = s2.r2 AND col_no = s2.c2 - 1 THEN 'F' -- toggle 
                    ELSE '???' 
               END 
           FROM symbols, symm s1, symm s2 
           WHERE symb = 'S' 
             AND row_no = s1.r1 
             AND col_no = s1.c1 
             AND row_no = s2.r1 
             AND col_no = s2.c1 
       ), 
       -- Enclosed(1,*) and Enclosed(*,1) are all false. 
       -- Enclosed(x+1,y+1) = Enclosed(x,y) perhaps toggled by pipe(x,y) 
       status(r INT, c INT, encl BOOL) AS ( 
           SELECT row_no, col_no, false 
           FROM symbols 
           WHERE row_no = 1 OR col_no = 1 
           UNION 
           SELECT 
               row_no + 1, 
               col_no + 1, 
               CASE WHEN pipe.symb IN (VALUES ('J'),('-'),('|'),('F')) THEN NOT encl 
                    ELSE encl 
               END 
           FROM status LEFT JOIN pipe ON (status.r = pipe.r AND status.c = pipe.c) 
           JOIN symbols ON (status.r = symbols.row_no AND status.c = symbols.col_no) 
       ), 
       part2(part2 BIGINT) AS ( 
           SELECT COUNT(*) 
           FROM status 
           WHERE encl = true AND (r, c) NOT IN (SELECT r, c FROM pipe) 
       ) 

 
   SELECT * FROM part1, part2; 

 
 sql

Contributors

Day 10 was brought to you by: @frankmcsherry

Day eleven presents a grid of "galaxies" and has you calculate the distance between pairs (the L1 or "Manhattan" distance, always the sum of absolute values of coordinate differences). Parts one and two were the same, but with different magnitudes of numbers. No recursion here!

See the solution

Link to puzzle(s) 🟢 🟢

Part one + two in one go!

   WITH MUTUALLY RECURSIVE 

 
       lines(line TEXT, r INT) AS ( 
           SELECT regexp_split_to_array(input, '\n')[i], i 
           FROM input, generate_series(1, array_length(regexp_split_to_array(input, '\n'), 1)) i 
       ), 

 
       symbols(symb TEXT, r INT, c INT) as ( 
           SELECT substring(line, j, 1), r, j 
           FROM lines, generate_series(1, length(line)) j 
       ), 

 
       row_gaps(r INT) AS ( 
           SELECT r 
           FROM symbols 
           GROUP BY r 
           HAVING COUNT(*) FILTER (WHERE symb = '#') = 0 
       ), 

 
       col_gaps(c INT) AS ( 
           SELECT c 
           FROM symbols 
           GROUP BY c 
           HAVING COUNT(*) FILTER (WHERE symb = '#') = 0 
       ), 

 
       -- Part1: Expand space and restrict to galaxies 
       galaxies(r INT, c INT) AS ( 
           SELECT 
               r + (SELECT COUNT(*) FROM row_gaps WHERE row_gaps.r < symbols.r), 
               c + (SELECT COUNT(*) FROM col_gaps WHERE col_gaps.c < symbols.c) 
           FROM symbols 
           WHERE symb = '#' 
       ), 
       -- Sum of L1 distance between distinct galaxies 
       part1(part1 BIGINT) AS ( 
           SELECT SUM(ABS(g1.r - g2.r) + ABS(g1.c - g2.c)) 
           FROM galaxies g1, galaxies g2 
           WHERE g1.r < g2.r 
              OR (g1.r = g2.r AND g1.c < g2.c) 
       ) 

 
       -- Part2: Expand space MORE and restrict to galaxies 
       galaxies2(r INT, c INT) AS ( 
           SELECT 
               r + 999999 * (SELECT COUNT(*) FROM row_gaps WHERE row_gaps.r < symbols.r), 
               c + 999999 * (SELECT COUNT(*) FROM col_gaps WHERE col_gaps.c < symbols.c) 
           FROM symbols 
           WHERE symb = '#' 
       ), 
       -- Sum of L1 distance between distinct galaxies 
       part2(part2 BIGINT) AS ( 
           SELECT SUM(ABS(g1.r - g2.r) + ABS(g1.c - g2.c)) 
           FROM galaxies2 g1, galaxies2 g2 
           WHERE g1.r < g2.r 
              OR (g1.r = g2.r AND g1.c < g2.c) 
       ) 

 
   SELECT * FROM part1, part2; 

 
 sql

Contributors

Day 11 was brought to you by: @frankmcsherry, @nrainer-materialize

Day twelve was about sequence alignment, matching partial observations with hard constraints. Dynamic programming was a great solution here, using recursion.

See the solution

Link to puzzle(s) 🟢 🟢

Part one

WITH MUTUALLY RECURSIVE 

 
   lines(r INT, characters TEXT, springs TEXT) AS ( 
       SELECT 
           row_id, 
           regexp_split_to_array(regexp_split_to_array(input, '\n')[row_id], ' ')[1] || '.', 
           regexp_split_to_array(regexp_split_to_array(input, '\n')[row_id], ' ')[2] 
       FROM 
           input, 
           generate_series(1, array_length(regexp_split_to_array(input, '\n'), 1)) row_id 
   ), 
   characters(r INT, pos INT, symb TEXT) AS ( 
       SELECT 
           r, 
           pos, 
           substring(characters, pos, 1) 
       FROM 
           lines, 
           generate_series(1, length(characters)) pos 
   ), 
   springs(r INT, pos INT, len INT) AS ( 
       SELECT 
           r, 
           pos, 
           regexp_split_to_array(springs, ',')[pos]::INT 
       FROM 
           lines, 
           generate_series(1, array_length(regexp_split_to_array(springs, ','), 1)) pos 
   ), 

 
   -- How many ways can we pack row `r`'s first `spring` springs (plus a space) into the first `chars` characters? 
   -- Importantly, the "plus a space" applies to the last spring also! Each of these should admit the immediate appending of a new spring. 
   fits(r INT, chars INT, spring INT) AS ( 
       -- We can pack no springs into no characters. 
       SELECT r, 0, 0 
       FROM lines 
       -- We can extend any fits with a blank, as long as there are no '#' observations. 
       UNION ALL 
       SELECT fits.r, fits.chars + 1, fits.spring 
       FROM fits, characters 
       WHERE fits.r = characters.r 
         AND fits.chars + 1 = characters.pos 
         AND characters.symb != '#' 
       -- We can extend any fits with the next spring and a blank, as long as no '.' in the spring and no '#' in the blank. 
       UNION ALL 
       SELECT fits.r, fits.chars + springs.len + 1, fits.spring + 1 
       FROM 
           fits, 
           springs, 
           characters 
       WHERE fits.r = springs.r 
         AND fits.spring + 1 = springs.pos 
         AND fits.r = characters.r 
         AND fits.chars + springs.len + 1 = characters.pos 
         AND characters.symb != '#' 
         AND NOT EXISTS (SELECT FROM characters c WHERE c.r = fits.r AND c.symb = '.' AND c.pos BETWEEN fits.chars + 1 AND fits.chars + springs.len) 
   ), 

 
   fit_counts(r INT, chars INT, spring INT, count BIGINT) AS ( 
       SELECT r, chars, spring, COUNT(*) AS count 
       FROM fits 
       GROUP BY r, chars, spring 
   ), 
   counts(r INT, chars INT, spring INT, count BIGINT) AS ( 
       SELECT DISTINCT ON (r) r, chars, spring, count 
       FROM fit_counts 
       ORDER BY r, chars DESC, spring DESC 
   ), 

 
   potato (x INT) AS ( SELECT 1 ) 

 
SELECT SUM(count) FROM counts; 

 
 sql

Contributors

Day 12 was brought to you by: @frankmcsherry, @nrainer-materialize

Day thirteen had grids of observations with the hypothesis that each is mirrored, horizontally or vertically, at some point that you need to find. SQL and subqueries were a great way to validate hypothetical mirroring axes.

See the solution

Link to puzzle(s) 🟢 🟢

Part one + two in one go!

   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; 

 
 sql

Contributors

Day 13 was brought to you by: @frankmcsherry, @nrainer-materialize

Day fourteen was a treat, in that it used nested recursion: a WMR block within a WMR block. The problem was simulation of rocks that roll in cardinal directions, changing the direction ninety degrees, and repeating. Each simulation was recursive (rocks roll until they stop), and we were meant to repeat the larger progress a great many times (1,000,000,000 cycles). The only bummer here was the amount of copy/paste re-use, as each of the four cardinal directions had different subqueries.

See the solution

Link to puzzle(s) 🟢 🟢

Part 1

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 
       ), 

 
       northward(r INT, c INT, symbol TEXT) AS ( 
           SELECT * FROM northward 
           -- Anyone on the move does so 
           UNION  ALL SELECT r - 1, c, 'O' FROM north_move 
           EXCEPT ALL SELECT r - 1, c, '.' FROM north_move 
           UNION  ALL SELECT r, c, '.' FROM north_move 
           EXCEPT ALL SELECT r, c, 'O' FROM north_move 
           -- Initial state is cells, but not refreshed each round. 
           UNION  ALL SELECT * FROM cells 
           EXCEPT ALL SELECT * FROM cells_delay 
       ), 

 
       -- Each 'O' with a '.' to the north will move. 
       north_move(r INT, c INT) AS ( 
           SELECT n1.r, n1.c 
           FROM northward n1, northward n2 
           WHERE n1.symbol = 'O' 
             AND n1.r = n2.r + 1 
             AND n1.c = n2.c 
             AND n2.symbol = '.' 
       ), 

 
       part1(part1 BIGINT) AS ( 
           SELECT SUM(1 + (SELECT MAX(r) FROM lines) - r) 
           FROM northward 
           WHERE symbol = 'O' 
       ), 

 
       output (r INT, line TEXT) AS ( 
           SELECT r, string_agg(symbol, ' ' ORDER BY c) 
           FROM northward 
           GROUP BY r 
       ), 

 
       cells_delay(r INT, c INT, symbol TEXT) AS ( SELECT * FROM cells ) 

 
   SELECT * FROM part1; 

 
 sql

Part 2

   WITH MUTUALLY RECURSIVE (RETURN AT RECURSION LIMIT 142) 

 
       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 
       ), 

 
       -- Where should we start each iteration from? 
       -- From `east`, once it exits, but initially `cells`. 
       round(r INT, c INT, symbol TEXT) AS ( 
           SELECT * FROM east 
           UNION  ALL SELECT * FROM cells 
           EXCEPT ALL SELECT * FROM cells_delay 
       ), 

 
       north(r INT, c INT, symbol TEXT) AS ( 
           WITH MUTUALLY RECURSIVE 
               start(r INT, c INT, symbol TEXT) AS ( 
                   SELECT * FROM round 
               ), 
               northward(r INT, c INT, symbol TEXT) AS ( 
                   SELECT * FROM northward 
                   -- Anyone on the move does so 
                   UNION  ALL SELECT r - 1, c, 'O' FROM north_move 
                   EXCEPT ALL SELECT r - 1, c, '.' FROM north_move 
                   UNION  ALL SELECT r, c, '.' FROM north_move 
                   EXCEPT ALL SELECT r, c, 'O' FROM north_move 
                   -- Second time around, the above cancels and `east` is non-empty. 
                   UNION  ALL SELECT * FROM start 
                   EXCEPT ALL SELECT * FROM start_delay 
               ), 
               -- Each 'O' with a '.' in front of them will move. 
               north_move(r INT, c INT) AS ( 
                   SELECT n1.r, n1.c 
                   FROM northward n1, northward n2 
                   WHERE n1.symbol = 'O' 
                   AND n1.r = n2.r + 1 
                   AND n1.c = n2.c 
                   AND n2.symbol = '.' 
               ), 
               start_delay(r INT, c INT, symbol TEXT) AS ( SELECT * FROM start ) 

 
           SELECT * FROM northward 
       ), 

 
        west(r INT, c INT, symbol TEXT) AS ( 
           WITH MUTUALLY RECURSIVE 
               start(r INT, c INT, symbol TEXT) AS ( 
                   SELECT * FROM north 
               ), 
               westward(r INT, c INT, symbol TEXT) AS ( 
                   SELECT * FROM westward 
                   -- Anyone on the move does so 
                   UNION  ALL SELECT r, c - 1, 'O' FROM west_move 
                   EXCEPT ALL SELECT r, c - 1, '.' FROM west_move 
                   UNION  ALL SELECT r, c, '.' FROM west_move 
                   EXCEPT ALL SELECT r, c, 'O' FROM west_move 
                   -- Initial state is cells, but not refreshed each round. 
                   UNION  ALL SELECT * FROM start 
                   EXCEPT ALL SELECT * FROM start_delay 
               ), 
               -- Each 'O' with a '.' in front of them will move. 
               west_move(r INT, c INT) AS ( 
                   SELECT w1.r, w1.c 
                   FROM westward w1, westward w2 
                   WHERE w1.symbol = 'O' 
                   AND w1.r = w2.r 
                   AND w1.c = w2.c + 1 
                   AND w2.symbol = '.' 
               ), 
               start_delay(r INT, c INT, symbol TEXT) AS ( SELECT * FROM start ) 

 
           SELECT * FROM westward 
       ), 

 
       south(r INT, c INT, symbol TEXT) AS ( 
           WITH MUTUALLY RECURSIVE 
               start(r INT, c INT, symbol TEXT) AS ( 
                   SELECT * FROM west 
               ), 
               southward(r INT, c INT, symbol TEXT) AS ( 
                   SELECT * FROM southward 
                   -- Anyone on the move does so 
                   UNION  ALL SELECT r + 1, c, 'O' FROM south_move 
                   EXCEPT ALL SELECT r + 1, c, '.' FROM south_move 
                   UNION  ALL SELECT r, c, '.' FROM south_move 
                   EXCEPT ALL SELECT r, c, 'O' FROM south_move 
                   -- Initial state is cells, but not refreshed each round. 
                   UNION  ALL SELECT * FROM start 
                   EXCEPT ALL SELECT * FROM start_delay 
               ), 
               -- Each 'O' with a '.' in front of them will move. 
               south_move(r INT, c INT) AS ( 
                   SELECT s1.r, s1.c 
                   FROM southward s1, southward s2 
                   WHERE s1.symbol = 'O' 
                   AND s1.r = s2.r - 1 
                   AND s1.c = s2.c 
                   AND s2.symbol = '.' 
               ), 
               start_delay(r INT, c INT, symbol TEXT) AS ( SELECT * FROM start ) 
           SELECT * FROM southward 
       ), 

 
       east(r INT, c INT, symbol TEXT) AS ( 
           WITH MUTUALLY RECURSIVE 
               start(r INT, c INT, symbol TEXT) AS ( 
                   SELECT * FROM south 
               ), 
               eastward(r INT, c INT, symbol TEXT) AS ( 
                   SELECT * FROM eastward 
                   -- Anyone on the move does so 
                   UNION  ALL SELECT r, c + 1, 'O' FROM east_move 
                   EXCEPT ALL SELECT r, c + 1, '.' FROM east_move 
                   UNION  ALL SELECT r, c, '.' FROM east_move 
                   EXCEPT ALL SELECT r, c, 'O' FROM east_move 
                   -- Initial state is cells, but not refreshed each round. 
                   UNION  ALL SELECT * FROM start 
                   EXCEPT ALL SELECT * FROM start_delay 
               ), 
               -- Each 'O' with a '.' in front of them will move. 
               east_move(r INT, c INT) AS ( 
                   SELECT e1.r, e1.c 
                   FROM eastward e1, eastward e2 
                   WHERE e1.symbol = 'O' 
                   AND e1.r = e2.r 
                   AND e1.c = e2.c - 1 
                   AND e2.symbol = '.' 
               ), 
               start_delay(r INT, c INT, symbol TEXT) AS ( SELECT * FROM start ) 
           SELECT * FROM eastward 
       ), 

 
       output (r INT, line TEXT) AS ( 
           SELECT r, string_agg(symbol, ' ' ORDER BY c) 
           FROM round 
           GROUP BY r 
       ), 

 
       transitions(source TEXT, target TEXT) AS ( 
           SELECT 
               (SELECT string_agg(symbol, '' ORDER BY r, c) FROM round), 
               (SELECT string_agg(symbol, '' ORDER BY r, c) FROM east) 
           UNION ALL 
           SELECT * FROM transitions 
       ), 

 
       part2(part2 BIGINT) AS ( 
           SELECT SUM(1 + (SELECT MAX(r) FROM lines) - r) 
           FROM east 
           WHERE symbol = 'O' 
       ), 

 
       cells_delay(r INT, c INT, symbol TEXT) AS ( SELECT * FROM cells ) 

 
   -- SELECT count, COUNT(*) 
   -- FROM ( 
   --     SELECT source, target, COUNT(*) count 
   --     FROM transitions 
   --     GROUP BY source, target) 
   -- GROUP BY count; 

 
   -- SELECT * FROM output ORDER BY r; 

 
   SELECT * FROM part2; 

 
 sql

Contributors

Day 14 was brought to you by: @frankmcsherry

Week three

Day fifteen has you implement a hash function, and then a hash map. Recursion was a handy way to walk through the input to be hashed, though the hash function was simple enough that you could have used math directly instead. The second part (the hash map) did not require recursion, as rather than simulate the operations you could leap to the final state you were looking for.

See the solution

Link to puzzle(s) 🟢 🟢

Part one + two in one go!

WITH MUTUALLY RECURSIVE (RETURN AT RECURSION LIMIT 10) 

 
       strings(r INT, string TEXT) AS ( 
           SELECT r, regexp_split_to_array(input, ',')[r] 
           FROM input, generate_series(1, array_length(regexp_split_to_array(input, ','), 1)) r 
       ), 

 
       -- Advance the hash by one character, until all strings are empty. 
       hashes(string TEXT, hash BIGINT) AS ( 
           SELECT string, 0 as hash 
           FROM strings 
           UNION ALL 
           SELECT substring(string, 2), ((hash + ascii(substring(string, 1, 1))) * 17) % 256 
           FROM hashes 
           WHERE length(string) > 0 
       ), 

 
       part1(part1 BIGINT) AS ( 
           SELECT SUM(hash) 
           FROM hashes 
           WHERE string = '' 
       ), 

 
       -- Parse strings as symbol plus commands; either `-` or `=X`. 
       commands(r INT, symb TEXT, op INT) AS ( 
           SELECT 
               r, 
               CASE WHEN substring(string, length(string)) = '-' 
                    THEN substring(string, 1, length(string)-1) 
                    ELSE substring(string, 1, length(string)-2) 
               END, 
               CASE WHEN substring(string, length(string)) = '-' 
                    THEN 0 
                    ELSE substring(string, length(string))::INT 
               END 
           FROM strings 
       ), 
       -- Operations that happen after a symbol's last delete operation. 
       -- All other operations do not matter, and do not affect the state. 
       final_ops(r INT, symb TEXT, op INT) AS ( 
           SELECT * 
           FROM commands 
           WHERE r > COALESCE( 
               (SELECT MAX(r) 
               FROM commands c2 
               WHERE commands.symb = c2.symb 
                 AND c2.op = 0), 0) 
       ), 
       -- Each symbol is summarized by their first final insert time, and the last final operation 
       final_state(r INT, symb TEXT, op INT) AS ( 
           SELECT DISTINCT ON(symb) 
               (SELECT MIN(r) FROM final_ops fo2 WHERE fo2.symb = final_ops.symb), 
               symb, 
               op 
           FROM final_ops 
           ORDER BY symb, r DESC, op 
       ), 
       -- Redo the hash computation on symbols rather than commands. 
       hashes2(start TEXT, string TEXT, hash BIGINT) AS ( 
           SELECT symb as start, symb as string, 0 as hash 
           FROM final_state 
           UNION ALL 
           SELECT start, substring(string, 2), ((hash + ascii(substring(string, 1, 1))) * 17) % 256 
           FROM hashes2 
           WHERE length(string) > 0 
       ), 
       -- Bin up the state, so's we can tabulate it 
       binned(hash BIGINT, r INT, symb TEXT, op INT) AS ( 
           SELECT hash, final_state.* 
           FROM hashes2, final_state 
           WHERE hashes2.start = symb 
             AND hashes2.string = '' 
       ), 
       -- Sum the product of 1 + hash, the position in bin by r, and the op. 
       part2(part2 BIGINT) AS ( 
           SELECT SUM( 
               (1 + hash) * 
               (SELECT COUNT(*) FROM binned b2 WHERE binned.hash = b2.hash AND binned.r >= b2.r) * 
               op 
           ) 
           FROM binned 
       ), 

 
       potato(x int) as (select 1) 

 
   SELECT * FROM part1, part2; 

 
 sql

Contributors

Day 15 was brought to you by: @frankmcsherry, @nrainer-materialize

Day sixteen was about bouncing light around in a grid, and seeing how many grid cells are illuminated. The illumination process was classic recursive SQL, where you keep expanding (row, col, dir) triples until the set reaches a fixed point. In the second part the light sources had an origin, which is just a fourth column to add, tracking the source of each ray of light.

See the solution

Link to puzzle(s) 🟢 🟢

Part one + two in one go!

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; 

 
 sql

Contributors

Day 16 was brought to you by: @frankmcsherry

Day seventeen is a pathfinding problem, with constraints on how you move around the path (not too short or too long in any direction at once). Classic recursive SQL to implement Bellman-Ford.

See the solution

Link to puzzle(s) 🟢 🟢

Part one + two in one go!

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, cost INT) AS ( 
       SELECT r, c, substring(line, c, 1)::INT 
       FROM lines, generate_series(1, length(line)) c 
   ), 

 
   -- For each cell, we can be headed n, e, w, s and have gone 1, 2, 3 steps already. 
   -- There is a mimimum cost path to reach this configuration, and .. we might need 
   -- to remember how we got there but let's do that in part 2. 
   min_cost(r INT, c INT, dr INT, dc INT, steps INT, cost INT) AS ( 
       SELECT r, c, dr, dc, steps, MIN(cost) 
       FROM ( 
           SELECT 1 as r, 1 as c, 1 as dr, 0 as dc, 0 as steps, 0 as cost 
           UNION ALL 
           SELECT 1, 1, 0, 1, 0, 0 
           -- We could have just stepped to r, c in a few ways, incurring its cost. 
           UNION ALL 
           SELECT cells.r, cells.c, dr, dc, steps + 1, min_cost.cost + cells.cost 
           FROM min_cost, cells 
           WHERE steps < 3 
             AND cells.r = min_cost.r + dr 
             AND cells.c = min_cost.c + dc 
           -- We could take a ??? turn 
           UNION ALL 
           SELECT cells.r, cells.c, dc, dr, 1, min_cost.cost + cells.cost 
           FROM min_cost, cells 
           WHERE cells.r = min_cost.r + dc 
             AND cells.c = min_cost.c + dr 
           -- We could take a ??? turn 
           UNION ALL 
           SELECT cells.r, cells.c, -dc, -dr, 1, min_cost.cost + cells.cost 
           FROM min_cost, cells 
           WHERE cells.r = min_cost.r - dc 
             AND cells.c = min_cost.c - dr 
       ) 
       GROUP BY r, c, dr, dc, steps 
   ), 

 
   part1(part1 INT) AS ( 
       SELECT MIN(cost) 
       FROM min_cost 
       WHERE r = (SELECT MAX(r) FROM cells) 
         AND c = (SELECT MAX(c) FROM cells) 
   ), 

 
   potato(x INT) AS (SELECT 1), 

 
   -- For each cell, we can be headed n, e, w, s and have gone 1, 2, 3 steps already. 
   -- There is a mimimum cost path to reach this configuration, and .. we might need 
   -- to remember how we got there but let's do that in part 2. 
   min_cost2(r INT, c INT, dr INT, dc INT, steps INT, cost INT) AS ( 
       SELECT r, c, dr, dc, steps, MIN(cost) 
       FROM ( 
           SELECT 1 as r, 1 as c, 1 as dr, 0 as dc, 0 as steps, 0 as cost 
           UNION ALL 
           SELECT 1, 1, 0, 1, 0, 0 
           -- We could have just stepped to r, c in a few ways, incurring its cost. 
           UNION ALL 
           SELECT cells.r, cells.c, dr, dc, steps + 1, min_cost2.cost + cells.cost 
           FROM min_cost2, cells 
           WHERE steps < 10 
             AND cells.r = min_cost2.r + dr 
             AND cells.c = min_cost2.c + dc 
           -- We could take a XYZ turn 
           UNION ALL 
           SELECT cells.r, cells.c, dc, dr, 1, min_cost2.cost + cells.cost 
           FROM min_cost2, cells 
           WHERE steps >= 4 
             AND cells.r = min_cost2.r + dc 
             AND cells.c = min_cost2.c + dr 
           -- We could take a ZYX turn 
           UNION ALL 
           SELECT cells.r, cells.c, -dc, -dr, 1, min_cost2.cost + cells.cost 
           FROM min_cost2, cells 
           WHERE steps >= 4 
             AND cells.r = min_cost2.r - dc 
             AND cells.c = min_cost2.c - dr 
       ) 
       GROUP BY r, c, dr, dc, steps 
   ), 
   part2(part2 INT) AS ( 
       SELECT MIN(cost) 
       FROM min_cost2 
       WHERE r = (SELECT MAX(r) FROM cells) 
         AND c = (SELECT MAX(c) FROM cells) 
         AND steps >= 4 
   ), 

 
SELECT * FROM part1, part2; 

 
 sql

Contributors

Day 17 was brought to you by: @frankmcsherry

Day eighteen provides instructions of how a digger will move around, excavating earth, and asks you to calculate the area. This is an opportunity to learn about the Trapezoid formula for computing the area as the addition and subtraction of trapezoid areas.

See the solution

Link to puzzle(s) 🟢 🟢

Part one + two in one go!

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 
   ), 

 
   split1(r INT, dr INT, dc INT, steps INT) AS ( 
       SELECT 
           r, 
           CASE WHEN regexp_split_to_array(line, ' ')[1] = 'U' THEN -1 
                WHEN regexp_split_to_array(line, ' ')[1] = 'D' THEN  1 
                ELSE 0 
           END, 
           CASE WHEN regexp_split_to_array(line, ' ')[1] = 'L' THEN -1 
                WHEN regexp_split_to_array(line, ' ')[1] = 'R' THEN  1 
                ELSE 0 
           END, 
           regexp_split_to_array(line, ' ')[2]::INT 
       FROM lines 
   ), 

 
   -- Part 1 is prefix sum followed by area calculations. 
   -- We'll brute force the prefix sum part, and use the 
   -- "trapezoid formula", summing + and - contributions 
   -- as the path moves around. 
   path1(r1 INT, c1 INT, r2 INT, c2 INT, rounds INT) AS ( 
       SELECT 0, 0, 0, 0, 1 
       UNION 
       SELECT 
           path1.r2, 
           path1.c2, 
           path1.r2 + split1.dr * split1.steps, 
           path1.c2 + split1.dc * split1.steps, 
           path1.rounds + 1 
       FROM path1, split1 
       WHERE path1.rounds = split1.r 
   ), 
   -- The area carved by the path, plus half a unit of area 
   -- for each path step, plus 4 * (1/4) units for the net 
   -- four 90 degree turns. 
   part1(part1 BIGINT) AS ( 
       SELECT 
           ABS((SELECT SUM((r1 + r2) * (c1 - c2)) FROM path1)) / 2 
         + (SELECT SUM(steps) FROM split1) / 2 
         + 1 
   ), 

 
   -- Part 2 changes how we parse each line to give long paths. 
   split2(r INT, dr INT, dc INT, steps INT) AS ( 
       SELECT 
           r, 
           CASE WHEN substring(regexp_split_to_array(line, ' ')[3], 8, 1) = '3' THEN -1 
                WHEN substring(regexp_split_to_array(line, ' ')[3], 8, 1) = '1' THEN  1 
                ELSE 0 
           END, 
           CASE WHEN substring(regexp_split_to_array(line, ' ')[3], 8, 1) = '2' THEN -1 
                WHEN substring(regexp_split_to_array(line, ' ')[3], 8, 1) = '0' THEN  1 
                ELSE 0 
           END, 
           256 * 256 * get_byte(decode('0' || substring(regexp_split_to_array(line, ' ')[3], 3, 5), 'hex'), 0) 
               + 256 * get_byte(decode('0' || substring(regexp_split_to_array(line, ' ')[3], 3, 5), 'hex'), 1) 
                     + get_byte(decode('0' || substring(regexp_split_to_array(line, ' ')[3], 3, 5), 'hex'), 2) 
       FROM lines 
   ), 

 
   path2(r1 BIGINT, c1 BIGINT, r2 BIGINT, c2 BIGINT, rounds INT) AS ( 
       SELECT 0, 0, 0, 0, 1 
       UNION 
       SELECT 
           path2.r2, 
           path2.c2, 
           path2.r2 + split2.dr * split2.steps, 
           path2.c2 + split2.dc * split2.steps, 
           path2.rounds + 1 
       FROM path2, split2 
       WHERE path2.rounds = split2.r 
   ), 
   -- The area carved by the path, plus half a unit of area 
   -- for each path step, plus 4 * (1/4) units for the net 
   -- four 90 degree turns. 
   part2(part2 BIGINT) AS ( 
       SELECT 
           ABS((SELECT SUM((r1 + r2) * (c1 - c2)) FROM path2)) / 2 
         + (SELECT SUM(steps) FROM split2) / 2 
         + 1 
   ) 

 
SELECT * FROM part1, part2; 

 
 sql

Contributors

Day 18 was brought to you by: @frankmcsherry

Day nineteen sneakily introduces you to binary space partitioning, where rules based on inequality tests route you to new rules, until eventually you reach some rule that says "accept" or "reject". This was all pretty easy, except for a substantial amount of SQL overhead related to the various symbols and characters and coordinates all of which required their own columns.

See the solution

Link to puzzle(s) 🟢 🟢

Part one + two in one go!

WITH MUTUALLY RECURSIVE 

 
   blocks(block1 TEXT, block2 TEXT) AS ( 
       SELECT 
           regexp_split_to_array(input, '\n\n')[1] block1, 
           regexp_split_to_array(input, '\n\n')[2] block2 
       FROM input 
   ), 
   states(state TEXT, trans TEXT) AS ( 
       SELECT 
           regexp_split_to_array(line, '\{')[1] state, 
           trim('}' FROM regexp_split_to_array(line, '\{')[2]) trans 
       FROM (SELECT regexp_split_to_table(block1, '\n') line FROM blocks) 
   ), 
   steps(state TEXT, priority INT, rule TEXT) AS ( 
       SELECT 
           state, 
           priority, 
           regexp_split_to_array(trans, ',')[priority] 
       FROM states, generate_series(1, array_length(regexp_split_to_array(trans, ','), 1)) priority 
   ), 

 
   starts(x INT, m INT, a INT, s INT) AS ( 
       SELECT 
           substring(regexp_split_to_array(trimmed, ',')[1], 3)::INT, 
           substring(regexp_split_to_array(trimmed, ',')[2], 3)::INT, 
           substring(regexp_split_to_array(trimmed, ',')[3], 3)::INT, 
           substring(regexp_split_to_array(trimmed, ',')[4], 3)::INT 
       FROM (SELECT trim('\{' FROM trim('\}' FROM regexp_split_to_table(block2, '\n'))) trimmed FROM blocks) 
   ), 

 
   -- 
   rules(state TEXT, priority INT, field TEXT, cmp TEXT, val INT, next TEXT) AS ( 
       SELECT 
           state, 
           priority, 
           CASE WHEN substring(rule, 2, 1) = '<' OR substring(rule, 2, 1) = '>' 
               THEN substring(rule, 1, 1) 
               ELSE 'x' 
           END, 
           CASE WHEN substring(rule, 2, 1) = '<' OR substring(rule, 2, 1) = '>' 
               THEN substring(rule, 2, 1) 
               ELSE '>' 
           END, 
           CASE WHEN substring(rule, 2, 1) = '<' OR substring(rule, 2, 1) = '>' 
               THEN regexp_split_to_array(substring(rule, 3), ':')[1]::INT 
               ELSE '0' 
           END, 
           CASE WHEN substring(rule, 2, 1) = '<' OR substring(rule, 2, 1) = '>' 
               THEN regexp_split_to_array(substring(rule, 3), ':')[2] 
               ELSE rule 
           END 
       FROM steps 
   ), 

 
   -- PART 1: iterate folks forward from `in` 
   movement(state TEXT, x INT, m INT, a INT, s INT) AS ( 
       SELECT 'in' state, * FROM starts 
       UNION ALL 
       SELECT next, x, m, a, s 
       FROM ( 
           SELECT DISTINCT ON (state, x, m, a, s) state, x, m, a, s, priority, next 
           FROM ( 
               SELECT movement.*, rules.next, rules.priority 
               FROM movement, rules 
               WHERE movement.state = rules.state 
               AND CASE WHEN rules.cmp = '<' 
                        THEN CASE WHEN rules.field = 'x' THEN x < val 
                                  WHEN rules.field = 'm' THEN m < val 
                                  WHEN rules.field = 'a' THEN a < val 
                                  WHEN rules.field = 's' THEN s < val 
                                  ELSE false 
                             END 
                        WHEN rules.cmp = '>' 
                        THEN CASE WHEN rules.field = 'x' THEN x > val 
                                  WHEN rules.field = 'm' THEN m > val 
                                  WHEN rules.field = 'a' THEN a > val 
                                  WHEN rules.field = 's' THEN s > val 
                                  ELSE false 
                             END 
                        ELSE false 
                   END 
           ) 
           ORDER BY state, x, m, a, s, priority 
       ) 
   ), 

 
   part1(part1 BIGINT) AS ( 
       SELECT SUM(x + m + a + s) 
       FROM movement 
       WHERE state = 'A' 
   ), 

 
   -- PART 2: just find all the bounding regions and label them 'A' or 'R'. 
   region(state TEXT, priority INT, xl INT, xu INT, ml INT, mu INT, al INT, au INT, sl INT, su INT) AS ( 
       SELECT 'in', 1, 1, 4000, 1, 4000, 1, 4000, 1, 4000 
       -- Could satisfy the rule, and transition to the next state .. 
       UNION ALL 
       SELECT 
           next, 
           1, 
           CASE WHEN rules.field = 'x' AND rules.cmp = '>' THEN GREATEST(val+1, xl) ELSE xl END, 
           CASE WHEN rules.field = 'x' AND rules.cmp = '<' THEN LEAST(val-1, xu) ELSE xu END, 
           CASE WHEN rules.field = 'm' AND rules.cmp = '>' THEN GREATEST(val+1, ml) ELSE ml END, 
           CASE WHEN rules.field = 'm' AND rules.cmp = '<' THEN LEAST(val-1, mu) ELSE mu END, 
           CASE WHEN rules.field = 'a' AND rules.cmp = '>' THEN GREATEST(val+1, al) ELSE al END, 
           CASE WHEN rules.field = 'a' AND rules.cmp = '<' THEN LEAST(val-1, au) ELSE au END, 
           CASE WHEN rules.field = 's' AND rules.cmp = '>' THEN GREATEST(val+1, sl) ELSE sl END, 
           CASE WHEN rules.field = 's' AND rules.cmp = '<' THEN LEAST(val-1, su) ELSE su END 
       FROM region, rules 
       WHERE region.state = rules.state 
         AND region.priority = rules.priority 
       -- .. or could fail the rule, and advance to the next priority. 
       UNION ALL 
       SELECT 
           region.state, 
           region.priority + 1, 
           CASE WHEN rules.field = 'x' AND rules.cmp = '<' THEN GREATEST(val, xl) ELSE xl END, 
           CASE WHEN rules.field = 'x' AND rules.cmp = '>' THEN LEAST(val, xu) ELSE xu END, 
           CASE WHEN rules.field = 'm' AND rules.cmp = '<' THEN GREATEST(val, ml) ELSE ml END, 
           CASE WHEN rules.field = 'm' AND rules.cmp = '>' THEN LEAST(val, mu) ELSE mu END, 
           CASE WHEN rules.field = 'a' AND rules.cmp = '<' THEN GREATEST(val, al) ELSE al END, 
           CASE WHEN rules.field = 'a' AND rules.cmp = '>' THEN LEAST(val, au) ELSE au END, 
           CASE WHEN rules.field = 's' AND rules.cmp = '<' THEN GREATEST(val, sl) ELSE sl END, 
           CASE WHEN rules.field = 's' AND rules.cmp = '>' THEN LEAST(val, su) ELSE su END 
       FROM region, rules 
       WHERE region.state = rules.state 
         AND region.priority = rules.priority 
   ), 

 
   part2(part2 NUMERIC) AS ( 
       SELECT SUM((1 + xu - xl)::BIGINT * (1 + mu - ml)::BIGINT * (1 + au - al)::BIGINT * (1 + su - sl)::BIGINT) 
       FROM region 
       WHERE state = 'A' 
   ), 

 
   potato(x INT) AS (SELECT 1) 

 
SELECT * FROM part1, part2; 

 
 sql

Contributors

Day 19 was brought to you by: @frankmcsherry

Day twenty presents you with the simulation of an asynchronous circuit, and this is the day that almost broke me. Mechanically the SQL isn't that complicated, but debugging the SQL was a real challenge. It got done over the course of a quite long train ride into the evening.

See the solution

Link to puzzle(s) 🟢 🟢

Part one + two in one go!

WITH MUTUALLY RECURSIVE 

 
   lines(line TEXT) AS ( SELECT regexp_split_to_table(input, '\n') FROM input ), 
   links(name TEXT, link TEXT) AS ( 
       SELECT 
           substring(regexp_split_to_array(line, ' ')[1], 2), 
           trim(',' FROM regexp_split_to_array(line, ' ')[x]) 
       FROM 
           lines, generate_series(3, array_length(regexp_split_to_array(line, ' '), 1)) x 
   ), 
   -- One special line has op 'b' and name 'roadcaster'. 
   types(op TEXT, name TEXT) AS ( 
       SELECT 
           substring(regexp_split_to_array(line, ' ')[1], 1, 1), 
           substring(regexp_split_to_array(line, ' ')[1], 2) 
       FROM 
           lines 
   ), 

 
   -- Part one: simulate 1000 steps of 'broadcaster' being activated with a low pulse. 
   -- tally up total low and high pulses, and then multiply. 
   -- The state carried across steps are the last-transmitted pulses of each operator. 
   -- This should also tell us the final state of the `%` operators. 
   -- We'll also need the totals of low and high pulses, so that we can add them up. 

 
   seed(press INT, counter INT) AS ( 
       SELECT 1, 1 
       UNION 
       SELECT press, counter - 1 
       FROM seed 
       WHERE counter > 0 
       UNION 
       SELECT press + 1, 20 
       FROM seed 
       WHERE counter = 0 
         AND press < 4100 
   ), 

 
   -- Emitted pulses after various button presses, in various rounds of resolution. 
   pulses(name TEXT, press INT, round INT, pulse TEXT) AS ( 
       -- One thousand button presses, each followed by rounds of resolution. 
       SELECT 'roadcaster', press, 1, 'lo' FROM seed WHERE counter = 0 
       UNION ALL SELECT * FROM flip 
       UNION ALL SELECT * FROM conj 
   ), 

 
   -- Counters; every 'lo' input pulse flips and emits the state. 
   flip(name TEXT, press INT, round INT, pulse TEXT) AS ( 
       -- Each `signal` needs to behave as if all "prior" signals have been processed, ordered by (press, round, source). 
       SELECT  
           name,  
           press, 
           round + 1,  
           -- Look for the most recently emitted signal, and we'll produce the opposite of that one. 
           CASE WHEN ( 
                   SELECT COUNT(*) 
                   FROM signal s1  
                   WHERE s1.target = types.name  
                     AND s1.pulse = 'lo' 
                     AND ((s1.press < signal.press) OR  
                          (s1.press = signal.press AND s1.round < signal.round) OR  
                          (s1.press = signal.press AND s1.round = signal.round AND s1.source < signal.source)) 
               ) % 2 = 0 
               THEN 'hi' 
               ELSE 'lo' 
           END 
       FROM signal, types 
       WHERE signal.target = types.name 
           AND types.op = '%' 
           AND signal.pulse = 'lo' 
   ), 

 
   -- NAND gates; every input pulse evokes the NAND of most recent inputs. 
   conj(name TEXT, press INT, round INT, pulse TEXT) AS ( 
       SELECT 
           name, 
           press, 
           round + 1, 
           -- Look for the most recently received signals from each input, 
           -- including this one, and iff all 'hi' then 'lo'. 
           CASE WHEN ( 
                   (SELECT COUNT(*) FROM links WHERE link = types.name) 
                   = 
                   (SELECT COUNT(*) FROM ( 
                       SELECT DISTINCT ON (source) source, pulse 
                       FROM signal s1 
                       WHERE s1.target = types.name 
                         AND ((s1.press < signal.press) OR 
                              (s1.press = signal.press AND s1.round < signal.round) OR 
                              (s1.press = signal.press AND s1.round = signal.round AND s1.source <= signal.source)) 
                       OPTIONS (DISTINCT ON INPUT GROUP SIZE = 1000) 
                       ORDER BY source, press DESC, round DESC 
                   ) 
                   WHERE pulse = 'hi')) 
                THEN 'lo' 
                ELSE 'hi' 
           END 
       FROM signal, types 
       WHERE signal.target = types.name 
           AND types.op = '&' 
   ), 

 
   -- A record of a pulse into an operator, from another operator. 
   -- We track the source so that '&' operators can make any sense. 
   signal(source TEXT, target TEXT, press INT, round INT, pulse TEXT) AS ( 
       SELECT pulses.name, links.link, pulses.press, pulses.round, pulses.pulse 
       FROM pulses, links 
       WHERE pulses.name = links.name 
         AND pulses.round > 0 
   ), 

 
   part1(pulse TEXT, count BIGINT) AS ( 
       SELECT pulse, count(*) FROM signal GROUP BY pulse 
   ), 

 
   potato(x INT) AS (SELECT 1) 

 
SELECT * FROM signal WHERE target = 'cn' AND pulse = 'hi'; 

 
 sql

Contributors

Day 20 was brought to you by: @frankmcsherry

Day twenty-one was another example of some (recursive) SQL for grid exploration, followed by some mathematics. In this case the grid exploration was standard, determining reachable locations on the grid, and then the math was quadratic extrapolation from a sequence of measurements (to something too large to actually evaluate, an answer of 621,289,922,886,149 reachable states).

See the solution

Link to puzzle(s) 🟢 🟢

Part one + two in one go!

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 
   ), 

 
   steps(r INT, c INT) AS ( 
       SELECT r, c FROM cells WHERE symbol = 'S' 
       EXCEPT ALL 
       SELECT * FROM s_delay 
       UNION 
       SELECT cells.r, cells.c 
       FROM cells, ( 
                 SELECT r + 1, c FROM steps 
           UNION SELECT r - 1, c FROM steps 
           UNION SELECT r, c + 1 FROM steps 
           UNION SELECT r, c - 1 FROM steps 
       ) as potato(r,c) 
       WHERE cells.r = potato.r 
         AND cells.c = potato.c 
         AND cells.symbol != '#' 
   ), 

 
   s_delay(r INT, c INT) AS ( 
       SELECT r, c FROM cells WHERE symbol = 'S' 
   ), 

 
   part1(part1 BIGINT) AS ( 
       SELECT COUNT(*) FROM (SELECT DISTINCT * FROM steps) 
   ), 

 
   -- PART 2 wants a much larger step count on an infinite repeating grid. 
   -- We know it will be quadratic based on the clear paths if nothing else. 
   -- Map out enough points to reverse out polynomial coefficients. 
   -- For me they were `ax^2 + bx + c` with a = 60724, b = 30602, c =  3849. 

 
   dists(r INT, c INT, d INT) AS ( 
       SELECT r, c, MIN(d) 
       FROM ( 
           SELECT r, c, 0 d 
           FROM cells 
           WHERE symbol = 'S' 
           UNION ALL 
           SELECT potato.r, potato.c, d + 1 
           FROM cells, ( 
                     SELECT r + 1, c, d FROM dists 
               UNION SELECT r - 1, c, d FROM dists 
               UNION SELECT r, c + 1, d FROM dists 
               UNION SELECT r, c - 1, d FROM dists 
           ) as potato(r,c,d) 
           WHERE cells.r = 1 + (((potato.r - 1) % 131) + 131) % 131 
             AND cells.c = 1 + (((potato.c - 1) % 131) + 131) % 131 
             AND cells.symbol != '#' 
             AND potato.d < 1000 
       ) 
       GROUP BY r, c 
   ), 

 
   part2(x0 BIGINT, x2 BIGINT, x4 BIGINT, x6 BIGINT) AS ( 
       SELECT 
           (SELECT COUNT(*) FROM dists WHERE d <=  0 * 131 + 65 AND d % 2 = 1), 
           (SELECT COUNT(*) FROM dists WHERE d <=  2 * 131 + 65 AND d % 2 = 1), 
           (SELECT COUNT(*) FROM dists WHERE d <=  4 * 131 + 65 AND d % 2 = 1), 
           (SELECT COUNT(*) FROM dists WHERE d <=  6 * 131 + 65 AND d % 2 = 1) 
   ), 

 
   potato (x INT) AS ( SELECT 1 ) 

 
SELECT 'idk'; 

 
 sql

Contributors

Day 21 was brought to you by: @frankmcsherry

Week four

The last week was shorter, but also culminated in some pretty exciting problems and techniques.

Day twenty-two had shapes made of cubes falling into a well, and coming to rest on others (or the ground). There were then questions about how many pieces are load bearing, and also for each load bearing piece how many others would fall if they were removed. Dropping the pieces used recursive SQL, determining the load bearing pieces did not, but then scoring the load bearing pieces again required recursion.

See the solution

Link to puzzle(s) 🟢 🟢

Part one + two in one go!

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 
   ), 

 
   cells(r INT, x INT, y INT, z INT) AS ( 
       SELECT xs.r, x, y, z 
       FROM (SELECT r, generate_series(regexp_split_to_array(regexp_split_to_array(line, '~')[1], ',')[1]::INT, 
                                       regexp_split_to_array(regexp_split_to_array(line, '~')[2], ',')[1]::INT) x FROM lines) xs, 
            (SELECT r, generate_series(regexp_split_to_array(regexp_split_to_array(line, '~')[1], ',')[2]::INT, 
                                       regexp_split_to_array(regexp_split_to_array(line, '~')[2], ',')[2]::INT) y FROM lines) ys, 
            (SELECT r, generate_series(regexp_split_to_array(regexp_split_to_array(line, '~')[1], ',')[3]::INT, 
                                       regexp_split_to_array(regexp_split_to_array(line, '~')[2], ',')[3]::INT) z FROM lines) zs 
       WHERE xs.r = ys.r 
         AND xs.r = zs.r 
   ), 

 
   -- Part one: let the pieces fall, with a minimum z value of one. 
   parts(r INT, x INT, y INT, z INT) AS ( 
       SELECT * FROM cells 
       EXCEPT ALL SELECT * FROM cells_delayed 
       UNION ALL 
       SELECT r, x, y, CASE WHEN r IN (SELECT * FROM supported) THEN z ELSE z - 1 END 
       FROM parts 
   ), 
   -- One piece supports a *different* piece if it is directly below a piece of the other. 
   supports(r1 INT, r2 INT) AS ( 
       SELECT DISTINCT p1.r, p2.r 
       FROM parts p1, parts p2 
       WHERE p1.x = p2.x 
         AND p1.y = p2.y 
         AND p1.z + 1 = p2.z 
         AND p1.r != p2.r 
   ), 
   supported(r INT) AS ( 
       SELECT r FROM parts WHERE z = 1 
       UNION 
       SELECT r2 FROM supports 
   ), 
   -- A piece is safe to remove if it is does not uniquely support any other piece. 
   part1(part1 BIGINT) AS ( 
       SELECT COUNT(DISTINCT r) 
       FROM lines 
       WHERE r NOT IN ( 
           SELECT r1 
           FROM supports 
           WHERE r2 IN ( 
               SELECT r2 
               FROM supports 
               GROUP BY r2 
               HAVING COUNT(*) = 1 
           ) 
       ) 
   ), 

 
   cells_delayed(r INT, x INT, y INT, z INT) AS ( SELECT * FROM cells ), 

 
   -- Part two: for each piece, how many pieces would fall if you removed it? 
   -- Extend `supports` to transitive support: if r1 vanished would r2 fall? 
   supports_trans(r1 INT, r2 INT) AS ( 
       -- Uniquely supported pieces would certainly fall. 
       SELECT * 
       FROM supports 
       WHERE r2 IN (SELECT r2 FROM supports GROUP BY r2 HAVING COUNT(*) = 1) 
       -- Any piece all of whose supports would fall without 'a' also falls without it. 
       UNION 
       SELECT st.r1, s1.r2 
       FROM supports_trans st, supports s1 
       WHERE st.r2 = s1.r1 
       GROUP BY st.r1, s1.r2 
       HAVING COUNT(*) = (SELECT COUNT(*) FROM supports WHERE supports.r2 = s1.r2) 
   ), 

 
   part2(part2 BIGINT) AS (SELECT COUNT(*) FROM supports_trans) 

 
SELECT * FROM part1, part2; 

 
 sql

Contributors

Day 22 was brought to you by: @frankmcsherry

Day twenty-three is a classic example of finding the "longest path" in a directed graph. This is a relatively easy problem when the input is acyclic (part one), and it is NP-hard when the input may have cycles (part two). Part one was a mostly vanilla recursive SQL query, and part two encoded the 32 prior state options in a large integer and just did a lot of work.

See the solution

Link to puzzle(s) 🟢 🟢

Part one + two in one go!

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 
   ), 

 
   cells(r INT, c INT, symbol TEXT) AS ( 
       SELECT r, c, substring(line, c, 1) 
       FROM lines, generate_series(1, length(line)) c 
   ), 

 
   -- Part one: longest path (on probably a DAG) 
   paths(r INT, c INT) AS ( 
       SELECT r, c FROM cells WHERE symbol = '.' 
   ), 

 
   steps(r1 INT, c1 INT, r2 INT, c2 INT) AS ( 
       SELECT r, c, r + 1, c FROM paths WHERE (r + 1, c) IN (SELECT * FROM PATHS) UNION 
       SELECT r, c, r - 1, c FROM paths WHERE (r - 1, c) IN (SELECT * FROM PATHS) UNION 
       SELECT r, c, r, c + 1 FROM paths WHERE (r, c + 1) IN (SELECT * FROM PATHS) UNION 
       SELECT r, c, r, c - 1 FROM paths WHERE (r, c - 1) IN (SELECT * FROM PATHS) 
   ), 

 
   -- A directional trip, forced by a slope and the no-revisting rule. 
   force(r1 INT, c1 INT, r2 INT, c2 INT) AS ( 
       SELECT r-1, c, r+1, c FROM cells WHERE symbol = 'v' UNION ALL 
       SELECT r+1, c, r-1, c FROM cells WHERE symbol = '^' UNION ALL 
       SELECT r, c-1, r, c+1 FROM cells WHERE symbol = '>' UNION ALL 
       SELECT r, c+1, r, c-1 FROM cells WHERE symbol = '<' 
   ), 

 
   dists(r INT, c INT, d INT) AS ( 
       SELECT 1, 2, 0 
       UNION 
       SELECT steps.r2, steps.c2, 1 + MIN(d) 
       FROM dists, steps 
       WHERE dists.r = steps.r1 
         AND dists.c = steps.c1 
       GROUP BY steps.r2, steps.c2 
       UNION  
       SELECT force.r2, force.c2, 2 + MAX(d) 
       FROM dists, force 
       WHERE dists.r = force.r1 
         AND dists.c = force.c1 
       GROUP BY force.r2, force.c2 
   ), 

 
   -- Part two: longest path on definitely not a DAG. 
   -- There are 32 optional nodes (not including first and last nodes) 
   -- Clearly meant to pack in to an int and avoid duplication. 
   paths2(r INT, c INT) AS ( 
       SELECT r, c FROM cells WHERE symbol != '#' 
   ), 

 
   steps2(r1 INT, c1 INT, r2 INT, c2 INT) AS ( 
       SELECT r, c, r + 1, c FROM paths2 WHERE (r + 1, c) IN (SELECT * FROM paths2) UNION 
       SELECT r, c, r - 1, c FROM paths2 WHERE (r - 1, c) IN (SELECT * FROM paths2) UNION 
       SELECT r, c, r, c + 1 FROM paths2 WHERE (r, c + 1) IN (SELECT * FROM paths2) UNION 
       SELECT r, c, r, c - 1 FROM paths2 WHERE (r, c - 1) IN (SELECT * FROM paths2) 
   ), 
   -- Locations where a choice exists (or start/end). 
   nodes(r INT, c INT) AS ( 
       SELECT r1, c1 FROM steps2 GROUP BY r1, c1 HAVING COUNT(*) != 2 
   ), 
   -- Determine node-to-node path lengths. Do not cross nodes. 
   trail(r1 INT, c1 INT, d INT, r2 INT, c2 INT) AS ( 
       SELECT r1, c1, MIN(d), r2, c2 
       FROM ( 
           SELECT r1, c1, 1 d, r2, c2 FROM steps2 WHERE (r1, c1) IN (SELECT * FROM nodes) 
           UNION ALL 
           SELECT trail.r1, trail.c1, d + 1, steps2.r2, steps2.c2 
           FROM trail, steps2 
           WHERE trail.r2 = steps2.r1 
           AND trail.c2 = steps2.c1 
           AND (trail.r1 != steps2.r2 OR trail.c1 != steps2.c2) 
           AND (steps2.r1, steps2.c1) NOT IN (SELECT * FROM nodes) 
       ) 
       GROUP BY r1, c1, r2, c2 
   ), 

 
   links(r1 INT, c1 INT, d INT, r2 INT, c2 INT) AS ( 
       SELECT * FROM trail WHERE (r2, c2) IN (SELECT * FROM nodes) 
   ), 

 
   -- These rows in links show that (12, 20) and (130, 126) are mandatory, 
   -- and are the first moments we have a choice. The remainaing 32 nodes 
   -- can each get a number, and be used in a bit pattern somewhere. 
   -- 
   --          1 |   2 | 105 |  12 |  20 
   --        141 | 140 | 121 | 130 | 126 

 
   -- Re-key nodes to dense integers. 
   internal(r INT, c INT, id INT) AS ( 
       SELECT r, c, ( 
           SELECT COUNT(*) 
           FROM nodes n1 
           WHERE (n1.r < n2.r OR (n1.r = n2.r AND n1.c < n2.c)) 
             AND (n1.r, n1.c) NOT IN (VALUES (1,2), (12,20), (130,126), (141,140)) 
       ) 
       FROM nodes n2 
       WHERE (r, c) NOT IN (VALUES (1,2), (12,20), (130,126), (141,140)) 
   ), 

 
   longest(r INT, c INT, d INT, v BIGINT) AS ( 
       SELECT r, c, MAX(d), v 
       FROM ( 
           SELECT 12 r, 20 c, 0 d, 0 v 
           UNION ALL 
           SELECT r2, c2, longest.d + links.d, v + (1::BIGINT << internal.id) 
           FROM longest, links, internal 
           WHERE longest.r = links.r1 
             AND longest.c = links.c1 
             AND links.r2 = internal.r 
             AND links.c2 = internal.c 
             AND ((v >> internal.id) % 2) != 1 
       ) 
       GROUP BY r, c, v 
   ), 

 
   potato(x INT) AS ( SELECT 1 ) 

 
SELECT * FROM longest ORDER BY d DESC; 

 
 sql

Contributors

Day 23 was brought to you by: @frankmcsherry

Day twenty-four had most folks reach for a numerical solver, something like Mathematica or z3. That is less easy in SQL, and I needed to learn some math instead (specifically how to find the intersection of two line segments). Although part two seemed quite complex, it ended up being relatively easy when you realize a few simplifications (an added dimension that can be ignored until the end, allowing you to re-use part one).

See the solution

Link to puzzle(s) 🟢 🟢

Part one + two in one go!

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; 

 
 sql

Contributors

Day 24 was brought to you by: @frankmcsherry

Day twenty-five asked for a minimum graph cut (of three edges). This is a standard optimization problem, but rather than try to implement the Stoer-Wagner algorithm I went with something from my PhD thesis: partitioning the graph based on the Fiedler vector. It turns out this gave the right answer on the first try, and the holidays were saved!

See the solution

Link to puzzle(s) 🟢

Part one

WITH MUTUALLY RECURSIVE (RETURN AT RECURSION LIMIT 50) 

 
   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 
   ), 

 
   edges(src TEXT, dst TEXT) AS ( 
       SELECT 
           trim(':' FROM regexp_split_to_array(line, ' ')[1]), 
           trim(',' FROM regexp_split_to_array(line, ' ')[x]) 
       FROM 
           lines, generate_series(2, array_length(regexp_split_to_array(line, ' '), 1)) x 
   ), 

 
   symm(src TEXT, dst TEXT) AS ( 
       SELECT src, dst FROM edges 
       UNION ALL 
       SELECT dst, src FROM edges 
   ), 

 
   init(src TEXT, val NUMERIC) AS ( 
       SELECT src, CASE WHEN src < 'n' THEN 1.0 ELSE -1.0 END 
       FROM (SELECT src FROM edges UNION ALL SELECT dst FROM edges) 
   ), 
   -- determine the second eigenvector of the adjacency matrix 
   weight(src TEXT, val NUMERIC) AS ( 
       SELECT * FROM init 
       EXCEPT ALL 
       SELECT * FROM init_delayed 
       UNION ALL 
       SELECT symm.src, SUM((val - (SELECT AVG(val) FROM weight))/(SELECT STDDEV(val) FROM weight)) 
       FROM symm, weight 
       WHERE symm.dst = weight.src 
       GROUP BY symm.src 
   ), 

 
   init_delayed(src TEXT, val NUMERIC) AS ( SELECT * FROM init ), 

 
   part1(part1 BIGINT) AS ( 
       SELECT 
           (SELECT COUNT(*) FROM weight WHERE val < 0.0) * 
           (SELECT COUNT(*) FROM weight WHERE val > 0.0) 
   ), 

 
   potato(x INT) AS ( SELECT 1 ) 

 
SELECT * FROM part1; 

 
 sql

Contributors

Day 25 was brought to you by: @frankmcsherry

Conclusions

The exercise was certainly helpful and informative, on multiple levels.

First, it really reinforced for me that WITH MUTUALLY RECURSIVE is a very valuable tool to have access to when faced with a new problem. Often your problem is a bunch of joins and reductions, but when it isn't you are immediately in a bit of a pickle. In most cases, algorithmic challenges immediately gave way to recursive SQL.

That being said, there's clearly an accessibility gap when reaching for recursive SQL. I find the idioms approachable, but I've spent a while working with data-parallel algorithms, and have seen several of the tricks. There's still plenty of work to do before the casual SQL author feels comfortable with recursive SQL.

Second, the majority of my time was spent debugging rather than authoring. This is a classic challenge with declaritive languages, who go from input program to output data in often inscrutable ways. I borrowed some techniques from debugging Datalog, but ideally the system itself would help me with this (and several research systems do provide integrated lineage).

Debugging the logic of SQL queries only gets harder when the data are changing underneath you. Techniques like spot checking data become infeasible when the data changes faster than you can observe records that are meant to line up. Materialize should help in these cases, with maintained diagnostic views that represent assertions, or better violations thereof, whose contents spell out records that at some moment violated something that was meant to be true. Materialize's SUBSCRIBE provides a full account of these views, reporting records that existed even for a moment, where anything other than "always empty" represents an error in your SQL (or your assertions).

Third, using Materialize in new and weird ways shook out several bugs. We've already fixed them. Dogfooding your own product, especially in surprising contexts, is a great way to forcibly increase your test coverage. Issues ranged from the silly ("why would you name a table count?") to the abstruse (doubly nested recursive SQL blocks), but they spilled out in the early days and became less frequent as the weeks went on.

Finally, the main conclusion was that it was all possible. Despite substantial anxiety about whether and when we would need to bail out, defeated, the whole project did work out. We were able to express a rich variety of computational tasks as data-driven SQL both expressed and maintained by Materialize.

Frank McSherry

Chief Scientist, Materialize

Frank was previously at Microsoft Research Silicon Valley where he co-invented Differential Privacy, and subsequently led the Naiad project. Frank holds a Ph.D in Computer Science from the University of Washington.

`1`	`WITH MUTUALLY RECURSIVE`
`2`
`3`	`-- Parse the problem input into tabular form.`
`4`	`lines(line TEXT) AS ( .. ),`
`5`
`6`	`-- SQL leading up to part 1.`
`7`	`part1(part1 BIGINT) AS ( .. ),`
`8`
`9`	`-- SQL leading up to part 2.`
`10`	`part2(part2 BIGINT) AS ( .. )`
`11`
`12`	`SELECT * FROM part1, part2;`
`13`

`1`	`SELECT SUM(LEFT(r, 1)::int * 10 + RIGHT(r, 1)::int) AS part1`
`2`	`FROM (`
`3`	`SELECT regexp_replace(input, '[^\d]', '', 'g') AS r`
`4`	`FROM aoc_1201`
`5`	`);`
`6`

`1`	`WITH`
`2`	`lines AS (`
`3`	`SELECT regexp_split_to_table(input, '\n') AS line`
`4`	`FROM aoc_1201`
`5`	`),`
`6`	`slices AS (`
`7`	`SELECT line, index, substring(line, index, width) AS slice`
`8`	`FROM`
`9`	`lines,`
`10`	`generate_series(1, length(line)) AS index,`
`11`	`generate_series(1, 5) AS width`
`12`	`),`
`13`	`numbers (t, n) AS (`
`14`	`VALUES ('0', 0), ('1', 1), ('2', 2), ('3', 3), ('4', 4), ('5', 5), ('6', 6), ('7', 7), ('8', 8), ('9', 9),`
`15`	`('zero', 0), ('one', 1), ('two', 2), ('three', 3), ('four', 4), ('five', 5), ('six', 6), ('seven', 7), ('eight', 8), ('nine', 9)`
`16`	`),`
`17`	`findings AS (`
`18`	`SELECT line, index, n AS number`
`19`	`FROM slices, numbers`
`20`	`WHERE slices.slice = numbers.t`
`21`	`),`
`22`	`first AS ( SELECT DISTINCT ON (line) line, number AS f FROM findings ORDER BY line, index ),`
`23`	`last AS ( SELECT DISTINCT ON (line) line, number AS l FROM findings ORDER BY line, index DESC )`
`24`	`SELECT SUM(f * 10 + l)`
`25`	`FROM first, last`
`26`	`WHERE first.line = last.line`
`27`

`1`	`game_id \| set_id \| green_cnt \| red_cnt \| blue_cnt`
`2`	`----------+--------+-----------+---------+----------`
`3`	`Game 4 \| set_2 \| 12 \| 0 \| 0`
`4`	`...`
`5`

`1`	`WITH game_cnt AS (`
`2`	`SELECT split_part(game_id,' ', 2)::int AS game_id,`
`3`	`COUNT(set_id) AS total_set_cnt,`
`4`	`COUNT(set_id) FILTER (WHERE (green_cnt <= 13) AND (red_cnt <= 12) AND (blue_cnt <= 14)) AS possible_set_cnt`
`5`	`FROM aoc_1202`
`6`	`GROUP BY game_id`
`7`	`)`
`8`	`SELECT SUM(game_id) FROM game_cnt WHERE total_set_cnt = possible_set_cnt;`
`9`

`1`	`WITH game_min AS (`
`2`	`SELECT split_part(game_id,' ', 2)::int AS game_id,`
`3`	`MAX(green_cnt) AS green_min,`
`4`	`MAX(red_cnt) AS red_min,`
`5`	`MAX(blue_cnt) AS blue_min`
`6`	`FROM aoc_1202`
`7`	`GROUP BY split_part(game_id,' ', 2)::int`
`8`	`)`
`9`	`SELECT SUM(green_minred_minblue_min) FROM game_min;`
`10`

`1`	-- Pre-supposes a view `input(input TEXT)` containing the string from AOC
`2`	`with mutually recursive`
`3`	`-- Parse the input up`
`4`	`lines(line TEXT) as (select regexp_split_to_table(input, '\n') as line from input),`
`5`	`games(game TEXT, report TEXT) as (select regexp_split_to_array(line, ':')[1], regexp_split_to_array(line, ':')[2] from lines),`
`6`	`round(game TEXT, visible TEXT) as (select game, regexp_split_to_table(report, ';') from games),`
`7`	`bacon(game TEXT, color TEXT) as (select game, regexp_split_to_table(visible, ',') from round),`
`8`	`parsed(game INT, color TEXT, number INT) as (`
`9`	`select`
`10`	`substring(game, 5)::INT as game,`
`11`	`regexp_split_to_array(color, ' ')[3] as color,`
`12`	`regexp_split_to_array(color, ' ')[2]::INT as number`
`13`	`from bacon`
`14`	`),`
`15`	`-- PART 1`
`16`	`limits(color TEXT, number INT) as (SELECT * FROM (VALUES ('red', 12), ('green', 13), ('blue', 14))),`
`17`	`bad_news(game INT) as (`
`18`	`select game`
`19`	`from parsed, limits`
`20`	`where parsed.color = limits.color`
`21`	`AND parsed.number > limits.number`
`22`	`),`
`23`	`plausible(game INT) as (select distinct parsed.game from parsed left join bad_news on(parsed.game = bad_news.game) where bad_news.game IS NULL),`
`24`	`part1(part1 BIGINT) as (select SUM(game) from plausible),`
`25`	`-- PART 2`
`26`	`maximum(game INT, color TEXT, number INT) as (select game, color, max(number) from parsed GROUP BY game, color),`
`27`	`red(game INT) as (select game from maximum, generate_series(1, number) where color = 'red'),`
`28`	`blue(game INT) as (select game from maximum, generate_series(1, number) where color = 'blue'),`
`29`	`green(game INT) as (select game from maximum, generate_series(1, number) where color = 'green'),`
`30`	`power(game INT, product BIGINT) as (SELECT red.game, count(*) from red, blue, green where red.game = blue.game and blue.game = green.game GROUP BY red.game),`
`31`	`part2(part2 BIGINT) as (select sum(product)::BIGINT from power)`
`32`	`select * from part1, part2;`
`33`

`1`	-- Pre-supposes a view `input(input TEXT)` containing the string from AOC
`2`	`WITH MUTUALLY RECURSIVE`
`3`	`-- PART 0`
`4`	`-- Parse the input as lines of text with line numbers.`
`5`	`lines(line TEXT, row_idx INT) AS (`
`6`	`SELECT`
`7`	`regexp_split_to_array(input, '\n')[row_idx],`
`8`	`row_idx`
`9`	`FROM`
`10`	`input,`
`11`	`generate_series(1, (SELECT COUNT(*)::INT FROM (SELECT regexp_split_to_table(input, '\n') FROM input))) as row_idx`
`12`	`),`
`13`	`chars(symbol TEXT, row_idx INT, col_idx INT) AS (`
`14`	`SELECT`
`15`	`substring(line, start, 1),`
`16`	`row_idx,`
`17`	`start`
`18`	`FROM`
`19`	`lines,`
`20`	`generate_series(1, length(line)) as start`
`21`	`WHERE`
`22`	`substring(line, start, 1) != '.'`
`23`	`),`
`24`	`numerals(number TEXT, row_idx INT, col_idx INT) AS (`
`25`	`SELECT symbol, row_idx, col_idx`
`26`	`FROM chars`
`27`	`WHERE symbol IN ( VALUES ('0'), ('1'), ('2'), ('3'), ('4'), ('5'), ('6'), ('7'), ('8'), ('9') )`
`28`	`),`
`29`	`symbols(symbol TEXT, row_idx INT, col_idx INT) AS (`
`30`	`SELECT symbol, row_idx, col_idx`
`31`	`FROM chars`
`32`	`WHERE symbol NOT IN ( VALUES ('0'), ('1'), ('2'), ('3'), ('4'), ('5'), ('6'), ('7'), ('8'), ('9') )`
`33`	`),`
`34`	`-- PART 1`
`35`	`-- Recursively build up ranges of numerals that are "active", in the sense of being adjacent to a symbol.`
`36`	`-- Each range has an accumulated number (as a string), a row index, a column index and length of the run.`
`37`	`active(number TEXT, row_idx INT, col_idx INT, length INT) AS (`
`38`	`-- Base case: numerals adjacent to a symbol`
`39`	`SELECT numerals.*, 1`
`40`	`FROM`
`41`	`numerals,`
`42`	`symbols,`
`43`	`generate_series(-1, 1) row_off,`
`44`	`generate_series(-1, 1) col_off`
`45`	`WHERE numerals.row_idx = symbols.row_idx + row_off`
`46`	`AND numerals.col_idx = symbols.col_idx + col_off`
`47`	`UNION`
`48`	`-- Inductive case 1: Join to the left`
`49`	`SELECT numerals.number \|\| active.number, numerals.row_idx, numerals.col_idx, active.length + 1`
`50`	`FROM numerals, active`
`51`	`WHERE numerals.row_idx = active.row_idx`
`52`	`AND numerals.col_idx = active.col_idx - 1`
`53`	`UNION`
`54`	`-- Inductive case 2: Join to the right`
`55`	`SELECT active.number \|\| numerals.number, numerals.row_idx, active.col_idx, active.length + 1`
`56`	`FROM numerals, active`
`57`	`WHERE numerals.row_idx = active.row_idx`
`58`	`AND numerals.col_idx = active.col_idx + active.length`
`59`	`),`
`60`	`parts(number INT, row_idx INT, col_idx INT, length INT) AS (`
`61`	`SELECT active.number::INT, row_idx, col_idx, length`
`62`	`FROM active`
`63`	`WHERE (active.row_idx, active.col_idx-1) NOT IN (SELECT row_idx, col_idx FROM numerals)`
`64`	`AND (active.row_idx, active.col_idx+length) NOT IN (SELECT row_idx, col_idx FROM numerals)`
`65`	`),`
`66`	`part1(part1 BIGINT) AS ( SELECT SUM(parts.number::INT) FROM parts ),`
`67`	`-- PART 2`
`68`	-- A "gear" is a `*` adjacent to exactly two part numbers. We want the sum over gears of their product.
`69`	`-- A gear is identified by a location, which we will want to attempt to join with part numbers.`
`70`	`gear_adjacent(row_idx INT, col_idx INT, number INT, part_row INT, part_col INT) AS (`
`71`	`SELECT DISTINCT symbols.row_idx, symbols.col_idx, parts.number, parts.row_idx, parts.col_idx`
`72`	`FROM`
`73`	`symbols,`
`74`	`generate_series(-1, 1) gear_r_off,`
`75`	`generate_series(-1, 1) gear_c_off,`
`76`	`parts,`
`77`	`generate_series(parts.col_idx, parts.col_idx + parts.length - 1) part_col`
`78`	`WHERE symbols.symbol = '*'`
`79`	`AND symbols.row_idx + gear_r_off = parts.row_idx`
`80`	`AND symbols.col_idx + gear_c_off = part_col`
`81`	`),`
`82`	`gears(row_idx INT, col_idx INT) AS (`
`83`	`SELECT row_idx, col_idx`
`84`	`FROM gear_adjacent`
`85`	`GROUP BY row_idx, col_idx`
`86`	`HAVING COUNT(*) = 2`
`87`	`),`
`88`	`gear_products(row_idx INT, col_idx INT, product INT) AS (`
`89`	`SELECT DISTINCT gears.row_idx, gears.col_idx, p1.number * p2.number`
`90`	`FROM gears, gear_adjacent p1, gear_adjacent p2`
`91`	`WHERE gears.row_idx = p1.row_idx`
`92`	`AND gears.col_idx = p1.col_idx`
`93`	`AND gears.row_idx = p2.row_idx`
`94`	`AND gears.col_idx = p2.col_idx`
`95`	`AND (p1.part_row != p2.part_row OR p1.part_col != p2.part_col)`
`96`	`),`
`97`	`part2(part2 BIGINT) AS ( SELECT SUM(product) FROM gear_products)`
`98`
`99`	`SELECT * FROM part1, part2;`
`100`

`1`	`-- PART 2`
`2`	-- Each card provides a copy of the next `score` cards.
`3`	`expanded(card INT, score BIGINT) AS (`
`4`	`SELECT * FROM matches`
`5`	`UNION ALL`
`6`	`SELECT`
`7`	`matches.card,`
`8`	`matches.score`
`9`	`FROM`
`10`	`expanded,`
`11`	`matches,`
`12`	`generate_series(1, expanded.score) as step`
`13`	`WHERE`
`14`	`expanded.card + step = matches.card`
`15`	`),`
`16`	`part2(part2 BIGINT) AS ( SELECT COUNT(*) FROM expanded)`
`17`

`1`	`WITH parsed AS (`
`2`	`SELECT regexp_split_to_table(input, '\n') AS line FROM aoc_1204`
`3`	`),`
`4`	`numbers AS (`
`5`	`SELECT split_part(line,':',1) AS card_id,`
`6`	`replace(split_part(line,':',2),'\|','') AS nrs`
`7`	`FROM parsed`
`8`	`),`
`9`	`arr AS (`
`10`	`SELECT card_id,`
`11`	`nrs,`
`12`	`regexp_split_to_array(ltrim(rtrim(nrs)),'\s') AS nrs_arr`
`13`	`FROM numbers`
`14`	`),`
`15`	`winning AS (`
`16`	`SELECT card_id,`
`17`	`unnest(array_remove(nrs_arr,'')) nr,`
`18`	`ROW_NUMBER() OVER (PARTITION BY card_id) AS row_num`
`19`	`FROM arr`
`20`	`GROUP BY card_id, nr HAVING COUNT(*)>1`
`21`	`ORDER BY card_id`
`22`	`),`
`23`	`winning_points AS (`
`24`	`SELECT ROUND(EXP(SUM(LN(CASE WHEN row_num = 1 THEN row_num ELSE 2 END)))) AS points`
`25`	`FROM winning`
`26`	`GROUP BY card_id`
`27`	`)`
`28`	`SELECT SUM(points)`
`29`	`FROM winning_points;`
`30`

`1`	`WITH MUTUALLY RECURSIVE`
`2`	`lines(line string) AS (`
`3`	`SELECT`
`4`	`regexp_split_to_table(input, '\n') AS line`
`5`	`FROM`
`6`	`aoc_1204`
`7`	`),`
`8`	`cards(match string[]) AS (`
`9`	`SELECT`
`10`	`regexp_match(line, 'Card +(\d+): (.*)') AS match`
`11`	`FROM`
`12`	`lines`
`13`	`),`
`14`	`card_parts(card_id int, parts string[]) AS (`
`15`	`SELECT`
`16`	`match[1]::int AS card_id,`
`17`	`regexp_split_to_array(match[2], ' \\| ') AS parts`
`18`	`FROM`
`19`	`cards`
`20`	`),`
`21`	`winners(card_id int, val int) AS (`
`22`	`SELECT`
`23`	`card_id,`
`24`	`regexp_split_to_table(trim(parts[1]), '\s+')::int AS val`
`25`	`FROM`
`26`	`card_parts`
`27`	`),`
`28`	`ours(card_id int, val int) AS (`
`29`	`SELECT`
`30`	`card_id,`
`31`	`regexp_split_to_table(trim(parts[2]), '\s+')::int AS val`
`32`	`FROM`
`33`	`card_parts`
`34`	`),`
`35`	`count_winning_numbers(card_id int, count int) AS (`
`36`	`SELECT`
`37`	`ours.card_id,`
`38`	`count(winners.val)::int AS count`
`39`	`FROM`
`40`	`ours LEFT OUTER JOIN winners ON (`
`41`	`ours.card_id = winners.card_id AND`
`42`	`ours.val = winners.val`
`43`	`)`
`44`	`GROUP BY ours.card_id`
`45`	`),`
`46`	`prizes(card_id int, prize_id int) AS (`
`47`	`SELECT`
`48`	`card_id,`
`49`	`prize_id`
`50`	`FROM`
`51`	`count_winning_numbers CROSS JOIN generate_series(card_id + 1, card_id + count) AS prize_id`
`52`	`UNION`
`53`	`SELECT`
`54`	`0 AS card_id,`
`55`	`ours.card_id AS prize_id`
`56`	`FROM`
`57`	`ours`
`58`	`),`
`59`	`multipliers(card_id int, multiplier int) AS (`
`60`	`SELECT`
`61`	`prizes.prize_id AS card_id,`
`62`	`SUM(coalesce(multipliers.multiplier, 1))::int AS multiplier`
`63`	`FROM`
`64`	`prizes left outer JOIN multipliers ON (`
`65`	`prizes.card_id = multipliers.card_id`
`66`	`)`
`67`	`GROUP BY prizes.prize_id`
`68`	`)`
`69`	`SELECT`
`70`	`SUM(multiplier) AS answer`
`71`	`FROM`
`72`	`multipliers;`
`73`

`1`	`WITH seeds AS (`
`2`	`SELECT`
`3`	`regexp_split_to_table(`
`4`	`regexp_split_to_array(`
`5`	`regexp_split_to_array(input, '\n')[1],`
`6`	`': '`
`7`	`)[2],`
`8`	`' '`
`9`	`)::bigint AS seed`
`10`	`FROM`
`11`	`input`
`12`	`),`
`13`	`seed_to_soil_lines AS (`
`14`	`SELECT`
`15`	`regexp_split_to_array(`
`16`	`regexp_split_to_table(`
`17`	`regexp_match(input, 'seed-to-soil map:\n([0-9 \n]*?)\n\n')[1],`
`18`	`'\n'`
`19`	`),`
`20`	`' '`
`21`	`)::bigint[] AS line`
`22`	`FROM`
`23`	`input`
`24`	`),`
`25`	`seed_to_soil AS (`
`26`	`SELECT`
`27`	`line[1] AS dst_base,`
`28`	`line[2] AS src_base,`
`29`	`line[3] AS len`
`30`	`FROM`
`31`	`seed_to_soil_lines`
`32`	`),`
`33`	`soil_to_fertilizer_lines AS (`
`34`	`SELECT`
`35`	`regexp_split_to_array(`
`36`	`regexp_split_to_table(`
`37`	`regexp_match(input, 'soil-to-fertilizer map:\n([0-9 \n]*?)\n\n')[1],`
`38`	`'\n'`
`39`	`),`
`40`	`' '`
`41`	`)::bigint[] AS line`
`42`	`FROM`
`43`	`input`
`44`	`),`
`45`	`soil_to_fertilizer AS (`
`46`	`SELECT`
`47`	`line[1] AS dst_base,`
`48`	`line[2] AS src_base,`
`49`	`line[3] AS len`
`50`	`FROM`
`51`	`soil_to_fertilizer_lines`
`52`	`),`
`53`	`fertilizer_to_water_lines AS (`
`54`	`SELECT`
`55`	`regexp_split_to_array(`
`56`	`regexp_split_to_table(`
`57`	`regexp_match(input, 'fertilizer-to-water map:\n([0-9 \n]*?)\n\n')[1],`
`58`	`'\n'`
`59`	`),`
`60`	`' '`
`61`	`)::bigint[] AS line`
`62`	`FROM`
`63`	`input`
`64`	`),`
`65`	`fertilizer_to_water AS (`
`66`	`SELECT`
`67`	`line[1] AS dst_base,`
`68`	`line[2] AS src_base,`
`69`	`line[3] AS len`
`70`	`FROM`
`71`	`fertilizer_to_water_lines`
`72`	`),`
`73`	`water_to_light_lines AS (`
`74`	`SELECT`
`75`	`regexp_split_to_array(`
`76`	`regexp_split_to_table(`
`77`	`regexp_match(input, 'water-to-light map:\n([0-9 \n]*?)\n\n')[1],`
`78`	`'\n'`
`79`	`),`
`80`	`' '`
`81`	`)::bigint[] AS line`
`82`	`FROM`
`83`	`input`
`84`	`),`
`85`	`water_to_light AS (`
`86`	`SELECT`
`87`	`line[1] AS dst_base,`
`88`	`line[2] AS src_base,`
`89`	`line[3] AS len`
`90`	`FROM`
`91`	`water_to_light_lines`
`92`	`),`
`93`	`light_to_temperature_lines AS (`
`94`	`SELECT`
`95`	`regexp_split_to_array(`
`96`	`regexp_split_to_table(`
`97`	`regexp_match(input, 'light-to-temperature map:\n([0-9 \n]*?)\n\n')[1],`
`98`	`'\n'`
`99`	`),`
`100`	`' '`
`101`	`)::bigint[] AS line`
`102`	`FROM`
`103`	`input`
`104`	`),`
`105`	`light_to_temperature AS (`
`106`	`SELECT`
`107`	`line[1] AS dst_base,`
`108`	`line[2] AS src_base,`
`109`	`line[3] AS len`
`110`	`FROM`
`111`	`light_to_temperature_lines`
`112`	`),`
`113`	`temperature_to_humidity_lines AS (`
`114`	`SELECT`
`115`	`regexp_split_to_array(`
`116`	`regexp_split_to_table(`
`117`	`regexp_match(input, 'temperature-to-humidity map:\n([0-9 \n]*?)\n\n')[1],`
`118`	`'\n'`
`119`	`),`
`120`	`' '`
`121`	`)::bigint[] AS line`
`122`	`FROM`
`123`	`input`
`124`	`),`
`125`	`temperature_to_humidity AS (`
`126`	`SELECT`
`127`	`line[1] AS dst_base,`
`128`	`line[2] AS src_base,`
`129`	`line[3] AS len`
`130`	`FROM`
`131`	`temperature_to_humidity_lines`
`132`	`),`
`133`	`humidity_to_location_lines AS (`
`134`	`SELECT`
`135`	`regexp_split_to_array(`
`136`	`regexp_split_to_table(`
`137`	`regexp_match(input, 'humidity-to-location map:\n([0-9 \n]*)')[1],`
`138`	`'\n'`
`139`	`),`
`140`	`' '`
`141`	`)::bigint[] AS line`
`142`	`FROM`
`143`	`input`
`144`	`),`
`145`	`humidity_to_location AS (`
`146`	`SELECT`
`147`	`line[1] AS dst_base,`
`148`	`line[2] AS src_base,`
`149`	`line[3] AS len`
`150`	`FROM`
`151`	`humidity_to_location_lines`
`152`	`),`
`153`	`soil AS (`
`154`	`SELECT`
`155`	`seed,`
`156`	`coalesce(`
`157`	`MAX(`
`158`	`CASE`
`159`	`WHEN seed >= src_base AND seed < src_base + len`
`160`	`THEN dst_base + (seed - src_base)`
`161`	`ELSE null`
`162`	`END`
`163`	`),`
`164`	`seed`
`165`	`) AS soil`
`166`	`FROM`
`167`	`seeds, seed_to_soil`
`168`	`GROUP BY seed`
`169`	`),`
`170`	`fertilizer AS (`
`171`	`SELECT`
`172`	`soil,`
`173`	`coalesce(`
`174`	`MAX(`
`175`	`CASE`
`176`	`WHEN soil >= src_base AND soil < src_base + len`
`177`	`THEN dst_base + (soil - src_base)`
`178`	`ELSE null`
`179`	`END`
`180`	`),`
`181`	`soil`
`182`	`) AS fertilizer`
`183`	`FROM`
`184`	`soil, soil_to_fertilizer`
`185`	`GROUP BY soil`
`186`	`),`
`187`	`water AS (`
`188`	`SELECT`
`189`	`fertilizer,`
`190`	`coalesce(`
`191`	`MAX(`
`192`	`CASE`
`193`	`when fertilizer >= src_base AND fertilizer < src_base + len`
`194`	`then dst_base + (fertilizer - src_base)`
`195`	`else null`
`196`	`END`
`197`	`),`
`198`	`fertilizer`
`199`	`) AS water`
`200`	`FROM`
`201`	`fertilizer, fertilizer_to_water`
`202`	`GROUP BY fertilizer`
`203`	`),`
`204`	`light AS (`
`205`	`SELECT`
`206`	`water,`
`207`	`coalesce(`
`208`	`MAX(`
`209`	`CASE`
`210`	`WHEN water >= src_base AND water < src_base + len`
`211`	`THEN dst_base + (water - src_base)`
`212`	`ELSE null`
`213`	`END`
`214`	`),`
`215`	`water`
`216`	`) AS light`
`217`	`FROM`
`218`	`water, water_to_light`
`219`	`GROUP BY water`
`220`	`),`
`221`	`temperature AS (`
`222`	`SELECT`
`223`	`light,`
`224`	`coalesce(`
`225`	`MAX(`
`226`	`CASE`
`227`	`WHEN light >= src_base AND light < src_base + len`
`228`	`THEN dst_base + (light - src_base)`
`229`	`ELSE null`
`230`	`END`
`231`	`),`
`232`	`light`
`233`	`) AS temperature`
`234`	`FROM`
`235`	`light, light_to_temperature`
`236`	`GROUP BY light`
`237`	`),`
`238`	`humidity AS (`
`239`	`SELECT`
`240`	`temperature,`
`241`	`coalesce(`
`242`	`MAX(`
`243`	`CASE`
`244`	`WHEN temperature >= src_base AND temperature < src_base + len`
`245`	`THEN dst_base + (temperature - src_base)`
`246`	`ELSE null`
`247`	`END`
`248`	`),`
`249`	`temperature`
`250`	`) AS humidity`
`251`	`FROM`
`252`	`temperature, temperature_to_humidity`
`253`	`GROUP BY temperature`
`254`	`),`
`255`	`location AS (`
`256`	`SELECT`
`257`	`humidity,`
`258`	`coalesce(`
`259`	`MAX(`
`260`	`CASE`
`261`	`WHEN humidity >= src_base AND humidity < src_base + len`
`262`	`THEN dst_base + (humidity - src_base)`
`263`	`ELSE null`
`264`	`END`
`265`	`),`
`266`	`humidity`
`267`	`) AS location`
`268`	`FROM`
`269`	`humidity, humidity_to_location`
`270`	`GROUP BY humidity`
`271`	`)`
`272`	`SELECT`
`273`	`MIN(location) AS answer`
`274`	`FROM`
`275`	`location;`
`276`

`1`	`WITH MUTUALLY RECURSIVE`
`2`	`blocks(head TEXT, body TEXT) AS (`
`3`	`SELECT`
`4`	`split_part(regexp_split_to_table(input, '\n\n'), ':', 1),`
`5`	`split_part(regexp_split_to_table(input, '\n\n'), ':', 2)`
`6`	`FROM`
`7`	`input`
`8`	`),`
`9`	`seeds(seed BIGINT) AS (`
`10`	`SELECT regexp_split_to_table(trim(body), ' ')::BIGINT`
`11`	`FROM blocks`
`12`	`WHERE head = 'seeds'`
`13`	`),`
`14`	`entry0(src_name TEXT, dst_name TEXT, dst_idx TEXT, src_idx TEXT, len TEXT) AS (`
`15`	`SELECT`
`16`	`split_part(split_part(head, ' ', 1), '-', 1),`
`17`	`split_part(split_part(head, ' ', 1), '-', 3),`
`18`	`split_part(regexp_split_to_table(body, '\n'), ' ', 1),`
`19`	`split_part(regexp_split_to_table(body, '\n'), ' ', 2),`
`20`	`split_part(regexp_split_to_table(body, '\n'), ' ', 3)`
`21`	`FROM`
`22`	`blocks`
`23`	`WHERE`
`24`	`head != 'seeds'`
`25`	`),`
`26`	`entry(src_name TEXT, dst_name TEXT, src_idx BIGINT, dst_idx BIGINT, len BIGINT) AS (`
`27`	`SELECT`
`28`	`src_name,`
`29`	`dst_name,`
`30`	`src_idx::BIGINT,`
`31`	`dst_idx::BIGINT,`
`32`	`len::BIGINT`
`33`	`FROM`
`34`	`entry0`
`35`	`WHERE`
`36`	`src_idx != ''`
`37`	`),`
`38`
`39`	`-- PART 1`
`40`	`-- Our active inventory of .. "stuff"`
`41`	`active(name TEXT, idx BIGINT) AS (`
`42`	`SELECT 'seed', seed FROM seeds`
`43`	`UNION ALL`
`44`	`SELECT`
`45`	`intent.dst_name,`
`46`	`COALESCE(intent.idx + (entry.dst_idx - entry.src_idx), idx)`
`47`	`FROM intent LEFT JOIN entry ON (`
`48`	`intent.src_name = entry.src_name AND`
`49`	`intent.dst_name = entry.dst_name AND`
`50`	`intent.idx BETWEEN entry.src_idx AND entry.src_idx + len - 1)`
`51`	`),`
`52`	`-- We would like to perform this mapping, but must find a range.`
`53`	`intent(src_name TEXT, dst_name TEXT, idx BIGINT) AS (`
`54`	`SELECT DISTINCT entry.src_name, dst_name, idx`
`55`	`FROM active, entry`
`56`	`WHERE active.name = entry.src_name`
`57`	`),`
`58`	`part1(part1 BIGINT) AS (`
`59`	`SELECT MIN(idx) FROM active WHERE name = 'location'`
`60`	`),`
`61`
`62`	`-- PART 2`
`63`	`-- Now we are doing ranges of seeds, rather than seed identifiers.`
`64`	`-- They are big ranges, so we'll need to be smarter!`
`65`	`seeds2(start_idx BIGINT, end_idx BIGINT) AS (`
`66`	`SELECT`
`67`	`regexp_split_to_array(trim(body), ' ')[2*x-1]::BIGINT,`
`68`	`regexp_split_to_array(trim(body), ' ')[2x-1]::BIGINT + regexp_split_to_array(trim(body), ' ')[2x]::BIGINT`
`69`	`FROM`
`70`	`blocks,`
`71`	`generate_series(1, array_length(regexp_split_to_array(trim(body), ' '), 1)/2) x`
`72`	`WHERE head = 'seeds'`
`73`	`),`
`74`	`active2(name TEXT, start_idx BIGINT, end_idx BIGINT) AS (`
`75`	`SELECT 'seed', start_idx, end_idx`
`76`	`FROM seeds2`
`77`	`UNION`
`78`	`SELECT`
`79`	`dst_name,`
`80`	`clipped_start + (entry_dst - entry_start),`
`81`	`clipped_end + (entry_dst - entry_start)`
`82`	`FROM intersection`
`83`	`UNION`
`84`	`SELECT`
`85`	`name,`
`86`	`start_idx,`
`87`	`end_idx`
`88`	`FROM hole`
`89`	`),`
`90`	`-- We would like to perform this mapping, but must find a range.`
`91`	`intent2(src_name TEXT, dst_name TEXT, start_idx BIGINT, end_idx BIGINT) AS (`
`92`	`SELECT DISTINCT entry.src_name, dst_name, start_idx, end_idx`
`93`	`FROM active2, entry`
`94`	`WHERE active2.name = entry.src_name`
`95`	`),`
`96`	`-- Each mapping has a potential intersection with a requested range.`
`97`	`intersection(src_name TEXT, dst_name TEXT, start_idx BIGINT, end_idx BIGINT, entry_start BIGINT, entry_end BIGINT, clipped_start BIGINT, clipped_end BIGINT, entry_dst BIGINT) AS (`
`98`	`SELECT`
`99`	`intent2.src_name,`
`100`	`intent2.dst_name,`
`101`	`intent2.start_idx,`
`102`	`intent2.end_idx,`
`103`	`entry.src_idx,`
`104`	`entry.src_idx + entry.len,`
`105`	`GREATEST(start_idx, entry.src_idx),`
`106`	`LEAST(end_idx, entry.src_idx + entry.len),`
`107`	`entry.dst_idx`
`108`	`FROM intent2, entry`
`109`	`WHERE intent2.src_name = entry.src_name`
`110`	`AND intent2.dst_name = entry.dst_name`
`111`	`AND GREATEST(intent2.start_idx, entry.src_idx)`
`112`	`< LEAST(intent2.end_idx, entry.src_idx + entry.len)`
`113`	`),`
`114`	`-- We may have holes in our intervals. Each intersection's start and end is the end and`
`115`	`-- start, respectively, of some hole we may have that needs to remain the identity.`
`116`	`hole(name TEXT, start_idx BIGINT, end_idx BIGINT) AS (`
`117`	`SELECT * FROM (`
`118`	`SELECT`
`119`	`dst_name,`
`120`	`clipped_end start_idx,`
`121`	`(`
`122`	`SELECT COALESCE(MIN(i2.clipped_start), i1.end_idx)`
`123`	`FROM intersection i2`
`124`	`WHERE i2.clipped_start >= i1.clipped_end`
`125`	`AND i2.clipped_start < i1.end_idx`
`126`	`AND i1.src_name = i2.src_name`
`127`	`AND i1.dst_name = i2.dst_name`
`128`	`AND i1.start_idx = i2.start_idx`
`129`	`AND i1.end_idx = i2.end_idx`
`130`	`) end_idx`
`131`	`FROM intersection i1`
`132`	`UNION`
`133`	`SELECT DISTINCT`
`134`	`dst_name,`
`135`	`start_idx,`
`136`	`(`
`137`	`SELECT COALESCE(MIN(i2.clipped_start), i1.end_idx)`
`138`	`FROM intersection i2`
`139`	`WHERE i2.clipped_start >= i1.start_idx`
`140`	`AND i2.clipped_start < i1.end_idx`
`141`	`AND i1.src_name = i2.src_name`
`142`	`AND i1.dst_name = i2.dst_name`
`143`	`AND i1.start_idx = i2.start_idx`
`144`	`AND i1.end_idx = i2.end_idx`
`145`	`)`
`146`	`FROM intent2 i1`
`147`	`)`
`148`	`WHERE start_idx < end_idx`
`149`	`),`
`150`	`part2(part2 BIGINT) AS ( SELECT MIN(start_idx) FROM active2 WHERE name = 'location')`
`151`
`152`	`SELECT * FROM part1, part2;`
`153`

`1`	`WITH options AS`
`2`	`(`
`3`	`SELECT`
`4`	`(floor((time - sqrt(time * time - 4 * record)) / 2) + 1)::int low,`
`5`	`(ceil((time + sqrt(time * time - 4 * record)) / 2) - 1)::int hi,`
`6`	`FROM input`
`7`	`)`
`8`	`SELECT exp(sum(ln(hi - low + 1)))::int`
`9`	`FROM options;`
`10`

`1`	`WITH MUTUALLY RECURSIVE`
`2`
`3`	`ties(slower NUMERIC, faster NUMERIC) AS (`
`4`	`SELECT`
`5`	`(time + sqrt(time * time - 4 * distance)) / 2 as slower,`
`6`	`(time - sqrt(time * time - 4 * distance)) / 2 as faster`
`7`	`FROM input`
`8`	`),`
`9`	`options(choices NUMERIC) AS (`
`10`	`SELECT 1 + FLOOR(slower)::NUMERIC - CEIL(faster)::NUMERIC FROM ties`
`11`	`),`
`12`	`part12(part12 NUMERIC) AS (`
`13`	`SELECT pow(10.0, SUM(log(choices))) FROM options`
`14`	`)`
`15`
`16`	`SELECT * FROM part12;`
`17`

`1`	`-- Hands of cards (e.g. 'AKJQT') and integer bids.`
`2`	`WITH MUTUALLY RECURSIVE`
`3`	`lines(line TEXT) AS ( SELECT regexp_split_to_table(input, '\n') FROM input ),`
`4`	`hands(hand TEXT, bid INT) as (`
`5`	`SELECT regexp_split_to_array(line, ' ')[1],`
`6`	`regexp_split_to_array(line, ' ')[2]::INT`
`7`	`FROM lines`
`8`	`),`
`9`	`cards(hand TEXT, value TEXT, position INT) AS (`
`10`	`SELECT hand, substring(hand, pos, 1), pos`
`11`	`FROM hands, generate_series(1, 5) pos`
`12`	`),`
`13`
`14`	`-- Part1`
`15`	`counts(hand TEXT, value TEXT, count INT) AS (`
`16`	`SELECT hand, value, COUNT(*)`
`17`	`FROM cards`
`18`	`GROUP BY hand, value`
`19`	`),`
`20`	`ranked(hand TEXT, bid INT, rank INT, score TEXT) AS (`
`21`	`SELECT`
`22`	`hand,`
`23`	`bid,`
`24`	`CASE WHEN hand IN (SELECT hand FROM counts WHERE count = 5) THEN 1`
`25`	`WHEN hand IN (SELECT hand FROM counts WHERE count = 4) THEN 2`
`26`	`WHEN hand IN (SELECT hand FROM counts WHERE count = 3)`
`27`	`AND hand IN (SELECT hand FROM counts WHERE count = 2) THEN 3`
`28`	`WHEN hand IN (SELECT hand FROM counts WHERE count = 3) THEN 4`
`29`	`WHEN hand IN (SELECT hand FROM (SELECT hand FROM counts WHERE count = 2) GROUP BY hand HAVING COUNT(*) = 2) THEN 5`
`30`	`WHEN hand IN (SELECT hand FROM counts WHERE count = 2) THEN 6`
`31`	`ELSE 7`
`32`	`END,`
`33`	`translate(hand, 'AKQJT98765432', 'ABCDEFGHIJKLM')`
`34`	`FROM`
`35`	`hands`
`36`	`),`
`37`	`part1(part1 INT) AS (`
`38`	`SELECT SUM(r1.bid)`
`39`	`FROM ranked r1, ranked r2`
`40`	`WHERE r1.rank < r2.rank OR (r1.rank = r2.rank AND r1.score <= r2.score)`
`41`	`),`
`42`
`43`	`-- Part2: J are now wild for determining rank, but last for score.`
`44`	`wild(hand TEXT, value TEXT, position INT) AS (`
`45`	`SELECT * FROM cards`
`46`	`UNION`
`47`	`SELECT c1.hand, c2.value, c1.position`
`48`	`FROM cards c1, cards c2`
`49`	`WHERE c1.hand = c2.hand`
`50`	`AND c1.value = 'J'`
`51`	`),`
`52`	`wild_hands(hand TEXT, new_hand TEXT) AS (`
`53`	`SELECT DISTINCT w1.hand, w1.value \|\| w2.value \|\| w3.value \|\| w4.value \|\| w5.value`
`54`	`FROM (SELECT * FROM wild w1 WHERE position = 1) w1,`
`55`	`(SELECT * FROM wild w2 WHERE position = 2) w2,`
`56`	`(SELECT * FROM wild w3 WHERE position = 3) w3,`
`57`	`(SELECT * FROM wild w4 WHERE position = 4) w4,`
`58`	`(SELECT * FROM wild w5 WHERE position = 5) w5`
`59`	`WHERE w1.hand = w2.hand`
`60`	`AND w1.hand = w3.hand`
`61`	`AND w1.hand = w4.hand`
`62`	`AND w1.hand = w5.hand`
`63`	`),`
`64`	`wild_cards(hand TEXT, value TEXT, position INT) AS (`
`65`	`SELECT DISTINCT new_hand, substring(new_hand, pos, 1), pos`
`66`	`FROM wild_hands, generate_series(1, 5) pos`
`67`	`),`
`68`	`wild_counts(hand TEXT, value TEXT, count INT) AS (`
`69`	`SELECT hand, value, COUNT(*)`
`70`	`FROM wild_cards`
`71`	`GROUP BY hand, value`
`72`	`),`
`73`	`wild_ranked(hand TEXT, new_hand TEXT, rank INT, score TEXT) AS (`
`74`	`SELECT`
`75`	`hand,`
`76`	`new_hand,`
`77`	`CASE WHEN new_hand IN (SELECT hand FROM wild_counts WHERE count = 5) THEN 1`
`78`	`WHEN new_hand IN (SELECT hand FROM wild_counts WHERE count = 4) THEN 2`
`79`	`WHEN new_hand IN (SELECT hand FROM wild_counts WHERE count = 3)`
`80`	`AND new_hand IN (SELECT hand FROM wild_counts WHERE count = 2) THEN 3`
`81`	`WHEN new_hand IN (SELECT hand FROM wild_counts WHERE count = 3) THEN 4`
`82`	`WHEN new_hand IN (SELECT hand FROM (SELECT hand FROM wild_counts WHERE count = 2) GROUP BY hand HAVING COUNT(*) = 2) THEN 5`
`83`	`WHEN new_hand IN (SELECT hand FROM wild_counts WHERE count = 2) THEN 6`
`84`	`ELSE 7`
`85`	`END,`
`86`	`translate(hand, 'AKQT98765432J', 'ABCDEFGHIJKLM')`
`87`	`FROM`
`88`	`wild_hands`
`89`	`),`
`90`	`best_hands(hand TEXT, new_hand TEXT, rank INT, score TEXT) AS (`
`91`	`SELECT DISTINCT ON (hand) hand, new_hand, rank, score`
`92`	`FROM wild_ranked`
`93`	`ORDER BY hand, rank, score`
`94`	`),`
`95`	`wild_bids(hand TEXT, bid INT, rank INT, score TEXT) AS (`
`96`	`SELECT hands.hand, hands.bid, rank, score`
`97`	`FROM hands, best_hands`
`98`	`WHERE hands.hand = best_hands.hand`
`99`	`),`
`100`	`part2(part2 INT) AS (`
`101`	`SELECT SUM(r1.bid)`
`102`	`FROM wild_bids r1, wild_bids r2`
`103`	`WHERE r1.rank < r2.rank OR (r1.rank = r2.rank AND r1.score <= r2.score)`
`104`	`)`
`105`
`106`	`SELECT * FROM part1, part2;`
`107`

`1`	`WITH MUTUALLY RECURSIVE`
`2`
`3`	`route(step TEXT, steps INT) AS (`
`4`	`SELECT substring(input, steps, 1), steps`
`5`	`FROM steps_input, generate_series(1, length(input)) steps`
`6`	`),`
`7`
`8`	-- Part 1: Start at 'AAA` and go until `ZZZ`.
`9`	`pos1(state TEXT, steps INT) AS (`
`10`	`SELECT 'AAA', 0`
`11`	`UNION ALL`
`12`	`SELECT`
`13`	`CASE WHEN route.step = 'L' THEN paths.left`
`14`	`WHEN route.step = 'R' THEN paths.right`
`15`	`ELSE '???'`
`16`	`END,`
`17`	`pos1.steps + 1`
`18`	`FROM paths, pos1, route`
`19`	`WHERE pos1.state = paths.state`
`20`	`AND 1 + (pos1.steps % 263) = route.steps`
`21`	`AND pos1.state != 'ZZZ'`
`22`	`AND pos1.state != '???'`
`23`	`)`
`24`	`part1(part1 INT) AS (SELECT steps FROM pos1 WHERE pos1.state = 'ZZZ'),`
`25`
`26`	-- Part 2: Start at all 'A` and go until all at 'Z'
`27`	`pos2(start TEXT, state TEXT, steps INT) AS (`
`28`	`SELECT state, state, 0`
`29`	`FROM paths`
`30`	`WHERE substring(state, 3, 1) = 'A'`
`31`	`UNION ALL`
`32`	`SELECT`
`33`	`pos2.start,`
`34`	`CASE WHEN route.step = 'L' THEN paths.left`
`35`	`WHEN route.step = 'R' THEN paths.right`
`36`	`ELSE '???'`
`37`	`END,`
`38`	`pos2.steps + 1`
`39`	`FROM paths, pos2, route`
`40`	`WHERE pos2.state = paths.state`
`41`	`AND 1 + (pos2.steps % 263) = route.steps`
`42`	`AND substring(pos2.state, 3, 1) != 'Z'`
`43`	`)`
`44`
`45`	`SELECT * FROM pos2 WHERE substring(state, 3, 1) = 'Z';`
`46`

`1`	`WITH MUTUALLY RECURSIVE (RETURN AT RECURSION LIMIT 30)`
`2`
`3`	`lines (line TEXT, line_no INT) AS (`
`4`	`SELECT regexp_split_to_array(input, '\n')[i], i`
`5`	`FROM input, generate_series(1, array_length(regexp_split_to_array(input, '\n'), 1)) i`
`6`	`),`
`7`
`8`	`numbers(value INT, line_no INT, col_no INT) AS (`
`9`	`SELECT regexp_split_to_array(line, ' ')[j]::INT, line_no, j`
`10`	`FROM lines, generate_series(1, array_length(regexp_split_to_array(line, ' '), 1)) j`
`11`	`),`
`12`
`13`	`-- Contains non-zero values of differences after each round.`
`14`	`derivatives(value INT, line_no INT, col_no INT, round INT) AS (`
`15`	`SELECT numbers.*, 1`
`16`	`FROM numbers`
`17`	`UNION`
`18`	`SELECT`
`19`	`COALESCE(i2.value, 0) - COALESCE(i1.value, 0),`
`20`	`COALESCE(i1.line_no, i2.line_no),`
`21`	`COALESCE(i1.col_no + 1, i2.col_no),`
`22`	`COALESCE(i1.round, i2.round) + 1`
`23`	`FROM derivatives i1 FULL OUTER JOIN derivatives i2 ON (i1.line_no = i2.line_no AND i1.round = i2.round AND i1.col_no + 1 = i2.col_no)`
`24`	`WHERE COALESCE(i2.value, 0) - COALESCE(i1.value, 0) != 0`
`25`	`AND COALESCE(i1.col_no + 1, i2.col_no) > COALESCE(i1.round, i2.round)`
`26`	`AND COALESCE(i1.col_no + 1, i2.col_no) <= 21`
`27`	`),`
`28`
`29`	`-- Accumulate the derivatives at the leading edge`
`30`	`part1(part1 BIGINT) AS (`
`31`	`SELECT SUM(value)`
`32`	`FROM derivatives`
`33`	`WHERE col_no = 21`
`34`	`),`
`35`
`36`	`-- Accumulate the derivatives at the preceding edge`
`37`	`part2(part2 BIGINT) AS (`
`38`	`SELECT SUM(pow(-1, round + 1) * value)`
`39`	`FROM derivatives`
`40`	`WHERE col_no = round`
`41`	`)`
`42`
`43`	`-- SELECT * FROM derivatives WHERE line_no = 1 ORDER BY round, col_no;`
`44`	`SELECT * FROM part1, part2;`
`45`

`1`	`WITH MUTUALLY RECURSIVE`
`2`
`3`	`lines(line TEXT, row_no INT) AS (`
`4`	`SELECT regexp_split_to_array(input, '\n')[i], i`
`5`	`FROM input, generate_series(1, array_length(regexp_split_to_array(input, '\n'), 1)) i`
`6`	`),`
`7`
`8`	`symbols(symb TEXT, row_no INT, col_no INT) as (`
`9`	`SELECT substring(line, j, 1), row_no, j`
`10`	`FROM lines, generate_series(1, length(line)) j`
`11`	`),`
`12`
`13`	`-- Each location that is pipe has two neighbors`
`14`	`edge1(r1 INT, c1 INT, r2 INT, c2 INT) AS (`
`15`	`SELECT`
`16`	`row_no,`
`17`	`col_no,`
`18`	`CASE WHEN symb = '-' THEN row_no`
`19`	`WHEN symb = '\|' THEN row_no - 1`
`20`	`WHEN symb = 'F' THEN row_no + 1`
`21`	`WHEN symb = 'L' THEN row_no - 1`
`22`	`WHEN symb = 'J' THEN row_no`
`23`	`WHEN symb = '7' THEN row_no`
`24`	`ELSE NULL`
`25`	`END,`
`26`	`CASE WHEN symb = '-' THEN col_no - 1`
`27`	`WHEN symb = '\|' THEN col_no`
`28`	`WHEN symb = 'F' THEN col_no`
`29`	`WHEN symb = 'L' THEN col_no`
`30`	`WHEN symb = 'J' THEN col_no - 1`
`31`	`WHEN symb = '7' THEN col_no - 1`
`32`	`ELSE NULL`
`33`	`END`
`34`	`FROM symbols`
`35`	`WHERE symb != '.' AND symb != 'S'`
`36`	`),`
`37`	`edge2(r1 INT, c1 INT, r2 INT, c2 INT) AS (`
`38`	`SELECT`
`39`	`row_no,`
`40`	`col_no,`
`41`	`CASE WHEN symb = '-' THEN row_no`
`42`	`WHEN symb = '\|' THEN row_no + 1`
`43`	`WHEN symb = 'F' THEN row_no`
`44`	`WHEN symb = 'L' THEN row_no`
`45`	`WHEN symb = 'J' THEN row_no - 1`
`46`	`WHEN symb = '7' THEN row_no + 1`
`47`	`ELSE NULL`
`48`	`END,`
`49`	`CASE WHEN symb = '-' THEN col_no + 1`
`50`	`WHEN symb = '\|' THEN col_no`
`51`	`WHEN symb = 'F' THEN col_no + 1`
`52`	`WHEN symb = 'L' THEN col_no + 1`
`53`	`WHEN symb = 'J' THEN col_no`
`54`	`WHEN symb = '7' THEN col_no`
`55`	`ELSE NULL`
`56`	`END`
`57`	`FROM symbols`
`58`	`WHERE symb != '.' AND symb != 'S'`
`59`	`),`
`60`	`-- Symmetrized graph`
`61`	`symm(r1 INT, c1 INT, r2 INT, c2 INT) AS (`
`62`	`SELECT r1, c1, r2, c2`
`63`	`FROM (`
`64`	`SELECT * FROM edge1`
`65`	`UNION ALL`
`66`	`SELECT * FROM edge2`
`67`	`UNION ALL`
`68`	`SELECT r2, c2, r1, c1 FROM edge1`
`69`	`UNION ALL`
`70`	`SELECT r2, c2, r1, c1 FROM edge2`
`71`	`UNION ALL`
`72`	`SELECT row_no, col_no, row_no + 1, col_no FROM symbols WHERE symb = 'S'`
`73`	`UNION ALL`
`74`	`SELECT row_no, col_no, row_no, col_no + 1 FROM symbols WHERE symb = 'S'`
`75`	`UNION ALL`
`76`	`SELECT row_no, col_no, row_no - 1, col_no FROM symbols WHERE symb = 'S'`
`77`	`UNION ALL`
`78`	`SELECT row_no, col_no, row_no, col_no - 1 FROM symbols WHERE symb = 'S'`
`79`	`)`
`80`	`GROUP BY r1, c1, r2, c2`
`81`	`HAVING COUNT(*) = 2`
`82`	`),`
`83`	`reach(r INT, c INT) AS (`
`84`	`SELECT row_no, col_no`
`85`	`FROM symbols`
`86`	`WHERE symb = 'S'`
`87`	`UNION`
`88`	`SELECT r2, c2`
`89`	`FROM reach, symm`
`90`	`WHERE r = r1 AND c = c1`
`91`	`),`
`92`	`part1(part1 BIGINT) AS (`
`93`	`SELECT COUNT(*)/2 FROM reach`
`94`	`),`
`95`
`96`	`-- Part 2: how many cells are inside the loop?`
`97`	`-- All (1, ) and (, 1) cells have their upper left outside the loop (outer edge of the diagram).`
`98`	`-- Each cell inherits from its UL neighbor, toggled by any pipe except '7' and 'L' pipe.`
`99`	`-- Rewrite the pipe to have symbols, and resolve 'S' to actual oriented pipe.`
`100`	`pipe(r INT, c INT, symb TEXT) AS (`
`101`	`SELECT r, c, symb`
`102`	`FROM reach, symbols`
`103`	`WHERE r = row_no AND c = col_no AND symb != 'S'`
`104`	`UNION`
`105`	`SELECT`
`106`	`row_no,`
`107`	`col_no,`
`108`	`CASE WHEN row_no = s1.r1 AND col_no = s1.c1 + 1 AND row_no = s2.r2 + 1 AND col_no = s2.c2 THEN 'J' -- toggle`
`109`	`WHEN row_no = s1.r1 AND col_no = s1.c1 + 1 AND row_no = s2.r2 AND col_no = s2.c2 - 1 THEN '-' -- toggle`
`110`	`WHEN row_no = s1.r1 AND col_no = s1.c1 + 1 AND row_no = s2.r2 - 1 AND col_no = s2.c2 THEN '7' -- no toggle`
`111`	`WHEN row_no = s1.r1 + 1 AND col_no = s1.c1 AND row_no = s2.r2 AND col_no = s2.c2 - 1 THEN 'L' -- no toggle`
`112`	`WHEN row_no = s1.r1 + 1 AND col_no = s1.c1 AND row_no = s2.r2 - 1 AND col_no = s2.c2 THEN '\|' -- toggle`
`113`	`WHEN row_no = s1.r1 AND col_no = s1.c1 - 1 AND row_no = s2.r2 AND col_no = s2.c2 - 1 THEN 'F' -- toggle`
`114`	`ELSE '???'`
`115`	`END`
`116`	`FROM symbols, symm s1, symm s2`
`117`	`WHERE symb = 'S'`
`118`	`AND row_no = s1.r1`
`119`	`AND col_no = s1.c1`
`120`	`AND row_no = s2.r1`
`121`	`AND col_no = s2.c1`
`122`	`),`
`123`	`-- Enclosed(1,) and Enclosed(,1) are all false.`
`124`	`-- Enclosed(x+1,y+1) = Enclosed(x,y) perhaps toggled by pipe(x,y)`
`125`	`status(r INT, c INT, encl BOOL) AS (`
`126`	`SELECT row_no, col_no, false`
`127`	`FROM symbols`
`128`	`WHERE row_no = 1 OR col_no = 1`
`129`	`UNION`
`130`	`SELECT`
`131`	`row_no + 1,`
`132`	`col_no + 1,`
`133`	`CASE WHEN pipe.symb IN (VALUES ('J'),('-'),('\|'),('F')) THEN NOT encl`
`134`	`ELSE encl`
`135`	`END`
`136`	`FROM status LEFT JOIN pipe ON (status.r = pipe.r AND status.c = pipe.c)`
`137`	`JOIN symbols ON (status.r = symbols.row_no AND status.c = symbols.col_no)`
`138`	`),`
`139`	`part2(part2 BIGINT) AS (`
`140`	`SELECT COUNT(*)`
`141`	`FROM status`
`142`	`WHERE encl = true AND (r, c) NOT IN (SELECT r, c FROM pipe)`
`143`	`)`
`144`
`145`	`SELECT * FROM part1, part2;`
`146`

`1`	`WITH MUTUALLY RECURSIVE`
`2`
`3`	`lines(line TEXT, r INT) AS (`
`4`	`SELECT regexp_split_to_array(input, '\n')[i], i`
`5`	`FROM input, generate_series(1, array_length(regexp_split_to_array(input, '\n'), 1)) i`
`6`	`),`
`7`
`8`	`symbols(symb TEXT, r INT, c INT) as (`
`9`	`SELECT substring(line, j, 1), r, j`
`10`	`FROM lines, generate_series(1, length(line)) j`
`11`	`),`
`12`
`13`	`row_gaps(r INT) AS (`
`14`	`SELECT r`
`15`	`FROM symbols`
`16`	`GROUP BY r`
`17`	`HAVING COUNT(*) FILTER (WHERE symb = '#') = 0`
`18`	`),`
`19`
`20`	`col_gaps(c INT) AS (`
`21`	`SELECT c`
`22`	`FROM symbols`
`23`	`GROUP BY c`
`24`	`HAVING COUNT(*) FILTER (WHERE symb = '#') = 0`
`25`	`),`
`26`
`27`	`-- Part1: Expand space and restrict to galaxies`
`28`	`galaxies(r INT, c INT) AS (`
`29`	`SELECT`
`30`	`r + (SELECT COUNT(*) FROM row_gaps WHERE row_gaps.r < symbols.r),`
`31`	`c + (SELECT COUNT(*) FROM col_gaps WHERE col_gaps.c < symbols.c)`
`32`	`FROM symbols`
`33`	`WHERE symb = '#'`
`34`	`),`
`35`	`-- Sum of L1 distance between distinct galaxies`
`36`	`part1(part1 BIGINT) AS (`
`37`	`SELECT SUM(ABS(g1.r - g2.r) + ABS(g1.c - g2.c))`
`38`	`FROM galaxies g1, galaxies g2`
`39`	`WHERE g1.r < g2.r`
`40`	`OR (g1.r = g2.r AND g1.c < g2.c)`
`41`	`)`
`42`
`43`	`-- Part2: Expand space MORE and restrict to galaxies`
`44`	`galaxies2(r INT, c INT) AS (`
`45`	`SELECT`
`46`	`r + 999999 * (SELECT COUNT(*) FROM row_gaps WHERE row_gaps.r < symbols.r),`
`47`	`c + 999999 * (SELECT COUNT(*) FROM col_gaps WHERE col_gaps.c < symbols.c)`
`48`	`FROM symbols`
`49`	`WHERE symb = '#'`
`50`	`),`
`51`	`-- Sum of L1 distance between distinct galaxies`
`52`	`part2(part2 BIGINT) AS (`
`53`	`SELECT SUM(ABS(g1.r - g2.r) + ABS(g1.c - g2.c))`
`54`	`FROM galaxies2 g1, galaxies2 g2`
`55`	`WHERE g1.r < g2.r`
`56`	`OR (g1.r = g2.r AND g1.c < g2.c)`
`57`	`)`
`58`
`59`	`SELECT * FROM part1, part2;`
`60`

`1`	`WITH MUTUALLY RECURSIVE`
`2`
`3`	`lines(r INT, characters TEXT, springs TEXT) AS (`
`4`	`SELECT`
`5`	`row_id,`
`6`	`regexp_split_to_array(regexp_split_to_array(input, '\n')[row_id], ' ')[1] \|\| '.',`
`7`	`regexp_split_to_array(regexp_split_to_array(input, '\n')[row_id], ' ')[2]`
`8`	`FROM`
`9`	`input,`
`10`	`generate_series(1, array_length(regexp_split_to_array(input, '\n'), 1)) row_id`
`11`	`),`
`12`	`characters(r INT, pos INT, symb TEXT) AS (`
`13`	`SELECT`
`14`	`r,`
`15`	`pos,`
`16`	`substring(characters, pos, 1)`
`17`	`FROM`
`18`	`lines,`
`19`	`generate_series(1, length(characters)) pos`
`20`	`),`
`21`	`springs(r INT, pos INT, len INT) AS (`
`22`	`SELECT`
`23`	`r,`
`24`	`pos,`
`25`	`regexp_split_to_array(springs, ',')[pos]::INT`
`26`	`FROM`
`27`	`lines,`
`28`	`generate_series(1, array_length(regexp_split_to_array(springs, ','), 1)) pos`
`29`	`),`
`30`
`31`	-- How many ways can we pack row `r`'s first `spring` springs (plus a space) into the first `chars` characters?
`32`	`-- Importantly, the "plus a space" applies to the last spring also! Each of these should admit the immediate appending of a new spring.`
`33`	`fits(r INT, chars INT, spring INT) AS (`
`34`	`-- We can pack no springs into no characters.`
`35`	`SELECT r, 0, 0`
`36`	`FROM lines`
`37`	`-- We can extend any fits with a blank, as long as there are no '#' observations.`
`38`	`UNION ALL`
`39`	`SELECT fits.r, fits.chars + 1, fits.spring`
`40`	`FROM fits, characters`
`41`	`WHERE fits.r = characters.r`
`42`	`AND fits.chars + 1 = characters.pos`
`43`	`AND characters.symb != '#'`
`44`	`-- We can extend any fits with the next spring and a blank, as long as no '.' in the spring and no '#' in the blank.`
`45`	`UNION ALL`
`46`	`SELECT fits.r, fits.chars + springs.len + 1, fits.spring + 1`
`47`	`FROM`
`48`	`fits,`
`49`	`springs,`
`50`	`characters`
`51`	`WHERE fits.r = springs.r`
`52`	`AND fits.spring + 1 = springs.pos`
`53`	`AND fits.r = characters.r`
`54`	`AND fits.chars + springs.len + 1 = characters.pos`
`55`	`AND characters.symb != '#'`
`56`	`AND NOT EXISTS (SELECT FROM characters c WHERE c.r = fits.r AND c.symb = '.' AND c.pos BETWEEN fits.chars + 1 AND fits.chars + springs.len)`
`57`	`),`
`58`
`59`	`fit_counts(r INT, chars INT, spring INT, count BIGINT) AS (`
`60`	`SELECT r, chars, spring, COUNT(*) AS count`
`61`	`FROM fits`
`62`	`GROUP BY r, chars, spring`
`63`	`),`
`64`	`counts(r INT, chars INT, spring INT, count BIGINT) AS (`
`65`	`SELECT DISTINCT ON (r) r, chars, spring, count`
`66`	`FROM fit_counts`
`67`	`ORDER BY r, chars DESC, spring DESC`
`68`	`),`
`69`
`70`	`potato (x INT) AS ( SELECT 1 )`
`71`
`72`	`SELECT SUM(count) FROM counts;`
`73`

`1`	`WITH MUTUALLY RECURSIVE`
`2`
`3`	`blocks(b INT, block TEXT) AS (`
`4`	`SELECT b, regexp_split_to_array(input, '\n\n')[b] as block`
`5`	`FROM input, generate_series(1, array_length(regexp_split_to_array(input, '\n\n'), 1)) b`
`6`	`),`
`7`	`lines(b INT, r INT, line TEXT) AS (`
`8`	`SELECT b, r, regexp_split_to_array(block, '\n')[r] as block`
`9`	`FROM blocks, generate_series(1, array_length(regexp_split_to_array(block, '\n'), 1)) r`
`10`	`),`
`11`	`cells(b INT, r INT, c INT, symbol TEXT) AS (`
`12`	`SELECT b, r, c, substring(line, c, 1)`
`13`	`FROM lines, generate_series(1, length(line)) c`
`14`	`),`
`15`	`columns(b INT, c INT, column TEXT) AS (`
`16`	`SELECT b, c, string_agg(symbol, '' ORDER BY r) FROM cells GROUP BY b, c`
`17`	`),`
`18`
`19`	`row_mirror(b INT, r INT) AS (`
`20`	`SELECT *`
`21`	`FROM (SELECT DISTINCT b, r FROM cells) o`
`22`	`WHERE NOT EXISTS (`
`23`	`-- We would be upset to find rows at mirrored positions that do not match`
`24`	`-- Rows that match, or have no mirrored position, are fine.`
`25`	`SELECT FROM lines`
`26`	`WHERE o.b = lines.b`
`27`	`GROUP BY abs(2 * lines.r - (2 * o.r - 1))`
`28`	`HAVING COUNT(DISTINCT lines.line) > 1`
`29`	`)`
`30`	`),`
`31`
`32`	`col_mirror(b INT, c INT) AS (`
`33`	`SELECT *`
`34`	`FROM (SELECT DISTINCT b, c FROM cells) o`
`35`	`WHERE NOT EXISTS (`
`36`	`-- We would be upset to find rows at mirrored positions that do not match`
`37`	`-- Rows that match, or have no mirrored position, are fine.`
`38`	`SELECT FROM columns`
`39`	`WHERE o.b = columns.b`
`40`	`GROUP BY abs(2 * columns.c - (2 * o.c - 1))`
`41`	`HAVING COUNT(DISTINCT columns.column) > 1`
`42`	`)`
`43`	`),`
`44`
`45`	`part1(part1 BIGINT) AS (`
`46`	`SELECT COALESCE((SELECT SUM(r-1) FROM row_mirror), 0) * 100`
`47`	`+ COALESCE((SELECT SUM(c-1) FROM col_mirror), 0)`
`48`	`),`
`49`
`50`	`row_mirror2(b INT, r INT) AS (`
`51`	`SELECT *`
`52`	`FROM (SELECT DISTINCT b, r FROM cells) o`
`53`	`WHERE 1 = (`
`54`	`SELECT COUNT(*)`
`55`	`FROM cells c1, cells c2`
`56`	`WHERE abs(2 * c1.r - (2 * o.r - 1)) = abs(2 * c2.r - (2 * o.r - 1))`
`57`	`AND c1.r < c2.r`
`58`	`AND c1.c = c2.c`
`59`	`AND c1.b = c2.b`
`60`	`AND c1.b = o.b`
`61`	`AND c1.symbol != c2.symbol`
`62`	`)`
`63`	`),`
`64`
`65`	`col_mirror2(b INT, c INT) AS (`
`66`	`SELECT *`
`67`	`FROM (SELECT DISTINCT b, c FROM cells) o`
`68`	`WHERE 1 = (`
`69`	`SELECT COUNT(*)`
`70`	`FROM cells c1, cells c2`
`71`	`WHERE abs(2 * c1.c - (2 * o.c - 1)) = abs(2 * c2.c - (2 * o.c - 1))`
`72`	`AND c1.c < c2.c`
`73`	`AND c1.r = c2.r`
`74`	`AND c1.b = c2.b`
`75`	`AND c1.b = o.b`
`76`	`AND c1.symbol != c2.symbol`
`77`	`)`
`78`	`),`
`79`
`80`	`part2(part2 BIGINT) AS (`
`81`	`SELECT COALESCE((SELECT SUM(r-1) FROM row_mirror2), 0) * 100`
`82`	`+ COALESCE((SELECT SUM(c-1) FROM col_mirror2), 0)`
`83`	`),`
`84`
`85`	`potato (x INT) AS ( SELECT 1 )`
`86`
`87`	`SELECT * FROM part1, part2;`
`88`

`1`	`WITH MUTUALLY RECURSIVE`
`2`
`3`	`lines(r INT, line TEXT) AS (`
`4`	`SELECT r, regexp_split_to_array(input, '\n')[r] as block`
`5`	`FROM input, generate_series(1, array_length(regexp_split_to_array(input, '\n'), 1)) r`
`6`	`),`
`7`	`cells(r INT, c INT, symbol TEXT) AS (`
`8`	`SELECT r, c, substring(line, c, 1)`
`9`	`FROM lines, generate_series(1, length(line)) c`
`10`	`),`
`11`
`12`	`northward(r INT, c INT, symbol TEXT) AS (`
`13`	`SELECT * FROM northward`
`14`	`-- Anyone on the move does so`
`15`	`UNION ALL SELECT r - 1, c, 'O' FROM north_move`
`16`	`EXCEPT ALL SELECT r - 1, c, '.' FROM north_move`
`17`	`UNION ALL SELECT r, c, '.' FROM north_move`
`18`	`EXCEPT ALL SELECT r, c, 'O' FROM north_move`
`19`	`-- Initial state is cells, but not refreshed each round.`
`20`	`UNION ALL SELECT * FROM cells`
`21`	`EXCEPT ALL SELECT * FROM cells_delay`
`22`	`),`
`23`
`24`	`-- Each 'O' with a '.' to the north will move.`
`25`	`north_move(r INT, c INT) AS (`
`26`	`SELECT n1.r, n1.c`
`27`	`FROM northward n1, northward n2`
`28`	`WHERE n1.symbol = 'O'`
`29`	`AND n1.r = n2.r + 1`
`30`	`AND n1.c = n2.c`
`31`	`AND n2.symbol = '.'`
`32`	`),`
`33`
`34`	`part1(part1 BIGINT) AS (`
`35`	`SELECT SUM(1 + (SELECT MAX(r) FROM lines) - r)`
`36`	`FROM northward`
`37`	`WHERE symbol = 'O'`
`38`	`),`
`39`
`40`	`output (r INT, line TEXT) AS (`
`41`	`SELECT r, string_agg(symbol, ' ' ORDER BY c)`
`42`	`FROM northward`
`43`	`GROUP BY r`
`44`	`),`
`45`
`46`	`cells_delay(r INT, c INT, symbol TEXT) AS ( SELECT * FROM cells )`
`47`
`48`	`SELECT * FROM part1;`
`49`

`1`	`WITH MUTUALLY RECURSIVE (RETURN AT RECURSION LIMIT 10)`
`2`
`3`	`strings(r INT, string TEXT) AS (`
`4`	`SELECT r, regexp_split_to_array(input, ',')[r]`
`5`	`FROM input, generate_series(1, array_length(regexp_split_to_array(input, ','), 1)) r`
`6`	`),`
`7`
`8`	`-- Advance the hash by one character, until all strings are empty.`
`9`	`hashes(string TEXT, hash BIGINT) AS (`
`10`	`SELECT string, 0 as hash`
`11`	`FROM strings`
`12`	`UNION ALL`
`13`	`SELECT substring(string, 2), ((hash + ascii(substring(string, 1, 1))) * 17) % 256`
`14`	`FROM hashes`
`15`	`WHERE length(string) > 0`
`16`	`),`
`17`
`18`	`part1(part1 BIGINT) AS (`
`19`	`SELECT SUM(hash)`
`20`	`FROM hashes`
`21`	`WHERE string = ''`
`22`	`),`
`23`
`24`	-- Parse strings as symbol plus commands; either `-` or `=X`.
`25`	`commands(r INT, symb TEXT, op INT) AS (`
`26`	`SELECT`
`27`	`r,`
`28`	`CASE WHEN substring(string, length(string)) = '-'`
`29`	`THEN substring(string, 1, length(string)-1)`
`30`	`ELSE substring(string, 1, length(string)-2)`
`31`	`END,`
`32`	`CASE WHEN substring(string, length(string)) = '-'`
`33`	`THEN 0`
`34`	`ELSE substring(string, length(string))::INT`
`35`	`END`
`36`	`FROM strings`
`37`	`),`
`38`	`-- Operations that happen after a symbol's last delete operation.`
`39`	`-- All other operations do not matter, and do not affect the state.`
`40`	`final_ops(r INT, symb TEXT, op INT) AS (`
`41`	`SELECT *`
`42`	`FROM commands`
`43`	`WHERE r > COALESCE(`
`44`	`(SELECT MAX(r)`
`45`	`FROM commands c2`
`46`	`WHERE commands.symb = c2.symb`
`47`	`AND c2.op = 0), 0)`
`48`	`),`
`49`	`-- Each symbol is summarized by their first final insert time, and the last final operation`
`50`	`final_state(r INT, symb TEXT, op INT) AS (`
`51`	`SELECT DISTINCT ON(symb)`
`52`	`(SELECT MIN(r) FROM final_ops fo2 WHERE fo2.symb = final_ops.symb),`
`53`	`symb,`
`54`	`op`
`55`	`FROM final_ops`
`56`	`ORDER BY symb, r DESC, op`
`57`	`),`
`58`	`-- Redo the hash computation on symbols rather than commands.`
`59`	`hashes2(start TEXT, string TEXT, hash BIGINT) AS (`
`60`	`SELECT symb as start, symb as string, 0 as hash`
`61`	`FROM final_state`
`62`	`UNION ALL`
`63`	`SELECT start, substring(string, 2), ((hash + ascii(substring(string, 1, 1))) * 17) % 256`
`64`	`FROM hashes2`
`65`	`WHERE length(string) > 0`
`66`	`),`
`67`	`-- Bin up the state, so's we can tabulate it`
`68`	`binned(hash BIGINT, r INT, symb TEXT, op INT) AS (`
`69`	`SELECT hash, final_state.*`
`70`	`FROM hashes2, final_state`
`71`	`WHERE hashes2.start = symb`
`72`	`AND hashes2.string = ''`
`73`	`),`
`74`	`-- Sum the product of 1 + hash, the position in bin by r, and the op.`
`75`	`part2(part2 BIGINT) AS (`
`76`	`SELECT SUM(`
`77`	`(1 + hash) *`
`78`	`(SELECT COUNT() FROM binned b2 WHERE binned.hash = b2.hash AND binned.r >= b2.r) `
`79`	`op`
`80`	`)`
`81`	`FROM binned`
`82`	`),`
`83`
`84`	`potato(x int) as (select 1)`
`85`
`86`	`SELECT * FROM part1, part2;`
`87`

`1`	`WITH MUTUALLY RECURSIVE`
`2`
`3`	`blocks(block1 TEXT, block2 TEXT) AS (`
`4`	`SELECT`
`5`	`regexp_split_to_array(input, '\n\n')[1] block1,`
`6`	`regexp_split_to_array(input, '\n\n')[2] block2`
`7`	`FROM input`
`8`	`),`
`9`	`states(state TEXT, trans TEXT) AS (`
`10`	`SELECT`
`11`	`regexp_split_to_array(line, '\{')[1] state,`
`12`	`trim('}' FROM regexp_split_to_array(line, '\{')[2]) trans`
`13`	`FROM (SELECT regexp_split_to_table(block1, '\n') line FROM blocks)`
`14`	`),`
`15`	`steps(state TEXT, priority INT, rule TEXT) AS (`
`16`	`SELECT`
`17`	`state,`
`18`	`priority,`
`19`	`regexp_split_to_array(trans, ',')[priority]`
`20`	`FROM states, generate_series(1, array_length(regexp_split_to_array(trans, ','), 1)) priority`
`21`	`),`
`22`
`23`	`starts(x INT, m INT, a INT, s INT) AS (`
`24`	`SELECT`
`25`	`substring(regexp_split_to_array(trimmed, ',')[1], 3)::INT,`
`26`	`substring(regexp_split_to_array(trimmed, ',')[2], 3)::INT,`
`27`	`substring(regexp_split_to_array(trimmed, ',')[3], 3)::INT,`
`28`	`substring(regexp_split_to_array(trimmed, ',')[4], 3)::INT`
`29`	`FROM (SELECT trim('\{' FROM trim('\}' FROM regexp_split_to_table(block2, '\n'))) trimmed FROM blocks)`
`30`	`),`
`31`
`32`	`--`
`33`	`rules(state TEXT, priority INT, field TEXT, cmp TEXT, val INT, next TEXT) AS (`
`34`	`SELECT`
`35`	`state,`
`36`	`priority,`
`37`	`CASE WHEN substring(rule, 2, 1) = '<' OR substring(rule, 2, 1) = '>'`
`38`	`THEN substring(rule, 1, 1)`
`39`	`ELSE 'x'`
`40`	`END,`
`41`	`CASE WHEN substring(rule, 2, 1) = '<' OR substring(rule, 2, 1) = '>'`
`42`	`THEN substring(rule, 2, 1)`
`43`	`ELSE '>'`
`44`	`END,`
`45`	`CASE WHEN substring(rule, 2, 1) = '<' OR substring(rule, 2, 1) = '>'`
`46`	`THEN regexp_split_to_array(substring(rule, 3), ':')[1]::INT`
`47`	`ELSE '0'`
`48`	`END,`
`49`	`CASE WHEN substring(rule, 2, 1) = '<' OR substring(rule, 2, 1) = '>'`
`50`	`THEN regexp_split_to_array(substring(rule, 3), ':')[2]`
`51`	`ELSE rule`
`52`	`END`
`53`	`FROM steps`
`54`	`),`
`55`
`56`	-- PART 1: iterate folks forward from `in`
`57`	`movement(state TEXT, x INT, m INT, a INT, s INT) AS (`
`58`	`SELECT 'in' state, * FROM starts`
`59`	`UNION ALL`
`60`	`SELECT next, x, m, a, s`
`61`	`FROM (`
`62`	`SELECT DISTINCT ON (state, x, m, a, s) state, x, m, a, s, priority, next`
`63`	`FROM (`
`64`	`SELECT movement.*, rules.next, rules.priority`
`65`	`FROM movement, rules`
`66`	`WHERE movement.state = rules.state`
`67`	`AND CASE WHEN rules.cmp = '<'`
`68`	`THEN CASE WHEN rules.field = 'x' THEN x < val`
`69`	`WHEN rules.field = 'm' THEN m < val`
`70`	`WHEN rules.field = 'a' THEN a < val`
`71`	`WHEN rules.field = 's' THEN s < val`
`72`	`ELSE false`
`73`	`END`
`74`	`WHEN rules.cmp = '>'`
`75`	`THEN CASE WHEN rules.field = 'x' THEN x > val`
`76`	`WHEN rules.field = 'm' THEN m > val`
`77`	`WHEN rules.field = 'a' THEN a > val`
`78`	`WHEN rules.field = 's' THEN s > val`
`79`	`ELSE false`
`80`	`END`
`81`	`ELSE false`
`82`	`END`
`83`	`)`
`84`	`ORDER BY state, x, m, a, s, priority`
`85`	`)`
`86`	`),`
`87`
`88`	`part1(part1 BIGINT) AS (`
`89`	`SELECT SUM(x + m + a + s)`
`90`	`FROM movement`
`91`	`WHERE state = 'A'`
`92`	`),`
`93`
`94`	`-- PART 2: just find all the bounding regions and label them 'A' or 'R'.`
`95`	`region(state TEXT, priority INT, xl INT, xu INT, ml INT, mu INT, al INT, au INT, sl INT, su INT) AS (`
`96`	`SELECT 'in', 1, 1, 4000, 1, 4000, 1, 4000, 1, 4000`
`97`	`-- Could satisfy the rule, and transition to the next state ..`
`98`	`UNION ALL`
`99`	`SELECT`
`100`	`next,`
`101`	`1,`
`102`	`CASE WHEN rules.field = 'x' AND rules.cmp = '>' THEN GREATEST(val+1, xl) ELSE xl END,`
`103`	`CASE WHEN rules.field = 'x' AND rules.cmp = '<' THEN LEAST(val-1, xu) ELSE xu END,`
`104`	`CASE WHEN rules.field = 'm' AND rules.cmp = '>' THEN GREATEST(val+1, ml) ELSE ml END,`
`105`	`CASE WHEN rules.field = 'm' AND rules.cmp = '<' THEN LEAST(val-1, mu) ELSE mu END,`
`106`	`CASE WHEN rules.field = 'a' AND rules.cmp = '>' THEN GREATEST(val+1, al) ELSE al END,`
`107`	`CASE WHEN rules.field = 'a' AND rules.cmp = '<' THEN LEAST(val-1, au) ELSE au END,`
`108`	`CASE WHEN rules.field = 's' AND rules.cmp = '>' THEN GREATEST(val+1, sl) ELSE sl END,`
`109`	`CASE WHEN rules.field = 's' AND rules.cmp = '<' THEN LEAST(val-1, su) ELSE su END`
`110`	`FROM region, rules`
`111`	`WHERE region.state = rules.state`
`112`	`AND region.priority = rules.priority`
`113`	`-- .. or could fail the rule, and advance to the next priority.`
`114`	`UNION ALL`
`115`	`SELECT`
`116`	`region.state,`
`117`	`region.priority + 1,`
`118`	`CASE WHEN rules.field = 'x' AND rules.cmp = '<' THEN GREATEST(val, xl) ELSE xl END,`
`119`	`CASE WHEN rules.field = 'x' AND rules.cmp = '>' THEN LEAST(val, xu) ELSE xu END,`
`120`	`CASE WHEN rules.field = 'm' AND rules.cmp = '<' THEN GREATEST(val, ml) ELSE ml END,`
`121`	`CASE WHEN rules.field = 'm' AND rules.cmp = '>' THEN LEAST(val, mu) ELSE mu END,`
`122`	`CASE WHEN rules.field = 'a' AND rules.cmp = '<' THEN GREATEST(val, al) ELSE al END,`
`123`	`CASE WHEN rules.field = 'a' AND rules.cmp = '>' THEN LEAST(val, au) ELSE au END,`
`124`	`CASE WHEN rules.field = 's' AND rules.cmp = '<' THEN GREATEST(val, sl) ELSE sl END,`
`125`	`CASE WHEN rules.field = 's' AND rules.cmp = '>' THEN LEAST(val, su) ELSE su END`
`126`	`FROM region, rules`
`127`	`WHERE region.state = rules.state`
`128`	`AND region.priority = rules.priority`
`129`	`),`
`130`
`131`	`part2(part2 NUMERIC) AS (`
`132`	`SELECT SUM((1 + xu - xl)::BIGINT * (1 + mu - ml)::BIGINT * (1 + au - al)::BIGINT * (1 + su - sl)::BIGINT)`
`133`	`FROM region`
`134`	`WHERE state = 'A'`
`135`	`),`
`136`
`137`	`potato(x INT) AS (SELECT 1)`
`138`
`139`	`SELECT * FROM part1, part2;`
`140`

`1`	`WITH MUTUALLY RECURSIVE`
`2`
`3`	`lines(line TEXT) AS ( SELECT regexp_split_to_table(input, '\n') FROM input ),`
`4`	`links(name TEXT, link TEXT) AS (`
`5`	`SELECT`
`6`	`substring(regexp_split_to_array(line, ' ')[1], 2),`
`7`	`trim(',' FROM regexp_split_to_array(line, ' ')[x])`
`8`	`FROM`
`9`	`lines, generate_series(3, array_length(regexp_split_to_array(line, ' '), 1)) x`
`10`	`),`
`11`	`-- One special line has op 'b' and name 'roadcaster'.`
`12`	`types(op TEXT, name TEXT) AS (`
`13`	`SELECT`
`14`	`substring(regexp_split_to_array(line, ' ')[1], 1, 1),`
`15`	`substring(regexp_split_to_array(line, ' ')[1], 2)`
`16`	`FROM`
`17`	`lines`
`18`	`),`
`19`
`20`	`-- Part one: simulate 1000 steps of 'broadcaster' being activated with a low pulse.`
`21`	`-- tally up total low and high pulses, and then multiply.`
`22`	`-- The state carried across steps are the last-transmitted pulses of each operator.`
`23`	-- This should also tell us the final state of the `%` operators.
`24`	`-- We'll also need the totals of low and high pulses, so that we can add them up.`
`25`
`26`	`seed(press INT, counter INT) AS (`
`27`	`SELECT 1, 1`
`28`	`UNION`
`29`	`SELECT press, counter - 1`
`30`	`FROM seed`
`31`	`WHERE counter > 0`
`32`	`UNION`
`33`	`SELECT press + 1, 20`
`34`	`FROM seed`
`35`	`WHERE counter = 0`
`36`	`AND press < 4100`
`37`	`),`
`38`
`39`	`-- Emitted pulses after various button presses, in various rounds of resolution.`
`40`	`pulses(name TEXT, press INT, round INT, pulse TEXT) AS (`
`41`	`-- One thousand button presses, each followed by rounds of resolution.`
`42`	`SELECT 'roadcaster', press, 1, 'lo' FROM seed WHERE counter = 0`
`43`	`UNION ALL SELECT * FROM flip`
`44`	`UNION ALL SELECT * FROM conj`
`45`	`),`
`46`
`47`	`-- Counters; every 'lo' input pulse flips and emits the state.`
`48`	`flip(name TEXT, press INT, round INT, pulse TEXT) AS (`
`49`	-- Each `signal` needs to behave as if all "prior" signals have been processed, ordered by (press, round, source).
`50`	`SELECT`
`51`	`name,`
`52`	`press,`
`53`	`round + 1,`
`54`	`-- Look for the most recently emitted signal, and we'll produce the opposite of that one.`
`55`	`CASE WHEN (`
`56`	`SELECT COUNT(*)`
`57`	`FROM signal s1`
`58`	`WHERE s1.target = types.name`
`59`	`AND s1.pulse = 'lo'`
`60`	`AND ((s1.press < signal.press) OR`
`61`	`(s1.press = signal.press AND s1.round < signal.round) OR`
`62`	`(s1.press = signal.press AND s1.round = signal.round AND s1.source < signal.source))`
`63`	`) % 2 = 0`
`64`	`THEN 'hi'`
`65`	`ELSE 'lo'`
`66`	`END`
`67`	`FROM signal, types`
`68`	`WHERE signal.target = types.name`
`69`	`AND types.op = '%'`
`70`	`AND signal.pulse = 'lo'`
`71`	`),`
`72`
`73`	`-- NAND gates; every input pulse evokes the NAND of most recent inputs.`
`74`	`conj(name TEXT, press INT, round INT, pulse TEXT) AS (`
`75`	`SELECT`
`76`	`name,`
`77`	`press,`
`78`	`round + 1,`
`79`	`-- Look for the most recently received signals from each input,`
`80`	`-- including this one, and iff all 'hi' then 'lo'.`
`81`	`CASE WHEN (`
`82`	`(SELECT COUNT(*) FROM links WHERE link = types.name)`
`83`	`=`
`84`	`(SELECT COUNT(*) FROM (`
`85`	`SELECT DISTINCT ON (source) source, pulse`
`86`	`FROM signal s1`
`87`	`WHERE s1.target = types.name`
`88`	`AND ((s1.press < signal.press) OR`
`89`	`(s1.press = signal.press AND s1.round < signal.round) OR`
`90`	`(s1.press = signal.press AND s1.round = signal.round AND s1.source <= signal.source))`
`91`	`OPTIONS (DISTINCT ON INPUT GROUP SIZE = 1000)`
`92`	`ORDER BY source, press DESC, round DESC`
`93`	`)`
`94`	`WHERE pulse = 'hi'))`
`95`	`THEN 'lo'`
`96`	`ELSE 'hi'`
`97`	`END`
`98`	`FROM signal, types`
`99`	`WHERE signal.target = types.name`
`100`	`AND types.op = '&'`
`101`	`),`
`102`
`103`	`-- A record of a pulse into an operator, from another operator.`
`104`	`-- We track the source so that '&' operators can make any sense.`
`105`	`signal(source TEXT, target TEXT, press INT, round INT, pulse TEXT) AS (`
`106`	`SELECT pulses.name, links.link, pulses.press, pulses.round, pulses.pulse`
`107`	`FROM pulses, links`
`108`	`WHERE pulses.name = links.name`
`109`	`AND pulses.round > 0`
`110`	`),`
`111`
`112`	`part1(pulse TEXT, count BIGINT) AS (`
`113`	`SELECT pulse, count(*) FROM signal GROUP BY pulse`
`114`	`),`
`115`
`116`	`potato(x INT) AS (SELECT 1)`
`117`
`118`	`SELECT * FROM signal WHERE target = 'cn' AND pulse = 'hi';`
`119`