Find cities reachable in given time-CodePudding

I am trying to solve a problem where i have 3 columns in csv like below

connection             Distance          Duration
Prague<>Berlin         400               4
Warsaw<>Berlin         600               6
Berlin<>Munich         800               8
Munich<>Vienna         400               3.5
Munich<>Stuttgart      800               8
Stuttgart<>Freiburg    150               2

I need to find out how many cities i can cover in given time from the origin city

Example if i would give input as

Input: Berlin, 10

Output: ["Prague","Munich","Warsaw"]

Input : Berlin, 30

Output : ["Prague","Munich","Warsaw", "Vienna", "Stuttgart", "Freiburg"]

This is something a Graph problem in real time. I am trying this with Scala, can someone help please.

Below what i tried:

I made it working partially.

import scalax.collection.Graph // or scalax.collection.mutable.Graph
import scalax.collection.GraphPredef._, scalax.collection.GraphEdge._
import scalax.collection.edge.WDiEdge
import scalax.collection.edge.Implicits._

val rows = """Prague<>Berlin,400,4
Warsaw<>Berlin,600,6
Berlin<>Munich,800,8
Munich<>Vienna,400,3.5
Munich<>Stuttgart,800,8
Stuttgart<>Freiburg,150,2""".split("\n").toList

I am preparing the input for my application. Below i am having a list of cities which are present in the given file.

NOTE: We can have it from file itself while reading and kept in list. Here i kept all as lowercase

val cityList = List("warsaw","berlin","prague","munich","vienna","stuttgart","freiburg")

Now creating a case class:

case class Bus(connection: String, distance: Int, duration: Float)


val buses: List[Bus] = rows.map(row => {
  val r =
 row.split("\\,")
  Bus(r(0).toLowerCase, r(1).toInt, r(2).toFloat)
})

case class City(name: String)
// case class BusMeta(distance: Int, duration: Float)

val t = buses.map(bus => {
  val s = bus.connection.split("<>")
  City(s.head) ~ City(s.last) % bus.duration
})

val busGraph = Graph(t:_*)

From above we will create a Graph as required from the input file. "busGraph" in my case.

import scala.collection.mutable
 
val travelFrom = ("BERLIN").toLowerCase
val travelDuration = 16F
val possibleCities: mutable.Set[String] = mutable.Set()


if (cityList.contains(travelFrom)){
  busGraph.nodes.get(City(travelFrom)).edges.filter(_.weight <= travelDuration).map(edge => edge.map(_.name)).flatten.toSet.filterNot(_ == travelFrom).foreach(possibleCities.add)
  println("City PRESENT in File")
}
else
{
  println("City Not Present in File")
}

I am geting Output here :

possibleCities: scala.collection.mutable.Set[String] = Set(munich, warsaw, prague)


Expected Output : Set(munich, warsaw, prague, stuttgart, Vienna)

CodePudding user response：

Do a breadth first search from the origin city, stopping going deeper when you reach the time limit. Output the stops reached by the search.

CodePudding user response：

Your solution only finds direct routes (that's why your output is shorter than expected). To get complete answer, you need to also consider connections, by recursively traversing the graph from each of the direct destinations.

Also, do not use mutable collections, they are evil.

Here is a possible solution for you:

// First, create the graph structure
  def routes: Map[String, (String, Double)] = Source
    .fromInputStream(System.in)
    .getLines
    .takeWhile(_.nonEmpty)
    .map(_.split("\\s "))
    .flatMap { case Array(from_to, dist, time) =>
      val Array(from,to) = from_to.split("<>")
      Seq(from -> (to, time.toDouble), to -> (from, time.toDouble))
    }.toSeq
    .groupMap(_._1)(_._2)
  

  // Now search for suitable routes
  def reachable(
    routes: Map[String, Seq[(String, Double)]],
    from: String,
    limit: Double,
    cut: Set[String] = Set.empty
  ): Set[String] = routes
    .getOrElse(from, Nil)
    .filter(_._2 <= limit)
    .filterNot { case (n, _) => cut(n) }
    .flatMap { case(name, time) => 
       reachable(routes, name, limit - time, cut   from)   name 
    }.toSet
    
  // And here is how you use it
  def main(argv: Array[String]): Unit = {
    val Array(from, limit) = new Scanner(System.in).nextLine().split("\\s")
    val reach = reachable(routes, from, limit.toDouble)
    println(reach)
  }