2020 Advent of Code – Day 5 | Voice of the DBA

2020 Advent of Code – Day 5

This series looks at the Advent of Code challenges.

As one of my goals, I’m working through challenges. This post looks at day 5. I’m going to do this one in Python here, though I did solve it in other languages in my repo.

Part 1

This is an interesting problem, and one that’s simpler than it appeared at first. I started down the path of some hash bucket thing, moving to calculate rows before I got to the end and realized this is really a binary problem.

As a result, after I loaded the data, I started here:

SELECT 
   (SUBSTRING(d.SeatCode, 1, 1) * 64) +
   (SUBSTRING(d.SeatCode, 2, 1) * 32 ) +
   (SUBSTRING(d.SeatCode, 3, 1) * 16 ) +
   (SUBSTRING(d.SeatCode, 4, 1) * 8 ) +
   (SUBSTRING(d.SeatCode, 5, 1) * 4    ) +
   (SUBSTRING(d.SeatCode, 6, 1) * 2    ) +
   (SUBSTRING(d.SeatCode, 7, 1) * 1    ) AS row,
   (SUBSTRING(d.SeatCode, 8, 1) * 4    )  +
   (SUBSTRING(d.SeatCode, 9, 1) * 2    )  +
   (SUBSTRING(d.SeatCode, 10, 1) * 1    )  AS seat
  FROM dbo.Day5 AS d

Here you can see I broke this into two binary sections. The first 7 characters get you a row code from 0 to 127. The last 3 values get you a 0 to 7 value. I should have been clued in when I saw the 0s here. In any case, this gets me the two binary values.

The seat code is the row multiplied by 8 and then adding the seat. I took the above query, wrapped it with a CTE and then ordered by seat codes. This gave me the highest value, which solved the problem.

WITH cteAirplane( ROW, seat)

AS

(SELECT 
   (SUBSTRING(d.SeatCode, 1, 1) * 64) +
   (SUBSTRING(d.SeatCode, 2, 1) * 32 ) +
   (SUBSTRING(d.SeatCode, 3, 1) * 16 ) +
   (SUBSTRING(d.SeatCode, 4, 1) * 8 ) +
   (SUBSTRING(d.SeatCode, 5, 1) * 4    ) +
   (SUBSTRING(d.SeatCode, 6, 1) * 2    ) +
   (SUBSTRING(d.SeatCode, 7, 1) * 1    ) AS row,
   (SUBSTRING(d.SeatCode, 8, 1) * 4    )  +
   (SUBSTRING(d.SeatCode, 9, 1) * 2    )  +
   (SUBSTRING(d.SeatCode, 10, 1) * 1    )  AS seat
  FROM dbo.Day5 AS d
  --ORDER BY row desc
  )
  SELECT (row * 8)+seat AS seatID
  FROM cteAirplane
  ORDER BY seatID DESC

Part 2

The second part is a different problem. Now I need the seat codes, but I’m looking for a gap here. Meaning a missing seat code.

I decided to use LAG here. I altered my first CTE to calculate the seat code directly rather than returning the row and seat. Then I added this CTE:

cteValues (SeatID, diff)

AS

(

SELECT seatid, SeatID - LAG(SeatID,1) OVER (ORDER BY SeatID) AS diff

FROM cteAirplane

) 

This CTE found the difference between each subsequent Seat codes using the OVER() clause. My final query was looking for a diff > 1, which returned 1 row. That was the answer.