LongestAirPath.scala

LongestAirPath.scala

// https://leetcode.com/problems/reconstruct-itinerary/
// Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the (longest) itinerary in order.

import scala.collection.immutable.{HashMap, HashSet}

object LongestAirPath extends App {

  type Ticket = (String, String)
  type TicketsFromMap = HashMap[String, List[String]]

  private def compareLists(a: List[String], b: List[String]): Boolean = {
    val flags = (a zip b).map { case (a, b) => a < b }.zipWithIndex
    val t = flags.map { case (b, index) => if (b == true) flags.length - index - 1 else 0 }.sum
    val f = flags.map { case (b, index) => if (b == false) flags.length - index - 1 else 0 }.sum
    t >= f
  }

  private def findRoutes(
    ticketsFrom: TicketsFromMap,
    from: String,
    currentRoute: List[String],
    allRoutes: List[List[String]],
    visited: HashSet[String],
    toList: List[String]
  ): List[List[String]] =
    if (toList.isEmpty) {
      val newCurrentRoute: List[String] = from :: currentRoute
      val newAllRoutes = newCurrentRoute :: allRoutes
      if (visited.contains(from)) {
        newAllRoutes
      } else {
        val newVisited: HashSet[String] = visited + from
        ticketsFrom.get(from) match {
          case Some(toList) if !toList.isEmpty => findRoutes(ticketsFrom, toList.head, newCurrentRoute, allRoutes, newVisited, toList.tail)
          case None => newAllRoutes
        }
      }
    } else {
      findRoutes(ticketsFrom, toList.head, currentRoute, allRoutes, visited, toList.tail)
    }

  private def ticketsToTicketsFrom(tickets: List[Ticket], ticketsFrom: TicketsFromMap): TicketsFromMap =
    if (tickets.isEmpty) ticketsFrom
    else {
      val ticket = tickets.head
      val (from, to) = ticket
      val toList = ticketsFrom.get(from) match {
        case Some(xs) => to :: xs
        case None => List(to)
      }
      val newTicketsFrom = ticketsFrom + (from -> toList)
      ticketsToTicketsFrom(tickets.tail, newTicketsFrom)
    }

  def findTickets(tickets: List[Ticket], from: String): List[String] = {
    val ticketsFrom: TicketsFromMap = ticketsToTicketsFrom(tickets, HashMap[String, List[String]]())
    val routes: List[List[String]] = findRoutes(ticketsFrom, from, List(), List(), HashSet(), List())
    val maxLen = routes.map { _.length }.max
    val result = routes.filter { _.length == maxLen }.sortWith { compareLists }.head.reverse
    result
  }
  
  {
    val tickets = List(("A", "B"), ("D", "E"), ("B", "D"))
    assert(findTickets(tickets, "A") == List(
      "A", "B", "D", "E"
    ))
  }
  
  {
    val tickets = List(("A", "B"), ("D", "E"), ("B", "D"), ("D", "F"))
    assert(findTickets(tickets, "A") == List(
      "A", "B", "D", "E"
    ))
  }
  
  {
    val tickets = List(("A", "B"), ("D", "E"), ("B", "D"), ("D", "F"), ("E", "A"))
    assert(findTickets(tickets, "A") == List(
      "A", "B", "D", "E", "A"
    ))
  }

  {
    val tickets = List(("MUC", "LHR"), ("JFK", "MUC"), ("SFO", "SJC"), ("LHR", "SFO"))
    assert(findTickets(tickets, "JFK") == List(
      "JFK", "MUC", "LHR", "SFO", "SJC"
    ))
  }

}