The Day 9 puzzle wants us to find certain anomalies in a stream of numbers: Each number must be the sum of two previous numbers in a range of 25 (between line-1 and line-25). We should find the first number that doesn’t meet this requirement.
For databases are great at adding numbers, I have no problem doing a lot of additional work (well, let the machine do a lot of additional work) and calculate the sum of each of these possibilities.
I also added a config-subquery so I can easily switch my actual data to the data provided in the example. The puzzles really get so challenging that I usually start with the example-data.
with
config as (
select
25 as preamble_length,
25 as search_range
from dual
),
base_data as (
select
rownum line,
to_number(column_value) num
from table (
aoc_file_loader.file_as_stringlist(
aoc_file_loader.local_url('day_9_input.txt')
)
)
),
calc_cube as (
select
d1.line line_1,
d1.num num_1,
d2.line line_2,
d2.num num_2,
d1.num+d2.num sum
from base_data d1
cross join base_data d2
cross join config
where
d1.line-d2.line between 1 and config.search_range
or d1.line-d2.line between 1 and config.search_range
)
select * from calc_cube
From there I can check whether there is such a sum in the requested range line by line, starting with the first line after the preamble.
with
config as (
select
25 as preamble_length,
25 as search_range
from dual
),
base_data as (
select
rownum line,
to_number(column_value) num
from table (
aoc_file_loader.file_as_stringlist(
aoc_file_loader.local_url('day_9_input.txt')
)
)
),
calc_cube as (
select
d1.line line_1,
d1.num num_1,
d2.line line_2,
d2.num num_2,
d1.num+d2.num sum
from base_data d1
cross join base_data d2
cross join config
where
d1.line-d2.line between 1 and config.search_range
or d1.line-d2.line between 1 and config.search_range
),
valid_sequence( line, num, parents_found) as (
select
line,
num,
(select count(*) from calc_cube cube
where
cube.sum = cur.num
and cube.line_2 between cur.line-config.search_range and cur.line-1
and cube.line_1 between cur.line-config.search_range and cur.line-1
)
from base_data cur
cross join config
where line = config.preamble_length+1 -- First line after preamble
union all
select
cur.line,
cur.num,
(select count(*) from calc_cube cube
where
cube.sum = cur.num
and cube.line_2 between cur.line-config.search_range and cur.line-1
and cube.line_1 between cur.line-config.search_range and cur.line-1
)
from base_data cur
inner join valid_sequence prev on cur.line = prev.line+1
cross join config
where prev.parents_found > 0
)
select
line,
num
from valid_sequence
where parents_found = 0
So far, so good – my database does this in like 1,5 seconds, which is okay.
Now Part 2. Phew. I really have no idea how to solve this in a set-based way, so I decided to take a “walk” approach with recursive subqueries.
After limiting the possible input data, I decide in each step what the next line to walk through will be. The logic is basically:
- add to run_total as long as it’s not greater than invalid_number
- reduce run_total by the amount of min_line until it’s lower than invalid_number again
- Also increase min_line in that case
- stop when run_total of the previous walk is equal to invalid_number
with
config as (
select
41682220 as invalid_num
from dual
),
base_data as (
select
rownum line,
to_number(column_value) num
from table (
aoc_file_loader.file_as_stringlist(
aoc_file_loader.local_url('day_9_input.txt')
)
)
),
possible_input as (
select
line,
num
from base_data
cross join config
where
line < (select line from base_data where num = config.invalid_num)
),
walk (line, num, run_total, min_line, max_line, action, next_line) as (
select
line,
num,
num,
line,
line,
'add',
line+1
from possible_input
where line = 1
union all
select
cur.line,
cur.num,
case when prev.run_total+cur.num > config.invalid_num then
prev.run_total - (select num from possible_input where line = prev.min_line)
else
prev.run_total + cur.num
end run_total,
case when prev.run_total+cur.num > config.invalid_num then
prev.min_line+1
else
prev.min_line
end min_line,
cur.line max_line,
case when prev.run_total+cur.num > config.invalid_num then
'rem'
else
'add'
end action,
case when prev.run_total+cur.num > config.invalid_num then
cur.line
else
cur.line+1
end next_line
from possible_input cur, walk prev, config
where cur.line = prev.next_line
and prev.run_total != config.invalid_num
) --cycle line, run_total set is_loop to 'Y' default 'N'
select
(select min(num) from possible_input where line between walk.min_line and walk.max_line) min_num,
(select max(num) from possible_input where line between walk.min_line and walk.max_line) max_num,
(select min(num)+max(num) from possible_input where line between walk.min_line and walk.max_line) sum_num
from walk, config
where run_total = config.invalid_num
The commented-out line was pretty helpful to check at which point I messed up and produced an infinite loop.
While the solution is unusual for a SQL-query, it’s very, very fast: ~250ms on my crappy dockerized database.
As always, you can find the code on my github-repository.
0 Comments