Merge pull request #3 from pesco/placebots easterhegg

place bots fairly

1 files changed, 60 insertions, 74 deletions

diff --git a/main.go b/main.go
index 2a742f7..0004ca8 100644
--- a/main.go
+++ b/main.go
@@ -1,6 +1,7 @@
 package main
 
 import (
+	"container/heap"
 	"flag"
 	"fmt"
 	"math/rand"
@@ -213,80 +214,77 @@ func initArena(config *Config) *r2pipe.Pipe {
 	return r2p
 }
 
+// a heap of integers (adapted from the container/heap documentation)
+type IntHeap []int
+
+func (h IntHeap) Len() int		{ return len(h) }
+func (h IntHeap) Less(i, j int) bool	{ return h[i] < h[j] }
+func (h IntHeap) Swap(i, j int)		{ h[i], h[j] = h[j], h[i] }
+
+func (h *IntHeap) Push(x any) {
+	*h = append(*h, x.(int))
+}
+
+func (h *IntHeap) Pop() any {
+	n := len(*h)
+	x := (*h)[n - 1]
+	*h = (*h)[0 : n - 1]
+	return x
+}
+
 // genRandomOffsets returns random offsets for all bots
 // This is used to get the offset the bots are initially placed in
 func genRandomOffsets(config *Config) {
 
 	logrus.Info("Generating random bot offsets")
 
-	// define the amount of bots, an array to store the offsets in and a counter
-	// to store the amount of tries it took to find a random positon for the bots
-	var amountOfBots int = len(config.Bots)
-	var offsets []int
-	var roundCounter int = 0
-
 	// seed the random number generator
 	rand.Seed(time.Now().UTC().UnixNano())
 
-	for {
-
-		// reset the offsets array
-		offsets = []int{}
-
-		// define a random address
-		// | ------------------------------------- | ----- |
-		// | generate an address in this space
-		address := rand.Intn(config.Memsize - config.MaxProgSize)
-		logrus.Tracef("%d", address)
-
-		// for all bots, try to generate another random address after the intially
-		// generated address and test if it fits in memory
-		for i := 0; i < amountOfBots; i++ {
-
-			// append the address to the offsets array
-			offsets = append(offsets, address)
-
-			// define a min and max bound
-			//
-			// | ------|-|----------------------------------|-|
-			// |       | |           in this space          | |
-			// a       b c                                  d e
-			//
-			// a = 0x0
-			// b = address
-			// c = address + config.MaxProcSize (min)
-			// d = config.Memsize - config.MaxProgSize (max)
-			// e = config.Memsize
-			min := address + config.MaxProgSize
-			max := config.Memsize - config.MaxProgSize
-
-			// if the new minimum bound is bigger or equal to the maximum bound,
-			// discard this try and start with a fresh new initial address
-			if min >= max {
-				roundCounter++
-				break
-			}
-
-			// generate a new address in the [min, max) range defined above
-			address = rand.Intn(max-min) + min
-			logrus.Tracef("%d", address)
-
-			// If there isn't enough space inbetween the address and the biggest
-			// possible address, as in, the biggest possible bot can't fit in that
-			// space, discard and start with a new fresh initial address
-			if (config.Memsize-config.MaxProgSize)-address < config.MaxProgSize {
-				roundCounter++
-				break
-			}
-		}
+	nbots := len(config.Bots)
 
-		// if the needed amount of offsets has been found, break out of the infinite loop
-		if len(offsets) == amountOfBots {
-			break
-		}
+	// calculate final occupied and remaining free space
+	needed := 0
+	for i := 0; i < nbots; i++ {
+		needed += len(config.Bots[i].Code)
+	}
+	if needed > config.Memsize {
+		panic("total bot size exceeds available memory")
 	}
+	free := config.Memsize - needed
+
+	// pick nbots random places among chunks of free memory.
+	// we consider as possible places the spaces between individual free
+	// bytes of memory and pick one uniformly at random for each bot.
+	// the results are stored in a heap so we can easily go through them
+	// from first to last later.
+	// it is okay to pick the same place multiple times, which just means
+	// that the corresponding bots will be adjacent.
+	places := &IntHeap{}
+	for i := 0; i < nbots; i++ {
+		// there are free + 1 possible places, one in front of each
+		// free byte, plus one after the last.
+		heap.Push(places, rand.Intn(free + 1))
+	}
+
+	// randomly choose the order in which the bots should appear
+	perm := rand.Perm(nbots)
+
+	// calculate the resulting bot offsets
+	offsets := make([]int, nbots)
+	occupied := 0;				// space allocated so far
+	for i := 0; i < nbots; i++ {
+		bot := perm[i]
+		size := len(config.Bots[bot].Code)
+		place := heap.Pop(places).(int)
+
+		offsets[bot] = place + occupied
+		if offsets[bot] + size > config.Memsize {
+			panic("BUG: bot placed out of bounds")
+		}
 
-	logrus.Infof("Initial bot positions found after %d tries", roundCounter)
+		occupied += size
+	}
 
 	// debug print all offsets
 	var fields0 logrus.Fields = make(logrus.Fields)
@@ -295,18 +293,6 @@ func genRandomOffsets(config *Config) {
 	}
 	logrus.WithFields(fields0).Debug("Offsets")
 
-	// shuffle the offsets
-	rand.Shuffle(len(offsets), func(i, j int) {
-		offsets[i], offsets[j] = offsets[j], offsets[i]
-	})
-
-	// debug print the shuffled offsets
-	var fields1 logrus.Fields = make(logrus.Fields)
-	for i := 0; i < len(offsets); i++ {
-		fields1[fmt.Sprintf("%d", i)] = offsets[i]
-	}
-	logrus.WithFields(fields1).Debug("Shuffled offsets")
-
 	config.RandomOffsets = offsets
 }