The Moving Bots

Question

Each of the 50 robots move around in a room. The room is 8 by 8 tiles long. Each bot takes up 1 tile. On each turn they move like the knight in Chess, they don't teleport, they move. They all move at the same speed. When they knock into eachother they stop. They cannot move into a wall, they are Pre-programmed to avoid walls. They all start off in different, random positions.

What's the most likely amount of turns it will take before they have all stopped.

A few rules not mentioned (and some mentioned)

1. They start off in random positions.

2. Each turn they move like a Chess knight.

3. They never bump into a wall.

4. They never go backwards (they CAN visit the same tile twice however).

5. They stop when they bump into eachother.

6. If they bump into eachother on the same tile, then they will stay on the tiles before that to stop, 2 bots may not exist on the 1 tile.

7. The board has 64 tiles (8x8).

8. There are 50 bots.

9. Each bot moves at the same speed.

Answer 1

The most likely number of turns is 1, in my interpretation of the rules at least. It's a crowded board, but 1 and 2 are neck-and-neck.

Here's the distribution from a simulation with ten million runs:

 1 turns: 4837276
 2 turns: 4774137
 3 turns:  336992
 4 turns:   42760
 5 turns:    6879
 6 turns:    1488
 7 turns:     334
 8 turns:     101
 9 turns:      10
10 turns:      17
11 turns:       4
12 turns:       1
13 turns:       1

And here's the code (in Scala), in case anyone wants to play with it.

object FiftyBots {
  import scala.util.Random
  import scala.math._

  case class Bot(var x: Int, var y: Int) {
    var alive = true
    var backwards = 16
    val ax = new Array[Int](4)
    val ay = new Array[Int](4)

    def out(xa: Int, ya: Int): Boolean = xa < 0 || xa > 7 || ya < 0 || ya > 7

    def mv(n: Int, a: Array[Int], b: Array[Int], i: Int) {
      val x = signum(n)
      a(i+1) = a(i) + x
      b(i+1) = b(i)
      if (n-x != 0) mv(n-x, a, b, i+1)
    }

    def pick(r: Random) {
      var choice = r.nextInt(16)
      while (choice == backwards) choice = r.nextInt(16)
      val (a1, a2) = if ((choice&1) != 0) (ax, ay) else (ay, ax)
      val (d1, d2) = if ((choice&2) != 0) (2, 1) else (1, 2)
      val s1 = if ((choice&4) != 0) 1 else -1
      val s2 = if ((choice&8) != 0) 1 else -1
      ax(0) = x
      ay(0) = y
      mv(d1*s1, a1, a2, 0)
      mv(d2*s2, a2, a1, d1)
      if (out(ax(3), ay(3))) pick(r)
      else backwards = choice ^ 0xF
    }

    def step(i: Int) { if (alive) { x = ax(i); y = ay(i) } }
  }

  class Board(r: Random) {
    val xs = Array.fill[Bot](8, 8)(null)
    val ts = Array.fill[Bot](8, 8, 4)(null)

    def wipe(a: Array[Bot]) { var i = 0; while (i < a.length) { a(i) = null; i += 1 } }
    def ins(a: Array[Bot], b: Bot) { var i = 0; while (a(i) != null) i += 1; a(i) = b }

    def every[A](f: (Int, Int) => A) {
      for (x <- 0 until 8; y <- 0 until 8) f(x,y)
    }

    def everyBot[A](f: Bot => A) { 
      every{ (x,y) => if (xs(x)(y) != null) f(xs(x)(y)) }
    }

    def ready {
      var n = 64
      var m = 50
      every{ (x,y) =>
        xs(x)(y) = if (r.nextInt(n) < m) { m -= 1; Bot(x,y) } else null
        n -= 1
      }
    }

    def move: Int = {
      everyBot( _.pick(r) )
      for (i <- 1 to 3) {
        var bump = true
        while (bump) {
          bump = false
          every{ (x,y) => wipe(ts(x)(y)) }
          everyBot{ b =>
            b.step(i)
            ins(ts(b.x)(b.y), b)
          }
          every{ (x,y) =>
            if (ts(x)(y)(1) != null) {
              var k = 0
              while (k < 4 && ts(x)(y)(k) != null) {
                ts(x)(y)(k).step(i-1)
                ts(x)(y)(k).alive = false
                bump = true
                k += 1
              }
            }
          }
        }
      }
      var n = 0
      everyBot{ b => if (b.alive) n += 1 }
      n
    }

    override def toString = xs.map(y => y.map{_ match {
      case null => '.'; case b if b.alive => '@'; case _ => 'X'
    }}.mkString).mkString("\n")
  }

  def main(args: Array[String]) {
    val n = args(0).toInt
    val N = args(1).toInt
    (0 until N).par.map{ _ =>
      val b = new Board(new Random())
      (0 until n).map{ _ => b.ready; var i = 1; while (b.move > 0) i += 1; i }
    }.seq.reduce(_ ++ _).
      groupBy(identity).mapValues(_.length).toList.sortBy(_._1).
      map{ case (n,m) => f"$n%2d turns: $m%7d" }.
      foreach(println)
  }
}

Edit: the first argument is the number of boards to run per thread, and the second is the number of threads. So if you are on a 4-core system and want a million boards run as fast as possible:

scala FiftyBots 250000 4