Сортировщик карточек путешественника

Вам дана стопка посадочных карточек на различные виды транспорта, которые доставят вас из точки A в точку B. Карточки перепутаны, и вы не знаете, где начинается и где заканчивается ваше путешествие. Каждая карточка содержит информацию о том, откуда и куда вы едете на данном отрезке маршрута, а также о типе транспорта (номер рейса, номер места и прочее).

Предоставьте JavaScript API, который отсортирует такой список карточек и вернет словесное описание, как проделать ваше путешествие. API должен принимать на вход несортированный список карточек в формате, придуманном вами, и возвращать, например, такое описание:

• Take train 78A from Madrid to Barcelona. Seat 45B.
• Take the airport bus from Barcelona to Gerona Airport. No seat assignment.
• From Gerona Airport, take flight SK455 to Stockholm. Gate 45B. Seat 3A. Baggage drop at ticket counter 344.
• From Stockholm, take flight SK22 to New York JFK. Gate 22. Seat 7B. Baggage will be automatically transferred from your last leg.

Требования:

• Алгоритм должен работать с любым количеством карточек, если все карточки образуют одну неразрывную цепочку.
• Время прибытия и отправления неизвестно и неважно. Подразумевается, что средство передвижения для следующего отрезка дожидается вас.
• Структура кода должна быть расширяема для использования любых типов транспорта и информации, которая может быть связана с каждым типом транспорта.
• API будет вызываться из других частей JavaScript-кода без необходимости дополнительных запросов между браузером и сервером.
• Не используйте библиотеки и фреймворки, напишите все с нуля.
• Задокументируйте в коде формат входных и выходных данных.

Что нас интересует:

• Какой формат входных данных вы придумаете.
• Как вы структурируете свой код, чтобы он был расширяем, легок к пониманию и изменениям другими программистами.
• Какой алгоритм сортировки вы придумаете.

===============

Решение

Установка

Добавьте travelCardSorter.js к проекту:

<script type="text/javascript" src="travelCardSorter.js"></script>

Документация

Формат входных данных

API принимает массив Javascript-объектов, со следующими свойствами. Обязательными являются только origin.name и origin.destination. Поддерживаемые типы транспорта/способы передвижения: plane, train, bus, airport_bus, taxi и walking. Если способ передвижения не указан, будет выведена простая инструкция "Go from A to B".

Также есть возможность указать номер рейса/маршрута transport.route, выход на посадку transport.gate, место transport.seat, номер багажной карусели transport.baggage_drop, и любые заметки transport.notes, которые будут выведены на экран. Тип этих свойств должен быть String.

Стоит отметить, что у свойства origin есть свойство location, которое состоит из координат lat и lng. Это сделано для того, чтобы избежать возможных дупликатов адресов (например, London, UK и London, ON). На данный момент эта функциональность не реализована, но всё же, я добавил его для перспективы. Также, пользователям необязательно вводить координаты - это может быть реализовано с помощью такого API, как Геокодер, компонент API Яндекс.Карт.

[
  {
    origin: {
      name: 'Domodedovo Airport',
      location: {
        lat: 55.4103099,
        lng: 37.9002626
      }
    },
    destination: {
      name: 'JFK',
      location: {
        lat: 40.6413151,
        lng: -73.7803278
      }
    },
    transport: {
      type: 'plane',
      route: 'SK455',
      gate: '22',
      seat: '7B',
      baggage_drop: '',
      notes: 'Check visa requirements before your flight.'
    }
  },
  {
    ...
  }
]

Использование

Структура кода может выглядеть вот так:

var sorter = new TravelCardSorter();
sorter.importCards(cards);
sorter.sortCards();
sorter.printItinerary();

TravelCardSorter(cards)

Метод-конструктор. cards - необязательный параметр. Если он передан, importCards будет вызван автоматически.

TravelCardSorter.importCards(cards)

Этот метод импортирует массив карточек cards в формате, описанном ранее. Не возвращает ничего, так как массив присваевается переменной this.cards.

TravelCardSorter.sortCards()

Этот метод cортирует массив карточек this.cards путём нахождения начальной карточки, и затем нахождения следующих карточек с помощью хеш-таблицы. В комментариях указано, что временная сложность алгоритма - O(n). Пространственная сложность также O(n), так как образуются 3 объекта размера n (изначальный массив карточек this.cards, упорядоченный массив карточек this.trip и хеш-таблица `this.hashTable')

Не нужно передавать массив карточек данному методу, так как он хранится во внутренней переменной this.cards. Метод ничего не возвращает.

TravelCardSorter.sortCards()

Этот метод создаёт и отображает HTML элемент с id 'itinerary', добавляет в него маршрут из упорядоченного массива карточек this.trip, формулируя инструкции в зависимости от указанного средства передвижения.

Не нужно передавать массив карточек данному методу, так как он хранится во внутренней переменной this.cards. Метод ничего не возвращает.