Advent of Code 2022 in Oracle - Day 10

My solution for the tenth day of the Advent of Code 2022 challenge "Cathode-Ray Tube" with Oracle. We simulate a CPU and a Pixel-Screen in pure SQL!

Advent of Code

Advent of Code is a cool yearly programming challenge. Each day from 1st to 25th December a new challenge appears. You can solve it in any programming language you like. After deepening my Go skills last year I will do this in Oracle (so PL/SQL and SQL) this year.

I try to blog about my solutions but I won’t make it every day or give up after a while as they get more difficult and time-consuming. You can find my solutions for this year in this repository.

I really suggest you check Advent of Code out yourself as it is a lot of fun and you will improve your problem-solving skills.

The challenges are clearly phrased with a simple example you can do in your head. You then get a way bigger generated and user-specific input and have to solve the challenge with that. You have to enter a solution in an input field and get a star for each day you solved. There is also a second challenge every day where you have to adapt some part of your algorithm to solve it.

Challenge 1

You can find the challenge here.

Today’s challenge was really fun. We receive some inputs that look like this:

1noop
2noop
3noop
4addx 6
5addx -1
6addx 5
7noop
8noop
9noop
10addx 5
11...
12

These are inputs for a CPU we have to simulate. Noop does nothing for one cycle whereas addx takes two cycles. In the first cycle nothing happens in the second we add up the given value to a register “x”.

In the end, we have to calculate the state of the register at the cycles 20, 60, 100, 140, and 180. We also have to multiply the state by the cycle number to get the signal strength and sum up all these values.

Solving challenge 1

Parsing the input

After parsing cryptic input for the last 10 days this was a breeze. We split the lines and extract the command (noop or addx) and the value:

1with lines as (
2      select rownum as line_no, column_value as line
3        from table (
4          select apex_string.split(input) from aoc_input where year = 2022 and day = 10
5        )
6)
7select line_no, substr(line, 1, 4) as op, to_number(substr(line, 6)) as add_x
8  from lines;
9
10/* Result_
11   LINE_NO OP         ADD_X
12__________ _______ ________
13         1 noop
14         2 noop
15         3 noop
16         4 addx           6
17         5 addx          -1
18         6 addx           5
19         7 noop
20         8 noop
21         9 noop
22        10 addx           5
23*/
24

Simulating the CPU Cycles

We can then simulate the CPU cycles by creating a second row for every addx command as it takes two cycles. I added a cycle_no column with row_number so we always know in which cycle we are. I also only display the add_x value for the second cycle of an addx command as it gets added after the first cycle and we can sum the column up now without getting adding the values two times. Additionally, I added an initial state with x = 1:

1-- ... previous part
2select row_number() over (order by line_no, command_cycle) + 1 as cycle_no
3     , case when command_cycle = 2 then add_x else null end as add_x
4     , op
5  from statements
6 cross join lateral(
7      select level command_cycle
8        from dual
9     connect by level <= case when op = 'noop' then 1 else 2 end
10  ) char_rows
11 union
12 select 1, 1, 'init' from dual -- initial state -> x = 1
13 fetch first 20 rows only
14;
15
16
17/* Result
18   CYCLE_NO    ADD_X OP
19___________ ________ _______
20          1        1 init
21          2          noop
22          3          noop
23          4          noop
24          5          addx
25          6        6 addx
26          7          addx
27          8       -1 addx
28          9          addx
29         10        5 addx
30         11          noop
31         12          noop
32         13          noop
33         14          addx
34         15        5 addx
35         16          addx
36         17       11 addx
37         18          addx
38         19      -10 addx
39*/
40

Now we have a table with all the commands and their cycles. The next step is to calculate the state of the register at the given cycle. For that, we can use rolling sums with the sum window function. The function adds up all the values in the add_x column until the current row. Additionally, we can calculate the signal strength by multiplying the state with the cycle number:

1-- ... previous part
2select cycle_no
3     , sum(add_x) over (order by cycle_no) as curr_x
4     , sum(add_x) over (order by cycle_no) * cycle_no as signal_strength
5  from cycle_times
6;
7
8/* Result
9   CYCLE_NO    CURR_X    SIGNAL_STRENGTH
10___________ _________ __________________
11          1         1                  1
12          2         1                  2
13          3         1                  3
14          4         1                  4
15          5         1                  5
16          6         7                 42
17          7         7                 49
18          8         6                 48
19          9         6                 54
20         10        11                110
21         11        11                121
22         12        11                132
23         13        11                143
24         14        11                154
25         15        16                240
26         16        16                256
27         17        27                459
28         18        27                486
29         19        17                323
30*/
31

Getting the result

Now we can just filter for the cycles we need and sum up the signal strength:

1-- ... previous part
2select sum(signal_strength) as sum_signal_strength
3  from signal_strength
4 where cycle_no in (20, 60, 100, 140, 180, 220)
5;
6

You can check out the full solution here.

Challenge 2

The second part goes a few steps further. Here I struggled a lot because of one little misunderstanding of the challenge description that lead to a completely different solution. Lesson learned for me: Read the challenge description carefully!

Turns out the CPU also renders pixels onto a screen with a width of 40 pixels. The x-register value is used for a sprite that is 3 pixels wide (so +1 and -1 of x) and 1 pixel high.

If the current pixel position (basically CPU Cycle) is within the sprite range we draw a pixel. Because the screen is also 6 pixels high, cycles 1 - 40 are for the first row, 41 - 80 for the second, and so on.

If we draw the screen correctly we can see letters appearing that we have to input to complete the challenge.

Solving challenge 2

We start with our prior query and move on by getting the current state of the register at every cycle. Then we need to figure out at which cycle which pixel is drawn:

1-- ... previous part
2), sprite_info as (
3select cycle_no
4     , sum(add_x) over (order by cycle_no) as sprite_position
5  from cycle_times
6)
7select cycle_no
8     , mod(cycle_no - 1, 40) as pixel_position -- starts at 0
9     , floor( (cycle_no - 1) / 40) as row_position
10     , sprite_position
11  from sprite_info
12;
13
14/* Result
15   CYCLE_NO    PIXEL_POSITION    ROW_POSITION    SPRITE_POSITION
16___________ _________________ _______________ __________________
17          1                 0               0                  1
18          2                 1               0                  1
19          3                 2               0                  1
20          4                 3               0                  1
21          5                 4               0                  1
22          6                 5               0                  7
23          7                 6               0                  7
24          8                 7               0                  6
25          9                 8               0                  6
26         10                 9               0                 11
27*/
28

With that we can easily determine if a pixel should be drawn or not by checking if the pixel position is within the sprite range:

1-- ... previous part
2select cycle_no
3     , pixel_position
4     , row_position
5     , sprite_position
6     , case when
7        pixel_position between sprite_position - 1 and sprite_position + 1
8          then 1 else 0
9       end as draw_pixel
10  from sprite_data
11;
12
13/* Result
14   CYCLE_NO    PIXEL_POSITION    ROW_POSITION    SPRITE_POSITION    DRAW_PIXEL
15___________ _________________ _______________ __________________ _____________
16          1                 0               0                  1             1
17          2                 1               0                  1             1
18          3                 2               0                  1             1
19          4                 3               0                  1             0
20          5                 4               0                  1             0
21          6                 5               0                  7             0
22          7                 6               0                  7             1
23          8                 7               0                  6             1
24          9                 8               0                  6             0
25         10                 9               0                 11             0
26*/
27

Now comes the tricky part, how to draw the screen?! I eventually went with a huge pivot query and some SQLcl column format options to get the result drawn in a readable way:

1-- show no headings, paginations and set the linesize to 1000
2set heading off
3set pagesize 0
4set linesize 1000
5
6-- every col should be 1 char wide
7column 0 Format a1
8column 1 Format a1
9column 2 Format a1
10-- ...
11column 39 Format a1
12
13--- ... previous part
14), prep_data as (
15select row_position
16     , pixel_position
17     , draw_pixel
18  from pixel_data
19 where cycle_no <= 240
20)
21  select row_position
22       , case when "0" = 1 then '#' else '.' end as "0"
23       , case when "1" = 1 then '#' else '.' end as "1"
24       , case when "2" = 1 then '#' else '.' end as "2"
25       -- ...
26       , case when "39" = 1 then '#' else '.' end as "39"
27    from prep_data
28  pivot (
29    max(draw_pixel)
30    for pixel_position in (
31      0  as "0"
32    , 1  as "1"
33    , 2  as "2"
34    -- ...
35    , 39 as "39"
36    )
37  )
38;
39
40/* Result
410 # # # . . . # # . . # # # . . # . . # . # # # . . # # # # . . # # . . # # # . .
421 # . . # . # . . # . # . . # . # . . # . # . . # . # . . . . # . . # . # . . # .
432 # . . # . # . . . . # . . # . # # # # . # # # . . # # # . . # . . # . # # # . .
443 # # # . . # . # # . # # # . . # . . # . # . . # . # . . . . # # # # . # . . # .
454 # . . . . # . . # . # . . . . # . . # . # . . # . # . . . . # . . # . # . . # .
465 # . . . . . # # # . # . . . . # . . # . # # # . . # # # # . # . . # . # # # . .
47*/
48

Seeing the resulting letters take shape was a beautiful moment. I took some time as I thought that at the render time the sprite was not yet updated. This small change caused the output to look really chaotic. I thought I was doing something fundamentally wrong. So close and yet so far… But I eventually figured it out!

You can check out the full solution here.

Comments

loading comments...