// 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"));