fork download
copy 
  1. import scala.collection.mutable._
  2. import scala.collection.{Map => CMap, Seq => CSeq}
  3. import scala.collection.immutable.{Map => IMap, Seq => ISeq}
  4. object Main extends App {
  5. 	val chart = IMap(
  6. 		'AB -> IMap('NB -> 5.0, 'AY -> 2.5, 'AG -> 3.0),
  7. 		'AY -> IMap('AB -> 2.5, 'AG -> 2.0, 'DY -> 3.0),
  8. 		'AG -> IMap('AY -> 2.0, 'AB -> 3.0, 'BG -> 2.0),
  9. 		'BG -> IMap('AG -> 2.0, 'CG -> 2.0),
  10. 		'CG -> IMap('DG -> 1.0, 'BG -> 2.0),
  11. 		'DG -> IMap('CG -> 1.0, 'EG -> 1.0, 'DY -> 1.5),
  12. 		'DY -> IMap('AY -> 3.0, 'GY -> 3.0, 'DG -> 1.5),
  13. 		'EG -> IMap('DG -> 1.0, 'FG -> 2.0),
  14. 		'FG -> IMap('EG -> 2.0, 'GG -> 2.0),
  15. 		'GG -> IMap('GY -> 1.5, 'FG -> 2.0, 'JG -> 3.0),
  16. 		'GY -> IMap('GG -> 1.5, 'DY -> 3.0, 'HY -> 2.0),
  17. 		'HY -> IMap('GY -> 2.0, 'IY -> 2.0),
  18. 		'IY -> IMap('HY -> 2.0, 'JY -> 1.0),
  19. 		'JY -> IMap('IY -> 1.0, 'KY -> 2.0, 'JG -> 1.5),
  20. 		'KY -> IMap('JY -> 2.0, 'LY -> 2.0),
  21. 		'LY -> IMap('KY -> 2.0, 'MY -> 1.0),
  22. 		'MY -> IMap('MG -> 1.5, 'MB -> 1.0, 'LY -> 1.0),
  23. 		'MG -> IMap('MY -> 1.5, 'MB -> 2.0, 'JG -> 3.0),
  24. 		'MB -> IMap('MG -> 2.0, 'MY -> 1.0, 'NB -> 5.0),
  25. 		'NB -> IMap('NP -> 2.0, 'AB -> 5.0, 'MB -> 5.0),
  26. 		'NP -> IMap('ZP -> 6.0, 'NB -> 2.0),
  27. 		'ZP -> IMap('NP -> 6.0)
  28. 	)
  29.  
  30. 	def getPath(chart: CMap[Symbol, CMap[Symbol, Double]], start: Symbol, end: Symbol): CSeq[Symbol] = {
  31. 		var current = start
  32. 		val paths = new Map.WithDefault[Symbol, CSeq[Symbol]](Map.empty[Symbol, CSeq[Symbol]], k => ISeq.empty[Symbol])
  33. 		val distance = new Map.WithDefault[Symbol, Double](Map(current -> 0.0), k => 1000000.0)
  34. 		val parent = Map.empty[Symbol, Symbol]
  35. 		val unvisited = Set.empty[Symbol] ++ chart.keys - current
  36. 		while (unvisited contains end) {
  37. 			val neighbors = chart(current)
  38. 			neighbors.keys.filter(unvisited contains _).foreach(s => {
  39. 				distance(s) = if (distance(s) > (distance(current) + chart(current)(s))) {
  40. 					parent(s) = current
  41. 					distance(current) + chart(current)(s)
  42. 				} else distance(s)
  43. 			})
  44. 			unvisited -= current
  45. 			val head = unvisited.toSeq.sortBy(distance.apply).head
  46. 			paths(head) = parent(head) +: paths(parent(head))
  47. 			current = head
  48. 		}
  49. 		paths(end).reverse :+ end
  50. 	}
  51.  
  52. 	def getDistance(chart: CMap[Symbol, CMap[Symbol, Double]], seq: CSeq[Symbol]): Double = {
  53. 		val distances = for {
  54. 			i <- Range(0, seq.length - 1)
  55. 			sym1 = seq(i)
  56. 			sym2 = seq(i+1)
  57. 		} yield chart(sym1)(sym2)
  58. 		(0.0 /: distances) (_ + _)
  59. 	}
  60.  
  61. 	def parse(s: Symbol): String = {
  62. 		val Symbol(str) = s
  63. 		val color = str(1) match {
  64. 			case 'P' => "Pink"
  65. 			case 'G' => "Green"
  66. 			case 'B' => "Blue"
  67. 			case 'Y' => "Yellow"
  68. 			case _ => "null"
  69. 		}
  70. 		str(0) + " " + color
  71. 	}
  72.  
  73. 	def getBest(chart: CMap[Symbol, CMap[Symbol, Double]], char1: Char, char2: Char): CSeq[Symbol] = {
  74. 		val paths = for {
  75. 			sym1 <- chart.keys.filter(_.name(0) == char1)
  76. 			sym2 <- chart.keys.filter(_.name(0) == char2)
  77. 		} yield getPath(chart, sym1, sym2)
  78. 		paths.toSeq.sortBy(getDistance(chart, _)).head
  79. 	}
  80. 	Seq(('M', 'Z'), ('Z', 'B')).foreach(p => println(s"Path: ${getBest(chart, p._1, p._2).map(parse).mkString(", ")}, time: ${getDistance(chart, getBest(chart, p._1, p._2))} minutes"))
  81. }
Success #stdin #stdout 0.22s 322496KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
Path: M Blue, N Blue, N Pink, Z Pink, time: 13.0 minutes
Path: Z Pink, N Pink, N Blue, A Blue, A Green, B Green, time: 18.0 minutes
https://ideone.com/oyx6a9
language:
Scala (scala 2.12.8)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!