Крисс проводит тебя в комнату для совещаний.

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

«Как дела?», — спрашивает он.

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

«Действительно, как?», — улыбаешься ты.

«… хм, отлично. Ну, приступим?»

Ты утвердительно киваешь.

«Хорошо. Мы займёмся небольшой программной головоломкой, чтобы я понял, как ты умеешь решать задачи. Не волнуйся, если не получится сделать это упражнение, мне главное понять, как ты мыслишь и общаешься».

Волноваться? Ты с трудом вспоминаешь это ощущение. Возможно, оно осталось в твоей юности, когда ты зимовал на Свальбарде* с медведями. Ещё до того, как ты понял сейд.

*Норвежское название Шпицбергена.

«Задача называется N-Queens, — продолжил Крисс. — Она довольно проста. На шахматной доске размером NxN нужно расположить N королев так, чтобы они не угрожали друг другу. Постарайся, чтобы код был кратким».

Ручеёк ощущаемого тобой дежавю превратился в наводнение. Ты действительно видел Крисса раньше. В этой комнате, решая эту головоломку. Но в памяти нет следов. Возможно, в прошлой жизни? Но он слишком молод для этого.

На секунду делаешь паузу, чтобы собраться.

«Я могу использовать любой язык?», — повторяешь ты.

«Ну… в основном мы пишем на TypeScript. И у нас был довольно… неудачный опыт с людьми, пишущими на других языках. Один кандидат использовал Haskell, но мне с трудом удавалось разбираться в том, что он делал. Код был не особо кратким».

Ах, вот что. Здесь был Видрун. Это объясняет дежавю. У вас есть много общего.

«Значит, TypeScript», — соглашаешься ты. Крисс выглядит спокойным. Его судьба уже предрешена.

«Нам нужно начать с нескольких рун», — произносишь ты.

Крисс мгновенно реагирует. «Руны, как в Go? Разве мы только что не договорились о TypeScript?»

«О, нет, не такие руны. Руны, тени смысла. Символические. Уникальные».

Делаешь вдох, создаёшь начертание.

const ᚾ = Symbol()
const ᛊ = Symbol()
const ᛚ = Symbol()
const ᛞ = Symbol()

«Видишь ли, в TypeScript используется утиная типизация. А одну утку нельзя путать с другой».

«Ты имеешь в виду, что он имеет структурную типизацию? В отличие от языков с номинальной типизацией наподобие Java или Haskell?»

«Да, именно так», — отвечаешь ты. Возможно, Крисс всё-таки поспевает за тобой. «Смотри, я покажу тебе».

Ты вызываешь саму космическую пустоту и связываешь её с сутью ᚾ. Нужда, небытие, тщетное желание стать чем-то.

type Nil = typeof ᚾ

«Постой-ка, разве у нас уже нет null и undefined? Зачем определять собственный тип для Nil?»

«Встроенные типы отягощены множеством лишнего — null, undefined, ложные ценности. Лучше начать с чистого листа».

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

type Cons<x, xs> = [x, xs]

Ты слышишь, как прервалось дыхание Крисса. Нужно действовать быстро, пока ты его не потерял.

«Добавим булевы значения, чтобы обозначить угрозу и безопасность».

Истина, огонь, солнце. Они связаны с ᛊ.

Ложь, фальшь, глубины озера. Связаны с ᛚ.

type True = typeof ᛊ
type False = typeof ᛚ

«И немного простой магии».

type Not<b1> = b1 extends True ? False : b1 extends False ? True : never
type Or<b1, b2> = b1 extends True ? True : b2 extends True ? True : False

"… но зачем…", — начинает, но не заканчивает Крисс. Не волнуйся. Продолжай.

Существует ли вообще хоть какая-то истина? Иногда ты задаёшься этим вопросом.

type AnyTrue<list> = list extends Cons<infer x, infer xs>
    ? x extends True
        ? True
        : AnyTrue<xs>
    : False

«Понадобится записывать координаты королев, поэтому нужны и числа».

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

type Zero = typeof ᛞ

«Теперь мы можем определить остальные натуральные числа, основываясь на нуле».

type S<n> = [n]

type One   = S<Zero>
type Two   = S<One>
type Three = S<Two>
type Four  = S<Three>
type Five  = S<Four>
type Six   = S<Five>

Лицо Крисса уже полностью серое. Его дыхание начинает паром вырываться изо рта, а прохлада в воздухе становится всё сильнее. Он знает, что грядёт.

«Нам нужно иметь возможность выполнять пару операций с нашими числами. Равенство, разность».

«Важные концепции для компании, подобной вашей», — добавляешь ты, отмечая отчётливое отсутствие последнего качества в тундре офиса открытого типа.

type Equals<a, b> = a extends S<infer a_>
    ? b extends S<infer b_>
        ? Equals<a_, b_>
        : False
    : b extends Zero
        ? True
        : False

type AbsDiff<a, b> = a extends S<infer a_>
    ? b extends S<infer b_>
        ? AbsDiff<a_, b_>
        : a
    : b extends S<any>
        ? b
        : Zero

«И для удобства напишем функцию, создающую интервал от нуля до n».

type RangeFromZeroTo<n, xs = Nil> = n extends S<infer n_>
    ? RangeFromZeroTo<n_, Cons<n, xs>>
    : Cons<Zero, xs>

«Крисс! Крисс, мы уже готовы. Всё хорошо, мы уже готовы».

Он еле слышно что-то бормочет. «только не это. только не снова».

Определяем королеву. Любой королеве твоего клана потребовалось бы больше глубины, чем простые x и y, но не будем усложнять.

type Queen<x, y> = [x, y]

Создадим ряд королев. Им слишком опасно находиться в одном ряду, в одно время, в одной вселенной. Их нужно рассредоточить по мультивселенной. Такое тоже происходило в истории твоего вида.

type RowOfQueens<cols, row> = cols extends Cons<infer col, infer cols_>
    ? Cons<Queen<row, col>, RowOfQueens<cols_, row>>
    : cols

«Королева угрожает другой королеве, если находится в том же ряду, столбце или диагонали».

type Threatens<a, b> = a extends Queen<infer ax, infer ay>
    ? b extends Queen<infer bx, infer by>
        ? Or<
            Or<Equals<ax, bx>, Equals<ay, by>>,
            Equals<AbsDiff<ax, bx>, AbsDiff<ay, by>>
        >
        : never : never

«never… never…», — скулит Крисс. Ты не совсем уверен, имеет ли он в виду код, но объясняешь:

«Threatens не должен вызываться ни с чем другим, кроме как Queen. Мы используем never, чтобы описать исключение, когда он вызывается с неверным типом».

Ты плавал в озере дьявола, но никогда, никогда, never, never. Ты никогда не совершишь той же ошибки. Нет, никогда, never, never.

«Мы спустимся до рядов шахматной доски, размещая королев там, где это возможно. Имея список уже размещённых королев, будем проверять, какие из них представляют угрозу для новой королевы».

type ThreateningQueens<placedQueens, queen> =
    placedQueens extends Cons<infer placedQueen, infer placedQueens_>
        ? Cons<
            Threatens<placedQueen, queen>,
            ThreateningQueens<placedQueens_, queen>
        >
        : Nil

«Королева в безопасности только тогда, когда ни одна из других королев ей не угрожает».

type Safe<placedQueens, queen> =
    Not<AnyTrue<ThreateningQueens<placedQueens, queen>>>

«Теперь, взяв список возможных королев, проверяем, какие из них будут в безопасности от других королев, уже находящихся на доске».

type FilterSafeQueens<candidates, placedQueens> =
    candidates extends Cons<infer q, infer qs>
        ? Safe<placedQueens, q> extends True
            ? Cons<q, FilterSafeQueens<qs, placedQueens>>
            : FilterSafeQueens<qs, placedQueens>
        : Nil

«В процессе работы с доской нам нужно рассматривать только позиции в следующем ряду, где королева будет в безопасности»

type Next<row, placedQueens = Nil> =
    FilterSafeQueens<RowOfQueens<RangeFromZeroTo<N>, row>, placedQueens>

«Крисс, ты готов?»

Его ресницы покрыты инеем, обрамляющим прекрасную пару глаз. Прекрасную, но пустую и расфокусированную.

«Пара взаимно рекурсивных функций для нахождения решения».

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

type SolveNextRow<row, placedQueens> =
    Solve<Next<S<row>, placedQueens>, S<row>, placedQueens>

type Solve<candidates, row, placedQueens> = Equals<row, N> extends True
    ? candidates extends Cons<infer x, any>
        ? Cons<x, placedQueens>
        : Nil
    : candidates extends Cons<infer x, infer xs>
        ? SolveNextRow<row, Cons<x, placedQueens>> extends Nil
            ? Solve<xs, row, placedQueens>
            : SolveNextRow<row, Cons<x, placedQueens>>
        : Nil

«Крисс, — ты произносишь мягко, — решение».

type N = Six
type Solution = Solve<Next<Zero>, Zero, Nil>

Курсор мыши пробегает по Решению и сервер языка выводит:

Cons<
 Queen<S<S<S<S<S<S<typeof ᛞ>>>>>>, Five>,
 Cons<
  Queen<S<S<S<S<S<typeof ᛞ>>>>>, Three>,
  Cons<
   Queen<S<S<S<S<typeof ᛞ>>>>, One>,
   Cons<
    Queen<S<S<S<typeof ᛞ>>>, Six>,
    Cons<
     Queen<S<S<typeof ᛞ>>, Four>,
     Cons<
      Queen<S<typeof ᛞ>, Two>,
      Cons<
       Queen<typeof ᛞ, typeof ᛞ>,
       Nil
      >
     >
    >
   >
  >
 >
>

«То есть королевы находятся на клетках (0,0), (1,2), (2,4), (3,6), (4,1), (5,3) и (6,5). Это соответствует ответу, Крисс?»

Ты рисуешь набросок решения на маркерной доске.


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

«Да, решение выглядит корректным, но в коде достаточно сложно разобраться, он не очень краткий», — заявляет он ошибочно.

«О, в основном это просто бойлерплейт TypeScript. Думаю, после компиляции в JavaScript он покажется тебе абсолютно кратким», — уверяю я его.

Ты запускаешь компилятор.

$ tsc *.ts --lib esnext --outFile /dev/stdout 
var ᚾ = Symbol();
var ᛊ = Symbol();
var ᛚ = Symbol();
var ᛞ = Symbol();

Крисс выглядит так, как будто ему дали пощёчину. Ты оставляешь его наедине с решением и покидаешь комнату.

---

Изучить код в TypeScript Playground можно здесь