Как отсортировать сегменты маршрута в порядке их прохождения?

Question

[dc65k]

Написал решение к задаче про сортировку билетов (сортировка маршрутов).
Как более правильно (оптимально) её решить?

Моё решение:

const arr = [
    {from: 'С.Петербург', to: 'Минск'},
    {from: 'Киев', to: 'Новосибирск'},
    {from: 'Череповец', to: 'Москва'},
    {from: 'Минск', to: 'Киев'},
    {from: 'Москва', to: 'С.Петербург'},
]

/*
output:
[
    {from: 'Череповец', to: 'Москва'},
    {from: 'Москва', to: 'С.Петербург'},
    {from: 'С.Петербург', to: 'Минск'},
    {from: 'Минск', to: 'Киев'},
    {from: 'Киев', to: 'Новосибирск'},
]

 */

const getRoutes = (arr) => {

    const fromArray = arr.map(currentValue => {
        return currentValue.from;
    });

    const toArray = arr.map(currentValue => currentValue.to);

    const obj = fromArray.concat(toArray).reduce((accumulator, currentValue) => {
        if (!accumulator[currentValue]) {
            accumulator[currentValue] = [];
        }

        accumulator[currentValue].push(currentValue);

        return accumulator;
    }, {});

    const a = Object.values(obj).filter(el => {
        return el.length < 2;
    }).flat();

    let firstRoute = arr.find(el => {
        return a.includes(el.from);
    });

    let output = [firstRoute];

    let idx = 0;

    arr = arr.filter(el => {
        return el.from !== firstRoute.from && el.to !== firstRoute.to;
    });

    while (arr.length) {

        const currentValue = arr[idx];

        if (currentValue?.from === firstRoute.to) {

            output.push(currentValue);

            firstRoute = currentValue;

            idx = 0;

            arr = arr.filter(el => {
                return el.from !== firstRoute.from && el.to !== firstRoute.to;
            });

        } else {
            idx++;
        }


    }

    return output;
}

console.log(getRoutes(arr));

Comments

[Alexandroppolus]

А что требуется в задаче? какие могут быть данные?

Answer 1

[0xD34F]

Собираем начальные и конечные точки сегментов маршрута (объекты вида { точка: сегмент }). Находим начальный сегмент маршрута - такой, начальная точка которого не является ничьей конечной. Следующий сегмент маршрута - такой, начальная точка которого является конечной точкой текущего сегмента. Ну и крутим цикл до тех пор, пока текущий сегмент маршрута существует, не забывая сохранять его в результирующий массив:

function sort(route) {
  const pointsFrom = Object.fromEntries(route.map(n => [ n.from, n ]));
  const pointsTo = Object.fromEntries(route.map(n => [ n.to, n ]));
  const sorted = [];

  for (
    let segment = route.find(n => !pointsTo[n.from]);
    segment;
    segment = pointsFrom[segment.to]
  ) {
    sorted.push(segment);
  }

  return sorted;
}

Answer 2

[Антон Неверов]

Я бы так решил.

const array = [
  { from: "С.Петербург", to: "Минск" },
  { from: "Киев", to: "Новосибирск" },
  { from: "Череповец", to: "Москва" },
  { from: "Минск", to: "Киев" },
  { from: "Москва", to: "С.Петербург" }
];
const cities = {};
const result = [];

const getNextDestanation = (destatnation, array) => {
  for (const i of array) {
    if (i.from === destatnation) return i;
  }
}
const checkCity = (city) => {
  if (cities[city]) cities[city]++;
  else cities[city] = 1;
}

array.map(i => {
  checkCity(i.from);
  checkCity(i.to);
});
const firstCandidates = Object.keys(cities).filter(c => cities[c] === 1);
const firstElement = array.find(i => firstCandidates.includes(i.from));
result.push(firstElement);

for (let i = 1; i < array.length; i++) {
  result.push(getNextDestanation(result[i - 1].to, array));
}

//result будет результатом