Alberi creator. Keepalive

This post is a follow-follow-up to this post and its follow-up.

In those two posts we managed to speed-up the solution of an Alberi puzzle, and to create a one-tree-per-region puzzle.

The complete code hereafter can be used to create multi-tree-per-region puzzles.

Using DFS I had little chance to find a valid puzzle, so I had to resort to a more exotic genetic algorithm.

The first class is the general genetic algorithm impementation (well the simplest of implementations):

```
"""Genetic algorithm simplicistic and generic implementation.
"""

import random

class GeneticAlgorithm(object):
"""Genetic algorithm iteration cycle.

The aim is to find an individual with the lowest fitness value
by evolving a population of such individuals.

Each individual is tested against a target value to evaluate its fitness

For each evolution loop part of the best are kept for the next cycle
(retain parameter for evolve method), part of the individuals are kept
indipendently from their fitness (random_select parameter), then these
individuals are mutated according to a mutation rate (mutate paramter),
the rest of the new population is made up crossing randomly picked
individuals.
"""
def __init__(self, individual, fitness, mutate, crossover):
"""Initializes the evolution functions from the problem factory.

Required argument:
individual -- function to generate a new individual. The function can
take a fixed number of parameters to initialize the individual.
This parameters are to be passed to the population method. The
return argument should be a mutable (see mutate).
fitness -- function to score an individual. An individual and the
target will be passed to the function. The target is set by the
evolve method. The function must return a numeric type.
mutate -- function to mutate in-place an individual. The function will
t

Your code looks good, well organised and well documented.

Here are a few details that you could probably improve (I haven't read the whole code).

float division

I assume summed / (len(pop) * 1.0) is just a hacky way to get a float division. Float division is the default behavior in Python 3 (you use // for integer division).

Thus, a probably clearer way to have what you want is to use : from __future__ import division .

Sort with key

The following code is quite confusing :

graded = [(self.fitness(x, target), x) for x in pop]
    graded = [x[1] for x in sorted(graded)]

I guess you are trying to get elements from pop sorted by their fitness by constructing tuples, sorting them and then retrieving the initial element from the tuple.

Good new, the sorted function has a parameter key to do exactly this.

graded = sorted(pop, key=lambda e: fitness(e, target))

(This is not tested)

Try except pass

This piece of code

try:
                            whatever
                        except:
                            pass

gave me shivers.

You should (almost) always specify the type of Exception you are trying to catch. Also, there is usually no good reason to pass on exception catching. More about this : Why is “except: pass” a bad programming practice?, The Most Diabolical Python Antipattern .

Consistent documentation

Your function docstrings use both imperative mode ("do something") and declarative mode ("does something").

As a side-note, PEP 257 suggests :


The docstring is a phrase ending in a period. It prescribes the function or method's effect as a command ("Do this", "Return that"), not as a description; e.g. don't write "Returns the pathname ...".

(And I think that pep257 tries to detect this).

Looping over a grid

self.m = m
    self.n = n
    self.size = size = m * n

    for idx in range(size):
        row, col = divmod(idx, m)
        ...

Seems a bit unnatural.
You know the two dimensions of a grid and you want to iterate over all cells. The natural (yet verbose) way to do so is probably to have 2 nested loops but you are using some mathematical trick in order to have a simple loop.

You might like to know that itertools offers a solution to this exact problem : itertools.product.

It works like this :

>>> n, m = 2, 3
>>> [divmod(i, m) for i in range(n*m)]
[(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2)]
>>> list(itertools.product(range(n), range(m)))
[(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2)]

StackExchange Code Review Q#111033, answer score: 2