Advent Of Code 2020 in SQL – Day 10: “Adapter Array”

Day 10 is a beast. Really.

We are supposed to order a bunch of adapters in a way that we get from 0 jolt to the jolt needed by our device (which is the max number in the input + 3) in a step-size between 1 and 3.

Part 1 feels nearly like cheating, because we can just use a little bit of window-function magic:

with
  base_data as (
    select
      to_number(column_value) num
    from table (
        aoc_file_loader.file_as_stringlist(
          aoc_file_loader.local_url('day_10_input.txt')
       )
    )
  ),
  jolt_diffs as (
    select
      num,
      num - nvl(lag(num) over (order by num),0) jolt_diff
    from base_data
  ),
  sums as (
    select
      jolt_diff,
      count(*) count,
      sum(jolt_diff) sum
    from jolt_diffs
    group by (jolt_diff)
  )
select
  (select count from sums where jolt_diff = 1)
  * (select count+1 -- +1 for the device-adapter
    from sums where jolt_diff = 3) result
from dual;

But then comes part 2, in which we need to calculate all the possible ways that we can use to get our adapter connected.

This was incredibly hard for me to solve and I’m not sure I got the best solution – but it’s very, very fast so I think I found a pretty efficient one.

For all possibilities need to end with the maximum number in the list, I decided to start with that number. But of course, iterating through all the possibilities would be terribly unefficient, so I dabbled around with multiplying and stuff – which didn’t work.

As a constant learner, I looked for algorithms other folks came up with (NOT in the context of Advent Of Code, of course) and found this explanation of an efficient algorithm to count possible ways to cover a distance.

It was not the solution to my problem, but it gave me the right idea to count the possibilities to each reachable next point in a recursive subquery.

This would look like the following for the larger example-data:

NUM	MULTIPLIER	DIST_1	DIST_2	DIST_3
	prev.DIST_1 (or 1 to start with)	prev.DIST_2 + (MULTIPLIER * Exists)	previous.DIST_3 + (MULTIPLIER * Exists)	MULTIPLIER * Exists
49	1	0+(1*Exists(48))=1	0+(1*Exists(47))=1	1*Exists(46)=1
48	1	1+(1*Exists(47))=2	1+(1*Exists(46))=2	1*Exists(45)=1
47	2	2+(2*Exists(46))=4	1+(2*Exists(45))=3	2*Exists(44)=0
46	4	3+(4*Exists(45))=7	0+(4*Exists(44))=0	4*Exists(43)=0
45	7	0+(7*Exists(44))=0	0+(7*Exists(43))=0	7*Exists(42)=7
44	0	0+(0*Exists(43))=0	7+(0*Exists(42))=7	0*Exists(41)=0

with
  base_data as (
    select
      to_number(column_value) num
    from table (
        aoc_file_loader.file_as_stringlist(
          aoc_file_loader.local_url('day_10_input.txt')
       )
    )
    union all select 0 from dual
  ),
  walk (num, multiplier, dist1, dist2, dist3) as (
    select
      num,
      1,
      (select count(*) from base_data where num = cur.num-1),
      (select count(*) from base_data where num = cur.num-2),
      (select count(*) from base_data where num = cur.num-3)
    from base_data cur
    where num = (select max(num) from base_data)
    union all
    select
      prev.num-1,
      prev.dist1,
      prev.dist2 + (
        prev.dist1 * (select count(*) from base_data where num = cur.num-1)),
      prev.dist3 + (
        prev.dist1 * (select count(*) from base_data where num = cur.num-2)),
      prev.dist1 * (select count(*) from base_data where num = cur.num-3)
    from walk prev
      left outer join base_data cur on prev.num-1 = cur.num
    where prev.num > 0
  )
select multiplier as result
from walk
order by num fetch first row only

Enjoy. I never did such a thing before and I’m pretty proud right now I’ve figured it out.

You can find the solution on my github-repository.