Задачи Javascript

Оглавление

Поиск пути по билетам

Поиск пути по билетам

Задача — восстановить маршрут из списка пар "из → в", начиная с указанного города. 

const paths = [{
  from: 'Vladimir',
  to: 'Nizhny Novgorod',
}, {
  from: 'Moscow',
  to: 'Vladimir'
}, {
  from: 'Yekaterinburg',
  to: 'Novosibirsk',
}, {
  from: 'Nizhny Novgorod',
  to: 'Kazan',
}, {
  from: 'Kazan',
  to: 'Yekaterinburg',
}];

const getRoute = (paths, start) => ...

/*
Вывод:

"Moscow" => [
  "Moscow",
  "Vladimir",
  "Nizhny Novgorod",
  "Kazan",
  "Yekaterinburg",
  "Novosibirsk",
]

"Kazan" => [
  "Kazan", 
  "Yekaterinburg", 
  "Novosibirsk",
]
*/

const getRoute = (paths, start) => {
  const map = new Map();
  
  for (const { from, to } of paths) {
    map.set(from, to);
  }
  
  const route = [start];
  
  while (map.has(start)) {
    start = map.get(start);
    route.push(start);
  }
  
  return route;
};