В этом году я решил принять вызов Пришествие кода вместе с некоторыми из моих коллег, и мне понадобился всего день, чтобы принять собственный интересный вызов. Посмотреть на мои успехи можно здесь: 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<[]>;

То, что делает этот код, так же просто, как:

  1. Проверьте, имеет ли предоставленный тип T свойство length
  2. Если это так и это number - верните его (L)
  3. Если нет — вернуть длину пустого массива (или по транзитивности — 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]>;

Опять же, этот код может кому-то показаться немного пугающим, но его можно прочитать так:

  1. Берем число N и накопленное значение T (которое по умолчанию является нашим Zero)
  2. Мы проверяем, является ли свойство length числа T точно искомым числом N
  3. Если да — то T это наше кортежное представление
  4. Если нет — мы рекурсивно вызываем 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]>;

Это говорит само за себя:

  1. Учитывая число N, мы создаем из него кортеж, используя BuildTuple
  2. Затем мы создаем еще один кортеж, расширяя текущий кортеж и добавляя еще один элемент типа (any).
  3. Наконец, мы используем 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>;

Здесь мы делаем следующее:

  1. Учитывая число N, мы создаем из него кортеж, используя BuildTuple, и сохраняем его как T.
  2. Мы проверяем, является ли T Zero, и если да, то возвращаем Length<Zero> (то есть 0)
  3. Если нет, проверяем, может ли T быть представлено одним типом any и некоторыми значениями Rest
  4. Если сможем, то Length<Rest> будет результатом вычитания (мы удалили один элемент)
  5. Если нет — то имеем 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>>;

Давайте построчно:

  1. Мы создаем кортеж из B и проверяем, является ли он Zero
  2. Если да — тоже создаем из A и сверяем с Zero.
  3. Если да — A и B равны, следовательно, мы возвращаем false
  4. Если A не равно, то A больше, чем B, и мы возвращаем true.
  5. Если 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);
  1. Нижняя часть нашей рекурсии — это когда мы прошли через все элементы. В этом случае мы возвращаем накопленное значение.
  2. Если у нас есть lastNumber (любой вызов, кроме первого) и current больше, мы рекурсивно вызываем функцию на rest чисел с увеличенным accumulator.
  3. Если нет, то мы просто рекурсивно вызываем функцию на 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. Чтобы исправить это, мы могли бы:

  1. Добавьте чек типа Curr extends number
  2. Используйте 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.

Это полезно? — Нет!
Это то, чем вам нужно заниматься в жизни? — Возможно, нет!
Было весело? — Для меня да!
Оно того стоило? — ДА!
Попробую ли я это для следующих головоломок? — ДА!

Пункты выноса

В процессе реализации строительных блоков, арифметики, сравнений и собственно алгоритма:

  1. Я обнаружил некоторые новые возможности Typescript
  2. Я напомнил себе некоторые математические основы
  3. Я написал свой первый и, надеюсь, не последний пост в блоге.
  4. Я нашел себе новое хобби

Вы можете найти полный код и проверить мои успехи с другими головоломками на AGalabov/advent-of-code-2021/type-system