Advent of Code 2022 in Oracle - Day 5

Solution for Day 4

As I enjoyed my weekend yesterday I did not describe my solution for day 4. I still solved it you can find my solution on GitHub. Spoiler: it was fairly easy with SQL. For today’s challenge, I used a fairly complex approach (I struggled a lot…).

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.

The elves have a crane and different stacks of goods. We get the initial stack setup in the first part of the input. Below that we get a list of commands to move the goods around. We need to find the topmost good in every stack after all commands are executed.

This is the sample input:

1    [D]
2[N] [C]
3[Z] [M] [P]
4 1   2   3
5
6move 1 from 2 to 1
7move 3 from 1 to 3
8move 2 from 2 to 1
9move 1 from 1 to 2
10

Solving challenge 1

Parsing the initial stack setup

We first need to parse the initial stack setup. To make it easier to parse I want to change the not filled goods from spaces to [-]. Basically, I want it to look like this:

1[-] [D] [-]
2[N] [C] [-]
3[Z] [M] [P]
4

This was more complex than I thought. As an empty box is represented as three spaces I replaced four spaces with [-]. This works great except for an empty box in the first stack:

1 [-][D] [-]
2[N] [C] [-]
3[Z] [M] [P]
4

So I needed to add another replace that adds a space between two boxes that are not separated by a space. An additional trim removes the leading space. I then excluded all not stack lines with a simple like resulting in the following query:

1with lines as (
2  select rownum as line_no, trim(replace(
3              replace(column_value, '    ', ' [-]')
4            , '][', '] ['
5         )) as line
6                 -- split by newline
7    from table ( select apex_string.split(sample_input) from aoc_input where year = 2022 and day = 5 )
8)
9select line_no, line
10    from lines
11   where line like '[%'
12;
13
14/* Result:
15
16   LINE_NO LINE
17__________ ______________
18         1 [-] [D] [-]
19         2 [N] [C] [-]
20         3 [Z] [M] [P]
21*/
22

My next step is to get each box in a single line. In the real input, the amount of stacks is 8 instead of 3 so I need this query to work for any amount of stacks. To achieve that I generated the rows with a hierarchical query and got each box with a regexp_substr:

1select distinct line_no
2     , block_no
3       -- basically match "[{any single uppercase letter}]" or "[-]"
4       -- and only capture the letter or "-"
5       --
6       -- block_no cycles through every stack number (1-3 for the sample input)
7       -- and thus gets a different block every time from the regex
8     , regexp_substr(line, '\[([A-Z]|-)\]', 1, block_no, null, 1) as block
9  from starting_grid
10  -- generate a row for each block
11  cross join lateral(
12    select level block_no
13      from dual
14   -- each block sperated by a ' ' so count the number
15   -- of spaces +1 to get amount of needed rows
16   connect by level <= regexp_count(line, ' ') + 1
17  ) block_rows
18order by line_no
19;
20
21/* Result:
22
23   LINE_NO    BLOCK_NO BLOCK
24__________ ___________ ________
25         1           1 -
26         1           2 D
27         1           3 -
28         2           1 N
29         2           2 C
30         2           3 -
31         3           1 Z
32         3           2 M
33         3           3 P
34*/
35

I got the hierarchical query approach from Kim Berg Hansen’s book Practical Oracle SQL. I highly recommend it if you want to deepen your SQL skills.

Parsing the crane inputs

Getting the crane inputs into a relational structure is fairly easy. We need to split the input by lines, only get the ones that start with move, and then extract the relevant information with regexp_substr:

1insert into aoc_moves
2 with lines as (
3    select rownum as line_no, trim(replace(
4                replace(column_value, '    ', ' [-]')
5              , '][', '] ['
6          )) as line
7      from table ( select apex_string.split(input) from aoc_input where year = 2022 and day = 5 )
8  )
9  select line_no
10       , regexp_substr(line, 'move ([0-9]+) from [0-9]+ to [0-9]+', 1, 1, null, 1) as amount
11       , regexp_substr(line, 'move [0-9]+ from ([0-9]+) to [0-9]+', 1, 1, null, 1) as from_stack
12       , regexp_substr(line, 'move [0-9]+ from [0-9]+ to ([0-9]+)', 1, 1, null, 1) as to_stack
13    from lines
14   where line like 'move%'
15;
16
17/* Result:
18
19   LINE_NO    AMOUNT    FROM_STACK    TO_STACK
20__________ _________ _____________ ___________
21         6         1             2           1
22         7         3             1           3
23         8         2             2           1
24         9         1             1           2
25*/
26

Store stack state

To simulate the crane inputs we need to keep track of the current state of the stacks. For that I created a PL/SQL map / associative array I can access via the stack number. Each entity holds another array of the blocks in the stack indexed by the block number (1 lowest stacking up to X).

1type t_block_arr is table of varchar2(1 char) index by pls_integer;
2type t_stack_arr is table of t_block_arr index by pls_integer;
3l_stack_arr t_stack_arr;
4

To set up the initial state I used a bulk collect query for each stack:

1select max(stack_no) into l_stack_count from aoc_initial_blocks;
2dbms_output.put_line('stack count: ' || l_stack_count);
3
4for i in 1 .. l_stack_count
5loop
6  select block
7    bulk collect into l_stack_arr(i)
8    from aoc_initial_blocks
9   where stack_no = i
10     and block != '-'
11   order by line_no desc;
12
13  dbms_output.put_line('stack ' || i || ' has ' || l_stack_arr(i).count || ' blocks');
14end loop;
15

Simulating the crane inputs

To process the crane inputs I looped over every entry of the stored moves. In there I need another loop to process multiple blocks being transferred from the same stack one after another. The moving part itself is just getting the last block of the “from” stack and adding it to the “to” stack. And don’t forget to delete the removed block from the “from” stack:

1for rec in (
2  select amount
3       , from_stack -- number
4       , to_stack   -- number
5    from aoc_moves order by line_no
6)
7loop
8
9  for i in 1 .. rec.amount
10  loop
11
12    l_tmp_from_index := l_stack_arr(rec.from_stack).count;
13    l_tmp_block_to_move := l_stack_arr(rec.from_stack)(l_tmp_from_index);
14    l_stack_arr(rec.from_stack).delete(l_tmp_from_index);
15
16    l_tmp_to_index := l_stack_arr(rec.to_stack).count + 1;
17    l_stack_arr(rec.to_stack)(l_tmp_to_index) := l_tmp_block_to_move;
18
19  end loop;
20end loop;
21

Output sequence

After all moves are processed we can get the final sequence by logging the top block of every stack:

1for i in 1 .. l_stack_count
2loop
3  l_result := l_result || l_stack_arr(i)(l_stack_arr(i).count);
4end loop;
5
6dbms_output.put_line('result: ' || l_result);
7

You can check out the full solution here.

Challenge 2

Part 2 just needs a small change to process the crane inputs. In the first part, the crane moved one box at a time meaning that when it moves more than one block the order gets reversed during this process.

In the second part the crane instead grabs multiple blocks at once and moves them in the same order they were stacked.

Solving challenge 2

To achieve that I first collect all blocks from a single move operation in a temporary array and then move them to the new stack in the same order with a reversed loop:

1for rec in (
2  select * from aoc_moves order by line_no
3)
4loop
5
6  l_tmp_block_arr := t_block_arr();
7
8  for i in 1 .. rec.amount
9  loop
10    l_tmp_from_index := l_stack_arr(rec.from_stack).count;
11    l_tmp_block_to_move := l_stack_arr(rec.from_stack)(l_tmp_from_index);
12    l_stack_arr(rec.from_stack).delete(l_tmp_from_index);
13
14    -- collect blocks to move
15    l_tmp_block_arr(i) := l_tmp_block_to_move;
16  end loop;
17
18  -- reversed loop because lowest of old stack
19  -- is highest of temp array
20  for i in reverse 1 .. rec.amount
21  loop
22    l_tmp_to_index := l_stack_arr(rec.to_stack).count + 1;
23    l_stack_arr(rec.to_stack)(l_tmp_to_index) := l_tmp_block_arr(i);
24    l_tmp_block_arr.delete(i);
25  end loop;
26end loop;
27