Как пройти испытание "Прыжки в облаках"

Как решить задачу HackerRank "прыгнуть в облака" кода с помощью JavaScript

Проблема

Вызов кода Jumping On The Cloud рассказывает о девушке по имени Эмма, которая прыгает из одного облака в другое, но хочет избежать грозовых облаков:

• 🏃‍♀️Эмма = перемычка
• Доступные типы прыжков = 1 космический прыжок или 2 космических прыжка.
• C = массив облаков контейнера 1 и 0
• ⛅️ 0 = обычное облако
• ⛈️ 1 = Грозовое облако
• N = количество облаков
• N - количество облаков от 2 до 100 (что может быть бесполезно, если мы просто вычисляем длину массива)
• Предполагается, что переданные нам данные уже отформатированы как массив

Примеры входных данных

// Example 1
// N = 7
// C = 0 0 1 0 0 1 0
// Expected: 4
// Path: 0 -> 1 -> 3 -> 4 -> 6
// Jumps Taken = 4
// Jump Types: 0-1 = 1, 1-3 = 2, 3-4 = 1, 4-6 = 2
// Example 2
// N = 6
// C = 0 0 0 0 1 0
// Expected: 3
// Path: 0 -> 2 -> 3 -> 5
// Jumps Taken = 3
// Jump Types: 0-2 = 2, 2-3 = 1, 3-5 = 2

Цель

Напишите функцию или функции, которые возвращают наименьшее количество прыжков, необходимое для прохождения сквозь облака (c), не прыгая в грозовую туча (1).

Покрытие наших баз

Прикрывая наши базы, мы должны убедиться, что:

• Количество элементов (значений) C находится в диапазоне от 2 до 100.
• В этом случае N не отправляется, поэтому нам не нужно с ним разбираться
• Установите начальное количество прыжков равным 0 и верните его, если C не соответствует требованиям.

function jumpingOnClouds(c) {
     const min = 2;
     const max = 100;
     let jumps = 0;
     if (c.length >= min && c.length <= max) {
          // continue
     }
     // return jumps
     return jumps;      
}

Понимание проблемы

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

Итерация по массиву

Первый шаг - перебрать массив, на этом первом шаге мы попробуем использовать цикл for.

// Example 1
// N = 7
// C = 0 0 1 0 0 1 0
...
if (c.length >= min && c.length <= max) {
     let path1 = [];
     for (let a = 0; a < c.length; a++) {
          if (c[a] !== 1) {
               path1.push(1); // a jump by one
          }  else {
               break; 
          } 
     }
     
     // Looping
     // 0->0 1 0 0 1 0, path1 = [ 1 ]
     // 0->0->1 0 0 1 0, break; (Already wrong route)
}
...

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

1. Это отлично подходит для прыжков на 1, но как насчет прыжков на 2?
2. А как насчет различных комбинаций прыжков 1 и 2?
3. Если это неправильный путь, нам нужно вернуться и попробовать другой маршрут.

Нам нужна рекурсия

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

Полностью переписав приведенное выше, мы можем предположить, что мы передадим ему значения массива (c) и обязательно остановимся, как только мы дойдем до последнего индекса массива или если путь будет полностью неправильным. Нам также нужно будет отслеживать все пути.

function findPaths(c, paths) {
 
     if (c.length > 1) { // remaining item of the array
     }
      
     // return the paths that were sent to us
     return paths;   
}  

Различные комбинации

Чтобы обрабатывать разные комбинации, нам нужно создать два разных направления для путей, по которым они будут идти, и отслеживать их. Для этого нам нужно скопировать существующий путь и увеличить (перейти) на 1 или 2. Кроме того, поскольку мы будем знать, когда произойдет прыжок, если следующим значением будет грозовая туча (1), мы можем полностью аннулировать путь.

function findPaths(c, paths) {
 
     if (c.length > 1) { // remaining item of the array
      
          // making copies of the path 
          let path1 = paths.slice();
          let path2 = paths.slice();
            
          // check path1 where we iterate over c by a jump of 1
          // check if c[1] is 1, quickly invalidate path1
          // or add 1 to the path1
          path1 = (c[1] !== 1) ? [ ...path1, 1 ] : 0;
          
          // and we do the same for path 2 for a jump of 2
          path2 = (c[2] !== 1) ? [ ...path2, 2] : 0;
          // quickly invalidating that we can't continue with
          // a jump of 1 or 2
          if (path1 === 0
               && path2 === 0) {
               paths = 0; // jump to end of function
          } 
     }
      
     // return the paths that were sent to us
     return paths;   
}

Проведение теста

// Example
// N = 8
// C = 1 1 1 0 0 1 0 1
// Expected: 0
findPaths([1, 1, 1, 0, 0, 1, 0, 1], []);
// Output: 0

Итерация для следующих прыжков

Теперь нам нужно продолжить итерационный процесс с рекурсией и охватить случаи сбоя path1 или path2.

function findPaths(c, paths) {
 
     if (c.length > 1) { // remaining item of the array
      
          // making copies of the path 
          let path1 = paths.slice();
          let path2 = paths.slice();
            
          // check path1 where we iterate over c by a jump of 1
          // check if c[1] is 1, quickly invalidate path1
          // or add 1 to the path1
          path1 = (c[1] !== 1) ? [ ...path1, 1 ] : 0;
          
          // and we do the same for path 2 for a jump of 2
          path2 = (c[2] !== 1) ? [ ...path2, 2] : 0;
          // quickly invalidating that we can't continue with
          // a jump of 1 or 2
          if (path1 === 0
               && path2 === 0) {
               paths = 0; // jump to end of function
 
          } else if (path1 !== 0
               && path2 === 0) { // Path 1 still good
               
               return findPaths(c.slice(1), path1);
          } else if (path1 === 0
               && path2 !== 0) { // Path 2 still good 
               
               return findPaths(c.slice(2), path2); 
          } 
     }
      
     // return the paths that were sent to us
     return paths;   
}

Пошаговый тест:

// Example
// N = 5
// C = 1 0 1 0 0 
findPaths([1, 0, 1, 0, 0], []);
// C = [1, 0, 1, 0, 0]
// Paths = []
// Path1 Viable? Yes. Path1 = [1]
// Path2 Viable? No. Path2 = 0
// C = [0, 1, 0, 0]
// Paths = [1]
// Path1 Viable? No. Path1 = 0
// Path2 Viable? Yes. Path2 = [1, 2]
// C = [0, 0]
// Paths = [1, 2]
// Path1 Viable? Yes. Path1 = [1, 2, 1]
// Path2 Viable? Yes. Path2 = [1, 2, 2]
// Result: [1, 2] (Looks like it didn't continue)

Как действовать, когда оба пути жизнеспособны

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

function findPaths(c, paths) {
 
     if (c.length > 1) { // remaining item of the array
      
          // making copies of the path 
          let path1 = paths.slice();
          let path2 = paths.slice();
            
          // check path1 where we iterate over c by a jump of 1
          // check if c[1] is 1, quickly invalidate path1
          // or add 1 to the path1
          path1 = (c[1] !== 1) ? [ ...path1, 1 ] : 0;
          
          // and we do the same for path 2 for a jump of 2
          path2 = (c[2] !== 1) ? [ ...path2, 2] : 0;
          // quickly invalidating that we can't continue with
          // a jump of 1 or 2
          if (path1 === 0
               && path2 === 0) {
               paths = 0; // jump to end of function
 
          } else if (path1 !== 0
               && path2 === 0) { // Path 1 still good
               
               return findPaths(c.slice(1), path1);
          } else if (path1 === 0
               && path2 !== 0) { // Path 2 still good 
               
               return findPaths(c.slice(2), path2); 
          } else if (path1 !== 0
               && path2 !== 0) {
 
               path1 = findPaths(c.slice(1), path1);
               path2 = findPaths(c.slice(2), path2);
        
               // compare and return the shortest path
               return (path1.length < path2.length) ? path1 : path2;
          } 
     }
      
     // return the paths that were sent to us
     return paths;   
}

Тот же пошаговый тест:

// Example
// N = 5
// C = 1 0 1 0 0
findPaths([1, 0, 1, 0, 0], []);
// C = [1, 0, 1, 0, 0]
// Paths = []
// Path1 Viable? Yes. Path1 = [1]
// Path2 Viable? No. Path2 = 0
// C = [0, 1, 0, 0]
// Paths = [1]
// Path1 Viable? No. Path1 = 0
// Path2 Viable? Yes. Path2 = [1, 2]
// C = [0, 0]
// Paths = [1, 2]
// Path1 Viable? Yes. Path1 = [1, 2, 1]
// Path2 Viable? Yes. Path2 = [1, 2, 2]
// PATH 1
// C = [0] (which doesn't meet our if (c.length > 1))
// Returned = [1, 2, 1]
// PATH 2
// C = [] (which doesn't meet our if (c.length > 1))
// Returned = [1, 2, 2]
// Path1 ([1, 2, 1]) < Path2 ([1, 2, 2]) = Nope, so return path 2
// Result: [1, 2, 2]

Подсчет шагов на возвращенном пути

function jumpingOnClouds(c) {
     const min = 2;
     const max = 100;
     let jumps = 0;
     if (c.length >= min && c.length <= max) {
          jumps = findPaths(c, []);
     }
     // return jumps
     return ((typeof jumps === "number") ? jumps : jumps.length);
}

Решение

И вот полное решение:

function findPaths(c, paths) {
     if (c.length > 1) {
          let path1 = paths.slice();
          let path2 = paths.slice();

          path1 = (c[1] !== 1) ? [ ...path1, 1 ] : 0;
          
          path2 = (c[2] !== 1) ? [ ...path2, 2] : 0;
          if (path1 === 0 && path2 === 0) {
               paths = 0;
          } else if (path1 !== 0 && path2 === 0) {
               return findPaths(c.slice(1), path1);
          } else if (path1 === 0 && path2 !== 0) {
               return findPaths(c.slice(2), path2); 
          } else if (path1 !== 0 && path2 !== 0) {
               path1 = findPaths(c.slice(1), path1);
               path2 = findPaths(c.slice(2), path2);
               return (path1.length < path2.length) ? path1 : path2;
          } 
     }
      
     return paths;   
}
function jumpingOnClouds(c) {
     const min = 2;
     const max = 100;
     let jumps = 0;
     if (c.length >= min && c.length <= max) {
          jumps = findPaths(c, []);
     }
     return ((typeof jumps === "number") ? jumps : jumps.length);
}

Тестовые кейсы

// N = 5, C = [0, 1, 0, 0, 0], Expected 2
// N = 5, C = [1, 1, 1, 0, 0], Expected 0
// N = 0, C = [], Expected 0
// N = 101, C = [1, 0, 1, 0, 0, 1, 0, 1 ... ], Expected 0
// N = 7, C = [0, 0, 1, 0, 0, 1, 0], Expected 4
// N = 6, C = [0, 0, 0, 1, 0, 0], Expected 3
jumpingOnClouds([0, 1, 0, 0, 0]); // 2 ✅
jumpingOnClouds([1, 1, 1, 0, 0]); // 0 ✅
jumpingOnClouds([]); // 0 ✅
jumpingOnClouds([1, 0, 1, 0, 0, 1, 0, 1 ... ]); // 0 ✅
jumpingOnClouds([1, 0, 1, 0, 0, 1, 0, 1 ... ]); // 0 ✅
jumpingOnClouds([0, 0, 1, 0, 0, 1, 0]); // 4 ✅
jumpingOnClouds([0, 0, 0, 1, 0, 0]); // 3 ✅

Обратная связь?

Если у вас есть рекомендации по оптимизации или даже лучшее решение, давайте поговорим. Я люблю обратную связь.

Если вы получили от этого пользу, похвалите эту статью 👏 и поделитесь ею в Twitter 🐦 или других социальных сетях. Еще раз спасибо за чтение. 🙏

Также подпишитесь на меня в twitter: @codingwithmanny и instagram на @codingwithmanny.