Advent of Code 2020

advent-of-code-2020.md

A Few Advent of Code 2020 Solutions

In SQLite

day1.sql

--
-- Day 1
--

create table p1 (n int);
.import advent1.txt p1

-- Day 1 Part 1
select distinct n * (2020 - n) 
from p1 
where (2020 - n) in p1;

-- Day 1 Part 2
select distinct p1.n * p1c.n * (2020 - p1.n - p1c.n) 
from p1 
inner join p1 as p1c 
where (2020 - p1.n - p1c.n) in p1;

day2.sql

--
-- Day 2
--

create table p2temp (line string);
.import advent2.txt p2temp

create table p2 (min int, max int, c char, password string);

insert into p2 
    select 
        cast(substr(line, 1, instr(line, '-')) as int) as min, 
        cast(substr(line, instr(line, '-') + 1, instr(line, ' ') - instr(line, '-')) as int) as max, 
        cast(substr(line, instr(line, ' ') + 1, instr(line, ':') - instr(line, ' ') - 1) as char) as c, 
        substr(line, instr(line, ': ') + 2) as password 
    from p2temp;

-- Day 2 Part 1
select count(*) 
from p2 
where 
    min <= length(password) - length(replace(password, c, '')) 
    and
    length(password) - length(replace(password, c, '')) <= max;

-- Day 2 Part 2
select count(*)
from p2 
where 
    (substr(password, min, 1) == c) 
    <> 
    (substr(password, max, 1) == c);

day3.sql

--
-- Day 3
--

create table p3 (line string);
.import aoc3.txt p3

-- Day 3 Part 1
select count(*)
from p3
where substr(line, ((rowid - 1) * 3) % length(line) + 1, 1) = '#';

-- Day 3 Part 2
create table slopes (right int, down int);

insert into slopes values (1, 1);
insert into slopes values (3, 1);
insert into slopes values (5, 1);
insert into slopes values (7, 1);
insert into slopes values (1, 2);

-- first we calculate the number of trees for each slope by joining the input
-- with the slopes we added above, running the query from part 1 with
-- modifications for the slope, and grouping by the slope. This gives us a
-- table with each row being the number of trees on a given slope
with recursive trees_per_slope as (
   select slopes.rowid as id, count(*) as num_trees
   from p3
   inner join slopes
   where
      (p3.rowid - 1) % slopes.down = 0
      and
      substr(
         p3.line, 
         (((p3.rowid - 1) / slopes.down) * slopes.right) % length(p3.line) + 1,
         1
      ) = '#'
   group by slopes.rowid
), 
-- once we have the trees on each slope, we need to multiply them together.
-- SQLite doesn't provide a product aggregate, so we use a recursive CTE that
-- starts with a row (1, 1) and inserts rows (n, p) where n is the current row
-- number being added and p is the product of the first n - 1 numbers
product (id, res) as (
   select 1, 1

   union

   select product.id + 1, trees_per_slope.num_trees * product.res
   from product
   inner join trees_per_slope on trees_per_slope.id = product.id
)
-- we can then look at the maximum product — since we only have positive
-- numbers, this will be the product of all of the numbers. We could also
-- select the res where the product.id is the maximum product.id, which works
-- for negative numbers but adds a little bit of complexity
select max(res)
from product;

-- and no, we can't use exp(sum(log(value))) to get a product aggregate instead
-- of the recursive CTE — SQLite does not support logarithms!

day4.sql

--
-- Day 4
--

create table raw_lines (line string);
.import aoc4.txt raw_lines

-- Day 4 Part 1

-- We'll start by taking each blank line separated passport and convert them
-- from multiline / multirow documents into single row documents with recursive
-- common table expressions.
--
-- We can do this by starting at blank rows and appending each following row
-- until we reach another blank row. We'll also hardcode first row in the
-- initial table since it doesn't have any blank row above it.
create table documents (line string);

insert into documents
with recursive single as (
   select trim(line) as line, rowid as doc, rowid as rowid
   from raw_lines 
   where 
      length(line) = 0 
      or rowid = 1

   union

   select 
      new.line as line,
      single.doc as doc,
      new.rowid as rowid
   from single
   inner join raw_lines as new 
   on single.rowid + 1 = new.rowid
   where length(new.line) > 0
)
select trim(group_concat(trim(single.line), ' ')) from single group by single.doc;

-- Now we need to separate each line into it's proper columns and values.
-- Not difficult by hand, just repetitive (other DBMS's would be nicer here).
-- This isn't really necessary yet, but it makes part 2 easier.
create table passports (
   byr string, 
   iyr string, 
   eyr string, 
   hgt string, 
   hcl string, 
   ecl string, 
   pid text, -- text instead of string otherwise leading zeros get removed. guess how long that bug took me.
   cid string
);

insert into passports
select 
case 
   when 
      instr(line, 'eyr:')
   then substr( -- take the substring that looks like "eyr:<a value> " or "eyr:<a value><EOF>"
      line, 
      instr(line, 'eyr:') + 4, -- start at the end of the substring "eyr:"
      case 
         when instr(substr(line, instr(line, 'eyr:')), ' ') = 0 -- if we're at the end of the line
         then
            length(line) -- go until the end of the line
         else
            instr( -- go until the first space after "eyr:"
               substr(
                  line, 
                  instr(line, 'eyr:')
               ),
               ' '
            -- subtract 1 to get rid of the trailing space
            -- subtract 4 because we don't include "eyr:" above
            ) - 1 - 4
      end
   ) 
   else null
end as eyr,
-- and the same thing over and over
case when instr(line, 'byr:') then substr(line, instr(line, 'byr:') + 4, case when instr(substr(line, instr(line, 'byr:')), ' ') = 0 then length(line) else instr(substr(line, instr(line, 'byr:')), ' ') - 1 - 4 end) else null end as byr,
case when instr(line, 'iyr:') then substr(line, instr(line, 'iyr:') + 4, case when instr(substr(line, instr(line, 'iyr:')), ' ') = 0 then length(line) else instr(substr(line, instr(line, 'iyr:')), ' ') - 1 - 4 end) else null end as iyr,
case when instr(line, 'hgt:') then substr(line, instr(line, 'hgt:') + 4, case when instr(substr(line, instr(line, 'hgt:')), ' ') = 0 then length(line) else instr(substr(line, instr(line, 'hgt:')), ' ') - 1 - 4 end) else null end as hgt,
case when instr(line, 'hcl:') then substr(line, instr(line, 'hcl:') + 4, case when instr(substr(line, instr(line, 'hcl:')), ' ') = 0 then length(line) else instr(substr(line, instr(line, 'hcl:')), ' ') - 1 - 4 end) else null end as hcl,
case when instr(line, 'ecl:') then substr(line, instr(line, 'ecl:') + 4, case when instr(substr(line, instr(line, 'ecl:')), ' ') = 0 then length(line) else instr(substr(line, instr(line, 'ecl:')), ' ') - 1 - 4 end) else null end as ecl,
case when instr(line, 'pid:') then substr(line, instr(line, 'pid:') + 4, case when instr(substr(line, instr(line, 'pid:')), ' ') = 0 then length(line) else instr(substr(line, instr(line, 'pid:')), ' ') - 1 - 4 end) else null end as pid,
case when instr(line, 'cid:') then substr(line, instr(line, 'cid:') + 4, case when instr(substr(line, instr(line, 'cid:')), ' ') = 0 then length(line) else instr(substr(line, instr(line, 'cid:')), ' ') - 1 - 4 end) else null end as cid
from documents;

-- and then we can count the rows with no null values (other than cid of course)
select count(*) 
from passports 
where 
   byr is not null
   and iyr is not null
   and eyr is not null
   and hgt is not null
   and hcl is not null
   and ecl is not null
   and pid is not null;

-- Day 4 Part 2

-- All the hard parsing work was done in the last problem. We just need to
-- edit our count statement's where clause to do data validation

select count(*)
from passports 
where 
   byr is not null
   and iyr is not null
   and eyr is not null
   and hgt is not null
   and hcl is not null
   and ecl is not null
   and pid is not null

   and (
      -- for some reason, byr -> eyr -> iyr -> byr all switched spots. Why? I don't really intend to debug that code any more
      -- We'll just switch them around here as well
      typeof(iyr) = 'integer' and iyr >= 1920 and iyr <= 2002 -- actually byr
      and typeof(eyr) = 'integer' and eyr >= 2010 and eyr <= 2020 -- actually iyr
      and typeof(byr) = 'integer' and byr >= 2020 and byr <= 2030 -- actually eyr
      and typeof(hgt) = 'text' 
         and length(hgt) > 2
         and (
            substr(hgt, 1, length(hgt) - 2) glob '[0-9][0-9]' 
            or substr(hgt, 1, length(hgt) - 2) glob '[0-9][0-9][0-9]'
         )
         and (
            (
               substr(hgt, length(hgt) - 1) = 'cm' 
               and cast(substr(hgt, 1, length(hgt) - 2) as unsigned) >= 150 
               and cast(substr(hgt, 1, length(hgt) - 2) as unsigned) <= 193
            )
            or
            (
               substr(hgt, length(hgt) - 1) = 'in'
               and cast(substr(hgt, 1, length(hgt) - 2) as unsigned) >= 59
               and cast(substr(hgt, 1, length(hgt) - 2) as unsigned) <= 76
            )
         )
      and typeof(hcl) = 'text' and hcl glob '#[0-9a-f][0-9a-f][0-9a-f][0-9a-f][0-9a-f][0-9a-f]'
      and typeof(ecl) = 'text' and length(ecl) = 3 and ecl in ('amb', 'blu', 'brn', 'gry', 'grn', 'hzl', 'oth')
      and pid glob '[0-9][0-9][0-9][0-9][0-9][0-9][0-9][0-9][0-9]'
   );

day5.sql

--
-- Day 5
--

create table p5 (seat text);
.import aoc5.txt p5

-- Day 5 Part 1

create table binary_max_seat (seat text);

-- first convert to binary (F/L -> 0, B/R -> 1)
-- and take the max binary string
insert into binary_max_seat
with taken_seats as (
   select (replace(replace(replace(replace(seat, "F", "0"), "B", "1"), "L", "0"), "R", "1")) as seat
   from p5
)
select seat
from taken_seats
order by seat desc
limit 1;

-- then use recursive CTEs to convert binary
-- to decimal since SQLite standard library
-- is nonexistant
with recursive max_seat as (
   select 0 as digit, 0 as value

   union

   select 
      (digit + 1) as digit, 
      (value * 2 + substr(seat, digit, 1)) as value
   from binary_max_seat
   cross join max_seat
   where digit < 11
)
select value
from max_seat
order by value desc
limit 1;

-- Day 5 Part 2

create table binary_seats (seat text);

-- like before, but this time get all the seats
-- in binary not just the max
insert into binary_seats
with taken_seats as (
   select (replace(replace(replace(replace(seat, "F", "0"), "B", "1"), "L", "0"), "R", "1")) as seat
   from p5
)
select seat
from taken_seats;

-- convert all of the binary seats into normal seats
-- then get the sum of numbers from min seat to max seat
-- and subtract the actual sum of the numbers we have
-- to get the missing seat number (our seat)
with recursive seats as (
   select 0 as digit, 0 as value, rowid as id
   from binary_seats

   union

   select 
      (digit + 1) as digit, 
      (value * 2 + substr(seat, digit, 1)) as value,
      id as id
   from binary_seats
   inner join seats on seats.id = binary_seats.rowid
   where digit < 11
),
final_seats as (
   select value
   from seats
   where digit = 11
)
select ((max(value) - min(value) + 1) * (max(value) + min(value)) / 2) - sum(value)
from final_seats;