DEV Community

Samuel Nitsche
Samuel Nitsche

Posted on • Originally published at cleandatabase.wordpress.com on <time datetime="2020-12-07T10:09:22Z" class="date">Dec 7, 2020</time>

Advent Of Code 2020 in SQL – Day 5: “Binary Boarding”

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_inputtable in the same way as I did with the previous inputs (downloading from local webserver).

with
  seat_data as (
    select
      substr(line, 1, 7) seat_row,
      substr(line, 8, 3) seat_col,
      line orig
    from aoc_day5_input
  ),
  binary_data as (
    select
      translate(seat_row, 'FB', '01') b_seat_row,
      translate(seat_col, 'LR', '01') b_seat_col
      from seat_data
  )
select * from binary_data
Enter fullscreen mode Exit fullscreen mode

Now, we need to convert these binary-like strings into decimal numbers. Unfortunately, Oracle doesn’t provide a convenient function to do this, but it’s not very difficult to do it on our own: Take each char of b_seat_rowand b_seat_coland multiply it with the according power of 2. For the first bit (which is the one with the highest value) it’s power(2,6), for the second power(2,5)etc.

After that, we calculated the ID as requested and can kindly ask the database to give us the max value.

with
  seat_data as (
    select
      substr(line, 1, 7) seat_row,
      substr(line, 8, 3) seat_col,
      line orig
    from aoc_day5_input
  ),
  binary_data as (
    select
      translate(seat_row, 'FB', '01') b_seat_row,
      translate(seat_col, 'LR', '01') b_seat_col
      from seat_data
  ),
  decimal_data as (
    select
      substr(b_seat_row, 1, 1)*power(2,6)
        + substr(b_seat_row, 2, 1)*power(2,5)
        + substr(b_seat_row, 3, 1)*power(2,4)
        + substr(b_seat_row, 4, 1)*power(2,3)
        + substr(b_seat_row, 5, 1)*power(2,2)
        + substr(b_seat_row, 6, 1)*power(2,1)
        + substr(b_seat_row, 7, 1)
      dec_seat_row,
      substr(b_seat_col, 1, 1)*power(2,2)
        + substr(b_seat_col, 2, 1)*power(2,1)
        + substr(b_seat_col, 3, 1)
      dec_seat_col,
      b_seat_row,
      b_seat_col
      from binary_data
  ),
  data_with_id as (
    select
      dec_seat_row * 8 + dec_seat_col id,
      dec_seat_col,
      b_seat_row,
      b_seat_col
      from decimal_data
  )
select max(id)
from data_with_id;
Enter fullscreen mode Exit fullscreen mode

Part 2 now requires us to find our seat-ID. It’s the only ID missing in the list, so we can use the analytic functions lag and lead to analyze the gaps between the IDs and find the one where there is a gap of 2.

with
  seat_data as (
    select
      substr(line, 1, 7) seat_row,
      substr(line, 8, 3) seat_col,
      line orig
    from aoc_day5_input
  ),
  binary_data as (
    select
      translate(seat_row, 'FB', '01') b_seat_row,
      translate(seat_col, 'LR', '01') b_seat_col
      from seat_data
  ),
  decimal_data as (
    select
      substr(b_seat_row, 1, 1)*power(2,6)
        + substr(b_seat_row, 2, 1)*power(2,5)
        + substr(b_seat_row, 3, 1)*power(2,4)
        + substr(b_seat_row, 4, 1)*power(2,3)
        + substr(b_seat_row, 5, 1)*power(2,2)
        + substr(b_seat_row, 6, 1)*power(2,1)
        + substr(b_seat_row, 7, 1)
      dec_seat_row,
      substr(b_seat_col, 1, 1)*power(2,2)
        + substr(b_seat_col, 2, 1)*power(2,1)
        + substr(b_seat_col, 3, 1)
      dec_seat_col,
      b_seat_row,
      b_seat_col
      from binary_data
  ),
  data_with_id as (
    select
      dec_seat_row * 8 + dec_seat_col id,
      dec_seat_col,
      b_seat_row,
      b_seat_col
      from decimal_data
  ),
  id_analysis as (
    select
      id,
      id-lag(id) over (order by id) gap_prev,
      lead(id) over (order by id)-id gap_next
    from data_with_id
  )
select
  prev.id+1 my_id
from id_analysis prev, id_analysis next
where prev.gap_next > 1
  and next.gap_prev > 1
  and next.id - prev.id = 2;

Enter fullscreen mode Exit fullscreen mode

You can find this complete example in the newly created github-repository.

To get the sample data into Oracle LiveSQL is too annoying at the moment, so I won’t do it.

Discussion (3)

Collapse
saxus profile image
saxus

Hi! I think this solution is way overcomplicated. You can simply cast it into bit(10) then an integer.

Here is my solution:

select
max(translate(rec, 'FLBR', '0011')::bit(10)::integer)
from day5;

Also you don't need to care about the rows and columns in part 1 because it is a single bit array.

Collapse
pesse profile image
Samuel Nitsche Author

I see you're using Postgres' CAST syntax.
Would be neat if this was possible in Oracle - which is not the case (as I wrote in the post).
I agree on the thing that I could just use the whole bit array, but I wanted to implement it as relatable to the original puzzle test as possible.

Collapse
saxus profile image
saxus

Oh, I didn't realize, that you're using Oracle.