// const bfs = (graph, source) => {
//   // инициализируем очередь и добавляем source в очередь
//   let queue = [{ vertex: source, count: 0 }];
//   // помечаем source как посещенную вершину
//   let visited = { source: true };
//   let tail = 0;
//   while (tail < queue.length) {
//     let u = queue[tail].vertex;
//     let count = queue[tail++].count; // Pop a vertex off the queue.
//     console.log("distance from ", source, " to ", u, ": ", count);
//     graph[u].forEach((v) => {
//       if (!visited[v]) {
//         visited[v] = true;
//         queue.push({ vertex: v, count: count + 1 });
//       }
//     });
//   }
// };
const graph = {
  "1": ["1", "*", "4", "2", "3"],
  "2": ["2", "1", "3", "5", "0"],
  "3": ["3", "2", "6", "1", "#"],
  "4": ["4", "1", "5", "7", "6"],
  "5": ["5","2", "6", "8", "4"],
  "6": ["6", "3", "5", "9", "4"],
  "7": ["7", "4", "8", "*", "9"],
  "8": ["8", "5", "9", "0", "7"],
  "9": ["9", "8", "6", "#", "7"],
  "0": ["0", "*", "8", "#", "2"],
  "*": ["*", "7", "0", "9", "1"],
  "#": ["#", "0", "9", "3", "*"],
};
const dictionary = {
  "1": { number: "1", clickCounts: 0 },
  a: { number: "2", clickCounts: 1 },
  b:  { number: "2", clickCounts: 2 },
  c:  { number: "2", clickCounts: 3 },
  d:  { number: "3", clickCounts: 1 },
  e:  { number: "3", clickCounts: 2 },
  f:  { number: "3", clickCounts: 3 },
  g:  { number: "4", clickCounts: 1 },
  h:  { number: "4", clickCounts: 2 },
  i:  { number: "4", clickCounts: 3 },
  j:  { number: "5", clickCounts: 1 },
  k:  { number: "5", clickCounts: 2 },
  l:  { number: "5", clickCounts: 3 },
  m:  { number: "6", clickCounts: 1 },
  n:  { number: "6", clickCounts: 2 },
  o:  { number: "6", clickCounts: 3 },
  p:  { number: "7", clickCounts: 1 },
  q:  { number: "7", clickCounts: 2 },
  r:  { number: "7", clickCounts: 3 },
  s:  { number: "7", clickCounts: 4 },
  t:  { number: "8", clickCounts: 1 },
  u:  { number: "8", clickCounts: 2 },
  v:  { number: "8", clickCounts: 3 },
  w:  { number: "9", clickCounts: 1 },
  x:  { number: "9", clickCounts: 2 },
  y:  { number: "9", clickCounts: 3 },
  z:  { number: "9", clickCounts: 4 },
};
const shortestPath = (graph, source, target) => {
  let queue = [source];
  let visited = { source: true };
  let predecessor = {};
  let tail = 0;
  while (tail < queue.length) {
    let u = queue[tail++];
    let newGraph = graph[u];
    for (let i = 0; i < newGraph.length; ++i) {
      let v = newGraph[i];
      if (visited[v]) {
        continue;
      }
      visited[v] = true;
      if (v === target) {
        let path = [v];
        while (u !== source) {
          path.push(u);
          u = predecessor[u];
        }
        path.push(u);
        path.reverse();
        return path;
      }
      predecessor[v] = u;
      queue.push(v);
    }
  }
};
const mobileRemote = (text) => {
  const array = text.split("");
  const startButton = "1";
  const chooseClick = 1;
  return array.reduce((count, item, index) => {
    let prevItem = index === 0 
      ? startButton
      : array[index-1]
  
    if (item === item.toUpperCase()) {
      count = count
        + shortestPath(graph, prevItem, "*").length
        + chooseClick
        + shortestPath(graph, "*", dictionary[item.toLowerCase()].number).length
        + dictionary[item.toLowerCase()].clickCounts
        + chooseClick
    } else {
      count = count
        + shortestPath(graph, dictionary[prevItem].number, dictionary[item].number).length
        + dictionary[item].clickCounts
        + chooseClick
    }
    return count
  }, 0);
};
console.log("mobileRemote", mobileRemote("C"));
console.log("mobileRemote", mobileRemote("yandex"));