0xDEADBEEF

gridcity.scala

case class Edge(a: Int, b: Int)

val edges = Seq(
  Edge(0,1), Edge(1,2), Edge(2,3), Edge(4,5),
  Edge(5,6), Edge(6,7), Edge(8,9), Edge(9,10),
  Edge(10,11), Edge(12,13), Edge(13,14), Edge(14,15),
  Edge(0,4), Edge(1,5), Edge(2,6), Edge(3,7),
  Edge(4,8), Edge(5,9), Edge(6,10), Edge(7,11),
  Edge(8,12), Edge(9,13), Edge(10,14), Edge(11,15),
)


def generateCity(edgeCount: Int) = {
  val es = util.Random.shuffle(edges).take(edgeCount)
  val es2 = es ++ es.map{ case Edge(a, b) => Edge(b, a) }
  val adjacencyLists: Map[Int, Seq[Int]] = es2.groupMap(_.a)(_.b)

  val marked = new Array[Boolean](16)

  def search(x: Int): Set[Int] = {
    if (marked(x)) {
      Set[Int]()

    } else {
      marked(x) = true
      adjacencyLists.getOrElse(x, Seq()).flatMap(search).toSet + x
    }
  }

  (0 until 16).map(search).map { c => c.size * (c.size - 1) }.sum / 240.0
}

for (edgeCount <- 1 until edges.length) {
  var sum = 0.0
  var min = 1.0

  for (_ <- 1 to 100000) {
    val traffic = generateCity(edgeCount)
    sum += traffic
    min = Math.min(min, traffic)
  }

  println(""+edgeCount+" "+(sum/100000)+" "+min)
}