В этом году я решил принять вызов Пришествие кода вместе с некоторыми из моих коллег, и мне понадобился всего день, чтобы принять собственный интересный вызов. Посмотреть на мои успехи можно здесь: AGalabov/advent-of-code-2021
О ПРОБЛЕМЕ
Advent of Code — это ежегодное соревнование, отсчитывающее дни до Рождества. Каждый день участникам предлагается решить две «головоломки». Вам нужно только найти правильное решение, поэтому вы можете использовать любой язык, фреймворк или технологию. Я решил, что, поскольку это мой первый вызов, я буду придерживаться того, что знаю лучше всего — Typescript и иногда C++.
День 1, головоломка 1
Появилась первая загадка. Был создан целый нарратив, который будет сопровождаться на протяжении всего мероприятия, но по сути задачу можно было описать так просто:
Учитывая массив целых положительных чисел, найдите, во сколько раз увеличились числа по сравнению с предыдущим. Например, учитывая массив:
199 200 208 210 200 207 240 269 260 263
желаемый результат будет 7
, а числа, которые мы подсчитали, равны 200 208 210 207 240 269 263
.
Как и ожидалось с первого дня, это не было сложной задачей. Решение, которое я придумал, заняло не более нескольких минут и дало ожидаемые результаты как на выборочных данных, так и на фактически введенных данных. Это выглядело так:
input
.map((x, i) => (i > 0 ? Number(x > input[i - 1]) : 0))
.reduce((x, y) => x + y);
Затем я пошел дальше и решил другую загадку дня, и на этом все. Или я так думал…
Система типов Typescript
На следующий день мы с коллегой начали обсуждать это событие. Он упомянул, что, зная, что Typescript на самом деле является конкурсом Тьюринга, вполне возможно решить эту головоломку, используя только систему типов. Сначала я был в замешательстве, но потом он объяснил мне свой подход, а также то, что он не успел его закончить из-за принудительного ограничения глубины TS (начиная с TS 4.5 это 1000). Вот тогда я и решил, что пришло время игры!
РЕШЕНИЕ
Чего я хотел добиться
Когда дело доходит до кодирования чего-то, что вы не совсем уверены, как реализовать, мне будет проще, если вы начнете с интерфейса. Поэтому я спросил себя
«Чего я хочу достичь?»
type Sample = [199, 200, 208, 210, 200, 207, 240, 269, 260, 263];
// Solution should be of the type 7 (the exact number 7) type Solution = NumberOfIncreases<Sample>;
Строительные блоки
Для начала нам нужно типовое представление числа, которое позволило бы нам выполнять простые арифметические действия. Глядя на возможные типы, которые предоставляет Typescript, у нас есть простые значения, такие как boolean
, number
, они просто не подойдут — мы не можем их расширить. Нам нужно что-то, что может хранить несколько значений (например, массив), но имеет значение между 2, 3 или 10 значениями. Введите кортежи!
Кортеж — это, по сути, массив, но определенного размера, где элементы в определенных позициях должны быть определенного типа. Например, type StringAndNumber = [string, number];
определяет тип. Любые переменные этого типа должны быть массивом ровно из 2 элементов, первый из которых является string
, а второй - number
.
Важной особенностью кортежей является то, что, как и в любом массиве, существует свойство length
, к которому можно получить доступ.
type Length = StringAndNumber['length'];// Length would be of type 2
Чтобы обобщить это, мы можем заставить Length
принимать общий аргумент:
type Length<T extends any[]> = T extends { length: infer L }
? L extends number
? L
: Length<[]>
: Length<[]>;
То, что делает этот код, так же просто, как:
- Проверьте, имеет ли предоставленный тип
T
свойствоlength
- Если это так и это
number
- верните его (L
) - Если нет — вернуть длину пустого массива (или по транзитивности —
0
)
Итак, теперь мы знаем, что кортежи могут дать нам фундаментальный строительный блок для чисел. Итак, давайте определим некоторые типы:
type Tuple = any[];
type Zero = [];
Что бы это ни стоило, кортеж по-прежнему является массивом элементов. Поскольку нас интересует только их длина, мы можем использовать any
. В любом другом случае избегайте использования any
и вместо этого указывайте осмысленные типы в своем коде.
Теперь мы можем вернуться к нашему определению Length
, чтобы сделать его немного более семантически привлекательным:
type Length<T extends Tuple> = T extends { length: infer L }
? L extends number
? L
: Length<Zero>
: Length<Zero>;
Итак, теперь у нас есть представление чисел. Но как мы на самом деле «представляем» числа в виде кортежей? Опять же, если мы сначала подумаем об использовании, нам нужно что-то вроде BuildTuple<5>
для создания кортежа вроде [any, any, any, any, any]
. Мы можем сделать это рекурсивно:
type BuildTuple<N extends number, T extends Tuple = Zero> = T extends {
length: N;
}
? T
: BuildTuple<N, [...T, any]>;
Опять же, этот код может кому-то показаться немного пугающим, но его можно прочитать так:
- Берем число
N
и накопленное значениеT
(которое по умолчанию является нашимZero
) - Мы проверяем, является ли свойство
length
числаT
точно искомым числомN
- Если да — то
T
это наше кортежное представление - Если нет — мы рекурсивно вызываем
BuildTuple
очень похоже на функцию с новым накопленным значениемT
с дополнительнымany
в конце
Просто чтобы убедиться, что все работает как положено, давайте применим Length
к типу, созданному из BuildTuple
.
type Five = Length<BuildTuple<5>>; // Five is actually of type 5.
Ограничения
Как я уже упоминал, существуют ограничения на глубину рекурсии, когда дело доходит до Typescript:
type UnderLimit = BuildTuple<999>; // this would be infered correctly
type AboveLimit = BuildTuple<1000>; // this one results in "Type instantiation is excessively deep and possibly infinite"
Арифметика:
Теперь, когда у нас есть концепция Zero
, и мы можем создать любое другое число в виде кортежа, как мы будем выполнять арифметические действия.
Добавление
Начнем с определения PlusOne
:
type PlusOne<N extends number> = Length<[...BuildTuple<N>, any]>;
Это говорит само за себя:
- Учитывая число
N
, мы создаем из него кортеж, используяBuildTuple
- Затем мы создаем еще один кортеж, расширяя текущий кортеж и добавляя еще один элемент типа (
any
). - Наконец, мы используем
Length
, чтобы вернуться к постоянному числовому типу.
В результате имеем:
type Six = PlusOne<5>; // Six is of type 6
Способ определения Plus
для двух чисел теперь довольно очевиден:
type Plus<A extends number, B extends number> = Length<
[...BuildTuple<A>, ...BuildTuple<B>]
>;
type Twelve = Plus<4, 8>; // Twelve is of type 12
вычитание
Делая наоборот, мы можем определить MinusOne
:
type MinusOne<N extends number, T = BuildTuple<N>> = T extends Zero
? Length<Zero>
: T extends [any, ...infer Rest]
? Length<Rest>
: Length<Zero>;
Здесь мы делаем следующее:
- Учитывая число
N
, мы создаем из него кортеж, используяBuildTuple
, и сохраняем его какT
. - Мы проверяем, является ли
T
Zero
, и если да, то возвращаемLength<Zero>
(то есть0
) - Если нет, проверяем, может ли
T
быть представлено одним типомany
и некоторыми значениямиRest
- Если сможем, то
Length<Rest>
будет результатом вычитания (мы удалили один элемент) - Если нет — то имеем
0
В результате имеем:
type Thirteen = MinusOne<14>; // Thirteen is of type 13
Как и в случае с Plus
, теперь довольно легко определить Minus
:
type Minus< A extends number, B extends number, T = BuildTuple<A> > = T extends Zero ? Length<Zero> : T extends [...infer Rest, ...BuildTuple<B>] // just like with the any, we just define and expand a tuple of the size to subtract ? Length<Rest> : Length<Zero>;
type Seven = Minus<13, 6>; // Seven is of type 7
Сравнения
Чтобы найти количество увеличений, нам нужно иметь возможность сравнить два числа. Давай сделаем это:
type GreaterThan<
A extends number,
B extends number
> = BuildTuple<B> extends Zero
? BuildTuple<A> extends Zero
? false
: true
: GreaterThan<MinusOne<A>, MinusOne<B>>;
Давайте построчно:
- Мы создаем кортеж из
B
и проверяем, является ли онZero
- Если да — тоже создаем из
A
и сверяем сZero
. - Если да —
A
иB
равны, следовательно, мы возвращаемfalse
- Если
A
не равно, тоA
больше, чемB
, и мы возвращаемtrue
. - Если
B
неZero
, то мы рекурсивно вызываемGreaterThan
, вычитая единицу изA
иB
.
Результаты ожидаемы:
type Greater = GreaterThan<5, 3>; // Greater is of type true
type Equal = GreaterThan<5, 5>; // Equal is of type false
type Smaller = GreaterThan<3, 5>; // Smaller is of type false
Фактическое решение
Давайте посмотрим на это с точки зрения разработчика и попытаемся найти рекурсивное решение (поскольку именно так работает TS):
function numberOfIncreases( numbers: number[], lastNumber: number | null = null, accumulator: number = 0 ): number { if (numbers.length === 0) { return accumulator; }
const [current, ...rest] = numbers;
if (lastNumber && current > lastNumber) { return numberOfIncreases(rest, current, accumulator + 1); }
return numberOfIncreases(rest, current, accumulator); }
numberOfIncreases(input);
- Нижняя часть нашей рекурсии — это когда мы прошли через все элементы. В этом случае мы возвращаем накопленное значение.
- Если у нас есть
lastNumber
(любой вызов, кроме первого) иcurrent
больше, мы рекурсивно вызываем функцию наrest
чисел с увеличеннымaccumulator
. - Если нет, то мы просто рекурсивно вызываем функцию на
rest
, не увеличиваяaccumulator
.
Теперь давайте «переведем» эту логику в определение типа:
type NumberOfIncreases<
Input extends number[],
Previous extends number | null = null,
Accumulator extends number = Length<Zero>
> = Input extends []
? Accumulator
: Input extends [infer Curr, ...infer Rest]
? Previous extends number
? GreaterThan<Curr, Previous> extends true
? NumberOfIncreases<Rest, Curr, PlusOne<Accumulator>>
: NumberOfIncreases<Rest, Curr, Accumulator>
: NumberOfIncreases<Rest, Curr, Accumulator>
: Accumulator;
Теперь, к сожалению, прямой «перевод» полностью не работает. Typescript выводит Curr
как unknown
вместо number
. Чтобы исправить это, мы могли бы:
- Добавьте чек типа
Curr extends number
- Используйте
Input[0]
вместоCurr
, чтобы получить правильный вывод
Однако мы могли бы упростить логику, извлекая часть ее. Давайте извлечем логику получения остальных элементов массива:
type RestFromArray<T extends Tuple> = T extends [any, ...infer Rest]
? Rest
: Zero;
Теперь, если мы создадим тип, используя RestFromArray<[1, 2, 3]>
, получится [2, 3]
.
Теперь окончательная реализация будет выглядеть так:
type NumberOfIncreases<
Input extends number[],
Previous extends number | null = null,
Accumulator extends number = Length<Zero>
> = Input extends []
? Accumulator
: Previous extends number
? GreaterThan<Input[0], Previous> extends true
? NumberOfIncreases<RestFromArray<Input>, Input[0], PlusOne<Accumulator>>
: NumberOfIncreases<RestFromArray<Input>, Input[0], Accumulator>
: NumberOfIncreases<RestFromArray<Input>, Input[0], Accumulator>;
Это очень хороший пример того, как реальная логика может быть написана с помощью типов.
И вот после всего этого мы подходим к моменту истины. Давайте проверим это? Вы взволнованы? Пойдем:
type Sample = [199, 200, 208, 210, 200, 207, 240, 269, 260, 263];
type Solution = NumberOfIncreases<Sample>;
ЭТО РАБОТАЕТ! Solution
правильно выводится как тип 7
.
Стресс тест
Теперь, когда головоломка была решена с использованием примера ввода, я хотел попробовать, как далеко она может зайти. Я ввел полный ввод из моего задания. Он содержит 2000
чисел в диапазоне от 174
до 4618
… Затем сразу же tsc
начинает снова выдавать ошибку "Type instantiation is excessively deep and possibly infinite"
. Но на самом деле это не должно никого сейчас удивлять. Мы уже обнаружили, используя текущую реализацию, даже выполнение BuildTuple<1000>
достигает максимальной глубины вычислений. Таким образом, мы не можем ожидать создания одного для 1938
, 2002
, 4618
(числа из ввода) и т. д., а затем выполнять вычисления поверх них.
Затем я попытался использовать разные подмножества моих входных данных, чтобы увидеть, каковы ограничения. Лучшее, что я получил, было на самом деле очень впечатляющим:
type Full = [174, ..., 912] // a total of 433 numbers
type Solution = NumberOfIncreases<Full> // resulting in 271
ЗАКЛЮЧЕНИЕ
Нам удалось реализовать алгоритм, который использует типы только для решения головоломки уровня Advent of Code.
Это полезно? — Нет!
Это то, чем вам нужно заниматься в жизни? — Возможно, нет!
Было весело? — Для меня да!
Оно того стоило? — ДА!
Попробую ли я это для следующих головоломок? — ДА!
Пункты выноса
В процессе реализации строительных блоков, арифметики, сравнений и собственно алгоритма:
- Я обнаружил некоторые новые возможности Typescript
- Я напомнил себе некоторые математические основы
- Я написал свой первый и, надеюсь, не последний пост в блоге.
- Я нашел себе новое хобби
Вы можете найти полный код и проверить мои успехи с другими головоломками на AGalabov/advent-of-code-2021/type-system