And then, there was Day 11. We are supposed to look for a stabilized layout of seat occupation when all of the people follow certain rules, depending on how many seats around them are already occupied.
Since I wanted to try out the Oracle MODEL clause for a while, I thought it couldn’t hurt to do this challenge with the special toolkit it provides. And it even worked pretty well, using the small input of the example.
Another benefit was that I could use Kim Berg Hansens awesome book “Practical Oracle SQL” which covers exactly that Game of Life example with the MODEL clause.
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.
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.
I never ran and debugged an infinite loop of program consisting of the instructions nop, jmp and acc in SQL before – but it’s possible and the Day 8 puzzle gives me the possibility to do so.
Each of the commands has a possible value, and while we ignore it for nop, acc manipulates a global variable and jmp redirects the program to a different line.
To solve this in SQL we need recursive subqueries again. With a bit of case we can easily determine the next line number to be exectued, but how to we prevent the infinite loop from running?
My solution was to add a stack-column which holds all the previously called lines. With that I can check whether a line has already been called. I use a “:” suffix and prefix, because when I check for “42” it will find that number in “142”, too, but “:42:” will not be found.
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:
The puzzle of Day 6 requests us to group answers to a customs declaration form and analyse them.
Challenge one is the format we need to normalize into something we can work with in SQL. Each answer is a line, but several answers are grouped together and the groups are separated by an empty line.
So as a first step, we introduce a new column that indicates whether the row is a break or not and then use window functions to summarize all breaks from beginning to the current position, which will be our group-ID
Ah, the title already reveals what the challenge will be about – and yes, I’m two days late, because it’s been weekend and weekend is family time, usually way from any computer device.
Our task is to get seat locations and IDs from the proprietary “FBFBBFFRLR” format – which is in reality a representation of binary numbers:
FBFBBFF = 7-bit number = 0101100 = 44 RLR = 3-bit number = 101 = 5
The first step is to get the binary representation of the row and column data. I used a little helper function I wrote to get the input as sys.odcivarchar2list and into the aoc_day5_input table in the same way as I did with the previous inputs (downloading from local webserver).
Day 4 comes with a new challenge – we need to validate passport data that comes in batches that are pretty unstructured. SQL is usually used to tame structured data, but it’s totally possible to use it to deal with unstructured data, too.
The main challenge here for SQL folks is to get the data into a structured form where we can filter it.
I could do the same as before, loading the data via PL/SQL, but I want to do as much as possible inside the boundaries of pure (Oracle) SQL. Therefore, I will use the SQL Loader feature to get access to external data. To be able to do that, we need an Oracle directory and the file stored reachable for the database.
We have a repeating pattern of trees and need to calculate how many trees we will hit, starting from top left position, when we always go 1 down and 3 right.
Today’s challenge is to analyze a given list of passwords towards the provided policy.
The policy of part 1 is that the given character must occur in the password inside a given threshold – sounds like we could use some regex.
The biggest challenge – again – was to get the input data into the database (I want to avoid setting up tables if I can). sys.odcivarchar2list seems like a good choice, but the input has 1000 entries and the constructor of odcivarchar2list only supports 999 items.
Clean Database Development 