# The Moving Bots

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.

• if they randomly started on same tile do they bump and game over? Oct 9 '14 at 21:04
• "2 bots may not exist on the 1 tile." From rule 6 Oct 9 '14 at 21:06
• @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? Oct 9 '14 at 21:07
• 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"? Oct 9 '14 at 21:10
• @Door They cannot spawn together Oct 9 '14 at 21:14

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)) }
}

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

• Great Answer, what language did you use? Oct 9 '14 at 23:28
• @warspyking It says it right in the code: import scala. ... Oct 9 '14 at 23:37
• Oh... Sorry. Nevermind my comment then. Oct 10 '14 at 0:30
• @warspyking - It now explicitly says it's Scala. Oct 10 '14 at 19:07