296. Мы родственники?

На планете Яндексорий жизнь развивается в огромном океане, окутывающем всю поверхность. Многообразие видов представлено одноклеточными организмами. У местных обитателей необычная ДНК, она состоит из единичной цепочки нуклеотидов — таких же, как у нас:

• A Аденин
• G Гуанин
• T Тимин
• C Цитозин

Но вот размножение и мутации происходят специфично: каждую секунду от клетки отпочковываются потомки с мутациями, а сама клетка делится надвое. Каждая мутация — приписывание нуклеотида либо в начало цепочки, либо в конец. Все 8 мутаций реализуются.

Пример размножения клетки местной «амёбы» AGGC:

AGGC > AGGC, AGGC, AAGGC, GAGGC, TAGGC, CAGGC, AGGCA, AGGCG, AGGCT, AGGCC

Для двух случайно взятых клеток определите, можно ли считать их родственниками. Клетки считаются родственниками со степенью родства N, если ДНК их общего предка порождает любую из ДНК исходных клеток не более чем за N мутаций. Общий предок видов — ДНК клетки, среди потомков которой есть клетки с ДНК как первого вида, так и второго. Все клетки имеют в составе ДНК нуклеотиды, пустых цепочек не существует.

Примеры

AT и TA — родственники со степенью родства 1:

• у вида AT нашелся родитель A через одно поколение (то есть A — предок по крайней мере одной клетки с ДНК AT), цепочка мутаций A -> AT;
• у вида TA тоже нашелся родитель A через одно поколение, цепочка мутаций A -> TA.

В данном случае можно было найти также предка с ДНК T.

ATGGC и TG — родственники со степенью родства 3:

TG — общий предок видов ATGGC и TG;

• среди потомков TG есть сама клетка TG, 0 мутаций
• среди потомков TG есть ATGGC, 3 мутации: TG -> ATG -> ATGG -> ATGGC

Клетка TG порождает клетки с ДНК ATGGC и TG не более чем за 3 мутации. ATGGC и TG — также родственники со степенью родства 4, 5 и т.д., так как условие «не более чем за 3 мутации» обобщается и на большие степени.

AAA и AAA — родственники со степенью родства 0.

При любой степени проверяемого родства они не родственники, так как нет общего предка (клетки с пустой ДНК не существует).

Условие

Напишите функцию, которая принимает ДНК двух клеток и проверяемую степень родства, и возращает булево значение: true, если клетки являются родственниками с нужной степенью родства, или false, если не являются

Шаблон решения для отправки:

/**
 * @param {string} genA
 * @param {string} genB
 * @param {number} level
 * @returns {boolean}
*/
function isRelativies(genA, genB, level) {
   // ... your code here
}

exports.isRelativies = isRelativies;

Тесты:

isRelativies('AT', 'TA', 1); // true
isRelativies('AT', 'TA', 0); // false
isRelativies('AT', 'TA', 5); // true

isRelativies('ATGGC', 'TG', 3); // true
isRelativies('ATGGC', 'TG', 2); // false
isRelativies('ATGGC', 'TG', 10); // true

isRelativies('AAA', 'AAA', 0); // true
isRelativies('AAA', 'AAA', 5); // true
isRelativies('AAA', 'AAA', 55); // true

isRelativies('ATTTGCGC', 'CGCGATTT', 4); // true
isRelativies('ATTTGCGC', 'CGCGATTT', 2); // false

isRelativies('G', 'T', 1); // false