Advent of Code 2021 in Db2 LUW SQL – Day 03!

Posted by

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

AOC Day 3

— 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.

My blog entries about Advent of Code 2021

Lead Database Administrator
Ember is always curious and thrives on change. Working in IT provides a lot of that change, but after 18 years developing a top-level expertise on Db2 for mid-range servers and more than 7 years blogging about it, Ember is hungry for new challenges and looks to expand her skill set to the Data Engineering role for Data Science. With in-depth SQL and RDBMS knowledge, Ember shares both posts about her core skill set and her journey into Data Science. Ember lives in Denver and work from home

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.