javascript

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

  • вторник, 31 октября 2023 г. в 00:00:18
https://habr.com/ru/articles/770646/
Yandex Cup 2023
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:

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

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

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

Например, у нас есть песня (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 за подсказку.