thanos/eisvoli-exoginon

A simulation example in Golang

Aisvoli Exoginon

A simulation example in golang

• Problem Outline
• Basic Needs
• Possible Solutions
  • Sequencial Non-goroutine Solution
  • Actor/Sprite Solution
• How To Run

Problem Outline

1. Read in map file of towns
2. Each town has upto four routes (north, south, east, or west) to other towns
3. N aliens land at random towns on the map and wander around randomly.
4. if two (or more ?) should meet they destroy the town along with themselves.
5. On a town's destruction the simulation should print "t has been destroyed by alien x and alien y!"
6. When a town is destroyed its removed from the map along with the routes to it.
7. When an alien finds itself in a town with all it's neighbours destroyed it becomes stuck.
8. Finnaly print out a map file of the remaining towns.
9. language to use: Golang

Some simple questions:

1. Can an alien start it's invasion in a isolated town ? This is a possible edgae case, unless we assume the landing town is randomly chosen from the connected twon set.
2. When aliens meet in a town do the kill each other and in the process destroy the town or when the town is desrotyed they die with it. The requirements states that they kill each other and then destroy the town. The interpretation will effect how this is coded.

Basic Needs

1. a map file reader that builds an internal map representation.

Foo north=Bar west=Baz south=Qu-ux
Bar south=Foo west=Bee
.
.

to

// non language specific maps of structs ?
{
  "Foo": {
    "routes": { "north": &Bar, "west": &Baz, "south": &Quux}},
    "occupiers": set{"Alien1"},
    }
    
   "Bar": {
    "routes":{ "west": &Bee, "south": &Foo},
      "occupiers": set{},
    }
 .
 .
 }

Possible Solutions

Sequencial Non-goroutine Solution

As possibly hinted in the requirements with "Each iteration...", one solution would be to cose the simulation without goroutes as an O(N**2) solution The main loop being the 10k iterations:

map = buildMap(map_file)
dead_or_trapped = {}

for iteration in 10k:
  alien_active_set = aliens(N) - dead_or_trapped
  for alien in alien_living_set:
    {killed, trapped, rampaging}, town = alien.pillage(map)
    if killed:
          map.remove(town)
          dead_or_trapped.add(alien)
     if trapped:
           dead_or_trapped.add(alien)

PROS

1. no race conditions
2. no deadlocks
3. deterministic so easy to debug (use constant randon seeds)
4. easy to test
5. performance predictable and linear
6. predictable dev cost and fast to market
7. any developer from any language.

CONS

1. can't scale to utilizes available CPU cores
2. simulation is forced - deterministic
3. boring
4. doesnt showoff the programmer's skill

Actor/Sprite Solution

Define one actor Alien and Town

an Alien's responibility is to

1. get a route from the Map
2. invade the new town
3. if the town is already invaded kill the other alien, destroy the town and die
4. if the town is vacant goto the first step

PROS

1. elegant
2. simulation is non-deterministic
3. will scale use available CPU cores

CONS

1. non-deterministc so it's hard to test and debug
2. performance unpredictable and linear
3. unpredictable dev cost
4. race and dead lock prone.
5. needs an expienced golang developer

A FEW POSSIBLE RACE CONDITIONS

1. an alien needs to get an available route and then occupy the town - but the at the same time could have beed destroyed. for instance the code look like:

if alien.location == nil {
	next_town = route_map.AnyTown() 
} else {
	next_town = alien.location.RandomRouteFrom()
}
if next_town != nill {
	if next_town.IsAlreadyOccupied() {
		occupier = next_town.GetOccupier()
		next_town.Destroy()
		occupier.Kill()
	} else {
		next_town.SetOccupier(alien)
		alien.location = next_town
	}
} else {
	alien.Trapped()
}

• location is *Town

1. there are race conditions on the next_town's state
2. there are race conditions on the next_town's routes - it's neighbours could have been detroyed between AnyTown(), RandomRouteFrom() and IsAlreadyOccupied()
3. between the test IsAlreadyOccupied() == false and next_town.SetOccupier(alien) it could have been already occupied.
4. And there are more in if next_town.IsAlreadyOccupied() {} condition.

So the next question is channels or Mutex and where ?

How to Run

go run main.go  -energy=bool -energy=int  N map_file

where required arguments are:

1. N is the number of aliens to land on the por planet
2. map_file the path to a map file in the described format below

where the optional (flag) arguments are:

• -debug
• -energy

Optional flags must be before the position line arguments, N and map_file

examples:

	go run main.go  10 maps/map_01.txt
	go run main.go -energy= 10 3 maps/map_01.txt
	go run main.go -debug=true -energy= 10 3 maps/map_01.txt

Map file format is like this:

#Foo north=Bar west=Baz south=Qu-ux
#Bar south=Foo west=Bee
#Qu-ux north=Foo west=Bee
#Bee west=Bar east=Qu-ux
#Baz west=Foo south=Daz
Daz north=Kaz
Naz west=Zaz south=Daz
Zaz north=Kaz east=Naz
Kaz south=Zaz

Lines starting with # are ignored`