Advent of Code 2022 in Oracle - Day 3

My solution for the third day of the Advent of Code 2022 challenge "Rucksack Reorganization" with Oracle. Its starting to get complex...

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 is quite more complex than yesterday’s.

We get a pretty random-looking input that consists of random letters both lower and uppercase:

1vJrwpWtwJgWrhcsFMMfFFhFp
2jqHRNqRjqzjGDLGLrsFMfFZSrLrFZsSL
3PmmdzqPrVvPwwTWBwg
4wMqvLMZHhHMvwLHjbvcjnnSBnvTQFn
5ttgJtRGJQctTZtZT
6CrZsJsPPZsGzwwsLwLmpwMDw
7

Each line represents one elf. Each letter represents some kind of item in the backpack of an elf.

The first task is to find the item of each elf, that is present in the first and second half of the input. We then need to translate this letter to a priority number (a-z = 1-26, A-Z = 27-52) and sum up all these.

Solving challenge 1

Today I had to fall back to PL/SQL again after I did yesterday’s challenge purely in SQL.

At first, I went ahead and created a table to store the backpack data of each elf:

1create table aoc_backpacks (
2  id number primary key
3, line  varchar2(1000)
4, half1 varchar2(500)
5, half2 varchar2(500)
6) inmemory;
7

The second table holds the char present in both halves and the priority number:

1create table aoc_duplicate_chars (
2  line     number primary key
3, dup_char varchar2(1 char)
4, prio     number
5) inmemory;
6

To fill the first table we split the input by line and then split it into halves with substr:

1insert into aoc_backpacks
2with data as (
3  select rownum as line_no
4       , column_value as line
5       , length(column_value) as line_len
6                 -- split by newline
7    from table ( select apex_string.split(input)
8                   from aoc_input
9                  where year = 2022 and day = 3
10               )
11)
12select line_no as id
13     , line
14     , substr(line, 1, line_len / 2) as half1
15     , substr(line, line_len / 2 + 1,  line_len / 2) as half2
16  from data
17;
18

We can now go ahead and find the duplicate chars in each half. For that we need to loop through every char of the first half and check if it is present in the second one:

1declare
2  type t_backpacks is table of aoc_backpacks%rowtype;
3  l_backpacks t_backpacks;
4
5  l_len   pls_integer;
6  l_char  varchar2(1 char);
7  l_count pls_integer;
8begin
9  select *
10    bulk collect into l_backpacks
11    from aoc_backpacks
12  ;
13
14  for i in 1 .. l_backpacks.count loop
15    l_len := length(l_backpacks(i).half1);
16
17    -- loop through every char of half1
18    for j in 1 .. l_len loop
19      l_char := substr(l_backpacks(i).half1, j, 1);
20
21      -- count occurrences of char in half2
22      l_count := regexp_count(l_backpacks(i).half2, l_char);
23
24      if l_count > 0 then
25        dbms_output.put_line(
26          apex_string.format('(%0) Char "%1" found in each half.', i, l_char)
27        );
28
29        insert into aoc_duplicate_chars (line, dup_char) values (i, l_char);
30
31        -- we only need to find the first match
32        exit;
33
34      end if;
35    end loop;
36  end loop;
37end;
38

Note that we did not assign a priority number yet. We can do that in a single update statement afterward. I did not want to manually assign a letter to all 52 numbers so I used the ascii function. It returns an ASCII integer code for a given character. It does not match the numbers we need but we can easily calculate them with a simple formula as they increase by 1 for each letter:

1update aoc_duplicate_chars
2   set prio  = case when lower(dup_char) = dup_char then
3                 ascii(dup_char) - 96  -- when lower char, subtract 96
4               else
5                 ascii(dup_char) - 38  -- when upper char, subtract 38
6               end
7;
8

Lastly, we only need to sum the priorities of all duplicate chars:

1select sum(prio) as sum
2  from aoc_duplicate_chars
3;
4

You can check out the full solution here.

Challenge 2

Part 2 is a bit more complex. The backpacks are not halved anymore instead we need to find the letter appearing for every elf in groups of 3. So lines 1-3 are a group, 4-6, and so on.

Solving challenge 2

We only need to modify the PL/SQL code. Instead of processing every line, we are looking at each group in a single loop now. We then need to find the longest line in the group and loop through every char of that line and check if it also appears in the other lines of the group:

1declare
2  type t_backpacks is table of aoc_backpacks%rowtype;
3  l_backpacks t_backpacks;
4
5  l_longest_line aoc_backpacks.line%type;
6  l_len   pls_integer;
7  l_char  varchar2(1 char);
8
9  l_idx_to_check1 pls_integer;
10  l_found1        boolean;
11  l_idx_to_check2 pls_integer;
12  l_found2        boolean;
13begin
14  select *
15    bulk collect into l_backpacks
16    from aoc_backpacks
17  ;
18
19  for i in 1 .. l_backpacks.count loop
20   -- only process every third line
21    if mod(i, 3) != 0 then
22      continue;
23    end if;
24
25    dbms_output.put_line('Processing line ' || i);
26
27    l_longest_line := l_backpacks(i).line;
28    l_len := length(l_backpacks(i).line);
29    l_idx_to_check1 := i - 1;
30    l_idx_to_check2 := i - 2;
31
32    -- check if line in other group is longer
33    if length(l_backpacks(i - 1).line) > l_len then
34      l_longest_line := l_backpacks(i - 1).line;
35      l_len := length(l_backpacks(i - 1).line);
36      l_idx_to_check1 := i;
37      l_idx_to_check2 := i - 2;
38    end if;
39
40    if length(l_backpacks(i - 2).line) > l_len then
41      l_longest_line := l_backpacks(i - 2).line;
42      l_len := length(l_backpacks(i - 2).line);
43      l_idx_to_check1 := i;
44      l_idx_to_check2 := i - 1;
45    end if;
46
47    -- dbms_output.put_line('Str1: ' || l_longest_line);
48    -- dbms_output.put_line('Str2: ' || l_backpacks(l_idx_to_check1).line || ' - ' || l_idx_to_check1);
49    -- dbms_output.put_line('Str3: ' || l_backpacks(l_idx_to_check2).line || ' - ' || l_idx_to_check2);
50
51    -- loop every char of the longest line
52    for j in 1 .. l_len loop
53      l_char := substr(l_longest_line, j, 1);
54
55      -- count occurrences of char in two other lines
56      l_found1 := regexp_count(l_backpacks(l_idx_to_check1).line, l_char) > 0;
57      l_found2 := regexp_count(l_backpacks(l_idx_to_check2).line, l_char) > 0;
58
59      if l_found1 and l_found2 then
60        dbms_output.put_line(
61          apex_string.format('(%0) Char "%1" found in every line.', i / 3, l_char)
62        );
63
64        insert into aoc_triplet_chars (line, dup_char) values (i, l_char);
65
66        -- we only need to find the first match
67        exit;
68
69      end if;
70    end loop;
71  end loop;
72end;
73

At last, we need again to assign a priority number and sum them up. You can check out the full solution here.

I really enjoyed this challenge. I can imagine that there are many different approaches to solving it. I would love to see your solutions.

Comments

loading comments...