@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));
  • Вопрос задан
  • 71 просмотр
Решения вопроса 1
0xD34F
@0xD34F Куратор тега JavaScript
function sort(arr) {
  const objFrom = Object.fromEntries(arr.map(n => [ n.from, n ]));
  const objTo = Object.fromEntries(arr.map(n => [ n.to, n ]));
  const sorted = [];

  for (let route = arr.find(n => !objTo[n.from]); route; route = objFrom[route.to]) {
    sorted.push(route);
  }

  return sorted;
}
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
TTATPuOT
@TTATPuOT
https://code.patriotovsky.ru/
Я бы так решил.
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 будет результатом
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы