Check out my general blog entry on Advent of Code 2021 for background and resources. In short, I’m working through the Advent of Code 2021 programming challenge using Db2 LUW SQL. This is the detailed entry for day 3. It’s posting on December 21. I mentioned in my intro post that I have no intention of keeping up daily, because with a full-time job, I just can’t pull off the time it takes me.
AOC Day 3
My day 3 solutions are available in my GitHub repo.
Part 1 Problem Statement
— Day 3: Binary Diagnostic —
The submarine has been making some odd creaking noises, so you ask it to produce a diagnostic report just in case.The diagnostic report (your puzzle input) consists of a list of binary numbers which, when decoded properly, can tell you many useful things about the conditions of the submarine. The first parameter to check is the power consumption.
You need to use the binary numbers in the diagnostic report to generate two new binary numbers (called the gamma rate and the epsilon rate). The power consumption can then be found by multiplying the gamma rate by the epsilon rate.
Each bit in the gamma rate can be determined by finding the most common bit in the corresponding position of all numbers in the diagnostic report. For example, given the following diagnostic report:
00100
11110
10110
10111
10101
01111
00111
11100
10000
11001
00010
01010
Considering only the first bit of each number, there are five 0 bits and seven 1 bits. Since the most common bit is 1, the first bit of the gamma rate is 1.The most common second bit of the numbers in the diagnostic report is 0, so the second bit of the gamma rate is 0.
The most common value of the third, fourth, and fifth bits are 1, 1, and 0, respectively, and so the final three bits of the gamma rate are 110.
So, the gamma rate is the binary number 10110, or 22 in decimal.
The epsilon rate is calculated in a similar way; rather than use the most common bit, the least common bit from each position is used. So, the epsilon rate is 01001, or 9 in decimal. Multiplying the gamma rate (22) by the epsilon rate (9) produces the power consumption, 198.
Use the binary numbers in your diagnostic report to calculate the gamma rate and epsilon rate, then multiply them together. What is the power consumption of the submarine? (Be sure to represent your answer in decimal, not binary.)
General Commentary on the Problem
There are several challenges here. First, the sample data only has numbers that are 5 characters long, while the full data has data that is 12 characters long. I’ve gone with separate code to solve each. I’ve also added a couple of functions to help translate these numbers to and from binary. Would love to hear if anyone has a better way of doing this in Db2 SQL.
First, a Couple of UDFs
Db2 does not have a string reversal function. Nor does it have a function to convert a string that is a representation of a binary number into a base 10 integer. So I created a couple of helper functions for that in SQL:
CREATE OR REPLACE FUNCTION REVERSE(INSTR VARCHAR(4000))
RETURNS VARCHAR(4000) SPECIFIC REVERSE
DETERMINISTIC NO EXTERNAL ACTION CONTAINS SQL
RETURN WITH rec(pos, res) AS (VALUES (1, CAST('' AS VARCHAR(4000)))
UNION ALL
SELECT pos + 1, SUBSTR(INSTR, pos , 1) || res
FROM rec
WHERE pos <= LENGTH(INSTR)
AND pos < 5000)
SELECT res FROM rec WHERE pos > LENGTH(INSTR)@
drop function bin_to_int@
create function bin_to_int (IN bin_str varchar(50))
returns bigint
language sql
begin
declare ans bigint;
declare digit_num, digit_max smallint;
declare this_digit char(1);
set digit_num = 1;
set ans = 0;
set digit_max = length(bin_str);
set bin_str=reverse(bin_str);
while digit_num <= digit_max
do
set this_digit=substr(bin_str,digit_num,1);
if this_digit != 0 and this_digit != 1 then
signal sqlstate '75001'
set message_text = 'Non binary digit in input string';
end if;
set ans=ans+this_digit*power(2,digit_num-1);
set digit_num=digit_num+1;
end while;
return ans;
end@Note that the reverse function is taken from this stack overflow thread, which I believe takes it from Serge Rileau's old blog, which was just gold before IBM removed it.
My Solution
My day 3 solutions are available in my GitHub repo.
First, I need to get the data into a table in the database. To do that, I create a table with this syntax for the sample data:
create table aoc_day03 (
seq int generated by default as identity primary key
, bin_num char(12) not null
, char_1 int generated always as (SUBSTR(bin_num,1,1))
, char_2 int generated always as (SUBSTR(bin_num,2,1))
, char_3 int generated always as (SUBSTR(bin_num,3,1))
, char_4 int generated always as (SUBSTR(bin_num,4,1))
, char_5 int generated always as (SUBSTR(bin_num,5,1))
);Or this syntax for the full data:
create table aoc_day03 (
seq int generated by default as identity primary key
, bin_num char(12) not null
, char_1 int generated always as (SUBSTR(bin_num,1,1))
, char_2 int generated always as (SUBSTR(bin_num,2,1))
, char_3 int generated always as (SUBSTR(bin_num,3,1))
, char_4 int generated always as (SUBSTR(bin_num,4,1))
, char_5 int generated always as (SUBSTR(bin_num,5,1))
, char_6 int generated always as (SUBSTR(bin_num,6,1))
, char_7 int generated always as (SUBSTR(bin_num,7,1))
, char_8 int generated always as (SUBSTR(bin_num,8,1))
, char_9 int generated always as (SUBSTR(bin_num,9,1))
, char_10 int generated always as (SUBSTR(bin_num,10,1))
, char_11 int generated always as (SUBSTR(bin_num,11,1))
, char_12 int generated always as (SUBSTR(bin_num,12,1))
);Note that I'm splitting up the number into different columns. I thought initially this would really help me, but I only ended up using this in part one, not in part two. I really don't have to split the data this way, but it might have made things more efficient had the data set been larger.
I then used this to import the data into the table:
delete from aoc_day03;
call admin_cmd ('import from /database/day03_input.del of del
insert into aoc_day03 (bin_num)');Query to Answer Part 1
Once I've done a quick verification that the data was inserted the way I intended, this is the SQL I came up with to generate the answer to part 1:
with params as (select case when float(sum(char_1))/float(count(*)) > 0.5 then 1 else 0 end * 2048
+ case when float(sum(char_2))/float(count(*)) > 0.5 then 1 else 0 end * 1024
+ case when float(sum(char_3))/float(count(*)) > 0.5 then 1 else 0 end * 512
+ case when float(sum(char_4))/float(count(*)) > 0.5 then 1 else 0 end * 256
+ case when float(sum(char_5))/float(count(*)) > 0.5 then 1 else 0 end * 128
+ case when float(sum(char_6))/float(count(*)) > 0.5 then 1 else 0 end * 64
+ case when float(sum(char_7))/float(count(*)) > 0.5 then 1 else 0 end * 32
+ case when float(sum(char_8))/float(count(*)) > 0.5 then 1 else 0 end * 16
+ case when float(sum(char_9))/float(count(*)) > 0.5 then 1 else 0 end * 8
+ case when float(sum(char_10))/float(count(*)) > 0.5 then 1 else 0 end * 4
+ case when float(sum(char_11))/float(count(*)) > 0.5 then 1 else 0 end * 2
+ case when float(sum(char_12))/float(count(*)) > 0.5 then 1 else 0 end * 1 as gamma
,case when float(sum(char_1))/float(count(*)) < 0.5 then 1 else 0 end * 2048
+ case when float(sum(char_2))/float(count(*)) < 0.5 then 1 else 0 end * 1024
+ case when float(sum(char_3))/float(count(*)) < 0.5 then 1 else 0 end * 512
+ case when float(sum(char_4))/float(count(*)) < 0.5 then 1 else 0 end * 256
+ case when float(sum(char_5))/float(count(*)) < 0.5 then 1 else 0 end * 128
+ case when float(sum(char_6))/float(count(*)) < 0.5 then 1 else 0 end * 64
+ case when float(sum(char_7))/float(count(*)) < 0.5 then 1 else 0 end * 32
+ case when float(sum(char_8))/float(count(*)) < 0.5 then 1 else 0 end * 16
+ case when float(sum(char_9))/float(count(*)) < 0.5 then 1 else 0 end * 8
+ case when float(sum(char_10))/float(count(*)) < 0.5 then 1 else 0 end * 4
+ case when float(sum(char_11))/float(count(*)) < 0.5 then 1 else 0 end * 2
+ case when float(sum(char_12))/float(count(*)) < 0.5 then 1 else 0 end * 1 as epsilon
from aoc_day03)
select gamma, epsilon, gamma*epsilon as power_consumption from params;Note that I calculated the conversion from a binary representation into an integer manually within the query, not using the functions to convert it. I could have done it either way.
Part 2 Problem Statement
AOC Day 2 - you can only see part 2 after you've completed part 1
--- Part Two ---
Next, you should verify the life support rating, which can be determined by multiplying the oxygen generator rating by the CO2 scrubber rating.Both the oxygen generator rating and the CO2 scrubber rating are values that can be found in your diagnostic report - finding them is the tricky part. Both values are located using a similar process that involves filtering out values until only one remains. Before searching for either rating value, start with the full list of binary numbers from your diagnostic report and consider just the first bit of those numbers. Then:
Keep only numbers selected by the bit criteria for the type of rating value for which you are searching. Discard numbers which do not match the bit criteria.
If you only have one number left, stop; this is the rating value for which you are searching.
Otherwise, repeat the process, considering the next bit to the right.
The bit criteria depends on which type of rating value you want to find:To find oxygen generator rating, determine the most common value (0 or 1) in the current bit position, and keep only numbers with that bit in that position. If 0 and 1 are equally common, keep values with a 1 in the position being considered.
To find CO2 scrubber rating, determine the least common value (0 or 1) in the current bit position, and keep only numbers with that bit in that position. If 0 and 1 are equally common, keep values with a 0 in the position being considered.
For example, to determine the oxygen generator rating value using the same example diagnostic report from above:Start with all 12 numbers and consider only the first bit of each number. There are more 1 bits (7) than 0 bits (5), so keep only the 7 numbers with a 1 in the first position: 11110, 10110, 10111, 10101, 11100, 10000, and 11001.
Then, consider the second bit of the 7 remaining numbers: there are more 0 bits (4) than 1 bits (3), so keep only the 4 numbers with a 0 in the second position: 10110, 10111, 10101, and 10000.
In the third position, three of the four numbers have a 1, so keep those three: 10110, 10111, and 10101.
In the fourth position, two of the three numbers have a 1, so keep those two: 10110 and 10111.
In the fifth position, there are an equal number of 0 bits and 1 bits (one each). So, to find the oxygen generator rating, keep the number with a 1 in that position: 10111.
As there is only one number left, stop; the oxygen generator rating is 10111, or 23 in decimal.
Then, to determine the CO2 scrubber rating value from the same example above:Start again with all 12 numbers and consider only the first bit of each number. There are fewer 0 bits (5) than 1 bits (7), so keep only the 5 numbers with a 0 in the first position: 00100, 01111, 00111, 00010, and 01010.
Then, consider the second bit of the 5 remaining numbers: there are fewer 1 bits (2) than 0 bits (3), so keep only the 2 numbers with a 1 in the second position: 01111 and 01010.
In the third position, there are an equal number of 0 bits and 1 bits (one each). So, to find the CO2 scrubber rating, keep the number with a 0 in that position: 01010.
As there is only one number left, stop; the CO2 scrubber rating is 01010, or 10 in decimal.
Finally, to find the life support rating, multiply the oxygen generator rating (23) by the CO2 scrubber rating (10) to get 230.Use the binary numbers in your diagnostic report to calculate the oxygen generator rating and CO2 scrubber rating, then multiply them together. What is the life support rating of the submarine? (Be sure to represent your answer in decimal, not binary.)
General Commentary on the Problem
I thought this one would be easier that it is, and I relied on the user defined functions I created to make it a bit easier
My Solution - Plain SQL
This one hurts a bit, and I didn't actually do the full thing in one query because it ended up rather long. I'd say I cheated it a bit, because the fewest queries I used to get the answer was three - one for the answer on the oxygen, one to figure out where the data set for CO2 narrows down to just one row, and one to return that row. I then did the actual calcuation with a simple calculator. But it works to get the right answer.
One of the advantages of being behind is that I can include links to other solutions. Check out this one in T-SQL.
So here's my solution:
-- Oxygen
with digit1 as (select case when float(sum(substr(bin_num,1,1)))/float(count(*)) >= 0.5 then 1 else 0 end as char_1_digit
from aoc_day03)
, set1 as (select * from aoc_day03, digit1 where substr(bin_num,1,1)=digit1.char_1_digit)
, digit2 as (select case when float(sum(substr(bin_num,2,1)))/float(count(*)) >= 0.5 then 1 else 0 end as char_2_digit
from set1)
, set2 as (select * from set1, digit2 where substr(bin_num,2,1)=digit2.char_2_digit)
, digit3 as (select case when float(sum(substr(bin_num,3,1)))/float(count(*)) >= 0.5 then 1 else 0 end as char_3_digit
from set2)
, set3 as (select * from set2, digit3 where substr(bin_num,3,1)=digit3.char_3_digit)
, digit4 as (select case when float(sum(substr(bin_num,4,1)))/float(count(*)) >= 0.5 then 1 else 0 end as char_4_digit
from set3)
, set4 as (select * from set3, digit4 where substr(bin_num,4,1)=digit4.char_4_digit)
, digit5 as (select case when float(sum(substr(bin_num,5,1)))/float(count(*)) >= 0.5 then 1 else 0 end as char_5_digit
from set4)
, set5 as (select * from set4, digit5 where substr(bin_num,5,1)=digit5.char_5_digit)
, digit6 as (select case when float(sum(substr(bin_num,6,1)))/float(count(*)) >= 0.5 then 1 else 0 end as char_6_digit
from set5)
, set6 as (select * from set5, digit6 where substr(bin_num,6,1)=digit6.char_6_digit)
, digit7 as (select case when float(sum(substr(bin_num,7,1)))/float(count(*)) >= 0.5 then 1 else 0 end as char_7_digit
from set6)
, set7 as (select * from set6, digit7 where substr(bin_num,7,1)=digit7.char_7_digit)
, digit8 as (select case when float(sum(substr(bin_num,8,1)))/float(count(*)) >= 0.5 then 1 else 0 end as char_8_digit
from set7)
, set8 as (select * from set7, digit8 where substr(bin_num,8,1)=digit8.char_8_digit)
, digit9 as (select case when float(sum(substr(bin_num,9,1)))/float(count(*)) >= 0.5 then 1 else 0 end as char_9_digit
from set8)
, set9 as (select * from set8, digit9 where substr(bin_num,9,1)=digit9.char_9_digit)
, digit10 as (select case when float(sum(substr(bin_num,10,1)))/float(count(*)) >= 0.5 then 1 else 0 end as char_10_digit
from set9)
, set10 as (select * from set9, digit10 where substr(bin_num,10,1)=digit10.char_10_digit)
, digit11 as (select case when float(sum(substr(bin_num,11,1)))/float(count(*)) >= 0.5 then 1 else 0 end as char_11_digit
from set10)
, set11 as (select * from set10, digit11 where substr(bin_num,11,1)=digit11.char_11_digit)
, digit12 as (select case when float(sum(substr(bin_num,12,1)))/float(count(*)) >= 0.5 then 1 else 0 end as char_12_digit
from set11)
, set12 as (select * from set11, digit12 where substr(bin_num,12,1)=digit12.char_12_digit)
select bin_to_int(bin_num) from set12;
-- CO2
-- figure out where the set narrows down to 1 row
with digit1 as (select case when float(sum(substr(bin_num,1,1)))/float(count(*)) < 0.5 then 1 else 0 end as char_1_digit
from aoc_day03)
, set1 as (select * from aoc_day03, digit1 where substr(bin_num,1,1)=digit1.char_1_digit)
, digit2 as (select case when float(sum(substr(bin_num,2,1)))/float(count(*)) < 0.5 then 1 else 0 end as char_2_digit
from set1)
, set2 as (select * from set1, digit2 where substr(bin_num,2,1)=digit2.char_2_digit)
, digit3 as (select case when float(sum(substr(bin_num,3,1)))/float(count(*)) < 0.5 then 1 else 0 end as char_3_digit
from set2)
, set3 as (select * from set2, digit3 where substr(bin_num,3,1)=digit3.char_3_digit)
, digit4 as (select case when float(sum(substr(bin_num,4,1)))/float(count(*)) < 0.5 then 1 else 0 end as char_4_digit
from set3)
, set4 as (select * from set3, digit4 where substr(bin_num,4,1)=digit4.char_4_digit)
, digit5 as (select case when float(sum(substr(bin_num,5,1)))/float(count(*)) < 0.5 then 1 else 0 end as char_5_digit
from set4)
, set5 as (select * from set4, digit5 where substr(bin_num,5,1)=digit5.char_5_digit)
, digit6 as (select case when float(sum(substr(bin_num,6,1)))/float(count(*)) < 0.5 then 1 else 0 end as char_6_digit
from set5)
, set6 as (select * from set5, digit6 where substr(bin_num,6,1)=digit6.char_6_digit)
, digit7 as (select case when float(sum(substr(bin_num,7,1)))/float(count(*)) < 0.5 then 1 else 0 end as char_7_digit
from set6)
, set7 as (select * from set6, digit7 where substr(bin_num,7,1)=digit7.char_7_digit)
, digit8 as (select case when float(sum(substr(bin_num,8,1)))/float(count(*)) < 0.5 then 1 else 0 end as char_8_digit
from set7)
, set8 as (select * from set7, digit8 where substr(bin_num,8,1)=digit8.char_8_digit)
, digit9 as (select case when float(sum(substr(bin_num,9,1)))/float(count(*)) < 0.5 then 1 else 0 end as char_9_digit
from set8)
, set9 as (select * from set8, digit9 where substr(bin_num,9,1)=digit9.char_9_digit)
, digit10 as (select case when float(sum(substr(bin_num,10,1)))/float(count(*)) < 0.5 then 1 else 0 end as char_10_digit
from set9)
, set10 as (select * from set9, digit10 where substr(bin_num,10,1)=digit10.char_10_digit)
, digit11 as (select case when float(sum(substr(bin_num,11,1)))/float(count(*)) < 0.5 then 1 else 0 end as char_11_digit
from set10)
, set11 as (select * from set10, digit11 where substr(bin_num,11,1)=digit11.char_11_digit)
, digit12 as (select case when float(sum(substr(bin_num,12,1)))/float(count(*)) < 0.5 then 1 else 0 end as char_12_digit
from set11)
, set12 as (select * from set11, digit12 where substr(bin_num,12,1)=digit12.char_12_digit)
select 'set02', count(*) from set2
union all
select 'set03', count(*) from set3
union all
select 'set04', count(*) from set4
union all
select 'set05', count(*) from set5
union all
select 'set06', count(*) from set6
union all
select 'set07', count(*) from set7
union all
select 'set08', count(*) from set8
union all
select 'set09', count(*) from set9
union all
select 'set10', count(*) from set10
union all
select 'set11', count(*) from set11
union all
select 'set12', count(*) from set12
order by 1
-- Return the one row
with digit1 as (select case when float(sum(substr(bin_num,1,1)))/float(count(*)) < 0.5 then 1 else 0 end as char_1_digit
from aoc_day03)
, set1 as (select * from aoc_day03, digit1 where substr(bin_num,1,1)=digit1.char_1_digit)
, digit2 as (select case when float(sum(substr(bin_num,2,1)))/float(count(*)) < 0.5 then 1 else 0 end as char_2_digit
from set1)
, set2 as (select * from set1, digit2 where substr(bin_num,2,1)=digit2.char_2_digit)
, digit3 as (select case when float(sum(substr(bin_num,3,1)))/float(count(*)) < 0.5 then 1 else 0 end as char_3_digit
from set2)
, set3 as (select * from set2, digit3 where substr(bin_num,3,1)=digit3.char_3_digit)
, digit4 as (select case when float(sum(substr(bin_num,4,1)))/float(count(*)) < 0.5 then 1 else 0 end as char_4_digit
from set3)
, set4 as (select * from set3, digit4 where substr(bin_num,4,1)=digit4.char_4_digit)
, digit5 as (select case when float(sum(substr(bin_num,5,1)))/float(count(*)) < 0.5 then 1 else 0 end as char_5_digit
from set4)
, set5 as (select * from set4, digit5 where substr(bin_num,5,1)=digit5.char_5_digit)
, digit6 as (select case when float(sum(substr(bin_num,6,1)))/float(count(*)) < 0.5 then 1 else 0 end as char_6_digit
from set5)
, set6 as (select * from set5, digit6 where substr(bin_num,6,1)=digit6.char_6_digit)
, digit7 as (select case when float(sum(substr(bin_num,7,1)))/float(count(*)) < 0.5 then 1 else 0 end as char_7_digit
from set6)
, set7 as (select * from set6, digit7 where substr(bin_num,7,1)=digit7.char_7_digit)
, digit8 as (select case when float(sum(substr(bin_num,8,1)))/float(count(*)) < 0.5 then 1 else 0 end as char_8_digit
from set7)
, set8 as (select * from set7, digit8 where substr(bin_num,8,1)=digit8.char_8_digit)
, digit9 as (select case when float(sum(substr(bin_num,9,1)))/float(count(*)) < 0.5 then 1 else 0 end as char_9_digit
from set8)
, set9 as (select * from set8, digit9 where substr(bin_num,9,1)=digit9.char_9_digit)
, digit10 as (select case when float(sum(substr(bin_num,10,1)))/float(count(*)) < 0.5 then 1 else 0 end as char_10_digit
from set9)
, set10 as (select * from set9, digit10 where substr(bin_num,10,1)=digit10.char_10_digit)
, digit11 as (select case when float(sum(substr(bin_num,11,1)))/float(count(*)) < 0.5 then 1 else 0 end as char_11_digit
from set10)
, set11 as (select * from set10, digit11 where substr(bin_num,11,1)=digit11.char_11_digit)
, digit12 as (select case when float(sum(substr(bin_num,12,1)))/float(count(*)) < 0.5 then 1 else 0 end as char_12_digit
from set11)
, set12 as (select * from set11, digit12 where substr(bin_num,12,1)=digit12.char_12_digit)
select bin_to_int(bin_num) from set8
Now I am nearly certain there is a way to better use recursive SQL to get these answers, but just could not get it to work with the interaction between the two CTEs I had. Would love to hear it if anyone managed to do it that way.
Summary
Today had me questioning my deep SQL skills, and I think that will only get worse as advent of code progresses. I'm guessing some of the later challenges may not be possible in a reasonable time in SQL, but we'll see.
