Feeds:
Posts
Comments

Flaky user interface tests don’t generally flake a second time unless there is a real problem.  Unfortunately the standard unit test runners don’t offer an option to double-check test failures.  This can result in a high build failure rate.  After being hit with a large number of suddenly flaky UI tests when a new version of Chrome came out we wrote our own test runner to double-check test failures.

Scooter is a simple NUnit console replacement.

It is compatible with NUnit attribute names out of the box but the attribute names can be replaced via command line configuration switches if your tests are marked with different attributes.

Unique features:

- Scooter double checks all test failures/errors by running the test a second time and only counting a failure if the second attempt fails.

- You can attribute an alternative method (via the -afta command line switch, e.g. -afta=AfterEachFailedTestAttribute) to be called after each test failure. This can be used for capturing screenshots, test failure notification, etc.

	[AfterEachFailedTest] 
	public void After_each_failed_test(string testFixtureName, string testMethodName) {}

- You can also create TestSuiteSetUpAttribute and TestSuiteTearDownAttribute (or equivalent) attributes and make a method for each to perform an action at the beginning and end of the test run respectively.

	[AttributeUsage(AttributeTargets.Method, AllowMultiple = false, Inherited = true)]
	public class TestSuiteTearDownAttribute : Attribute
	{
	}
	
	[Test]
	[TestSuiteTearDownAttribute]
	public void Close_all_the_browsers()
	{

- Scooter can optionally run the tests in parallel (-parallel) and/or shuffled (-shuffle).

Usage:

Replace the call to NUnit console in your build script with one that calls Scooter.Console.exe instead.
All TestFixtures in your assemblies will be run unless marked with an Ignore or Explicit attributes.

License: MIT License.

We were introduced to Settlers of Catan by some friends around 2004 and it has become one of our favorite family games. Over the years we have evolved our own variant that is much more cooperative and positive – features that we look for in all games. Here’s a list of the changes we’ve made:

  • Monopoly cards are treated like a Year of Plenty – the original was a source of contention and could make for a really unhappy experience in a resource-starved game.
  • We eliminated the concept of robbing and stealing resources for the same reason.
  • Once a settlement or city is built on a port location, any player can use its 2-to-1 or 3-to-1 resource conversion feature. This can result in some strategic trading in order to encourage/reward a particular player to build a port for which resources are plentiful.
  • Soldiers don’t steal.  They’re not brigands; they’re professionals. They allow the player to put a soldier piece (we use horsemen from a Risk set) on the board adjacent to one of his/her structures. A soldier piece on the board acts like a mobile settlement. It may move to (but is not required to) an adjacent land, whether owned by the player or not, but only on the owner’s turn. When the number of the land tile the soldier is on is rolled, the owner of the solder also receives a resource card for that land. Any number of soldiers may occupy a land tile at the same time. The concept is that soldiers make the inhabitants feel safe and assist in resource gathering, so the land is more productive.
  • A soldier can decide to settle down and establish a settlement if there is in a legal building spot where the soldier is location and the player pays the cost of a settlement and a road. The soldier (horseman) is removed from the board and the player gives up the card. The player places a settlement and road on a valid intersection of the tile formerly occupied by the soldier.  This is based on the historical idea that soldiers would travel out into wilderness areas, build forts and trade with the locals. Eventually individual soldiers might get out of the military and decide to build a farm, store, etc nearby.  This allows a player to project power to a new area of the board to overcome a resource problem or road-block that is preventing them from earning points.
  • At the start of the game, resource numbers are randomized and placed face-down on the board. This means players must make blind choices for their initial settlement locations. Once all players have chosen settlement locations, only numbers on lands adjacent to settlements are turned face-up. As players build additional settlements  the numbers next to the new settlements are turned face-up. As soldiers move onto lands with face-down numbers they also cause the numbers for those lands to be turned face-up. Reasoning: you don’t know how good a location is going to be for mining, grazing, etc until you go there.
  • Rolling 7 does not cause players to discard resources.
  • When a 7 is rolled, the player who rolled it may swap the numbers on two of his/her land tiles, or between one of his/her tiles and a land with a face-down number, turning that number face-up in the process. The player may not move a number from a land that is shared with another player unless that player agrees.  This gives the player the ability to concentrate his/her  resource gathering activities (e.g. use fertilizer on crops, establish a breeding program, innovate better mining practices, etc) based on current needs and how the dice appear to be rolling.

picture of one of our game boards

 

In this project we’ll be solving a variant of John Koza‘s Lawnmower Problem. The previous projects in this series successively drove out the functionality of a genetic solver capable of handling this kind of problem. This project raises our understanding of genetic algorithms and their application to problem solving to a whole new level.

The Lawnmower Problem asks us to provide instructions to a lawnmower to make it mow a field of grass. The field wraps in all directions – if the mower goes off the top it ends up at the bottom and vice versa and the same side-to-side. Let’s say the mower begins in the middle of an 8×8 field facing south.

 .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .
 .  .  .  .  M  .  .  .
 .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .

Next let’s say the available instructions are: mow and turn. mow moves the mower forward one grid square in whatever direction it is facing and cuts the grass in that square. turn causes the mower to turn left 90 degrees.

Simple enough right? Using our previous experience in this series we know we can define a gene for each instruction and use hill climbing to find an optimal solution. I leave this as an exercise to the reader – check out the previous post if you need a refresher.

You should end up with a solution that looks something like the this:

mow mow mow mow mow mow mow mow turn mow mow mow mow mow mow mow turn mow mow mow mow mow mow mow turn mow mow mow mow mow mow turn mow mow mow mow mow mow turn mow mow mow mow mow turn mow mow mow mow mow turn mow mow mow mow turn mow mow mow mow turn mow mow mow turn mow mow mow turn mow mow turn mow mow turn mow turn mow

We can visualize it by numbering each grid square in the order it is mowed:

64  57  42  19  4   31  50  61

63  56  41  18  5   32  51  62

54  55  40  17  6   33  52  53

37  38  39  16  7   34  35  36

12  13  14  15  8*  9   10  11

25  24  23  22  1   28  27  26

46  45  44  21  2   29  48  47

59  58  43  20  3   30  49  60

* - starting location

Or by showing the route traveled graphically:

Mow-turn instructions visualized graphically

Cool, a spiral.

Now let’s expand the available instruction set because all we ever get is spiral shaped mowing patterns. The new instruction is: jump. jump has 2 non-negative arguments, forward and right. The mower will jump forward and to the right the specified number of squares and cut the grass where it lands.

For example, if the mower is facing south at the start location (4,4)

 .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .
 .  .  .  .  M  .  .  .
 .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .

and is told to jump (2,3) it will end up at (1,6), still facing south.

 .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .
 .  .  .  .  #  .  .  .
 .  .  .  .  .  .  .  .
 .  M  .  .  .  .  .  .
 .  .  .  .  .  .  .  .

To implement this simply add jump to the set of genes that require special handling and treat the two genes that follow it as the arguments. If less than 2 genes follow it because it is at or near the end of the gene sequence then fill the missing arguments with zeros. Again, I leave the implementation as an exercise. Note: also make your implementation of getFitness() prefer shorter sequences if and only if the gene sequence mows the entire field.

You may end up with a result similar to the following:

jump (2,5) mow mow mow mow mow mow mow jump (4,3) mow mow mow mow mow mow mow jump (0,3) mow mow mow mow mow mow mow jump (0,3) mow mow mow mow mow mow mow jump (3,3) mow mow mow mow mow mow mow jump (5,3) mow mow mow mow mow jump (5,3) mow mow mow mow mow mow mow jump (1,3) mow mow mow mow mow mow mow jump (5,2) mow

Note that the genetic algorithm has completely abandoned the turn instruction in favor of the more powerful jump instruction because this results in a shorter program.

Here’s a visualization of the mowing route:

44  17  56  40  16  48  26  3

45  18  57  33  9   49  27  4

46  19  58  34  10  50  28  5

63  20  59  35  11  51  29  6

64  21  60  36  12* 52  30  7

41  22  61  37  13  53  31  8

42  23  62  38  14  54  32  1

43  24  55  39  15  47  25  2

* - starting location

Now back the Koza’s purpose for this problem. As interesting as this solution is, the sequence of instructions generated by the solver are completely different from the solution a human would use. Now think about how you’d tell another person to mow a toroidal field. You wouldn’t give them detailed instructions for every step right? You’d break it down into a set of repeatable sequences. In a non-toroid field you might say something like: start at the corner of the field and mow a strip along the edge of the field all the way to the other side.

 .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .
 #  #  #  #  #  #  #  M>

Then turn the mower back this way and mow the strip right next to the one you just completed until you get back to where you started.

 .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .
 .  .  .  .  .  .  .  .
<M  #  #  #  #  #  #  #
 #  #  #  #  #  #  #  #

Turn around again and repeat the process until you’ve mowed the whole field.

You automatically combine squares into strips and trips across-and-back into a repeatable pattern. How do we do that with the mower?

The best result we’ve generated so far requires 64 jump and mow instructions, one for each grid square, to tell the mower how to cut the grass in the field. How can we make it look more like the instructions you’d give a human? We have to introduce the ability to repeat a sequence of instructions by reference and make this an instruction too.

This is where things get interesting. We’re going from using the genes of the genetic sequence more-or-less one-to-one to solve a problem, to genetic programming.

Implementation-wise this means we need two more special genes: begin-numbered-reference and call-numbered-reference. begin-numbered-reference will increment an id and start a new instruction sequence, or block, if and only if the current block is non-empty. call-numbered-sequence, or more simply call, will take a parameter for the id of the sequence to execute. Once that sequence has completed, execution will return to the sequence that made the call – exactly like calling a subroutine.

Here’s a Go implementation of a gene decoder that builds a program for the mower as described above.

func parseProgram(genes string, f *field, m *mower) *program {
	p := NewProgram()

	instructionCodes := make(chan int)
	builders := make(chan builder)
	go streamInstructionCodes(genes, instructionCodes)
	go func() {
		offset := 0
		for instructionCode := range instructionCodes {
			switch instructionCode % numberOfInstructions {
			case 0:
				builders <- createMowBuilder()
			case 1:
				builders <- createTurnBuilder()
			case 2:
				builders <- createJumpBuilder(instructionCodes)
			case 3:
				builders <- createBlockBuilder()
			case 4:
				builders <- createCallBuilder(instructionCodes)
			default:
				panic(fmt.Sprint("No builder defined for instructionCode '", instructionCode, "' from gene '", genes[offset:offset+1], "'"))
			}
			offset++
		}
		builders <- builder{stop: true}
	}()

	currentBlockName := "main"
	blockId := -1
	instructions := make([]Instruction, 0, len(genes))

	for builder := range builders {
		if builder.stop {
			break
		}
		if builder.startNewBlock {
			if len(instructions) > 0 {
				p.addBlock(currentBlockName, instructions)
				blockId++
				currentBlockName = createBlockName(blockId)
				instructions = make([]Instruction, 0, len(genes))
			}
			continue
		}
		instructions = append(instructions, builder.create(f, m))
	}

	if len(instructions) > 0 {
		p.addBlock(currentBlockName, instructions)
	}

	return p
}

Note: Koza’s implementation prevents recursion. This implementation allows recursion but it isn’t difficult to modify it to work Koza’s way. I just find the recursive results more interesting.

Now when we move to from one-to-one gene evaluation to running a program, determining fitness becomes a problem in its own right. On the face it is the same: perform the instructions, determine how many field positions were mowed, switch evaluation strategies to program length if all field squares have been mowed. The problem is we need to handle the flow control involved in fetching subroutines, running them, and returning to the previous location upon completion. We also need the ability to track the number of instructions executed and optionally exit if we run beyond a pre-determined maximum – this prevents infinite loops from blocking evolution in the solver.

I implemented this functionality as a domain independent interpreter (GitHub) while coding my implementation of the Lawnmower Problem.

With the gene-to-program converter and interpreter in place we are free to continue our exploration of the Lawnmower Problem. Here’s a sample optimal solution found by my implementation:

Final: 10119     16.6669533s
main: block1
block0: mow mow mow jump (0,1)
block1: block0 block0 mow block1


52  15  44  5   35  60  26  25

17  16  45  6   36  61  27  53

18  46  8   7   37  62  28  54

19  47  9   39  38  63  29  55

20  48  10  40  64* 31  30  56

21  49  11  41  1   32  57  22

50  13  12  42  2   33  58  23

51  14  43  4   3   34  59  24

* - starting location

Note that the program is recursive in that block1 calls itself.

If we change the logic to prevent recursion we get a slightly longer optimal solution like this:

Final: 10115     15.4188819s
main: block0 block0 block0 block0
block0: jump (6,6) block1 block1 block1 block1
block1: jump (0,1) mow mow mow


34  37  24  10  9   60  48  50

39  38  25  11  62  61  49  51

40  27  26  12  63  2   1   52

41  28  14  13  64  3   54  53

42  29  15  19  18* 4   55  43

31  30  16  20  6   5   56  44

32  35  17  21  7   58  57  45

33  36  23  22  8   59  47  46

* - starting location

Welcome to the world of genetic programming!

You can get the code for my Lawnmower Problem solver from my GitHub repository.

The goal of knapsack problems is to put as much stuff into a container as it will hold, optimizing for constraints such as item weight and size and value. The standard Knapsack Problem adds the limitation that there is only one of each particular item available. In the unbounded variant of the Knapsack Problem there is no limit. This project solves the Unbounded Knapsack Problem (UKP) by improving upon the genetic solver used in the previous post. The code is written in Go.

We’ll start with an easy one so we can understand how it works. We’ll do that by using the item weights, sizes and values from the Rosetta Code page for the Unbounded Knapsack Problem, but with different names, as follows:

Name Value (each) Weight Volume (each)
Bark 3000 0.3 .025
Herb 1800 0.2 .015
Root 2500 2.0 .002

The knapsack contents cannot weigh more than 25 units and its maximum volume is 0.25 units. Our goal is to maximize the value of the contents of the knapsack without exceeding either of the weight or volume limits.

Let’s think about how we would solve this problem by hand. We want to maximize the value within the constraints. So we want a high ratio of value to weight and value to volume. And we want as many of those in the bag as we can get. When we can’t stuff any more of the top item into the bag, we fill in the remaining space with the next most valuable item, and so on. This process is known as hill climbing.

First we need a struct to hold the resource information.

type resource struct {
	name   string
	value  int
	weight float64
	volume float64
}

This project uses genes in a new way – as indexes and counts. Each chromosome will have two parts. The first will represent an index into the list of available resources. The second will be the quantity of that resource to take. The candidate gene sequence will be decoded as follows:

func decodeGenes(candidate string, resources []resource, geneSet string) map[resource]int {
	resourceCounts := make(map[resource]int, len(candidate)/2)
	for i := 0; i < len(candidate); i += 2 {
		chromosome := candidate[i : i+2]
		resourceId := scale(strings.Index(geneSet, chromosome[0:1]), len(geneSet), len(resources))
		resourceCount := strings.Index(geneSet, chromosome[1:2])
		resource := resources[resourceId]
		resourceCounts[resource] = resourceCounts[resource] + resourceCount
	}
	return resourceCounts
}

func scale(value, currentMax, newMax int) int {
	return value * newMax / currentMax
}

The fitness function will use the decoded resource counts and the resource constraints to determine an appropriate fitness for the candidate.

func getFitness(resourceCounts map[resource]int, maxWeight float64, maxVolume float64) int {
	weight := 0.0
	volume := 0.0
	value := 0

	for resource, count := range resourceCounts {
		weight += resource.weight * float64(count)
		volume += resource.volume * float64(count)
		value += resource.value * count
	}

	if weight > maxWeight || volume > maxVolume {
		return -value
	}
	return int(value)
}

Next is a display function that tells us which resources and how many of each to take and their value (fitness).

func display(resourceCounts map[resource]int, fitness int, elapsed time.Duration) {
	label := ""
	for resource, count := range resourceCounts {
		label += fmt.Sprint(count, " ", resource.name, " ")
	}
	fmt.Println(
		fitness,
		"\t",
		label,
		"\t",
		elapsed)
}

The only thing left is to define the resources and invoke the solver:

func main() {
	resources := []resource{
		{name: "Bark", value: 3000, weight: 0.3, volume: .025},
		{name: "Herb", value: 1800, weight: 0.2, volume: .015},
		{name: "Root", value: 2500, weight: 2.0, volume: .002},
	}

	const maxWeight = 25.0
	const maxVolume = .25

	geneSet := "0123456789ABCDEFGH"

	calc := func(candidate string) int {
		decoded := decodeGenes(candidate, resources, geneSet)
		return getFitness(decoded, maxWeight, maxVolume)
	}

	start := time.Now()

	disp := func(candidate string) {
		decoded := decodeGenes(candidate, resources, geneSet)
		fitness := getFitness(decoded, maxWeight, maxVolume)
		display(decoded, fitness, time.Since(start))
	}

	var solver = new(genetic.Solver)
	solver.MaxSecondsToRunWithoutImprovement = .1
	solver.MaxRoundsWithoutImprovement = 2

	var best = solver.GetBestUsingHillClimbing(calc, disp, geneSet, 10, 2, math.MaxInt32)

	fmt.Println("\nFinal:")
	disp(best)
}

Sample output:

$ go run samples/ukp/rosetta/rosetta.go
30000    12 Root                 0
33600    12 Root 2 Herb          2.0001ms
36000    2 Bark 12 Root          2.0001ms
37200    12 Root 4 Herb          3.0002ms
39600    2 Herb 2 Bark 12 Root   3.0002ms
44100    2 Herb 9 Root 6 Bark    5.0003ms
49500    9 Root 5 Herb 6 Bark    5.0003ms
50100    2 Herb 9 Root 8 Bark    5.0003ms
51500    8 Bark 11 Root          6.0003ms
52600    8 Bark 10 Root 2 Herb   6.0003ms
54500    11 Root 5 Herb 6 Bark   6.0003ms

Final: 
54500    11 Root 6 Bark 5 Herb   248.0142ms

Excellent. A success with a sub-second run time. Also, that result matches one of the four optimal combinations for this problem from the RosettaCode page.

Now, just as there are standard problem sets for the Travelling Salesperson Problem, there are also standard problem sets available for the Unbounded Knapsack Problem. One such set, named exnsd16, comes from the PYAsUKP site.

Let’s use the structure of the code above as a guide to implementing a solver for standard problem sets.

First, the resource data must be imported from the file. The file has the following format:

...
c: 1234  <-- constraint
...
begin data <-- resource data
55 32 <-- weight and value
91 3212
...
832 88
end data
...
sol: <-- begin optimal solution
	83	21	58	65 <-- item index, count, weight, value
	71	51	13	20
...

This means the parser will have several transitions because we need the constraint and resource data as a minimum. It would also be nice to have the optimal solution info for result verification.

The resource type doesn’t need a volume field:

type resource struct {
	name   string
	value  int
	weight int
}

Here’s the parser:

func loadResources(routeFileName string) ([]resource, int, map[resource]int) {
	parts := make(chan part)

	lineHandler := ukpResourceFileHeader
	go func() {
		for line := range File.EachLine(routeFileName) {
			lineHandler = lineHandler(line, parts)
		}
		close(parts)
	}()

	resources := make([]resource, 0, 10)
	solution := make(map[resource]int)

	maxWeight := -1
	for part := range parts {
		switch {
		case part.partType == constraintPart:
			maxWeight = parseConstraint(part.line)
		case part.partType == resourcePart:
			resources = append(resources, parseResource(part.line, len(resources)))
		case part.partType == solutionPart:
			resourceId, count := parseSolutionResource(part.line)
			solution[resources[resourceId-1]] = count
		}
	}

	return resources, maxWeight, solution
}

func parseConstraint(line string) int {
	parts := strings.Fields(line)
	constraint, err := strconv.Atoi(parts[1])
	if err != nil {
		panic("failed to parse constraint from '" + line + "'")
	}
	return constraint
}

func parseResource(line string, totalResources int) resource {
	parts := strings.Fields(line)
	weight, err := strconv.Atoi(parts[0])
	if err != nil {
		panic("failed to parse weight from '" + line + "'")
	}
	value, err := strconv.Atoi(parts[1])
	if err != nil {
		panic("failed to parse value from '" + line + "'")
	}

	return resource{
		name:   fmt.Sprint("Item_" + strconv.Itoa(1+totalResources)),
		weight: weight,
		value:  value,
	}
}

func parseSolutionResource(line string) (int, int) {
	parts := strings.Fields(line)
	resourceId, err := strconv.Atoi(parts[0])
	if err != nil {
		panic("failed to parse resourceId from '" + line + "'")
	}
	count, err := strconv.Atoi(parts[1])
	if err != nil {
		panic("failed to parse count from '" + line + "'")
	}

	return resourceId, count
}

type ukpLineFn func(line string, parts chan part) ukpLineFn

func ukpResourceFileHeader(line string, parts chan part) ukpLineFn {
	if strings.Index(line, "c:") != 0 {
		return ukpResourceFileHeader
	}
	parts <- part{line: line, partType: constraintPart}
	return ukpDataHeader
}

func ukpDataHeader(line string, parts chan part) ukpLineFn {
	if strings.Index(line, "begin data") != 0 {
		return ukpDataHeader
	}
	return ukpData
}

func ukpData(line string, parts chan part) ukpLineFn {
	if strings.Index(line, "end data") != 0 {
		parts <- part{line: line, partType: resourcePart}
		return ukpData
	}
	return ukpSolutionHeader
}

func ukpSolutionHeader(line string, parts chan part) ukpLineFn {
	if strings.Index(line, "sol:") != 0 {
		return ukpSolutionHeader
	}
	return ukpSolution
}

func ukpSolution(line string, parts chan part) ukpLineFn {
	if len(line) > 0 {
		parts <- part{line: line, partType: solutionPart}
		return ukpSolution
	}
	return ukpFooter
}

func ukpFooter(line string, parts chan part) ukpLineFn {
	return ukpFooter
}

type partType int

type part struct {
	line     string
	partType partType
}

const (
	constraintPart partType = 1 + iota
	resourcePart
	solutionPart
)

A chromosome will still have two parts, the index and count, but this time it will need more genes because the problem we’re solving has 2000 possible resources and the quantities may need to go as high as 160.

spreadsheet demonstrating picking best first item

If we use hexadecimal values for the geneSet we’ll need 3 genes for the resource index and 2 for the quantity.

const hexLookup = "0123456789ABCDEF"
const numberOfGenesPerChromosome = 5

Here is the decoder:

func decodeGenes(candidate string, resources []resource) map[resource]int {
	resourceCounts := make(map[resource]int, len(candidate)/numberOfGenesPerChromosome)
	const maxHexValue = 16 * 16 * 16
	for i := 0; i < len(candidate); i += numberOfGenesPerChromosome {
		chromosome := candidate[i : i+numberOfGenesPerChromosome]
		resourceId := scale(hexToInt(chromosome[0:3]), maxHexValue, len(resources))
		resourceCount := hexToInt(chromosome[3:numberOfGenesPerChromosome])
		resource := resources[resourceId]
		resourceCounts[resource] = resourceCounts[resource] + resourceCount
	}
	return resourceCounts
}

func hexToInt(hex string) int {
	value := 0
	multiplier := 1
	for i := len(hex) - 1; i >= 0; i-- {
		value += multiplier * strings.Index(hexLookup, hex[i:i+1])
		multiplier *= len(hexLookup)
	}
	return value
}

func scale(value, currentMax, newMax int) int {
	return value * newMax / currentMax
}

Once we’ve decoded the candidate’s gene sequence we can get its fitness:

func getFitness(resourceCounts map[resource]int, maxWeight, optimalFitness int) int {
	weight := 0
	value := 0

	for resource, count := range resourceCounts {
		weight += resource.weight * count
		value += resource.value * count
	}

	if weight > maxWeight {
		if value == optimalFitness {
			return optimalFitness + weight - maxWeight
		}
		return -value
	}

	return int(value)
}

And the last utility function is one to display the decoded genes and quantities in a useful format:

func display(resourceCounts map[resource]int, fitness int, elapsed time.Duration, shorten bool) {
	label := ""
	for resource, count := range resourceCounts {
		if count == 0 {
			continue
		}
		if len(label) > 0 {
			label += ", "
		}
		label += fmt.Sprint(count, " of ", resource.name)
	}
	if shorten && len(label) > 33 {
		label = label[:33] + " ..."
	}
	fmt.Println(
		fitness,
		"   ",
		label,
		"\t",
		elapsed)
}

Finally, here’s the code that glues all the parts together to try to solve the problem.

func main() {
	flag.Parse()
	if flag.NArg() != 1 {
		fmt.Println("Usage: go run standard.go RESOURCEFILEPATH")
		return
	}
	var resourceFileName = flag.Arg(0)
	if !File.Exists(resourceFileName) {
		fmt.Println("file " + resourceFileName + " does not exist.")
		return
	}
	fmt.Println("using resource file: " + resourceFileName)

	resources, maxWeight, solution := loadResources(resourceFileName)

	optimalFitness := 0
	for resource, count := range solution {
		optimalFitness += resource.value * count
	}

	calc := func(candidate string) int {
		decoded := decodeGenes(candidate, resources)
		return getFitness(decoded, maxWeight, optimalFitness)
	}

	start := time.Now()

	disp := func(candidate string) {
		decoded := decodeGenes(candidate, resources)
		fitness := getFitness(decoded, maxWeight, optimalFitness)
		display(decoded, fitness, time.Since(start), true)
	}

	var solver = new(genetic.Solver)
	solver.MaxSecondsToRunWithoutImprovement = 5
	solver.MaxRoundsWithoutImprovement = 3

	var best = solver.GetBestUsingHillClimbing(calc, disp, hexLookup, 10, numberOfGenesPerChromosome, optimalFitness)

	fmt.Print("\nFinal: ")
	decoded := decodeGenes(best, resources)
	fitness := getFitness(decoded, maxWeight, optimalFitness)
	display(decoded, fitness, time.Since(start), false)
	if fitness == optimalFitness {
		fmt.Println("-- that's the optimal solution!")
	} else {
		percentOptimal := float32(100) * float32(fitness) / float32(optimalFitness)
		fmt.Printf("-- that's %f%% optimal\n", percentOptimal)
	}
}

Sample output:

using resource file: samples/ukp/data/exnsd16.ukp
1001881     137 of Item_730      3.0002ms
1016358     147 of Item_1698     5.0003ms
1023272     148 of Item_1698     5.0003ms
1023775     155 of Item_480      283.0162ms
1025480     155 of Item_1227     1.2450713s
1025681     157 of Item_1331     2.7771589s
1027260     156 of Item_288      3.4291962s
1027500     156 of Item_288, 6 of Item_1567      3.9722272s
1027540     7 of Item_1567, 156 of Item_288      3.9732273s
1027860     156 of Item_288, 15 of Item_1567     3.9732273s
1028783     156 of Item_288, 1 of Item_1692      4.212241s
1028950     156 of Item_288, 1 of Item_1801      4.212241s
1029261     1 of Item_1810, 156 of Item_288      4.213241s
1029581     156 of Item_288, 1 of Item_1790      4.2452429s
1029663     156 of Item_288, 1 of Item_1248      4.2492431s
1029664     1 of Item_1767, 156 of Item_288      7.4734275s
1029680     156 of Item_288, 1 of Item_987       8.8265049s

Final: 1029680     1 of Item_987, 156 of Item_288        14.0928061s
-- that's the optimal solution!

It doesn’t achieve an optimal solution every time but it does find a solution that’s better than 99 percent optimal almost every time. Here’s the fitness results across 100 runs with 5 seconds to run and a maximum of 3 rounds without improvement:

1029680 21
1029582 3
1029504 1
1029477 1
1029459 1
1029356 1
1029094 1
1028950 2
1028926 1
1028911 1
1028905 2
1028891 1
1028890 1
1028888 1
1028872 1
1028603 1
1028209 1
1028205 1
1028198 1
1028183 10  <- median
1028176 1
1028166 4
1028127 1
1028101 14
1028100 1
1028058 1
1028050 2
1027991 1
1027776 1
1027416 3
1027311 1
1027042 1
1026972 1
1026799 5
1026747 1
1026721 1
1026345 1
1026285 1
1026204 1
1025834 2
1025681 3 <- 99.611626% optimal

The source code for this project is available from my GitHub repository.

Go on to part 6.

This Go project uses the genetic solver from my previous post to evolve a regular expression that matches all items in a set of wanted strings without matching any items in the set of unwanted strings. For example:

	wanted := []string{"00", "01", "10"}
	unwanted := []string{"11"}

We desire a regular expression that finds strings from wanted without finding those from unwanted. We’ll start by determining the unique set of characters in the wanted strings:

func getUniqueCharacters(wanted []string) string {
	uniqueCharacters := make(map[string]bool)

	characters := ""
	for _, item := range wanted {
		for i := 0; i < len(item); i++ {
			token := item[i : i+1]
			if !uniqueCharacters[token] {
				characters += token
				uniqueCharacters[token] = true
			}
		}
	}
	return characters
}

And we’ll combine those with a set of regex special characters to get our gene set:

const regexSpecials = "[]()|?*+"

geneSet := getUniqueCharacters(wanted) + regexSpecials

Next, when we receive a candidate regex from the solver we’ll verify that it is a valid regex by trying to compile it.

func isValidRegex(candidate string) bool {
	if strings.Contains(candidate, "()") || strings.Contains(candidate, "??") {
		return false
	}

	_, err := regexp.Compile(candidate)
	return err == nil
}

We also need a function to calculate the fitness of a given candidate based on the number of wanted and unwanted strings it matches.

func calculate(wanted, unwanted []string, geneSet string, candidate string) int {
	if !isValidRegex(candidate) {
		return math.MaxInt32
	}

	regex := regexp.MustCompile("^(" + candidate + ")$")
	fitness := 0
	for _, item := range wanted {
		if !regex.MatchString(item) {
			fitness++
		}
	}

	for _, item := range unwanted {
		if regex.MatchString(item) {
			fitness += 10
		}
	}

	return fitness
}

Next we’ll need a way to visualize what’s happening:

	disp := func(candidate string) {
		fmt.Println(candidate,
			"\t",
			calc(candidate),
			"\t",
			time.Since(start))
	}

Finally we glue it all together as follows:

package main

import (
	"github.com/handcraftsman/GeneticGo"
	"fmt"
	"math"
	"regexp"
	"strings"
	"time"
)

const regexSpecials = "[]()|?*+"

func main() {
	wanted := []string{"AL", "AK", "AS", "AZ", "AR"}
	unwanted := []string{"AA"}

	geneSet := getUniqueCharacters(wanted) + regexSpecials

	calc := func(candidate string) int {
		return calculate(wanted, unwanted, geneSet, candidate)
	}
	start := time.Now()

	disp := func(candidate string) {
		fmt.Println(candidate,
			"\t",
			calc(candidate),
			"\t",
			time.Since(start))
	}

	var solver = new(genetic.Solver)
	solver.MaxSecondsToRunWithoutImprovement = 3
	solver.LowerFitnessesAreBetter = true
	solver.MaxRoundsWithoutImprovement = 10

	var best = solver.GetBestUsingHillClimbing(calc, disp, geneSet, 10, 1, 0)
	fitness := calc(best)

	if fitness == 0 {
		println("\nsolved with: " + best)
	} else {
		println("\nfailed to find a solution")
	}

	fmt.Print("Total time: ")
	fmt.Println(time.Since(start))
}

Note: depending on the speed of your processor you may be able to reduce MaxSecondsToRunWithoutImprovement. For this problem I’ve set it to 1/10 second.

solver.MaxSecondsToRunWithoutImprovement = .1

Output:

$ go run samples/regex.go
|        3       0
10       2       1.0001ms
1*0+     1       131.0075ms
0*1?0*   0       335.0192ms

solved with: 0*1?0*
Total time: 335.0192ms

Cool!

Now, here’s a somewhat more interesting problem – repetition:

	wanted := []string{"01", "0101", "010101"}
	unwanted := []string{"0011"}

	solver.MaxSecondsToRunWithoutImprovement = .1

Output:

$ go run samples/regex.go
0        3       1ms
01       2       1ms
(01)+    0       215.0123ms

solved with: (01)+
Total time: 216.0123ms

Nailed it! And one more based on U.S. state mail codes:

	wanted := []string{"AL","AK","AS","AZ","AR"}
	unwanted := []string{"AA"}

	solver.MaxSecondsToRunWithoutImprovement = .5

Output:

$ go run samples/regex.go
R        5       0
AS       4       1.0001ms
AK?L?    3       1.0560604s
AS*L?K*          2       2.1301218s
A[SKLZ]          1       2.62215s
A[LRSZK]         0       3.1391795s

solved with: A[LRSZK]
Total time: 3.6392081s

The source code for this project is available from my GitHub repository.

Go on to part 5.

In my 3rd Go program, I once again have two goals: to expand my knowledge of Go while exploring an interesting problem – the Travelling Salesperson Problem (TSP). This problem involves trying to find a route between various points that optimizes some resource e.g. distance traveled between cities. This project builds upon the genetic solver from my previous post.

There are a bunch of standard Travelling Salesman Problems in TSPLIB for which optimal answers are known. I’ve picked eil51, a medium difficulty one, for this project but any compatible route would work. Here’s what the eil51 problem looks like:

eil51 points plotted

My Go language goals for this project included learning how to handle commandline arguments and read and parse files. Once again I was exposed to even more:

  • built a simple parser based on Rob Pike’s code
  • go can pull projects like ruby gems e.g. go get “github.com/handcraftsman/File”
  • pulled projects can be imported e.g. import “github.com/handcraftsman/File”
  • usage of “go fmt FILE” to standardize the code
  • initialization of struct arrays with [...]
  • use fmt.Sprint(…) to combine various value types into 1 string
  • the go way to use two variables in a for loop:
    for i, j := 0, len(a)-1; i < j; i, j = i+1, j-1

The bulk of the travelling salesperson code revolves around parsing the route files:

NAME : foo
COMMENT : bar
TYPE : TSP
DIMENSION : 51
EDGE_WEIGHT_TYPE : EUC_2D
NODE_COORD_SECTION
1 8 5
2 7 60
... more lines
51 33 25
EOF

and optimal route files:

NAME : foo.opt.tour
COMMENT : ...
TYPE : TOUR
DIMENSION : 51
TOUR_SECTION
30
2
24
// .. more point ids
-1
EOF

Here’s that portion of the code:

type Point struct {
	row int
	col int
}

func readPoints(routeFileName string) map[string]Point {
	pointLines := make(chan string)

	lineHandler := tspRouteFileHeader
	go func() {
		for line := range File.EachLine(routeFileName) {
			lineHandler = lineHandler(line, pointLines)
		}
		close(pointLines)
	}()

	points := make(map[string]Point)

	for pointLine := range pointLines {
		parts := strings.Split(pointLine, " ")

		geneIndex, err := strconv.Atoi(parts[0])
		if err != nil {
			panic(err)
		}

		x, err := strconv.Atoi(parts[1])
		if err != nil {
			panic(err)
		}

		y, err := strconv.Atoi(parts[2])
		if err != nil {
			panic(err)
		}

		point := Point{col: x, row: y}

		geneId := genericGeneSet[geneIndex : geneIndex+1]

		points[geneId] = point
	}

	return points
}
func readOptimalRoute(optimalRouteFileName string, numberExpected int) []string {
	pointLines := make(chan string)

	lineHandler := tspOptimalRouteFileHeader
	go func() {
		for line := range File.EachLine(optimalRouteFileName) {
			lineHandler = lineHandler(line, pointLines)
		}
		close(pointLines)
	}()

	pointIds := make([]string, numberExpected)

	i := 0
	for pointLine := range pointLines {
		x, err := strconv.Atoi(pointLine)
		if err != nil {
			panic(err)
		}

		pointIds[i] = genericGeneSet[x : x+1]

		i++
	}

	return pointIds
}

func values(m map[string]Point) []Point {
	list := make([]Point, len(m))
	i := 0
	for _, v := range m {
		list[i] = v
		i++
	}
	return list
}

type tspLineFn func(line string, pointLines chan string) tspLineFn

func tspRouteFileHeader(line string, pointLines chan string) tspLineFn {
	if line != "NODE_COORD_SECTION" {
		return tspRouteFileHeader
	}
	return tspRoutePoint
}

func tspRoutePoint(line string, pointLines chan string) tspLineFn {
	if line != "EOF" {
		pointLines <- line
		return tspRoutePoint
	}
	return tspRouteFileDone
}

func tspRouteFileDone(line string, pointLines chan string) tspLineFn {
	return tspRouteFileDone
}

func tspOptimalRouteFileHeader(line string, pointLines chan string) tspLineFn {
	if line != "TOUR_SECTION" {
		return tspOptimalRouteFileHeader
	}
	return tspOptimalRoutePoint
}

func tspOptimalRoutePoint(line string, pointLines chan string) tspLineFn {
	if line != "-1" {
		pointLines <- line
		return tspOptimalRoutePoint
	}
	return tspRouteFileDone
}

The remainder is dominated by utility functions that have to convert the genes to points, determine the length of the route, and return a fitness value.

func getPointsInOptimalOrder(idToPointLookup map[string]Point, optimalRoute []string) []Point {
	points := make([]Point, len(optimalRoute))
	i := 0
	for _, v := range optimalRoute {
		points[i] = idToPointLookup[v]
		i++
	}
	return points
}

func genesToPoints(genes string, idToPointLookup map[string]Point) []Point {
	points := make([]Point, len(idToPointLookup))
	if len(genes) != len(idToPointLookup) {
		panic(genes + " - incorrect gene sequence length")
	}
	for i := 0; i < len(genes); i++ {
		geneId := genes[i : i+1]
		point := idToPointLookup[geneId]
		points[i] = point
	}
	return points
}

func getFitness(genes string, points []Point) int {
	distinctPoints := make(map[string]bool)

	for i := 0; i < len(genes); i++ {
		distinctPoints[genes[i:i+1]] = true
	}

	fitness := getDistance(points[0], points[len(points)-1])
	for i := 0; i < len(points)-1; i++ {
		fitness += getDistance(points[i], points[i+1])
	}
	if len(distinctPoints) != len(genes) {
		fitness += 10000 * (len(genes) - len(distinctPoints))
	}
	return fitness
}

func getDistance(pointA, pointB Point) int {
	sideA := float64(pointA.row - pointB.row)
	sideB := float64(pointA.col - pointB.col)
	sideC := math.Sqrt(sideA*sideA + sideB*sideB)
	return int(.5 + sideC)
}

Here’s the main function that glues all the working parts together:

package main

import (
	genetic "github.com/handcraftsman/GeneticGo"
	"flag"
	"fmt"
	"github.com/handcraftsman/File"
	"math"
	"strconv"
	"strings"
	"time"
)

const genericGeneSet string = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890"

func main() {
	flag.Parse()
	if flag.NArg() != 1 {
		println("Usage: go run samples/tsp.go ROUTEFILEPATH")
		return
	}
	var routeFileName = flag.Arg(0)
	if !File.Exists(routeFileName) {
		println("file " + routeFileName + " does not exist.")
		return
	}
	println("using route file: " + routeFileName)

	idToPointLookup := readPoints(routeFileName)
	println("read " + strconv.Itoa(len(idToPointLookup)) + " points...")

	calc := func(genes string) int {
		points := genesToPoints(genes, idToPointLookup)
		return getFitness(genes, points)
	}

	if File.Exists(routeFileName + ".opt.tour") {
		println("found optimal solution file: " + routeFileName + ".opt")
		optimalRoute := readOptimalRoute(routeFileName+".opt.tour", len(idToPointLookup))
		println("read " + strconv.Itoa(len(optimalRoute)) + " segments in the optimal route")
		points := getPointsInOptimalOrder(idToPointLookup, optimalRoute)
		genes := genericGeneSet[0:len(idToPointLookup)]
		idToPointLookup = make(map[string]Point, len(idToPointLookup))
		for i, v := range points {
			idToPointLookup[genericGeneSet[i:i+1]] = v
		}
		print("optimal route: " + genes)
		print("\t")
		println(getFitness(genes, points))
	}

	genes := genericGeneSet[0:len(idToPointLookup)]

	start := time.Now()

	disp := func(genes string) {
		points := genesToPoints(genes, idToPointLookup)
		print(genes)
		print("\t")
		print(getFitness(genes, points))
		print("\t")
		fmt.Println(time.Since(start))
	}

	var solver = new(genetic.Solver)
	solver.MaxSecondsToRunWithoutImprovement = 20
	solver.LowerFitnessesAreBetter = true

	var best = solver.GetBest(calc, disp, genes, len(idToPointLookup), 1)
	disp(best)
	print("Total time: ")
	fmt.Println(time.Since(start))
}

I’ve coded it so that when an optimal solution is available for a problem, the optimal route will be alphabetical. This makes it easier to analyze the output and look for new solver strategies.

In the output, the first column is the route. The second is the fitness, lower is better. And the 3rd is the elapsed time.

ObryFVbutoxyGvfhTIQGeMVVYvxojETuAeHmgdMxCAMFNFrrTyK   211506  1.0001ms

Sample output from a run against the eil51 problem included in the repository:

$ go run samples/tsp.go samples/data/tsp/eil51.tsp
using route file: samples/data/tsp/eil51.tsp
read 51 points...
found optimal solution file: samples/data/tsp/eil51.tsp.opt
read 51 segments in the optimal route
optimal route: abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXY      426

        Solver will run at most 20 second(s) without improvement.

OAryrrFNFMACxMdgmHeAuTEjoxvYVVMeGQIThfvGyxotubVFTyK   211549  0
OAryrrFNFMACxMdgmHeAuTEjoxvyVVMeGQIThfvGYxotubVFTyK   211543  1.0001ms
ObryFVbutoxyGvfhTIQGeMVVYvxojETuAeHmgdMxCAMFNFrrTyK   211506  1.0001ms
ObryFVbutoxyGvfhTIQGeMVVYvxojETuAeHmgrMxCAkFNFdrTyK   201583  2.0001ms
ObryFVbutoxyGvfhTIQGeMVVYvxojETuAeHmgrMxCAkFNFdGTyK   201573  2.0001ms
ObryFVbutoxyGvfhTIQGeMVVYvxyTGdFNFkACxMrgmHeAuTEjoK   201546  3.0002ms
ObryFVbutoxyGvfhTIQReMVVYvxojETuAeHmgrMxCAMFNFdrTyK   201540  3.0002ms
ObryFVbutoxyGvfhrIQReMVVYvxojETuAeHmgrMxCAMFNFdTTyK   201500  3.0002ms
ObryFVbutoxyGvfhrIQReMVVYvxojETuANFMACxMrgmHeFdTTyK   201490  4.0002ms
ObryFVbutoxyGvfhrIQReMVVYvxojETuANFMACxMKgmHeFdTTyK   201469  4.0002ms
ObVryFbutoxyGvfhrIQReMVVYvxojETuANFMACxMKgmHeFdTTyK   201459  5.0003ms
ObVryFbutoxyGvfhrIQRFeHmgKMxCAMFNAuTEjoxvYVVMedTTyK   201408  6.0003ms
ObVrbFyutoxyGvfhrIQRFeHmgKMxCAMFNAuTEjoxvYVVMedTTyK   201390  6.0003ms
ObVrbFyutoxyGvfhrIQRFeHmgKMxCAMFNAuTEjoYxvVVMedTTyK   201379  7.0004ms
ObVrbFyutoxyGMfhrIQRFeHmgKMxCAvFNAuTEjoYxvVVMedTTyK   201330  7.0004ms
ObVrbFyutoxyGMfhrIQRFeHmgKMxCAvFNAuTEjoYxvVVMedTDyK   191370  8.0005ms
ObVrbyutoxyGMfhrIQRFeHmgKMxCAvFNAuTEjooYxvVVMedTDyK   191348  9.0005ms
ObVrbyutoxyGMfhrIQRFeHmgKMxuAvFNACTEjooYxvVVMedTDyK   191330  9.0005ms
ObVrbyutoxyGMfhrKQRFeHmgIMxuAvFNACTEjooYxvVVMedTDyK   191328  9.0005ms
ObVrbYutoxyGMfhrKQRFeHmgIMxuAvFNACTEjooYxvVVMedTDyK   191304  10.0006ms
ObVrbYutoxyGMfhrKQRFgmHeIMxuAvFNACTEjooYxvVVMedTDyK   191299  10.0006ms
ObVryxotuYbGMfhrKQRFgmHeIMxuAvFNACTEjooYxvVVMedTDyK   191292  11.0006ms
ObVryxotuYbGMfhrKQRFgmHeIMxuAvFNACTEjooYxvVBMedTDyK   181342  11.0006ms
ObVryxotuYMGMfhrKQRFgmHeIMxuAvFNACTEjooYxvVBbedTDyK   181331  12.0007ms
ObVryxotuYMGMfhrkQRFgmHeIMxuAvFNACTEjooYxvVBbedTDyK   171318  12.0007ms
ObVryxotuYMGMfhrkQRFgmHeIxuAvFNACTEjooYxvVBbedTDyyK   171316  13.0007ms
ObVryxotuYMGMfhrkQRFgmHelxuAvFNACTEjooYxvVBbedTDyyK   171313  14.0008ms
ObVryxotuYMGMfhrkQRFgmHeIBuAvFNACTEBooYxvVjbedTDyyK   171301  14.0008ms
ObVryxotuYMGMfhrkQRFgdHeIBuAvFNACTEBooYxvVjbemTDyyK   171285  15.0009ms
ObVryxotuYMGMfhrkQRFgdHeIBCAvFNACTEBooYxvVjbemTDyyK   171201  15.0009ms
ObzryxotuYMGMfhrkQRFgdHeIBCANFvACTEBooYxvVjbemTDyyK   161252  16.0009ms
ObzryxutoYMGMfhrkQRFgdHeIBCANFvACTEBooYxvVjbemTDyyK   161229  17.001ms
ObzryxutoYMGMfhrkQRFgdHeIBXANFvACTEBooYxvVjbemTDyyK   151303  17.001ms
ObzryxutoYMGMfhrkQRFxdHeIBXANFvACTEBooYgvVjbemTDylK   141392  18.001ms
ObzryxutoYMGMfhrkQRFxAHeIBXdNFvACTEBooYgvVjbemTDylK   141374  18.001ms
ObzryxutoYMGMfhrkQRFxAHeIBXdNFOACTEBooYgvVjbemTDylK   141349  19.0011ms
ObzYyxutoXMGMfhrkQRFxAHeIBXdNFOACTEBoogvVjbemTTDylK   141339  20.0011ms
ObzYyxutoXMGMfhrkQRFxAHeIBXdNFOACTEBoorgjVvbemTDylK   141335  20.0011ms
ObzYyxutoXMGMfhrkQRFxAHLIBXdNFOACTEBoorgjVvbemTDyKl   131329  21.0012ms
ObzYyxutoXMGMfhrkQRFxAHLIBXdNFOACTEBoorgjVpbemTDyKl   131313  21.0012ms
ObTYyxutoXMGMfhrkQRFxAHLIBXdNFOACTEBoorgjVpbemzDyKl   131296  22.0013ms
ObTYyxutoXMGFNdXBILHAxFRQkrhfMOACTEBoorgjVpbemzDyKl   131274  22.0013ms
xAHLIBXdNFGMXotuxyYTbOFRQkrhfMOACTEBoorgjVpbemzDyKl   131270  23.0013ms
xAHLIBXdNFGMMfhrkQRFObTYyxutoXOACTEBoorgjVpbemzDyKl   131257  23.0013ms
xAHLIBXdNFGMMrhfKyDzmebpVjgrooBETCAOXotuxyYTbOFRQkl   131242  24.0014ms
xAHLIBSdNOGMMrhfkQRFFbTYyxutoXOACzEBoorgjVpbemTDyKl   121233  24.0014ms
xAHLIBSJNOGMMrhfkQRFFbTYyxutoXOACzEBoorgjVpbemTDyKl   121215  25.0014ms
xAHLIBSJNOGMMrhfkQRFFbTYyxutoXOACzEBoorgjVplbemTDyK   121185  26.0015ms
xqHLIBSJNOGMMrhfkQRFFbTYyxutoXOACzEBoorgjVplbemTDyK   111184  26.0015ms
xqHLIBSJNOGMMrhfkQRFFbTYyxutoVXOACzEBoorgjplbemTDyK   111168  27.0015ms
xqHLIBSJNOGMMrhfkQRFFyDTmeblpjgrooBEzCAOXVotuxyYTbK   111143  27.0015ms
xqHLIBSJNOGMMrhfkQRFFyDTmeclpjgrooBEzCAOXVotuxyYTbK   101151  27.0015ms
xqHLIBSJNOGMMrhfkQRFFyDTmeclpjgrooBEzCAOXWotuxyYTbK   101141  28.0016ms
xqHdIBSJNOGMMrhfkQRFFyDTmeclpjgrooBEzCAOXWotuxyYTbK   101135  29.0017ms
xqHLIBSJNOGMMrhfkQRFFyDTmeclpjgrooMEzCAOXWotuxyYTbK   101119  30.0017ms
xqyxutoWXOACzEMoorgjplcemTDyFFRQkfhrMMGONJSBILHYTbK   101090  30.0017ms
xqyxutpjgrooMEzCAOXWolcemTDyFFRQkfhrMMGONJSBILHYTbK   101085  31.0018ms
xqyxutoWXOACzEMoorgjlpcerhfkQRFFyDTmMMGvNJSBILHYTbK   91157   31.0018ms
xqyxutoWXOACzEMoecpljgrorhfkbTYHLIBSJNvGMMmTDyFFRQK   91149   32.0018ms
xTyxutoWXOACzEMoecpljgrorhfkbTYHLIBSJNvGMMmqDyFFRQK   91121   33.0019ms
xTyxutoWXOACzEoecpljgrorhfkbTYHLIBSJNvGMMmqDyyFFRQK   91117   34.0019ms
xTyxutoWvNJSBILHYTbkfhrorgjlpceoEzCAOXGMMmqDyyFFRQK   91114   34.0019ms
xTyxutoWvNJSBXOACzEoecpljgrorhfkbTYHLIGMMmqDyyFFRQK   91082   35.002ms
xTyxutoWvNJSBXOACzDqmMMGILHYTbkfhrorgjlpceoEyyFFRQK   91079   35.002ms
xTyxutoWvNJSBXOACzDqmMMGILHYTbkfhromgjlpceoEyyFFRQK   91074   36.0021ms
TxyxutoWvNJSBXOACzDqmMMGILHYTbkfhromgjlpceoEyyFFRQK   91062   37.0021ms
TxyxutoWvNJSBXOACzDqmMMIGLHYTbkfhromgjlpceoEyyFFRQK   91058   37.0021ms
xTyxuthfkbTYHLIGMMKNJSBXOACzEoecpljgroroWmqDyyFFRQv   91011   38.0022ms
xTyxuthfkbTYHLIGMMKNJSBQRFFyyDqoWmrorgjlpceoEzCAOXv   90995   38.0022ms
xTyxuthfkbTYHLIGMMKNJSBXOACzEHecpljgrormWoqDyyFFRQv   90984   39.0022ms
xTyxuthfkboYHLIGMMKNJSqXOACzEHecpljgrormWoBDyyFFRQv   90970   40.0023ms
xTyxuthfkboYHLIGMMKNJSqXOACzEHecoljgrprmWoBDyyFFRQv   90965   41.0023ms
xTyxutqTYHLIGMMKNJSbkfhXOACzEHecpljgrormWoBDyyFFRQv   90956   41.0023ms
xTyxutqTYHLIGMMKNJSbkfhXOACzEHecpljgrormoWBDyyFFRQv   90936   42.0024ms
xTyyDBWomrorgjlpceHEzCAOXhfkbKSJNMMGILHYTqtuxyFFRQv   90927   43.0025ms
xTyyDBWomrorgjlpceHEzCAOXhfkbJSNKMMGILHYTqtuxyFFRQv   90919   43.0025ms
xTyyDBWomrogjlpceHEzCAOXhfkbJSSNKMMGILHYTqtuxyFFRQv   90909   45.0026ms
xTyyDBWomrogjlpceHEzCAOXhfkbJSSNKMMGILHYTqutxyFFRQv   90905   45.0026ms
xTyyDBWomrogjXOACzEHecplhfkbYSSNKMMGILHJTqutxyFFRQv   90873   47.0027ms
xTyyDBWomrogjXOACzEHecplhfkbYSSNKMMGIHLJTqutxyFFRQv   90867   48.0027ms
xTyyDBWomrogjXOACzEHecplhfkbYSSNKMMGIHLJTqutxynFRQv   80909   48.0027ms
xTyyzCAOXjgormoWBDEHecplhfkbYSSNKMMGIHLJTqutxynFRQv   80874   49.0028ms
xTyyDBWomrogjXOACzEPecplhfkbNSSYKMMGIHLFTqutxynJRQv   70922   49.0028ms
xTyyDBWomrogjXOACzEPekplhfcbNSSYKMMGIHLFTqutxynJRQv   70909   51.0029ms
xTyyDBWomrogjXOACzEPnkplhfcbNSSYKMMGIHLFTqutxyeJRQv   70886   52.003ms
xTyyDBWomrogjXOACzEPnkTFLHIGMMKYSSNbcfhlpqutxyeJRQv   70876   54.0031ms
xTyyDBWomrogjXOACzEPnkTFLHIGMMKYSSNbeyxtuqplhfcJRQv   70869   55.0031ms
xTyyDBWomrogjXOACzEPnkFLHIGMMKYYSSNbeyxtuqplhfcJRQv   70849   56.0032ms
xTTyDBWomrogjXOACzEPnkFLHIGMMKYYSSNbeRJcfhlpqutxyQv   70846   57.0033ms
xTTyDBWomrogjXOACzEPnkFLHIGMMKYYQyxtuqplhfcJRebNSSv   70839   58.0033ms
xTTyDBWmrogjXOACzEPnkFLHIGMMKYYQyxtuqplhfcJRebbNSSv   70838   58.0033ms
xTTyDBWmrogjXOACzEPnkFLHIGMMKYYQyxtuqplhfcJRebiNSSv   60877   60.0034ms
xTTyDBWmrogjXOACzEPnkFLHIGRJcfhlpqutxyQYYKMMebiNSSv   60857   60.0034ms
xTTNpqutxyQYYKMMebilhfcJRGIHLFanPEzCAOXjgormWBDySSv   60856   61.0035ms
xTTNpqutxyQYYKMMebilhfcJRLHIGFanPEzCAOXjgormWBDySSv   60851   62.0035ms
xTTNogjXOACzEPnaFGIHLRJcfhlibeMMKYYQyxtuqprmWBDySSv   60848   63.0036ms
xTTNpqutxyQYYKMMebilgfcIRLJHGFknPEzCASyDBWmrohjXOSv   60838   64.0037ms
xTTNpqutxyQYYKMMebilgfcIRLJHGFknPEzACSyDBWmrohjXOSv   60829   68.0039ms
xTTNpqutxyQYYKMMebilgfcIdLJHGFknPEzACSyDBWmrohjXOSv   60817   70.004ms
xTTNpqutxyQYYKMMebilgfcIdLJHGFknPVzACSyDBWmrohjXOSv   60798   71.0041ms
xTTNpqutxyQYYKMMcbilgfeIdLJHGFknPVzACSyDBWmrohjXOSv   60789   72.0041ms
xTTNpqutxyQSOXjhormWBDySCAzVPnkFGHJLdIefglibcMMKYYv   60784   73.0042ms
xTNppqutxyQSOXjhormWBDDSCAzVPnkFGHJLdIefglibcMMKYYv   60757   76.0043ms
xTNppqutxyQSOXjhormWBDDSCAzVPnkFGIHJLdefglibcMMKYYv   60749   77.0044ms
xTNppqutxyQSOXjiormWBDDSCAzVPnkFGIHJLdefglhbcMMKYYv   60746   77.0044ms
xTNppqutxyQSOXlgfedLJHIGFknPVzACSDDBWmroijhbcMMKYYv   60731   78.0045ms
xTNppqutyQSOXlgfedLJHIGFMMcbhjiormWBDDDSCAzVPnkKYYv   60728   79.0045ms
xTNppqutyQSOXlgfedLJHIGFMMcbhjiormWBDDDBCAzVPnkKYYv   60719   81.0046ms
xTNppqutyQSOXlgfedLJHIGFMMcbhjiYYKknPVzACBDDDBWmrov   60713   81.0046ms
xTnkKYYijhbcMMFGIHJLdefglXOSQytuqppNPVzACBDDDBWmrov   60712   82.0047ms
xTnkKYwijhbcMMFGIHJLdefglXOSQytuqppNPVzACBDDDBWmrov   50777   84.0048ms
xTnkLJHIGFMMcbhjiwYKdefglXOSQytuqppNPVzACBDDDBWmrov   50771   85.0049ms
xTUkLJHIGFMMcbhjiwYKdefglXOSQytuqppNPVzACBDDDBWmrov   50768   86.0049ms
xTUkLJHIGFMMcbhjiwYKdefglXOSQytuqppNPVzACDDDBWmroov   50758   88.005ms
xwUkLJHIGFMMcbhjiTYKdefglXOSQytuqppNPVzACDDDBWmroov   50747   90.0051ms
xwskLJHIGFMMcbhjiTYKdefglXOSQytuqppNPVzACDDDBWmroov   50742   92.0053ms
xwskLJHIGFTijhbcMMYKdefglXOSQytuqpNPVzACDDDBWmmroov   50730   94.0054ms
yQSOXlgfedKYMMcbhjiTFGIHJLkswxtuqpNPVzACDDDBWmmroov   50729   95.0054ms
yQSOXlgfedKYMMcbkhjiTFGIHJLsVxtuqpNPwzACDDDBWmmroov   50724   98.0056ms
yQSONlgfedKYMMcbkhjiTFGIHJLsVxtuqpXPwzACDDDBWmmroov   50723   100.0057ms
yQSONlgfedKYMMcbkhjiTFGIHJLsVXpqutxPwzACDDDBWmmroov   50722   100.0057ms
yQSONlgfedKYMMcbkhjiTFGIHJLsVXpqutxPwzABCDDDWmmroov   50714   102.0058ms
yQSONlgfedKYMMcbkhjiTFGIHJLWDDDCBAzwPxtuqpXVsmmroov   50710   103.0059ms
yQSONlgfedKYMMcbkhjiTFGIHJLWPwzABCDDDxtuqpXVsmmroov   50698   104.0059ms
yQSONlgfedKYMMcbkhjiTFGIHJLWPxDDDCBAzwtuqpXVsmmroov   50692   105.006ms
yQSONlgfedKYMMcbkhjiTFGIHJLWPxDDDCBAzwtuqpXVsEmroov   40769   107.0061ms
yQsVXpqutwzABCDDDxPWLJHIGFTijhkbcMMYKdefglNOSEmroov   40760   109.0062ms
yQsVXpqutwzABCDDDxPWLJHIGFTijhgbcMMYKdefklNOSEmroov   40751   110.0063ms
yQVsXpqutwzABCDDDxPWLJHIGFTijhgbcMMYKdefklNOSEmroov   40746   111.0063ms
yQVsXpqutwzABCDDDxPWLJHIGFTijhgfedKYMMcbklNOSEmroov   40735   112.0064ms
yQVsXmqutwzABCDDDSxPWLJHIGFTijhgfedKYMMcbklNOEproov   40729   113.0065ms
yQVsXmqutwzABCDDDxPWLJHIGFTijhgfedKYMMcbklNOSEroopv   40724   114.0065ms
yQVTFGIHJLWPxDDDCBAzwtuqmXsijhgfedKYMMcbklNOSEroopv   40716   115.0066ms
yQPWLJHIGFTVxDDDCBAzwtuqmXsijhgfedKYMMcbklNOSEroopv   40705   116.0066ms
yQPWLJHIGFTVxDDDCBAzwtuqmlkbcMMYKdefghjisXNOSEroopv   40675   117.0067ms
yESONXsijhgfedKYMcbklmqutwzABCDDDxVTFGIHJLWPQrooppv   40672   120.0069ms
yzwtuqmlkbcMYKdefghjisXNOSEABCDDDxVTFGIHJLWPQrooppv   40665   122.007ms
yzwtuqoorQPWLJHIGFTVxDDDCBAESONXsijhgfedKYMcbklmppv   40662   123.007ms
yzwtuqoorQPWLJHIGEFTVxDDDCBASONXsijhgfedKYMcbklmppv   40646   127.0073ms
yzwtuqoorQPWLJHIGEFTVxABCDDDSONXsijhgfedKYMcbklmppv   40637   128.0073ms
yzwtuqoorQPsXNOSDDCBAxVTFEGIHJLWijhgfedKYMcbkklmppv   40635   130.0074ms
yzwPQrooqutsXNOSDDCBAxVTFEGIHJLWijhgfedKYMcbkklmppv   40633   132.0075ms
yzwPQrooqutsXNOSDDCBAxVTFEGIHJLWijhgfedcMYKbkklmppv   40632   136.0078ms
yzwPQtuqoorsXNOSDDCBAxVTFEGIHJLWijhgfedcMYKbkklmppv   40631   139.0079ms
yzwPQtuqoorsXNOSTVxABCDDFEGIHJLWijhgfedcMYKbkklmppv   40618   142.0081ms
yzwPQtuqoorsXNOSTVxABCDDFEGIHJLWijhgfedKMYcbkklmppv   40615   143.0082ms
yzwPQtuqoorsXNOSDDCBAxVTFEGIHJLWijhgfedcMYKbkklmUpv   30689   144.0082ms
yzwPQtuqUoorsXNOSDDCBAxVTFEGIHJLWijhgfedcMYKbkklmpv   30675   146.0083ms
yzwPQtuqoorsXNOSDDCBAxVTFEGIHJLWijghfedcMYKbkklpmUv   30672   146.0083ms
yzwPQtuqoorsXNOSDDCBAxVTFEGIHJLKYMcdefhgjiWbkklpmUv   30659   147.0084ms
yzwPQtuqoorsYXNOSDDCBAxVTFEGIHJLKMcdefhgjiWbkklpmUv   30657   148.0085ms
yzwTQtuqoorsYXNOSDDCBAxVPFEGIHJLKMcdefhgjiWbkklpmUv   30646   150.0086ms
yzwTQtuqoorsYXNOSDDCBAxVPFEGIHJLKMcdefhgjimbkklpWUv   30626   152.0087ms
yzwTQtuqoorsplkkbmijghfedcMKLJHIGEFPVxABCDDSONXYWUv   30616   157.009ms
yzwTQtuqoorsplkkbmijghfedcMKLJHIGEFPVxABCDDSNOXYWUv   30613   158.009ms
yzwTQtuqoarsplkkbmijghfedcMKLJHIGEFPVxABCDDSNOXYWUv   20655   160.0092ms
yzwTQtuqokklpsrabmijghfedcMKLJHIGEFPVxABCDDSNOXYWUv   20641   161.0092ms
yzwTQtuqokklpsrabmijghfedcMKLJHIGEFSDDCBAxVPNOXYWUv   20629   166.0095ms
yzwTQWYXONPVxABCDDSFEGIHJLKMcdefhgjimbarsplkkoqutUv   20622   168.0096ms
yzwTQWYXONPVvABCDDSFEGIHJLKMcdefhgjimbarsplkkoqutUx   20614   173.0099ms
yzwTQPNOXYWVvABCDSFEGIHJLKMcdefhgjimbarssplkkoqutUx   20598   175.01ms
yzwTQPNOXYWVqokklpssrabmijghfedcMKLJHIGEFSDCBAvutUx   20597   176.0101ms
yzwTQPNOXrssplkoqVWYabmijghfedcMMKLJHIGEFSDCBAvutUx   20586   178.0102ms
yzwTQPNOXrsspbaYWVqoklmijghfedcMMKLJHIGEFSDCBAvutUx   20584   186.0106ms
yzwTQPNOXssrpbaYWVqoklmijghfedcMMKLJHIGEFSDCBAvutUx   20580   191.0109ms
yzwTQPNOXssrpbaYWVqoklmjighfedcMMKLJHIGEFSDCBAvutUx   20578   192.011ms
yzwTQPNOXsnrpbaYWVqoklmjighfedcMMKLJHIGEFSDCBAvutUx   10594   193.011ms
yzwTQPNOXsnrpbaYWVqoklmjihgfedcMMKLJHIGEFSDCBAvutUx   10579   194.0111ms
yzwtuvABCDSFEGIHJLKMMcdefghijmlkoqVWYabprnsXONPQTUx   10563   198.0113ms
yvutwzABCDSFEGIHJLKMMcdefghijmlkoqVWYabprnsXONPQTUx   10545   210.012ms
yvutwzABCDSFEGJHILKMMcdefghijmlkoqnrpbaYWVsXONPQTUx   10536   213.0122ms
yvutwzABCDSFEGHJILKMMcdefghijmlkoqnrpbaYWVsXONPQTUx   10533   214.0122ms
yvutwzABCDSFEGHJILKMMcdefghijmlkrnqopbaYWVsXONPQTUx   10532   219.0125ms
yvutwzABCDSFEGHJILKMMcdefghijmlkrnoqpbaYWVsXONPQTUx   10524   220.0126ms
yvutwzABCDSFEGHJILKMMcdefghijmlkYabpqonrWVsXONPQTUx   10513   221.0126ms
yvutwzABCDSFEGHJILKMMcdefghijmlkYabpqonrsVWXONPQTUx   10505   222.0127ms
yvutwzABCDSFEGHJIKLMMcdefghijmlkYabpqonrsVWXONPQTUx   10500   229.0131ms
yvutwzABCDSFEGHJIKLMMaYklmjihgfedcbpqonrsVWXONPQTUx   10499   232.0133ms
yvutwzABCDSFEGHJIKLMMaYklmjihgfedcbnqoprsVWXONPQTUx   10496   236.0135ms
yvutwzABCDSFEGHJIKLMMaYkbcdefghijmlnqoprsVWXONPQTUx   10488   239.0137ms
ytuvwzABCDSFEGHJIKLMMaYkbcdefghijmlnqoprsVWXONPQTUx   10484   240.0137ms
ytuvwzABCDSFEGHJIKLMMaYkbcdefghijmlnpoqrsVWXONPQTUx   10480   243.0139ms
ytuvwzBACDSFEGHJIKLMMaYkbcdefghijmlnoqprsVWXONPQTUx   10476   245.014ms
ytuvwzBACDRFEGHJIKLMMaYkbcdefghijmlnoqprsVWXONPQTUx   10467   247.0141ms
ytuvwzABCDRFEGHJIKLMMaYkbcdefghijmlnopqrsVWXONPQTUx   10462   255.0146ms
wvutyzABCDRFEGHJIKLMMaYkbcdefghijmlnopqrsVWXONPQTUx   10455   257.0147ms
wvutUTQPNOXWVsrqponlmjihgfedcbkYaMMLKIJHGEFRDCABzyx   10451   263.015ms
wvutUTQPNOXWVsrqponlmjihgfedcbkYaMMLKJIHGEFRDCABzyx   10448   273.0156ms
wvutUTQPNOXWVsrqponlmjihgfedcbkYaMMLKJIHGFERDCABzyx   10446   282.0161ms
wvutUTQPNOXWVsrqponmljihgfedcbkYaMMLKJIHGFERDCABzyx   10440   396.0226ms
wvutUTQPNOXWVsrqponmljihgfedcbkYaSMLKJIHGFERDCABzyx   487     454.026ms
wvutUTSaYkbcdefghijlmnopqrsVWXONPQMLKJIHGFERDCABzyx   479     463.0265ms
wvutUTSPNOXWVsrqponmljihgfedcbkYaQMLKJIHGFERDCABzyx   478     474.0271ms
wvutUTSPNQaYkbcdefghijlmnopqrsVWXOMLKJIHGFERDCABzyx   477     481.0275ms
wvutUTSPNQLMOXWVsrqponmljihgfedcbkYaKJIHGFERDCABzyx   473     487.0279ms
wvutVUTSPNQLMOXWsrqponmljihgfedcbkYaKJIHGFERDCABzyx   472     552.0316ms
wvutVUTSPNOQLMXWsrqponmljihgfedcbkYaKJIHGFERDCABzyx   470     571.0327ms
wvutVUTSPQONLMXWsrqponmljihgfedcbkYaKJIHGFERDCBAzyx   463     606.0347ms
wvutVUTSQPONLMXWsrqponmljihgfedcbkYaKJIHGFERDCBAzyx   455     788.0451ms
wvutVUTSRQPONLMXWsrqponmljihgfedcbkYaKJIHGFEDCBAzyx   451     813.0465ms
wvutsVUTSRQPONLMYkbcdefghijlmnopqrWXaKJIHGFEDCBAzyx   446     833.0476ms
wvutsrqponmljihgfedcbkYMLNOPQRSTUVWXaKJIHGFEDCBAzyx   444     876.0501ms
wvutsrqponmljihgfedcbkYXWVUTSRQPONLMaKJIHGFEDCBAzyx   438     936.0535ms
wvutsrqponmljihgfedcbkaYXWVUTSRQPONLMKJIHGFEDCBAzyx   434     1.2390709s
wvutsrqponmljihgfedcbkaYXWVUTSRQPONMLKJIHGFEDCBAzyx   431     1.3590777s
wvutsrqponkmljihgfedcbaYXWVUTSRQPONMLKJIHGFEDCBAzyx   429     2.2171268s
wvutsrqpomnkljihgfedcbaYXWVUTSRQPONMLKJIHGFEDCBAzyx   428     2.4981429s
wvutsrqpomlnkjihgfedcbaYXWVUTSRQPONMLKJIHGFEDCBAzyx   427     2.6031489s
wvutsrqponmlkjihgfedcbaYXWVUTSRQPONMLKJIHGFEDCBAzyx   426     5.4333108s

wvutsrqponmlkjihgfedcbaYXWVUTSRQPONMLKJIHGFEDCBAzyx   426     25.4354548s
Total time: 25.4354548s

The genetic.go code associated with the TSP solver also received some updates.

  • added strategies: shift, reverse, and crossover
  • weighted strategy selection based on their success rate

The genetic solver changes were necessary to make it capable of solving routes like eil51 but insufficient to make it capable of doing so very often. Here’s a summary of the results received with a 20 second non-improvement timeout over 100 runs:

      4 426
      6 427
      8 428
      1 429
      4 430
      5 431
      8 432
      5 433
     10 434 <- MEDIAN
     16 435
     11 436
      3 437
      4 438
      4 439
      3 440
      4 441
      2 442
      1 446
      1 447

You can get the code from my github repository.

Go on to part 4.

For my second Go project I’ve expanded the genetic solver I wrote in my first Go program to solve the 8 Queens Puzzle. This is another programming problem I previously solved with C#, (q.v for a fuller description of the problem).

My language-related goal for this project was to learn how to implement generators in Go. The hardest part was figuring out how to eliminate the memory leaks I was getting from orphaned go routines.

leaked go routine memory

This project introduced me to more features of the Go language. Points of interest include:

  • channels make writing deferred execution generators a snap
  • emptying channels is critical to eliminating memory leaks from abandoned go routines
  • defer is a pretty cool way to cleanup other potential memory leaks
  • println() can be used to output basic values but it doesn’t understand e.g. time values. Use fmt.Println() for those
  • ranges in loops
  • use strconv.Itoa() to append integer values to a string
  • maps

Here’s the code specific to the 8 Queens Puzzle:

package main

import (
	"fmt";
	"strconv";
	"strings";
	"time";
	"./genetic"
)

const North, West, South, East, Same int = -1, -1, 1, 1, 0
const boardWidthHeight = 8

func main() {
	genes := ""
	for i := 0; i < boardWidthHeight; i++ {
		genes += strconv.Itoa(i)
	}

	start := time.Now()

	calc := func (current string) int {
		return getFitness(current, boardWidthHeight)
	}

	disp := func (current string) {
		display(current, boardWidthHeight)
		print(current)
		print("\t")
		print(getFitness(current, boardWidthHeight))
		print("\t")
		fmt.Println(time.Since(start))
	}

	var solver = new(genetic.Solver)
	solver.MaxSecondsToRunWithoutImprovement = 1

	var best = solver.GetBest(calc, disp, genes, boardWidthHeight, 2)
	disp(best)
	print("Total time: ")
	fmt.Println(time.Since(start))
}

func display(current string, boardWidthHeight int) {
	board := convertGenesToBoard(current)
	defer func() {board = nil}()

	for y := 0; y < boardWidthHeight; y++ {
		for x:= 0; x < boardWidthHeight; x++ {
			key := strconv.Itoa(x) + "," + strconv.Itoa(y)
			if board[key] {
				print("Q ")
			} else {
				print(". ")
			}
		}
		println()
	}
}

func getFitness(current string, boardWidthHeight int) int {
	distinctX := make(map[int]bool)
	defer func() {distinctX = nil}()

	distinctY := make(map[int]bool)
	defer func() {distinctY = nil}()

	board := convertGenesToBoard(current)
	defer func() {board = nil}()

	safeQueens := 0
	for coordinate, _ := range ( board ) {
		parts := strings.Split(coordinate, ",")

		x, err := strconv.Atoi(parts[0])
		if err != nil { panic(err) }
		distinctX[x] = true

		y, err := strconv.Atoi(parts[1])
		if err != nil { panic(err) }
		distinctY[y] = true

		nextPosition := make(chan string)
		defer func() {nextPosition = nil}()

		quit := false
		go getAttackablePositions(x, y, boardWidthHeight, nextPosition, &quit)

		isValid := true
        for n := range (nextPosition) {
			if board[n] {
				quit = true
				<- nextPosition
				isValid = false
				break
			}
		}
		if isValid {
			safeQueens++
		}
	}
	fitness := 1000 * len(board) + safeQueens * 100 + len(distinctX) * len(distinctY)

	return fitness
}

func getAttackablePositions(x, y, boardWidthHeight int, nextPosition chan string, quit *bool) {
	generators := []func (x, y, boardWidthHeight int, nextPosition chan string, quit *bool) {
		generatePositionsNorth, generatePositionsNorthEast, 
		generatePositionsEast, generatePositionsSouthEast,
		generatePositionsSouth, generatePositionsSouthWest, 
		generatePositionsWest, generatePositionsNorthWest }

	for _, generator := range (generators) {
		if *quit {
			break
		}
		generator(x, y, boardWidthHeight, nextPosition, quit)
	}

	close(nextPosition)
}

func generatePositionsNorth(x, y, boardWidthHeight int, nextPosition chan string, quit *bool) {
	generatePositions(x, y, North, Same, boardWidthHeight, nextPosition, quit)
}

func generatePositionsSouth(x, y, boardWidthHeight int, nextPosition chan string, quit *bool) {
	generatePositions(x, y, South, Same, boardWidthHeight, nextPosition, quit)
}

func generatePositionsWest(x, y, boardWidthHeight int, nextPosition chan string, quit *bool) {
	generatePositions(x, y, Same, West, boardWidthHeight, nextPosition, quit)
}

func generatePositionsEast(x, y, boardWidthHeight int, nextPosition chan string, quit *bool) {
	generatePositions(x, y, Same, East, boardWidthHeight, nextPosition, quit)
}

func generatePositionsNorthEast(x, y, boardWidthHeight int, nextPosition chan string, quit *bool) {
	generatePositions(x, y, North, East, boardWidthHeight, nextPosition, quit)
}

func generatePositionsNorthWest(x, y, boardWidthHeight int, nextPosition chan string, quit *bool) {
	generatePositions(x, y, North, West, boardWidthHeight, nextPosition, quit)
}

func generatePositionsSouthEast(x, y, boardWidthHeight int, nextPosition chan string, quit *bool) {
	generatePositions(x, y, South, East, boardWidthHeight, nextPosition, quit)
}

func generatePositionsSouthWest(x, y, boardWidthHeight int, nextPosition chan string, quit *bool) {
	generatePositions(x, y, South, West, boardWidthHeight, nextPosition, quit)
}

func generatePositions(x, y, yDifference, xDifference, boardWidthHeight int, nextPosition chan string, quit *bool) {
	x += xDifference
	y += yDifference
	for ; y >= 0 && y < boardWidthHeight && x >= 0 && x < boardWidthHeight; {
		if *quit {
			return
		}
		nextPosition <- strconv.Itoa(x) + "," + strconv.Itoa(y)
		x += xDifference
		y += yDifference
	}
}

func convertGenesToBoard(genes string) map[string] bool {
	board := make(map[string]bool)
	for i := 0; i < len(genes); i+=2 {
		coordinate := genes[i:i+1] + "," + genes[i+1:i+2]
		board[coordinate] = true
	}
	return board
}

Sample output:

. . . . . . . .
. . . . . . . .
. . Q Q . . . .
. . . Q . . Q .
. . Q . . Q . .
. . . . . . . .
. . . . . . . .
. . . Q . . Q .
2432675433633722        8016    3.0002ms

This represents a chess board with the positions of 8 queens as indicated. The line below the visual board contains:

  • 2432675433633722 – the genetic sequence used to create that board (just the 8 zero-based x and y coordinates of the queens – 0,0 is the top left corner – all run together)
  • 8016 – the fitness value for this particular board layout. 1st digit is the number of queens on the board, 2nd digit is the number of safe queens, 3rd and 4th digits is the number of rows containing queens times the number of columns containing queens
  • 3.0002ms – elapsed time

Output from a full run:

>go run 8queens.go
    Solver will run at most 1 second(s) without improvement.
. . . . . . . .
. . . . . . . .
. . Q Q . . . .
. . . Q . . Q .
. . Q . . Q . .
. . . . . . . .
. . . . . . . .
. . . Q . . Q .
2432675433633722        8016    3.0002ms
. . . . . . . .
. . . . . . . .
. . Q Q . . . .
. . . Q . . Q .
. . Q . . Q . .
. . . . . . . .
. . . Q . . . .
. . . . . . Q .
2432675463333622        8020    6.0004ms
. . . . . . . .
. . . . . . . .
. . . Q . Q . .
. . . Q . . Q .
. . Q . . . . .
. . . Q . . . .
. . . Q . . . .
. . . . . . Q .
2433673563323652        8024    8.0005ms
. . . Q . . . .
. . . . . . . .
. . . Q . . . .
. . Q . . . . .
. . Q . . . . .
. . Q . . . . .
. . . Q . Q . .
. . . . . . Q .
2430672523323656        8028    11.0007ms
. . . Q . . . .
. . . . . . . .
. Q . . . . . .
. . Q Q . . . .
. . Q . . . . .
. . Q . . . . .
. . . . . Q . .
. . . . . . Q .
2430672523123356        8035    14.0008ms
. . . Q . . . .
. . Q . . . . .
. . . . . . . Q
. Q . . . . . .
. . Q . . . . .
. . . . . . . .
. . . . . Q . .
. . . Q . . Q .
2430672113723756        8142    23.0014ms
. . . Q . . . .
. . Q . . . . .
. . . . . . . Q
. Q . . . . . .
. . . . . . . .
. . Q . . . . .
. . . . . Q . .
. . . . Q . Q .
2530672113724756        8249    29.0017ms
. . . Q . . . .
. . Q . . . . .
. . . . . . . Q
. Q . . . . . .
. . . . . . Q .
. . Q . . . . .
. . . . . Q . .
. . . . . . . Q
2530642113727756        8348    36.0021ms
. . . Q . . . .
. . . . . Q . .
. . . . . . . Q
. Q . . . . . .
. . . . . . Q .
. . Q . . . . .
. . . . . Q . .
. . . . . . . Q
2530645113727756        8448    43.0025ms
. . . Q . . . .
. . . . . Q . .
. . . . . . . Q
. Q . . . . . .
. . . . . . Q .
. . Q . . . . .
. . . . . . . Q
. . . . . . . Q
2530645113727776        8548    50.0029ms
. . . Q . . . .
. . . . . Q . .
. . . . . . . Q
. Q . . . . . .
. . . . . . Q .
Q . . . . . . .
. . Q . . . . .
. . . . . . . Q
0530647713725126        8656    189.0109ms
. . . Q . . . .
. . . . . Q . .
. . . . . . . Q
. Q . . . . . .
. . . . . . Q .
Q . . . . . . .
. . Q . . . . .
. . . . Q . . .
0530476413725126        8864    217.0125ms
. . . Q . . . .
. . . . . Q . .
. . . . . . . Q
. Q . . . . . .
. . . . . . Q .
Q . . . . . . .
. . Q . . . . .
. . . . Q . . .
0530476413725126        8864    1.2240701s
Total time: 1.2250701s

The fitness value for the final board (8864) is optimal. This means the displayed board is a layout where all 8 queens can be placed safely on the board. This board position was found after only 217.0125ms, which reiterates how fast Go is.

You may have noticed that I separated the genetic solver code into an importable library. I also used a number of Go features similar to those used in 8queens.go. See 8queens.go and the associated genetic.go in my github repository for the details.

Go on to part 3.

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: