Появление Кодекса — День 3

Сегодняшнее испытание «Пришествие кода» действительно интересное. Как-то легко, но с парочкой интересных дискуссионных моментов.

День 3: Реорганизация рюкзака помогает эльфам организовать и расставить приоритеты в своих припасах.

Я импортировал входные данные, как обычно, скопировав их с веб-сайта в мой запрос Azure Data Studio, а затем используя STRING_SPLIT для импорта каждой отдельной строки, представляющей содержимое рюкзака, в отдельной строке:

declare @input nvarchar(max) = 'QLFdFCdlLcVqdvFLnFLSSShZwptfHHhfZZZpSwfmHp
rTJRjjbJTgzDJjdsRsfwtfNwtfmZpZNhmmzt
...
jGrGqjJfqccrfqGcGplrJpFvzggqmCtMzmsMnvMvvCgm';

drop table if exists dbo.ch03_input;
create table ch03_input 
(
    id int identity not null primary key,
    items varchar(100) collate Latin1_General_BIN2
);

insert into 
    dbo.ch03_input (items)
select 
    trim(replace([value], char(13), ''))
from
    string_split(@input, char(10))
go

Предметы в рюкзаках обозначаются буквами, а идентификаторы чувствительны к регистру. По этой причине я использовал сортировку Latin1_General_BIN2, которая гарантирует соблюдение требований и получение максимально возможной производительности со строками, как описано в посте о решении задач второго дня.

Часть 1

В первой части задания список рюкзаков разделен на две части, и вы должны найти тип предмета, представленный его буквой, который есть в обоих списках. Это проблема сравнения строк: какая буква из первого списка тоже во втором списке?

Первый шаг — разбить список на два списка одинакового размера:

select 
    *,
    len(items) as itemcount,
    left(items, len(items)/2) as comp1,
    right(items, len(items)/2) as comp2
into    
    #step1
from 
    ch03_input;

Я также рассчитываю длину строки, так как она пригодится на следующем шаге, где я разделю строку рюкзака на буквы и буду хранить каждую букву в отдельной строке:

select top(100) row_number() over (order by a.object_id) as n into #n from sys.columns a cross join sys.columns b

select 
    *,
    substring(items, n, 1) as item 
into
    #step2 
from 
    #step1 s  
cross join
    #n n
where 
    n.n <= s.itemcount

Разбить строку на буквы легко, если у вас есть таблица с числами, что я и создаю в первую очередь в приведенном выше запросе. Затем я использую эту таблицу чисел для создания строки для каждой буквы в строке через CROSS JOIN, и для каждой строки генерируется извлечение Nth буквы строки. Предложение WHERE использует itemcount, чтобы убедиться, что я генерирую ровно одну строку для каждой буквы в каждой строке, и не более того.

Затем мне нужно найти, какой предмет находится в обоих отсеках. Это означает проверку наличия буквы в строке, что можно сделать с помощью CHARINDEX:

select distinct
    id, items, comp1, comp2, item,
    charindex(item, comp1, 1) as p1, 
    charindex(item, comp2, 1) as p2
into 
    #step3
from 
    #step2 
where 
    charindex(item, comp1, 1) != 0 
and 
    charindex(item, comp2, 1) != 0
order by id

Запросу требуется DISTINCT, так как в строке может быть более одного элемента одного типа, мне нужен только один элемент для каждого типа. Тот факт, что мне нужно использовать DISTINCT, звонит в колокола (или приносит какой-то запах): я почти уверен, что смогу реорганизовать свой код, чтобы выполнить эту операцию раньше и избежать проверки буквы, которая уже была найдена. Я сделаю это позже, если у меня будет достаточно свободного времени. А пока я хочу посмотреть, работает ли мое решение; после этого я могу оптимизировать его.

Теперь, когда предметы, присутствующие в обоих отсеках, найдены, я должен присвоить каждому типу предметов значение приоритета, как описано в задаче. Значения приоритетов основаны на алфавитном порядке, поэтому я могу использовать ASCII, чтобы получить буквенное значение и преобразовать его в соответствующее значение приоритета. Значения приоритета упорядочены иначе, чем порядок ASCII, поэтому для применения правильных преобразований требуется оператор CASE:

select
    item,
    case 
        when item like '[a-z]' then ASCII(item) - ASCII('a') + 1
        when item like '[A-Z]' then ASCII(item) - ASCII('A') + 27
    end as priority,
    id,
    comp1,
    comp2
into
    #priorities
from
    #step3
order by
    item

А теперь просто суммируя все приоритеты, мы получим ответ:

select sum(priority) from #priorities

Ответ правильный, поэтому переходим к следующей части задания.

Часть 2

Эльфы собираются группами по три человека, и цель состоит в том, чтобы выяснить, какой тип предметов несут все в группе.

Первый шаг — создать способ легко сгруппировать эльфов вместе. Используя существующие столбцы id и оператор по модулю, я могу определить, когда начинается новая группа. Когда результат операции по модулю равен единице:

Мне просто нужно знать, когда начинается группа, поэтому я могу установить все, что не равно 1, на 0:

Теперь я могу использовать простой и быстрый промежуточный итог для создания group_id, который позволит быстро идентифицировать все элементы в одной группе. Удивительно, не так ли?

Забавно, что мой друг SQL Guru Itzik упомянул эту технику с промежуточным итогом, когда мы встретились вчера вечером. Забавно, что он мне понадобился бы прямо на следующий день. Спасибо, Ицик!

Окончательный запрос следующий:

select 
    *,
    len(items) as itemcount,
    sum(case when (id % 3) != 1 then 0 else 1 end) over (order by id) as group_id
into    
    #step1
from 
    ch03_input;

легко, быстро и элегантно!

Как только появится способ идентифицировать каждую группу, задача почти решена. Это просто вопрос разделения строк на их буквы, как я сделал и в первой части.

select 
    *,
    substring(items, n, 1) as item 
into
    #step2 
from 
    #step1 s  
cross join
    #n n
where 
    n.n <= s.itemcount

Теперь у меня есть все необходимое, чтобы увидеть, какая буква присутствует во всех трех рюкзаках. Как простая GROUP BY фильтрация только тех букв, которые встречаются ровно три раза с использованием предложения HAVING, даст ответ:

with cte as
(    
    select distinct id, group_id, item from #step2 
)
select
    group_id,
    item
into
    #step3
from
    cte
group by 
    group_id, item
having
    count(*) = 3
order by
    group_id

Сложность здесь заключается в операторе DISTINCT в Common Table Expression. Этот DISTINCT гарантирует, что я смогу отличить предмет, появляющийся трижды в одном и том же рюкзаке, от предмета, появляющегося по одному во всех трех рюкзаках. Нас интересует только последнее, а не первое.

Теперь мне просто нужно применить ту же логику, чтобы получить значение приоритета, которое использовалось ранее, вычислить общую сумму, и я получу решение части 2. Задача выполнена.

Попробуй сам

Полное решение доступно здесь: yorek/aoc-2022

Техника работы с островками данных полезна во многих практических случаях, поэтому я настоятельно рекомендую вам глубоко погрузиться в нее. Воспользуйтесь бесплатной главой книги на эту тему, доступной здесь: Пробелы и острова.

Альтернативное решение части 2

Альтернативным решением могло бы быть простое СОЕДИНЕНИЕ между тремя рюкзаками в одной группе:

select distinct
    a.id as group_id,
    a.item as item
into
    #step3
from 
    #step2 a 
inner join
    #step2 b on a.id + 1 = b.id and a.item = b.item
inner join
    #step2 c on b.id + 1 = c.id and b.item = c.item
where
    a.id % 3 = 1
order by a.id
go

Это бы сработало, но только для группы ровно из трех эльфов. Идеально отвечая требованиям, я считаю, что выбранное решение обеспечивает большую гибкость, является более элегантным и ориентированным на будущее. Или agile, если хотите. Это требует некоторого нестандартного мышления, что всегда является хорошей возможностью для тренировки, так здорово, что есть возможность ее использовать. Учитывая, что результирующий запрос касается таблицы только один раз, я также подозреваю, что он также будет быстрее. Стоит покопаться в этом немного больше, если у вас есть время.

Веселиться!