2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ if they randomly started on same tile do they bump and game over? $\endgroup$ – d'alar'cop Oct 9 '14 at 21:04
  • $\begingroup$ "2 bots may not exist on the 1 tile." From rule 6 $\endgroup$ – warspyking Oct 9 '14 at 21:06
  • 1
    $\begingroup$ @warspyking Is that a yes or a no? In other words, if before any of the bots have moved, two of them are randomly generated with the same coordinates, does the simulation immediately end at 0 turns? $\endgroup$ – Doorknob Oct 9 '14 at 21:07
  • $\begingroup$ Some more questions: how do they choose how to move? That is, do they always move 1 square, then 2? Can they move left/down/left? etc. Also, is there a way for two bots to bump other than trying to end up in the same square at the end of a "tick"? $\endgroup$ – TheRubberDuck Oct 9 '14 at 21:10
  • $\begingroup$ @Door They cannot spawn together $\endgroup$ – warspyking Oct 9 '14 at 21:14
5
$\begingroup$

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
$\endgroup$
  • $\begingroup$ Great Answer, what language did you use? $\endgroup$ – warspyking Oct 9 '14 at 23:28
  • $\begingroup$ @warspyking It says it right in the code: import scala. ... $\endgroup$ – Doorknob Oct 9 '14 at 23:37
  • $\begingroup$ Oh... Sorry. Nevermind my comment then. $\endgroup$ – warspyking Oct 10 '14 at 0:30
  • $\begingroup$ @warspyking - It now explicitly says it's Scala. $\endgroup$ – Rex Kerr Oct 10 '14 at 19:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.