Advent of Code 2020, Day 13 in Postgresql

day-13.sql

CREATE TEMP TABLE input (lineno SERIAL, line TEXT);

--\copy input (line) FROM '13-test-input.txt';
\copy input (line) FROM '13-input.txt';

CREATE TEMP TABLE arrivals(arrival_time) AS
SELECT line::int FROM input WHERE lineno = 1;

CREATE TEMP TABLE bus_lines AS
SELECT column_,
       cell::BIGINT AS bus_id,
       ROW_NUMBER() OVER () AS i
FROM input
JOIN UNNEST(regexp_split_to_array(input.line, ','))
     WITH ORDINALITY _(cell, column_) ON TRUE
WHERE lineno = 2 AND cell != 'x';

WITH bus_arrivals AS (
  SELECT bus_id - MOD(arrival_time, bus_id) AS in_minutes,
         bus_id
  FROM arrivals, bus_lines
)
SELECT bus_id * in_minutes AS answer_1
FROM bus_arrivals
ORDER BY in_minutes ASC
LIMIT 1;

-- This was a big mistake; I spent incredible amounts of time hunting for a
-- bug in my logic when I was actually using inaccurate congruence system
-- period due to using floating points here. I should have know better.
/*
CREATE TEMP TABLE period AS
SELECT ROUND(EXP(SUM(LN(bus_id))))::bigint AS period,
       EXP(SUM(LN(bus_id))) AS period_d,
       MAX(column_) AS max_column
FROM bus_lines;
*/

CREATE TEMP TABLE period AS
WITH helper1 AS (
       WITH RECURSIVE go(j, prod) AS (
         SELECT 1, 1::bigint
         UNION ALL
           SELECT j + 1, bus_id * prod FROM go, bus_lines WHERE i = j
       )
       SELECT MAX(prod) AS period FROM go
     ),
     helper2 AS (
       SELECT MAX(column_) AS max_column FROM bus_lines
     )
SELECT period, max_column FROM helper1, helper2;

CREATE TEMP TABLE congruence_system AS
SELECT bus_id AS p,
       period / bus_id AS q,
       max_column - column_ AS beta,
       RANK() OVER (ORDER BY bus_id DESC) AS ord
FROM bus_lines, period;

WITH terms AS (
       WITH RECURSIVE by_fermats_little_theorem AS (
         SELECT beta,
                p,
                p - 3 AS i,
                q,
                MOD(q, p) AS q_p,
                MOD(q, p) AS q_inv_p
         FROM congruence_system
       UNION ALL
         SELECT beta, p, i - 1, q, q_p, MOD(q_inv_p * q_p, p)
         FROM by_fermats_little_theorem
         WHERE i > 0
       )
       SELECT beta, p, q, q_p, q_inv_p
       FROM by_fermats_little_theorem
       WHERE i = 0
     ),
     by_chinese_remainder_theorem AS (
       SELECT SUM(MOD(MOD(beta * q_inv_p, period) * q, period)) AS x
       FROM terms, period
     )
SELECT MOD(x, period) - max_column + 1 AS answer_2
FROM by_chinese_remainder_theorem, period;