Advent of Code 2022 in Oracle - Day 10
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...
12These 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*/
24Simulating 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*/
40Now 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*/
31Getting 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;
6You 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*/
28With 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*/
27Now 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*/
48Seeing 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.