Где ошибка в алгоритме?

Question

[New Developer]

Пытаюсь решить задачу codewars.com/kata/585894545a8a07255e0002f1 с помощью DFS итеративным путем. Когда соединяемых узлов больше 6, функция работает неправильно, выдает меньшее значение. Где искать ошибку ?

const O = {
  'A': ['B', 'D', 'E', 'F', 'H'],
  'B': ['A', 'C', 'D', 'E', 'F', 'G', 'I'],
  'C': ['B', 'D', 'E', 'F', 'H'],
  'D': ['A', 'B', 'C', 'E', 'G', 'H', 'I'],
  'E': ['A', 'B', 'C', 'D', 'F', 'G', 'H', 'I'],
  'F': ['A', 'B', 'C', 'E', 'G', 'H', 'I'],
  'G': ['B', 'D', 'E', 'F', 'H'],
  'H': ['A', 'C', 'D', 'E', 'F', 'G', 'I'],
  'I': ['B', 'D', 'E', 'F', 'H']
};
const Active = {
  'E': { 'A': 'I', 'B': 'H', 'C': 'G', 'D': 'F', 'F': 'D', 'G': 'C', 'H': 'B', 'I': 'A' },
  'B': { 'A': 'C', 'C': 'A' },
  'H': { 'G': 'I', 'I': 'G' },
  'D': { 'A': 'G', 'G': 'A' },
  'F': { 'C': 'I', 'I': 'C' }
};
function countPatternsFrom2(firstPoint, length) {
  if (length > 9) return 0;
  let sum = 0, stack = [firstPoint], actived = [], id = 0;
  while (stack.length) {
    let v0 = stack.slice(-1)[0], w = stack.slice(-2)[0], x = stack.length;
    if (x == length) {
      id = O[w].findIndex((v, i) => i > O[w].indexOf(v0) && !stack.includes(v));
      stack.pop();
      sum++;
      if (id == -1) {
        for (key in Active) {
          if (stack.includes(key) && w in Active[key] && !stack.includes(Active[key][w])) {
            sum++
          }
        }
      }
      continue
    };
    if (id == -1) {
      if (actived[x - 1] == `${actived[x - 1]}`) {
        if (actived[x - 1].length) {
          stack[x - 1] = actived[x - 1][0];
          id = O[stack[x - 1]].findIndex(v => !stack.includes(v));
          actived[x - 1] = actived[x - 1].slice(1)
        } else {
          stack.length -= 1;
          actived.length = stack.length;
        }
        continue
      }
      id = O[w].findIndex((v, i) => i > O[w].indexOf(v0) && !stack.includes(v));
      stack.pop();
      if (id == -1) {
        let L = '';
        for (key in Active) {
          if (stack.includes(key) && w in Active[key] && !stack.includes(Active[key][w])) {
            L += Active[key][w]
          }
        }
        if (L.length) {
          stack[x - 1] = L[0];
          actived[x - 1] = L.slice(1);
          id = O[stack[x - 1]].findIndex(v => !stack.includes(v));
        }
      }
      continue
    };
    stack.push(O[v0][id]);
    id = O[stack.slice(-1)[0]].findIndex(v => !stack.includes(v))
  }
  return sum
}
console.log(countPatternsFrom2('E', 7));

Здесь O - соединения по прямой, Active - соединения через ранее посещенные узлы.
Задача не сложная, если решать через BFS, но нужно именно итеративным DFS.

Comments

[New Developer]

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

[New Developer]

Удалось добиться правильных вычислений при 7 соединяемых точках путем замены блока

if (x == length) {
      id = O[w].findIndex((v, i) => i > O[w].indexOf(v0) && !stack.includes(v));
      stack.pop();
      sum++;
      if (id == -1) {
        for (key in Active) {
          if (stack.includes(key) && w in Active[key] && !stack.includes(Active[key][w])) {
            sum++
          }
        }
      }
      continue
    }

на

if (x + 1 == length) {
      O[v0].forEach(v => { if (!stack.includes(v)) sum++ });
      for (key in Active) {
        if (stack.includes(key) && v0 in Active[key] && !stack.includes(Active[key][v0])) {
          sum++
        }
      }
      id = -1
    }

[New Developer]

При построении алгоритма узлы из таблицы O я отметил черным, из Active - красным. Ошибка в том, что при поиске вниз могла произойти ситуация, когда черных узлов больше нет, можно добавить только красные, при length > 7.
Исправил ситуацию:

function countPatternsFrom2(firstPoint, length) {
  if (length > 9 || length == 0) return 0;
  if (length == 1) return 1;
  if (length == 2) return O[firstPoint].length;
  let sum = 0, stack = [firstPoint], actived = [], id = 0, d = true;
  while (stack.length) {
    if (id > -1) stack.push(O[stack.slice(-1)[0]][id]);
    let v0 = stack.slice(-1)[0], w = stack.slice(-2)[0], x = stack.length;
    if (x + 1 == length) {
      O[v0].forEach(v => { if (!stack.includes(v)) sum++ });
      for (let key in Active) {
        if (stack.includes(key) && v0 in Active[key] && !stack.includes(Active[key][v0])) {
          sum++
        }
      };
      d = false
    }
    if (d) {
      id = O[v0].findIndex(v => !stack.includes(v));
      if (id == -1) {
        let L = '';
        for (let key in Active) {
          if (stack.includes(key) && v0 in Active[key] && !stack.includes(Active[key][v0])) {
            L += Active[key][v0]
          }
        }
        if (L.length) {
          stack[x] = L[0];
          actived[x] = L.slice(1)
        }
      }
      continue
    };
    if (actived[x - 1] == `${actived[x - 1]}`) {
      if (actived[x - 1].length) {
        stack[x - 1] = actived[x - 1][0];
        actived[x - 1] = actived[x - 1].slice(1);
        d = true
      } else {
        stack.length--;
        actived.length = stack.length
      }
      continue
    }
    id = O[w].findIndex((v, i) => i > O[w].indexOf(v0) && !stack.includes(v));
    stack.pop();
    if (id == -1) {
      let L = '';
      for (let key in Active) {
        if (stack.includes(key) && w in Active[key] && !stack.includes(Active[key][w])) {
          L += Active[key][w]
        }
      }
      if (L.length) {
        stack[x - 1] = L[0];
        actived[x - 1] = L.slice(1);
        d = true
      }
    } else d = true
  }
  return sum
}
console.log(countPatternsFrom2('E', 9));

Потом переделал на самый оптимальный вариант, который чуть медленнее BFS, но потребляет мало памяти:

function countPatternsFrom2(firstPoint, length) {
  if (length > 9 || length < 1) return 0;
  let sum = 0, stack = [firstPoint], que = [''], down = true;
  while (stack.length) {
    let x = stack.length, v0 = stack[x - 1];
    if (x == length) {
      sum += que[x - 1].length + 1;
      down = false;
      stack.pop();
      que.pop();
      x--
    }
    if (down) {
      let L = '';
      O[v0].forEach(v => { if (!stack.includes(v)) L += v });
      for (let key in Active) {
        if (stack.includes(key) && v0 in Active[key] && !stack.includes(Active[key][v0])) {
          L += Active[key][v0]
        }
      }
      stack.push(L[0]);
      que.push(L.slice(1))
    } else {
      if (que[x - 1]) {
        stack[x - 1] = que[x - 1][0];
        que[x - 1] = que[x - 1].slice(1);
        down = true
      } else {
        stack.pop();
        que.pop()
      }
    }
  }
  return sum
}
console.log(countPatternsFrom2('E', 9))

Здесь que - массив следующих узлов, но в отличии от actived туда добавляются и черные и красные, d или down - флаг для спуска вниз.
С каким BFS сравнивал:

function countPatternsFrom2(firstPoint, length) {
  if (length == 1) return 1;
  if (length > 9) return 0;
  let sum = 0, visited = [[firstPoint]], next = [];
  for (let counter = length; counter > 0; counter--) {
    visited.forEach(v => {
      let x = v.length + 1;
      O[v[0]].forEach(w => {
        if (!v.includes(w)) x == length ? sum++ : next.push([w].concat(v))
      });
      for (key in Active) {
        if (v.includes(key) && v[0] in Active[key]) {
          if (!v.includes(Active[key][v[0]])) x == length ? sum++ :
            next.push([Active[key][v[0]]].concat(v))
        }
      }
    });
    visited = next.slice();
    next = [];
  }
  return sum
}
console.log(countPatternsFrom2('E', 9))