Advent of Code 2019 in SQL

1. Advent of Code 2019 in SQL
2. Day 1: Rocket Fuel
3. Day 2: Virtual Machine Interpreter
- 3.1. The solution
4. Day 3 - Crossed Wires
5. Day 4 - Secure Container
- 5.1. Solution
6. Conclusions
7. Bonus: Mandelbrot

1 Advent of Code 2019 in SQL

SQL supports recursion in Common Table Expressions (CTEs) and so is Turing complete. If it's Turing complete, we should be able to write any function in SQL, right? Lets put that proposition to the test by implementing Advent of Code 2019 problems in SQL!

2 Day 1: Rocket Fuel

Okay, so in Day 1 we have a rocket fuel equation: for every V units of payload on a rocket, we require floor(V / 3) - 2 units of fuel.

For Day 1 Part 2, each V units of fuel recursively requires another floor(V / 3) - 2 units of additional fuel.

select "Part 1", sum(val / 3 - 2) from input_day1;

with weight as (
  select 0 as is_fuel, val from input_day1
  union all select 1, val / 3 - 2 from weight where val > 0
) select 'Part 2', sum(is_fuel * val) from weight;

Part 1	6546942
Part 2	9814454

Okay, that was pretty easy! Maybe writing logic in SQL isn't that bad!

3 Day 2: Virtual Machine Interpreter

Uh oh. This seems a lot more involved than Day 1.

We're given as input an array of numbers. Starting at index 0, we should interpret the first number as an opcode:

1 means ADD - add the operands
2 means MUL - multiply the operands
99 means HALT - stop and do not read any more data.

Next, Three numbers representing the addresses into the array. Two operand values are loaded from the first two addresses, they are added or multiplied, and the result is written to the third address.

For example, the input

is $0 <- ADD $0 $4. The operand values are 1 and 99 and the result 100 is written to index 0, so the program state becomes

100

The program counter is now pointing to index 4, which contains 99, so the program terminates.

In Part 1, Run the given program after putting 12 in index 1 and 2 in index 2, returning the final value in index 0;

In Part 2, figure out for which starting values < 100 at index 1 and 2 result in a final value in index 0 of 19690720.

3.1 The solution

After writing about 200 lines of really messy SQL and having huge issues debugging, I decided to encode the array as a JSON column, since most SQL databases these days have some kind of JSON format. This way, reading and writing memory is simply calls to json_replace and json_extract.

with initial as (select json('[1,0,0,3,1,1,2,3,1,3,4,3,1,5,0,3,2,1,10,19,1,19,6,23,2,23,13,27,1,27,5,31,2,31,10,35,1,9,35,39,1,39,9,43,2,9,43,47,1,5,47,51,2,13,51,55,1,55,9,59,2,6,59,63,1,63,5,67,1,10,67,71,1,71,10,75,2,75,13,79,2,79,13,83,1,5,83,87,1,87,6,91,2,91,13,95,1,5,95,99,1,99,2,103,1,103,6,0,99,2,14,0,0]') as arr),
program as (
   select
   -1 gen,
   0 pc,
   json_replace(json_replace(arr, '$[1]', 12), '$[2]', 2) mem
   from initial
   union all
   select
      gen + 1,
      pc + 4,
      json_replace(mem, '$[' || json_extract(mem, '$['||(pc + 3)||']') || ']',
      case when json_extract(mem, '$['||pc||']') = 1 then
      json_extract(mem, '$[' || json_extract(mem, '$['||(pc + 1)||']') || ']')+
      json_extract(mem, '$[' || json_extract(mem, '$['||(pc + 2)||']') || ']')
      else
      json_extract(mem, '$[' || json_extract(mem, '$['||(pc + 1)||']') || ']')*
      json_extract(mem, '$[' || json_extract(mem, '$['||(pc + 2)||']') || ']')
      end)
      from program
   where
      json_extract(mem, '$[' || pc || ']') <> 99
)
select 'Part 1', json_extract(mem, '$[0]') from program order by gen desc limit 1;

; with recursive
initial0 as (select json('[1,0,0,3,1,1,2,3,1,3,4,3,1,5,0,3,2,1,10,19,1,19,6,23,2,23,13,27,1,27,5,31,2,31,10,35,1,9,35,39,1,39,9,43,2,9,43,47,1,5,47,51,2,13,51,55,1,55,9,59,2,6,59,63,1,63,5,67,1,10,67,71,1,71,10,75,2,75,13,79,2,79,13,83,1,5,83,87,1,87,6,91,2,91,13,95,1,5,95,99,1,99,2,103,1,103,6,0,99,2,14,0,0]') as arr),
initial as (
  select -1 n, arr mem from initial0
  union all
  select n + 1, json_replace(json_replace(mem, '$[1]', (n + 1) / 100), '$[2]', (n + 1) % 100) from initial
  where n < 10000
),
program as (
   select
   -1 gen,
   0 pc,
   mem, n from initial
   union all
   select
      gen + 1,
      pc + 4,
      json_replace(mem, '$[' || json_extract(mem, '$['||(pc + 3)||']') || ']',
      case when json_extract(mem, '$['||pc||']') = 1 then
      json_extract(mem, '$[' || json_extract(mem, '$['||(pc + 1)||']') || ']')+
      json_extract(mem, '$[' || json_extract(mem, '$['||(pc + 2)||']') || ']')
      else
      json_extract(mem, '$[' || json_extract(mem, '$['||(pc + 1)||']') || ']')*
      json_extract(mem, '$[' || json_extract(mem, '$['||(pc + 2)||']') || ']')
      end),
      n
      from program
   where
      json_extract(mem, '$[' || pc || ']') <> 99
)
select 'Part 2', json_extract(mem, '$[0]'), n from program
 where json_extract(mem, '$[0]') = 19690720
order by gen desc limit 10000;

Part 1	3790645
Part 2	19690720	6577

4 Day 3 - Crossed Wires

Given a series of Directions and Lengths, calculate the positions where two wires cross. Both wires start at the origin, so the crossing represents a loop of wire.

In Part 1, find the closest intersection by manhattan distance from origin.

In Part 2: find the shortest intersection by total wire distance in loop.

.headers on
;with raw_input(wire, input_str) as (select wire, input_str from input_day3 where test_case = 2)
,w1 as ( -- split an entry into direction string and length
   select wire,
     substr(input_str, 0, instr(input_str, ',')) d,
     substr(input_str, instr(input_str, ',')+1) str
     from raw_input
   union all
   select wire,
     case instr(str, ',') when 0 then str else substr(str, 0, instr(str, ',')) end,
     case instr(str, ',') when 0 then NULL else substr(str, instr(str, ',') + 1) end 
   from w1 where str is NOT NULL
)
, wire as (
   select wire, substr(d, 1, 1) dir, cast (substr(d, 2) as int) len,
   row_number() over () i
   from w1
)
,steps as ( -- Expand "D5" into "DDDDD"
   select i, dir, wire, len from wire
   union all
   select i, dir, wire, len - 1 from steps where len > 1)
, ordered as ( -- turn directions into vectors
   select
   case dir when 'R' then 1 when 'L' then -1 else 0 end dx,
   case dir when 'U' then 1 when 'D' then -1 else 0 end dy,
   wire, row_number() over (partition by wire order by i) t from steps 
)
, positions as (
  select
      t,
      sum(dx) over (partition by wire order by t) x,
      sum(dy) over (partition by wire order by t) y,
      wire
  from ordered
)
select
  min(a.t + b.t) min_total_steps,
  min(abs(a.x) + abs(a.y)) min_distance
from positions a
  join positions b on a.wire < b.wire and a.x = b.x and a.y = b.y;

min_total_steps	min_distance
3454	217

5 Day 4 - Secure Container

Given a minimum and maximum of a number range, find all password candidates in that range. A number is a password candidate if:

It has a pair of repeated digits
It is nondecreasing

For Part 1: return the number of candidates For Part 2: The pair of repeated digits cannot be part of a longer series of repeats. Return the number of candidates also satisfying this new rule.

5.1 Solution

This seems like a pretty straightforward problem, so I'm going to avoid using JSON and do everything relationally.

with input (minval, maxval) as (values (109165, 576723)),
--with input (minval, maxval) as (values (100, 130)),
vals as (
  select minval n from input
  union all
  select n + 1 from vals where n < (select maxval from input)
),
digits as (
  select n, n / 10 remainder, 0 pos, n % 10 d from vals
  union all
  select n, remainder / 10, pos + 1, remainder % 10 d from digits where remainder > 0
),
all_pairs as (
   select d1.n, d1.d d1, d2.d d2, d1.pos e1, d2.pos e2
   from digits d1
   join digits d2 on d1.n = d2.n and d1.pos = d2.pos + 1
),
doubled_pair_part1 as (select distinct n from all_pairs where d1 = d2),
doubled_pair_part2 as (
   select distinct p1.n from all_pairs p1
   left outer join all_pairs p2 on p2.n = p1.n and p2.d1 = p2.d2 and p2.e2 = p1.e1
   left outer join all_pairs p3 on p3.n = p1.n and p3.d1 = p3.d2 and p1.e2 = p3.e1
   where p1.d1 = p1.d2 and p2.n IS NULL and p3.n is NULL
),
decreasing_pair as (select distinct n from all_pairs where d1 > d2)
select 'Part 1', count(*) from doubled_pair_part1 dubble
 where not exists (
   select * from decreasing_pair where decreasing_pair.n = dubble.n)
union all select 'Part 2', count(*) from doubled_pair_part2 dubble
 where not exists(
   select * from decreasing_pair where decreasing_pair.n = dubble.n)
;

Part 1	2814
Part 2	1991

6 Conclusions

???
This was fun
Don't immediately rewrite all your code in SQL just yet

7 Bonus: Mandelbrot

;with x as (
  select -1.8 x union all
  select x + 0.03 from x where x < 0.7),
y as (
  select -1 y union all
  select y + 0.1 from y where y < 1),
mandelbrot as (
  select ' ' c, 0 gen, 0 x, 0 y, x x0, y y0 from x cross join y
  union all
  select case when gen >= 30 then '#' else ' ' end,
    gen + 1, x * x - y * y + x0, 2 * x * y + y0, x0, y0
    from mandelbrot
   where gen <= 30 and x < 2 and y < 2
),
last_entries as (
   select c, x0, y0, gen, row_number() over (partition by x0, y0 order by gen desc) rn
   from mandelbrot
)
select '.' || group_concat(c, '')
from last_entries
where rn = 1
group by y0;

".                                                            #                        "
".                                                       ##                            "
".                                                     #######                         "
".                                                     #######                         "
".                                          ### ################### #  #               "
".                                         ##############################              "
".                                       #################################             "
".                           #          ###################################            "
".                      ###########   #######################################          "
".                   ######################################################            "
".#####################################################################                "
".                   ######################################################            "
".                      ###########   #######################################          "
".                           #         ####################################            "
".                                       #################################             "
".                                         ##############################              "
".                                          ### ################### #  #               "
".                                                     ######                          "
".                                                     #######                         "
".                                                       ##                            "
".                                                            #                        "
".                                                                                     "