Решение задачи про определение типа в Typescript с Yandex Cup 2023

Всю прошлую неделю проходила квалификация на Yandex Cup 2023. Я решил тряхнуть стариной и вспомнить что такое спортивное программирование.

Яндекс представил 8 задачек разной сложности, которые необходимо сделать за пять часов. Я принял участие. На старте был уверен в себе. Однако, получил плохие результаты. Следующие пол дня я чувствовал уныние и разочарование. Потом пришла идея, как это использовать.

Мое внимание зацепила одна задача, связанная с типизацией в Typescript. Я давно хотел написать статью про типы, показать бекенду какие сложные интерфейсы можно создавать в Typescript.

Завариваем чаек, я начинаю.

Постановка задачи

Чтобы работать более продуктивно, многие слушают музыку. Кому‑то помогает сосредоточиться lo‑fi, кому‑то — белый шум, а кто‑то максимально эффективен, когда слушает тяжёлый металл. Учёные Института Б выяснили, что способность концентрации человека зависит от уровня серотонина в крови во время прослушивания музыки. Причём каждый жанр, и даже трек, влияют на выработку гормона по‑разному.

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

Условие

Разработайте тип Get, который позволит по запросу выдавать параметры песни, такие как автор, дата выпуска песни или другие различные параметры и настройки музыкальных дорожек.

На входе программа должна получать константный тип массива и строку с путём в формате точечно‑скобочной нотации (например, «keys→(0–2)→val»), а возвращать — литерал значений объектов по заданному пути.

Тип должен позволить запросить информацию по определенным ключам аналогично примерам.

Пример структуры:

const song = {     metaData: {         title: 'Highway to Hell',         author: 'AC/DC',         date: '27.07.1979',     },     tracks: [         {             id: 1,             name: 'Piano',             soundType: 'virtual_instrument',             instrument: 'piano',             regions: [                 {                     id: 1,                     start: 0,                     end: 3,                     midiData: [                         {note: 'F4', velocity: 80, startTime: 0, duration: 1},                         {note: 'D4', velocity: 80, startTime: 1, duration: 1},                         {note: 'E4', velocity: 90, startTime: 2, duration: 1},                     ],                     effects: [                         {type: 'reverb', intensity: 15},                         {type: 'delay', time: 0.5, feedback: 30, mix: 20},                     ],                 },             ],             pan: 5,             volume: 78,         },         {             id: 2,             name: 'Guitar',             soundType: 'virtual_instrument',             instrument: 'guitar',             regions: [                 {                     id: 1,                     start: 0,                     end: 5,                     midiData: [                         {note: 'C4', velocity: 10, startTime: 0, duration: 1},                         {note: 'E4', velocity: 20, startTime: 1, duration: 1},                         {note: 'E4', velocity: 30, startTime: 2, duration: 1},                         {note: 'F4', velocity: 40, startTime: 3, duration: 1},                         {note: 'D4', velocity: 50, startTime: 4, duration: 1},                     ],                 },             ],             pan: 10,             volume: 60,         },     ], } as const;

Примеры тестов:

type songAuthor = Get<typeof song, 'metaData->author'>; // AC/DC type firstTrackVolume = Get<typeof song, 'tracks->0->volume'>; // 78 type tracksVolume = Get<typeof song, 'tracks->(0-2)->volume'>; // 78 | 60 type notes = Get<typeof song, 'tracks->1->regions->0->midiData->(0-5)->note'>; // "F4" | "D4" | "E4" | "C4" type midiData = Get<typeof song, 'tracks->1->regions->0->midiData->(0-2)'>; // { note: "C4", velocity: 10,  startTime: 0, duration: 1, } | { note: "E4", velocity: 20, startTime: 1, duration: 1 } type thirdNoteVelocity = Get<typeof song, 'tracks->1->regions->0->midiData->3->velocity'>; // 40

Ваше решение должно содержать определение типа Get.

 type Get<T extends unknown, Path extends string> = ...

Основной вопрос, который может появиться после прочтения — зачем и как это применяется на практике?

Сложно ответить не находясь в контексте. Субъективно, для решения большинства задач подойдут простые типы.

Если судить по характеру примера, то видимо где‑то в Яндекс.музыке это используется.

Если вы знаете ответ, обязательно напишите в комментариях.

Необходимый минимум

Если вы не знакомы с Typescript, то советую обратиться к документации.

Описать принцип работы типов в Typescript можно с помощью утверждения:

Если что-то выглядит как утка, плавает как утка и крякает как утка, то это, вероятно, и есть утка.

Необходимые познания в Typescript:

• Generics

• Keyof Type Operator

• Indexed Access Types

• Conditional Types, особенно infer

• Mapped Types

• Template Literal Types

Перейдем к решению задачи.

Декомпозиция

От нас требуется вернуть тип, который по объекту ищет совпадение по строке свойств.

Например, у нас есть песня (song).

const song = {    metaData: {      author: 'AC/DC'    }  };

И мы хотим узнать ее автора (author).

Тогда цепочка обращений будет следующей: song.metaData.author. В строковом представлении — metaData->author.

По всей видимости, Yandex любит PHP, и в качестве разделителя использует → вместо

Нам необходимо написать type Get, который по объекту, вернет новый тип. В данном случае — AC/DC.

type Get<Record, Path> = <some code>; type author = Get<typeof song, 'metaData->author'>; // AC/DC

Задачу разобьем на 2 этапа, где каждый делится еще на два:

1. Получения списка свойств из строки.

   1. Разбиение Path по ‘->’.

   2. Создание диапазона значений в виде массива.

2. Генерация нового типа из Record, используя список параметров.

   1. Прохождение по атрибутам Record вниз. 

   2. Перебор коллекции значений в Record.

Задача 1.1

Для задачи A первого этапа достаточно написать рекурсивный тип, который будет разбивать строку по шаблону.

Используем следующий алгоритм:

1. Берем текущее значение и ищем ->.

2. Если находим, то левую часть без разделителя добавляем в массив, а над правой повторяем Шаг 1.

type Split<   Value extends string,   Pattern extends string = '->' > = Value extends `${infer LValue}${Pattern}${infer RValue}`   ? [LValue, ...Split<RValue, Pattern>]  : [Value];

Выражение — Value extends ${infer LValue}${Pattern}${infer RValue} проверяет, можно ли из входного параметра Value выделить 3 объекта: LValue, Pattern и RValue.

Infer позволяет создать условный тип. В данном случае, истинным выражением будет если найдено ->, где звездочка это любое значение.

Корректные варианты: a->b, a->, ->b, ->.

Отмечу, Split не проверяет невалидные кейсы. Полагается, что каждый разделитель с обеих сторон имеет соседей, который не является → или пустой строкой. То есть, решения с meta->'' или ->-> считаются неверными.

Для определения рекурсивного типа, достаточно вызвать самого себя, но уже с измененными параметрами: [LValue, ...Split<RValue, Pattern>]

В коллекцию добавляется LValue, а затем вызывается Split с RValue. Если не выполняется проверка, то возвращается сам объект в виде массива — [Value].

Для примера, опишу итерации:

1. На первом шаге metaData->author разобьется на metaData и author. Соответственно в массив попадет [metaData] и алгоритм повторяется для author.

2. На втором шаге разделитель найден не будет, что следующим значением станет author.

В итоге получается type = [metaData,author].

Задача 1.2

Задача сводится к созданию массива с фиксированным диапазоном.

Для выражений (0-2) и (3-6) должны вернуться результаты [0, 1] и [3, 4, 5].

Используя подход из Split, аналогично найдем Start и End.

type Range<T extends string> = T extends `(${infer Start}-${infer End})`  ? [Start, End]  : never;

Стоит отметить, что в данном случае мы получим коллекцию строк, а для создания диапазона необходим number.

Если при приведении типов в JavaScript можно просто добавить плюс перед значением (+stringValue) или обернуть в Number(stringValue), то с типизацией это не пройдет.

Для преобразования из строки в число также infer:

type StringToInt<Value extends string> = Value extends `${infer Digit extends number}`  ? Digit  : never;

Очень интересна сама реализация в Typescript. Я сталкивался с написанием трансляторов, но разработка оператора infer это что‑то из параллельной вселенной.

Упростим решение и сделаем проверку внутри:

type Range<T extends string> = T extends `(${infer Start extends number}-${infer End extends number})`  ? [Start, End]  : never;

Создадим перечисление фиксированной длины.

type Enumerate<   Length extends number,   Accumulation extends number[] = [] > = Accumulation['length'] extends Length   ? Accumulation[number]   : Enumerate<Length, [...Accumulation, Accumulation['length']]>;

Использование рекурсии просто зашкаливает. Стоит переименовать Typescript в RecursiveScript.

Принцип работы алгоритма следующий:

1. Проверяем, что в массиве уже требуемое количество элементов.

2. Если истина, то возвращаем допустимые значения. В противном случае добавляем объект и переходим на шаг 1.

Пример использования Enumerate:

type Arr = Enumerate<4>; // 0 | 1 | 2 | 3

Самое неочевидное в реализации — это Accumulation[number].

Тут number выступает не в качестве численного типа, а в виде указания обращения к перечисляемому свойству.

Так как Accumulation это массив, то Accumulation[number] формально говорит компилятору — верни все возможные значения.

Достаточно убрать number и тогда Enumerate будет возвращать массив [0, 1, 2, …].

type Enumerate<   Length extends number,    Accumulation extends number[] = [] > = Accumulation['length'] extends Length   ? Accumulation   : Enumerate<Length, [...Accumulation, Accumulation['length']]>;

Теперь type Arr = Enumerate<2> вернет [0, 1].

Но как тогда получить диапазон значений?

Нужно создать два списка (Start, End) и вычесть из End - Start.

Реализации TS будет выглядеть следующим образом:

type RangeArray<   Start extends number,   End extends number > = Exclude<Enumerate<End>, Enumerate<Start>>;

Вычитание сделано с помощью стандартной утилиты — Exclude.

Финальная версия примет вид:

type RangeArray<   Range extends string > = Range extends `(${infer Start extends number}-${infer End extends number})`   ? Exclude<Enumerate<End>, Enumerate<Start>>   : never;

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

Задача 2.1

Необходимо создать тип, который будет выбирать из объекта данные по предоставленному списку свойств.

Можно выделить два кейса:

• в навигации нету перебора коллекций metaData->author.

• необходимо пройти несколько элементов tracks->(0-2)->volume.

Начнем решение с реализации первого варианта. 

Снова используем infer.

Infer имеет такое же значение в Typescript как слово Ку на Плюке.

Алгоритм следующий:

1. Получаем Record и Path. 

2. Если первое свойство является ключом в объекте, то читаем значение из Record и переходим на шаг 1. Иначе возвращаем сам Record.

Реализовать это можно следующим образом:

type ReadProperty<   Record,    Path > = Path extends [first: infer FirstProperty extends keyof Record, ...args: infer OtherProperties]   ? ReadProperty<Record[FirstProperty], OtherProperties>   : Record;

Проверяем утверждение — Path extends [first: infer FirstProperty extends keyof Record,...args: infer OtherProperties].

Если оно валидно, то тогда, рекурсивно вызываем ReadProperty<Record[FirstProperty], OtherProperties>.

В противном случае, ничего делать не требуется и следует передать обратно Record.

Как так выходит, что возвращается неизмененный Record?

Когда мы спустились до низа Record, то у нас будет объект и нет аргумента.

Пример. Наша цель найти автора.

type Record = {   metaData: {     title: 'Highway to Hell',     author: 'AC/DC',     date: '27.07.1979',   }, };  type Path = ['metaData', 'author'];

На первой итерации условие выполняется и мы идем дальше.

type Record = {   title: 'Highway to Hell',   author: 'AC/DC',   date: '27.07.1979', };  type Path = ['author'];

Спускаемся еще ниже.

type Record = 'AC/DC'; type Path = [];

Как видно из примера, мы в самом низу и поэтому просто возвращаем Record.

Немного изменим реализацию и учтем, что свойство из Path может быть не только ключом, но и диапазоном.

type ReadProperty<   Record,    Path > = Path extends [first: infer FirstProperty extends string, ...args: infer OtherProperties]   ? FirstProperty extends keyof Record     ? ReadProperty<Record[FirstProperty], OtherProperties>     : never // Array   : Record; 

Теперь FirstProperty является просто строкой, а не частью Record. Из-за этого добавилась проверка на принадлежность FirstProperty части Record.

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

Задача 2.2

Задача сводится к тому, чтобы пройтись по диапазону и выбрать нужные значения.

Вот на этом моменте я и застопорился на Cup-е. Решение оказалось простым до гениальности:

Для того чтобы выполнить обход, достаточно использовать объединение — “|”.

Пример реализации:

type ReadArrayProperty<   Array,    Record,    Path > = Array extends [first: infer FirstElem extends keyof Record, ...args: infer OtherElements]   ? ReadProperty<Record[FirstElem], Path> | ReadArrayProperty<OtherElements, Record, Path>   : never;

В данном случае мы перебираем массив с помощью infer.

Сначала мы вызываем ReadProperty, а уже потом снова рекурсивно ReadArrayProperty.

На понимание того, как применить тип для первого элемента и затем пройти по оставшимся, я потратил больше двух часов. 

На то оно и спортивное программирование — чьи мозги соображают быстрее, тот и побеждает.

Полное решение

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

type Split<   Value extends string,    Pattern extends string = '->' > = Value extends `${infer LValue}${Pattern}${infer RValue}`   ? [LValue, ...Split<RValue, Pattern>]   : [Value];  type Enumerate<   Length extends number,    Accumulation extends number[] = [] > = Accumulation['length'] extends Length   ? Accumulation   : Enumerate<Length, [...Accumulation, Accumulation['length']]>;  type ReadArrayProperty<   Array,   Record,   Path > = Array extends [first: infer FirstElem extends keyof Record, ...args: infer OtherElements]   ? ReadProperty<Record[FirstElem], Path> | ReadArrayProperty<OtherElements, Record, Path>   : never;  type ReadProperty<   Record,   Path > = Path extends [first: infer FirstProperty extends string, ...args: infer OtherProperties]   ? FirstProperty extends keyof Record     ? ReadProperty<Record[FirstProperty], OtherProperties>     : ReadArrayProperty<RangeArray<FirstProperty>, Record, OtherProperties>   : Record;  type RangeArray<   Range extends string > = Range extends `(${infer Start extends number}-${infer End extends number})`   ? Exclude<Enumerate<End>, Enumerate<Start>>   : never;  type Get<T, Path extends string> = ReadProperty<T, Split<Path>>;

Примеры для проверки:

type songAuthor = Get<typeof song, 'metaData->author'>; // AC/DC type firstTrackVolume = Get<typeof song, 'tracks->0->volume'>; // 78 type tracksVolume = Get<typeof song, 'tracks->(0-2)->volume'>; // 78 | 60 type notes = Get<typeof song, 'tracks->1->regions->0->midiData->(0-5)->note'>; // "F4" | "D4" | "E4" | "C4" type midiData = Get<typeof song, 'tracks->1->regions->0->midiData->(0-2)'>; // { note: "C4", velocity: 10, startTime: 0, duration: 1, } | { note: "E4", velocity: 20, startTime: 1, duration: 1 } type thirdNoteVelocity = Get<typeof song, 'tracks->1->regions->0->midiData->3->velocity'>; // 40

Я не проверял эту финальную версию в Яндекс.Контесте, так как доделал задачу после завершения отведенного времени. 

Будет забавно, если оно неверно.

Я доверился только WebStorm:

Напишите в комментариях свою реализацию. Мне очень интересно, можно ли как-то  упростить. Есть шанс, что лучшее решение будет на две строчки.

UPD: В комментариях есть обновленная версия, в которой убрана задача 2.2. Вместо обхода массива, можно напрямую использовать перечисление. Спасибо @Alexandroppolus за подсказку.