Day 7’s puzzle comes with a bunch of rules about bags that contain other bags – and a lot of different colors (very cool puzzle setting btw!)
As always, the first thing we want to do is to normalize the input in a way that gives us a workable result set. In this case I aim to have a row for each child-rule, groupable by the bag’s name.
If we want to split a column into several rows, one of best approaches (if we cannot easily unpivot) is to use recursive subqueries. They seemed complicated to me at first, but once I used them several times I really get to like them:
with
base_data as (
select
column_value line
from table(
aoc_file_loader.file_as_stringlist(
aoc_file_loader.local_url('day_7_input.txt')
)
)
),
bag_children as (
select
replace(
regexp_replace(line, '^(.+) contain (.+)$', '\1'),
'bags',
'bag'
) bag,
regexp_replace(line, '^(.+) contain (.+)$', '\2') children
from base_data
),
children_in_rows (bag, child, children) as (
select
bag,
nvl(substr(children, 1, instr(children, ', ')-1), children),
case when instr(children, ', ') > 0 then
substr(children, instr(children, ', ')+2)
else null end
from bag_children
union all
select
bag,
nvl(substr(children, 1, instr(children, ', ')-1), children),
case when instr(children, ', ') > 0 then
substr(children, instr(children, ', ')+2)
else null end
from children_in_rows where children is not null
)
select * from children_in_rows;
It’s important we normalize the “bags” in the bag column to “bag”, because we have rules that say “contain 1 other bag.” and we won’t be able to match that with the “bags”.
The first task now is to wander upwards and count how many different (parent) bag-colors we have.
This might be possible with connect by prior, too, but I noticed I have way more control about how exactly my recursion behaves if I use recursive subquery again:
with
base_data as (
select
column_value line
from table(
aoc_file_loader.file_as_stringlist(
aoc_file_loader.local_url('day_7_input.txt')
)
)
),
bag_children as (
select
replace(
regexp_replace(line, '^(.+) contain (.+)$', '\1'),
'bags',
'bag'
) bag,
regexp_replace(line, '^(.+) contain (.+)$', '\2') children
from base_data
),
children_in_rows (bag, child, children) as (
select
bag,
nvl(substr(children, 1, instr(children, ', ')-1), children),
case when instr(children, ', ') > 0 then
substr(children, instr(children, ', ')+2)
else null end
from bag_children
union all
select
bag,
nvl(substr(children, 1, instr(children, ', ')-1), children),
case when instr(children, ', ') > 0 then
substr(children, instr(children, ', ')+2)
else null end
from children_in_rows where children is not null
),
bag_hierarchy( bag, child, hierarchy_level, path ) as (
select
bag,
child,
1,
bag
from children_in_rows
where child like '%shiny gold bag%'
union all
select
cur_bag.bag,
cur_bag.child,
parent_bag.hierarchy_level+1,
cur_bag.bag || '/' || parent_bag.path
from children_in_rows cur_bag
inner join bag_hierarchy parent_bag on cur_bag.child like '%'||parent_bag.bag||'%'
)
select count(distinct bag)
from bag_hierarchy
Part 2 now wants us to walk down the tree and count all the bags inside of the shiny gold bag – and the bags inside the bags etc.
Therefore we need to extract the number from the text – easy with regular expressions. We also replace “no other bags.” with 0 so we can calculate properly.
I found it easier to calculate the cumulated children of each bag (on parent-level) rather than the cumulated number on child-level.
with
base_data as (
select
column_value line
from table(
aoc_file_loader.file_as_stringlist(
aoc_file_loader.local_url('day_7_input.txt')
)
)
),
bag_children as (
select
replace(
regexp_replace(line, '^(.+) contain (.+)$', '\1'),
'bags',
'bag'
) bag,
regexp_replace(line, '^(.+) contain (.+)$', '\2') children
from base_data
),
children_in_rows (bag, child, children) as (
select
bag,
nvl(substr(children, 1, instr(children, ', ')-1), children),
case when instr(children, ', ') > 0 then
substr(children, instr(children, ', ')+2)
else null end
from bag_children
union all
select
bag,
nvl(substr(children, 1, instr(children, ', ')-1), children),
case when instr(children, ', ') > 0 then
substr(children, instr(children, ', ')+2)
else null end
from children_in_rows where children is not null
),
children_with_count as (
select
bag,
to_number(
replace(
regexp_replace(child, '^([0-9]+) (.*)$', '\1'),
'no other bags.',
'0'
)
)child_count,
regexp_replace(child, '^([0-9]+) (.*)$', '\2') child_name
from children_in_rows
),
bag_hierarchy( bag, child_name, child_count, cumulated_child_count, hierarchy_level, path ) as (
select
bag,
child_name,
child_count,
child_count,
1,
bag
from children_with_count
where bag like '%shiny gold bag%'
union all
select
cur_bag.bag,
cur_bag.child_name,
cur_bag.child_count,
parent_bag.cumulated_child_count*cur_bag.child_count,
parent_bag.hierarchy_level+1,
parent_bag.path || '/' || cur_bag.bag
from children_with_count cur_bag
inner join bag_hierarchy parent_bag on parent_bag.child_name like '%'||cur_bag.bag||'%'
)
select sum(cumulated_child_count)
from bag_hierarchy
This was quite a challenge and I had several errors (mainly from the missing “one some-colored bag.” connection) – hierarchical queries are something I don’t do that often. But it was very funny and I learned and refreshed a lot!
You can find the whole code on my github-repository.
0 Comments