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.
0 Comments