Shaping Inputs with Constraints

Shaping Inputs with Constraints#

The Limits of Grammars#

So far, all the operations we have performed on our data were syntax-oriented - that is, we could shape the format and structure of our values, but not their semantics - that is, their actual meaning. Consider our Person/Age dataset from the previous section. What would we do if we want the “age” in a specific range? Or we want it to be odd? Or we want the age to be distributed in a certain way?

All of this refers to context-free grammars, which are the ones Fandango uses.

Some of these can be obtained by altering the grammar - limiting the age to two digits at most, for instance, will keep the value below 100 - but others cannot. Properties that cannot be expressed in a grammar are called semantic properties - in contrast to syntactical properties, which is precisely what grammars are good for.

Specifying Constraints#

Fandango solves this problem through a pretty unique feature: It allows users to specify constraints which inputs have to satisfy. These thus narrow down the set of possible inputs.

Constraints are predicates over grammar symbols. Essentially, you write a Boolean expression, using grammar symbols (in <...>) to refer to individual elements of the input.

As an example, consider this Fandango constraint:

int(<age>) < 50

This constraint takes the <age> element from the input and converts it into an integer (all symbols are strings in the first place). Inputs are produced only if the resulting value is less than 50.

We can add such constraints to any .fan file, say the persons.fan file from the previous section. Constraints are preceded by a keyword where. So the line we add reads

where int(<age>) < 50

and the full persons.fan file reads

<start> ::= <person_name> "," <age>
<person_name> ::= <first_name> " " <last_name>
<first_name> ::= <name>
<last_name> ::= <name>
<name> ::= <ascii_uppercase_letter><ascii_lowercase_letter>+
<age> ::= <digit>+
where int(<age>) < 50

If we do this and run Fandango, we obtain a new set of inputs:

$ fandango fuzz -f persons.fan -n 10

Nkrhcc Dwbvtk,12
Vjr Poiv,014
Citr Dxkpk,9
Egdjoy Earj,6
Jicy Pcq,5
Yfxgi Mkc,28
Tall Qanq,4
Zqus Dvas,4
Hzyyqf Vkac,7
Gulczn Quqg,6

We see that all persons produced now indeed have an age of less than 50. Even if an age begins with 0, it still represents a number below 50.

The language Fandango uses to express constraints is Python, so you can make use of arbitrary Python expressions. For instance, we can use Python Boolean operators (and, or, not) to request values in a range of 25-45:

Interestingly, having symbols in <...> does not conflict with the rest of Python syntax. Be sure, though, to leave spaces around < and > operators to avoid confusion.

25 <= int(<age>) and int(<age>) <= 45

and we obtain these inputs:

Iis Arnnqt,45
Aj Nnvw,25
Hb Erlpba,043

Bgesr Chz,41
Mja Gu,37

Pgh Nt,40
Bgyjt An,27
Higb Vhk,29
Lfhjgd Xmf,40
Ld Jr,32

Start with persons.fan and add a constraint such that we generate people whose age is a multiple of 7, as in

Nqzv Qwtjp,0
Ysmzyt Hnjsp,0
Svbs Tjrg,0
Bzpsc Fzc,707
Bmzy Wuxejk,0
Un Eouut,0
Buxxh Dqwpvx,0
Fk Gs,0
Lkfiok Qj,0
Kgw Juaoxj,0

(Hint: The modulo operator in Python is %).

Solution

This is not too hard. Simply add

where int(<age>) % 7 == 0

as a constraint.

Constraints and `DerivationTree` types#

Whenever Fandango evaluates a constraint, such as

int(<age>) > 20

the type of <age> is actually not a string, but a DerivationTree object - a tree representing the structure of the output.. You can use DerivationTree objects as other basic python data types by converting them using (int(<age>), str(<age>), bytes(<age>)).

You can then invoke most string, bytes and int methods on them (<age>.startswith('0')) (see Details)
You can compare them against each other (<age_1> == <age_2>) as well as against other strings (<age> != "19")

One thing you cannot do, though, is passing them directly as arguments to functions that do not expect a DerivationTree type. This applies to the vast majority of Python functions.

Important

If you want to pass a symbol as a function argument, convert it to the proper type (int(<age>), float(<age>), str(<age>)) first. Otherwise, you will likely raise an internal error in that very function.

Important

On symbols, the [...] operator operates differently from strings - it returns a subtree of the produced output: <name>[0] returns the <first_name> element, not the first character. If you want to access a character (or a range of characters) of a symbol, convert it into a string first, as in str(<name>)[0].

We will learn more about derivation trees, DerivationTree types, and their operators in Accessing Input Elements.

Constraints on the Command Line#

If you want to experiment with constraints, keeping on editing .fan files is a bit cumbersome. As an alternative, Fandango also allows to specify constraints on the command line. This is done with the -c (constraint) option, followed by the constraint expression (typically in quotes).

Starting with the original persons.fan, we can thus apply age constraints as follows:

$ fandango fuzz -f persons.fan -n 10 -c '25 <= int(<age>) and int(<age>) <= 45'

Constraints can be given multiple times, so the above can also be obtained as

$ fandango fuzz -f persons.fan -n 10 -c '25 <= int(<age>)' -c 'int(<age>) <= 45'

Important

On the command line, always put constraints in single quotes ('...'), as the angle brackets might otherwise be interpreted as I/O redirection.

When do constraints belong in a .fan file, and when on the command line? As a rule of thumb:

If a constraint is necessary for obtaining valid input files (i.e. if the inputs would not be accepted otherwise), it belongs into the .fan file.
If a constraint is optional, for instance for shaping inputs towards a particular goal, then it can also go on the command line.

How Fandango Solves Constraints#

How does Fandango obtain these inputs? In a nutshell, Fandango is an evolutionary test generator:

It first uses the grammar to generate a population of inputs.
It then checks which individual inputs are closest in fulfilling the given constraints. For instance, for a constraint int(<X>) == 100, an input where <X> has a value of 90 is closer to fulfillment than one with value of, say 20.

Selecting the best inputs is also known as “survival of the fittest”

The best inputs are selected, the others are discarded.
Fandango then generates new offspring by mutating the remaining inputs, recomputing parts according to grammar rules. It can also exchange parts with those from other inputs; this is called crossover.
Fandango then repeats Steps 2-4 until all inputs satisfy the constraints.

All of this happens within Fandango, which runs through these steps with high speed. The -v option (verbose) produces some info on how the algorithm progresses:

$ fandango -v fuzz -f persons.fan -n 10 -c 'int(<age>) % 7 == 0'

fandango:INFO: ---------- Parsing FANDANGO content ----------
fandango:INFO: <stdlib>: loading cached spec from /home/runner/.cache/fandango/aceaa3c625c2c9dff9e9555d703a72b446055ebd4b1117f8469b832e31b6f156.pickle
fandango:INFO: persons.fan: loading cached spec from /home/runner/.cache/fandango/3cbca9420e175b17486d43fd2035bd10bfb3550ba6e20d7d9a279c25f1231d83.pickle
fandango:INFO: <string>: loading cached spec from /home/runner/.cache/fandango/b344dde9cd12fe3dbc86a3757339909d4fd6a1c8d89c37c213b6fb0d82fbedee.pickle
fandango:INFO: int(<age>) % 7 == 0: loading cached spec from /home/runner/.cache/fandango/a6dc7b7613530086c955f2f0af3375cf16ada6378101eb8f45e356811a96daea.pickle

fandango:INFO: File mode: text
fandango:INFO: ---------- Initializing base population ----------
fandango:INFO: ---------- Initializing FANDANGO algorithm ---------- 
fandango:INFO: ---------- Done initializing base population ----------
fandango:INFO: ---------- Generating  for 500 generations----------
fandango:INFO: Generating (additional) initial population (size: 100)...
Swkdk Kbxjo,0
Jpwky Bbxza,6503
Ywvl Yuac,0
Zs Ep,0
Uga Djoxxu,1722
Oqqjwh Dxbado,0
Zv Xzh,92421
Gnftsa Bl,0
Tch Zwoh,0
Hheht Gfhici,56

Note

The -v option comes right after fandango (and not after fandango fuzz), as -v affects all commands (and not just fuzz).

The Fandango Progress Bar#

While Fandango is solving constraints, you may see a progress bar in the terminal. The progress bar looks like this:

progress-bar

The progress bar is composed of three parts. On the leftmost side, we have the Fandango logo (“💃 Fandango”), followed by a generation counter (“6/500”) showing how often (6) the population has evolved (out of a maximum 500).

Most of the line, however, is filled by a fitness visualization illustrating how the fitness is distributed across the inputs in the population. Each fraction of the line corresponds to an equal fraction of individual inputs. Hence, a 1/70 of the line (typically one character) stands for 1/70 of the population.

The color of each fraction how fit the inputs in the fraction are - on a scale from bright green (perfect fitness, fulfilling the given constraints) to dark red (very little fitness, far away from fulfilling the constraints). Depending on its capabilities, your terminal may also show shades between these colors. Inputs that do not satisfy the constraints at all (zero fitness) are shown in gray.

In the above example, we can see that Fandango already has produces a few inputs that satisfy the constraints; a few more are close and may get there through further evolution.

Note

By default, the progress bar only shows up if

Fandango’s standard error is a terminal;
Fandango is not run within Jupyter notebook (Jupyter cannot interpret the terminal escape sequences); and
Fandango logging is turned off (it also writes to standard error).

The option --progress-bar=on turns on the progress bar even if the above conditions are not met. The option --progress-bar=off turns the progress bar off.

Soft Constraints and Optimization#

So far, we have seen constraints that have to be satisfied for Fandango to produce a string. On top, Fandango also supports so-called “soft” constraints that Fandango aims to satisfy as good as it can. These “soft” constraints come in two forms:

maximizing constraints: These constraints specify an expression whose value should be as high as possible
minimizing constraints: These constraints specify an expression whose value should be as low as possible.

Such soft constraints are specified

on the command line, using --maximizing EXPR and --minimizing EXPR, respectively; or
in the .fan file, introducing them with minimizing and maximizing (instead of where), respectively.

If, for instance, you want Fandango to maximize the <age> field, you write

$ fandango fuzz -f persons.fan --maximize 'int(<age>)'

Jnqlk Xeattp,62889
Mipw Eho,96564

Kc Ynj,32904577

Mv Bosrupvzv,33601064
Oiufoicv Baee,93766204

Ho Pgkceti,95275833

Rd Yvktm,6453122239

Pajae Smsfswfsxlbpr,150940460519
Klzzbiczyu Chbpt,834271600449

Juwvbq Sicr,959722407461

Conversely, minimizing the <age> field yields

$ fandango fuzz -f persons.fan --minimize 'int(<age>)'

Ecm Ue,2

Ezzu Qcq,0
Jw Qy,0

Bcrxa Obvm,0
Oh Zwe,0

Enchvjup Smahbk,00

Pznzsiunmysiw Zsuglewqt,0

Enchvjup Smahbk,0
Bcrxa Obvm,00

Jw Urknmpejgslfycphpnw,0

Alternatively, you could also add to the .fan file:

maximizing int(<age>)

or

minimizing int(<age>)

respectively.

To express optional goals (i.e., real “soft” constraints), simply use a Boolean expressions as the expressions for --maximize or --minimize. Then, Fandango will aim to maximize (or minimize) its value.

Note

Remember that in Python True is equivalent to 1, and False is equivalent to 0; therefore, “maximizing” a Boolean value means that Fandango will aim to solve it.

Here is an example of a “soft” Boolean constraints, aiming to obtain names that start with “F”:

$ fandango fuzz -f persons.fan --maximize '<name>.startswith("A")' -n 10

Keafh Bf,65
Henii Pvkozx,898
Pcqy Bkice,37903
Ha Wyp,738
Dxpc Axhq,649
Ak Nykdc,70
Atbfen Jbdac,6

Xpnzw Amuyvv,111

Aiv Pufnjp,30
Afijwm Zbr,03490

As you see, “soft” constraints are truly optional :-)

When Constraints Cannot be Solved#

Normally, Fandango continues evolving the population until all inputs satisfy the constraints. Some constraints, however, may be difficult or even impossible to solve. After a maximum number of generations (which can be set using -N), Fandango stops and produces the inputs it has generated so far. We can see this if we specify False as a constraint:

$ fandango -v fuzz -f persons.fan -n 10 -c 'False' -N 50

fandango:INFO: ---------- Parsing FANDANGO content ----------
fandango:INFO: <stdlib>: loading cached spec from /home/runner/.cache/fandango/aceaa3c625c2c9dff9e9555d703a72b446055ebd4b1117f8469b832e31b6f156.pickle
fandango:INFO: persons.fan: loading cached spec from /home/runner/.cache/fandango/3cbca9420e175b17486d43fd2035bd10bfb3550ba6e20d7d9a279c25f1231d83.pickle
fandango:INFO: <string>: loading cached spec from /home/runner/.cache/fandango/b344dde9cd12fe3dbc86a3757339909d4fd6a1c8d89c37c213b6fb0d82fbedee.pickle

fandango:INFO: False: saving spec to cache /home/runner/.cache/fandango/bc2c8e53f0e4988c0aeff5d495cfd1726638f7d33fd7002ce89f1fc7a8a56431.pickle
fandango:INFO: File mode: text
fandango:INFO: ---------- Initializing base population ----------
fandango:INFO: ---------- Initializing FANDANGO algorithm ---------- 
fandango:INFO: ---------- Done initializing base population ----------
fandango:INFO: ---------- Generating  for 50 generations----------
fandango:INFO: Generating (additional) initial population (size: 100)...

fandango:INFO: Initial population generated in 0.09 seconds
fandango:INFO: Generation 1 - Average Fitness: 0.02

fandango:INFO: Generation 1: Increasing mutation rate from 0.200 to 0.220
fandango:INFO: Generation 1: Decreasing crossover rate from 0.800 to 0.760
fandango:INFO: Generation 1: Increasing MAX_REPETITION from 5 to 8
fandango:INFO: Generation 1 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 2 - Average Fitness: 0.02

fandango:INFO: Generation 2: Increasing mutation rate from 0.220 to 0.242
fandango:INFO: Generation 2: Decreasing crossover rate from 0.760 to 0.722
fandango:INFO: Generation 2: Increasing MAX_REPETITION from 8 to 12
fandango:INFO: Generation 2 stats -- Best fitness: 0.02, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 3 - Average Fitness: 0.02

fandango:INFO: Generation 3: Increasing mutation rate from 0.242 to 0.266
fandango:INFO: Generation 3: Decreasing crossover rate from 0.722 to 0.686
fandango:INFO: Generation 3: Increasing MAX_REPETITION from 12 to 18

fandango:INFO: Generation 3 stats -- Best fitness: 0.02, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 4 - Average Fitness: 0.02

fandango:INFO: Generation 4: Increasing mutation rate from 0.266 to 0.293
fandango:INFO: Generation 4: Decreasing crossover rate from 0.686 to 0.652
fandango:INFO: Generation 4: Increasing MAX_REPETITION from 18 to 27
fandango:INFO: Generation 4 stats -- Best fitness: 0.01, Avg fitness: 0.01, Avg diversity: 0.01, Population size: 100
fandango:INFO: Generation 5 - Average Fitness: 0.01

fandango:INFO: Generation 5: Increasing mutation rate from 0.293 to 0.322
fandango:INFO: Generation 5: Decreasing crossover rate from 0.652 to 0.619
fandango:INFO: Generation 5: Increasing MAX_REPETITION from 27 to 41
fandango:INFO: Generation 5 stats -- Best fitness: 0.01, Avg fitness: 0.01, Avg diversity: 0.01, Population size: 100
fandango:INFO: Generation 6 - Average Fitness: 0.01

fandango:INFO: Generation 6: Increasing mutation rate from 0.322 to 0.354
fandango:INFO: Generation 6: Decreasing crossover rate from 0.619 to 0.588
fandango:INFO: Generation 6: Increasing MAX_REPETITION from 41 to 62
fandango:INFO: Generation 6 stats -- Best fitness: 0.02, Avg fitness: 0.01, Avg diversity: 0.01, Population size: 100
fandango:INFO: Generation 7 - Average Fitness: 0.01

fandango:INFO: Generation 7: Increasing mutation rate from 0.354 to 0.390
fandango:INFO: Generation 7: Decreasing crossover rate from 0.588 to 0.559
fandango:INFO: Generation 7: Increasing MAX_REPETITION from 62 to 93
fandango:INFO: Generation 7 stats -- Best fitness: 0.02, Avg fitness: 0.01, Avg diversity: 0.01, Population size: 100
fandango:INFO: Generation 8 - Average Fitness: 0.01

fandango:INFO: Generation 8: Increasing mutation rate from 0.390 to 0.429
fandango:INFO: Generation 8: Decreasing crossover rate from 0.559 to 0.531
fandango:INFO: Generation 8: Increasing MAX_REPETITION from 93 to 140

fandango:INFO: Generation 8 stats -- Best fitness: 0.02, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 9 - Average Fitness: 0.02

fandango:INFO: Generation 9: Increasing mutation rate from 0.429 to 0.472
fandango:INFO: Generation 9: Decreasing crossover rate from 0.531 to 0.504
fandango:INFO: Generation 9: Increasing MAX_REPETITION from 140 to 210

fandango:INFO: Generation 9 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 10 - Average Fitness: 0.02

fandango:INFO: Generation 10: Increasing mutation rate from 0.472 to 0.519
fandango:INFO: Generation 10: Decreasing crossover rate from 0.504 to 0.479
fandango:INFO: Generation 10: Increasing MAX_REPETITION from 210 to 315

fandango:INFO: Generation 10 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 11 - Average Fitness: 0.02

fandango:INFO: Generation 11: Increasing mutation rate from 0.519 to 0.571
fandango:INFO: Generation 11: Decreasing crossover rate from 0.479 to 0.455
fandango:INFO: Generation 11: Increasing MAX_REPETITION from 315 to 473
fandango:INFO: Generation 11 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 12 - Average Fitness: 0.02

fandango:INFO: Generation 12: Increasing mutation rate from 0.571 to 0.628
fandango:INFO: Generation 12: Decreasing crossover rate from 0.455 to 0.432
fandango:INFO: Generation 12: Increasing MAX_REPETITION from 473 to 710
fandango:INFO: Generation 12 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 13 - Average Fitness: 0.02

fandango:INFO: Generation 13: Increasing mutation rate from 0.628 to 0.690
fandango:INFO: Generation 13: Decreasing crossover rate from 0.432 to 0.411
fandango:INFO: Generation 13: Increasing MAX_REPETITION from 710 to 1000
fandango:INFO: Generation 13 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 14 - Average Fitness: 0.02

fandango:INFO: Generation 14: Increasing mutation rate from 0.690 to 0.759
fandango:INFO: Generation 14: Decreasing crossover rate from 0.411 to 0.390
fandango:INFO: Generation 14 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 15 - Average Fitness: 0.02

fandango:INFO: Generation 15: Increasing mutation rate from 0.759 to 0.835
fandango:INFO: Generation 15: Decreasing crossover rate from 0.390 to 0.371

fandango:INFO: Generation 15 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 16 - Average Fitness: 0.02

fandango:INFO: Generation 16: Increasing mutation rate from 0.835 to 0.919
fandango:INFO: Generation 16: Decreasing crossover rate from 0.371 to 0.352
fandango:INFO: Generation 16 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 17 - Average Fitness: 0.02

fandango:INFO: Generation 17: Increasing mutation rate from 0.919 to 1.000
fandango:INFO: Generation 17: Decreasing crossover rate from 0.352 to 0.334
fandango:INFO: Generation 17 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 18 - Average Fitness: 0.02

fandango:INFO: Generation 18: Increasing mutation rate from 1.000 to 1.000
fandango:INFO: Generation 18: Decreasing crossover rate from 0.334 to 0.318
fandango:INFO: Generation 18 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 19 - Average Fitness: 0.02

fandango:INFO: Generation 19: Increasing mutation rate from 1.000 to 1.000
fandango:INFO: Generation 19: Decreasing crossover rate from 0.318 to 0.302

fandango:INFO: Generation 19 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 20 - Average Fitness: 0.02

fandango:INFO: Generation 20: Increasing mutation rate from 1.000 to 1.000
fandango:INFO: Generation 20: Decreasing crossover rate from 0.302 to 0.287

fandango:INFO: Generation 20 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 21 - Average Fitness: 0.02

fandango:INFO: Generation 21: Increasing mutation rate from 1.000 to 1.000
fandango:INFO: Generation 21: Decreasing crossover rate from 0.287 to 0.272

fandango:INFO: Generation 21 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 22 - Average Fitness: 0.02

fandango:INFO: Generation 22: Increasing mutation rate from 1.000 to 1.000
fandango:INFO: Generation 22: Decreasing crossover rate from 0.272 to 0.259
fandango:INFO: Generation 22 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 23 - Average Fitness: 0.02

fandango:INFO: Generation 23: Increasing mutation rate from 1.000 to 1.000
fandango:INFO: Generation 23: Decreasing crossover rate from 0.259 to 0.246
fandango:INFO: Generation 23 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 24 - Average Fitness: 0.02

fandango:INFO: Generation 24: Increasing mutation rate from 1.000 to 1.000
fandango:INFO: Generation 24: Decreasing crossover rate from 0.246 to 0.234
fandango:INFO: Generation 24 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 25 - Average Fitness: 0.02

fandango:INFO: Generation 25: Increasing mutation rate from 1.000 to 1.000
fandango:INFO: Generation 25: Decreasing crossover rate from 0.234 to 0.222
fandango:INFO: Generation 25 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 26 - Average Fitness: 0.02

fandango:INFO: Generation 26: Increasing mutation rate from 1.000 to 1.000
fandango:INFO: Generation 26: Decreasing crossover rate from 0.222 to 0.211

fandango:INFO: Generation 26 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 27 - Average Fitness: 0.02

fandango:INFO: Generation 27: Increasing mutation rate from 1.000 to 1.000
fandango:INFO: Generation 27: Decreasing crossover rate from 0.211 to 0.200
fandango:INFO: Generation 27 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 28 - Average Fitness: 0.02

fandango:INFO: Generation 28: Increasing mutation rate from 1.000 to 1.000
fandango:INFO: Generation 28: Decreasing crossover rate from 0.200 to 0.190
fandango:INFO: Generation 28 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 29 - Average Fitness: 0.02

fandango:INFO: Generation 29: Increasing mutation rate from 1.000 to 1.000
fandango:INFO: Generation 29: Decreasing crossover rate from 0.190 to 0.181
fandango:INFO: Generation 29 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 30 - Average Fitness: 0.02

fandango:INFO: Generation 30: Increasing mutation rate from 1.000 to 1.000
fandango:INFO: Generation 30: Decreasing crossover rate from 0.181 to 0.172
fandango:INFO: Generation 30 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 31 - Average Fitness: 0.02

fandango:INFO: Generation 31: Increasing mutation rate from 1.000 to 1.000
fandango:INFO: Generation 31: Decreasing crossover rate from 0.172 to 0.163

fandango:INFO: Generation 31 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 32 - Average Fitness: 0.02

fandango:INFO: Generation 32: Increasing mutation rate from 1.000 to 1.000
fandango:INFO: Generation 32: Decreasing crossover rate from 0.163 to 0.155
fandango:INFO: Generation 32 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 33 - Average Fitness: 0.02

fandango:INFO: Generation 33: Increasing mutation rate from 1.000 to 1.000
fandango:INFO: Generation 33: Decreasing crossover rate from 0.155 to 0.147
fandango:INFO: Generation 33 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 34 - Average Fitness: 0.02

fandango:INFO: Generation 34: Increasing mutation rate from 1.000 to 1.000
fandango:INFO: Generation 34: Decreasing crossover rate from 0.147 to 0.140
fandango:INFO: Generation 34 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 35 - Average Fitness: 0.02

fandango:INFO: Generation 35: Increasing mutation rate from 1.000 to 1.000
fandango:INFO: Generation 35: Decreasing crossover rate from 0.140 to 0.133

fandango:INFO: Generation 35 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 36 - Average Fitness: 0.02

fandango:INFO: Generation 36: Increasing mutation rate from 1.000 to 1.000
fandango:INFO: Generation 36: Decreasing crossover rate from 0.133 to 0.126

fandango:INFO: Generation 36 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 37 - Average Fitness: 0.02

fandango:INFO: Generation 37: Increasing mutation rate from 1.000 to 1.000
fandango:INFO: Generation 37: Decreasing crossover rate from 0.126 to 0.120

fandango:INFO: Generation 37 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 38 - Average Fitness: 0.02

fandango:INFO: Generation 38: Increasing mutation rate from 1.000 to 1.000
fandango:INFO: Generation 38: Decreasing crossover rate from 0.120 to 0.114

fandango:INFO: Generation 38 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 39 - Average Fitness: 0.02

fandango:INFO: Generation 39: Increasing mutation rate from 1.000 to 1.000
fandango:INFO: Generation 39: Decreasing crossover rate from 0.114 to 0.108

fandango:INFO: Generation 39 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 40 - Average Fitness: 0.02

fandango:INFO: Generation 40: Increasing mutation rate from 1.000 to 1.000
fandango:INFO: Generation 40: Decreasing crossover rate from 0.108 to 0.103
fandango:INFO: Generation 40 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 41 - Average Fitness: 0.02

fandango:INFO: Generation 41: Increasing mutation rate from 1.000 to 1.000
fandango:INFO: Generation 41: Decreasing crossover rate from 0.103 to 0.100
fandango:INFO: Generation 41 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 42 - Average Fitness: 0.02

fandango:INFO: Generation 42: Increasing mutation rate from 1.000 to 1.000
fandango:INFO: Generation 42: Decreasing crossover rate from 0.100 to 0.100
fandango:INFO: Generation 42 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 43 - Average Fitness: 0.02

fandango:INFO: Generation 43: Increasing mutation rate from 1.000 to 1.000
fandango:INFO: Generation 43: Decreasing crossover rate from 0.100 to 0.100
fandango:INFO: Generation 43 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 44 - Average Fitness: 0.02

fandango:INFO: Generation 44: Increasing mutation rate from 1.000 to 1.000
fandango:INFO: Generation 44: Decreasing crossover rate from 0.100 to 0.100
fandango:INFO: Generation 44 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 45 - Average Fitness: 0.02

fandango:INFO: Generation 45: Increasing mutation rate from 1.000 to 1.000
fandango:INFO: Generation 45: Decreasing crossover rate from 0.100 to 0.100

fandango:INFO: Generation 45 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 46 - Average Fitness: 0.02

fandango:INFO: Generation 46: Increasing mutation rate from 1.000 to 1.000
fandango:INFO: Generation 46: Decreasing crossover rate from 0.100 to 0.100
fandango:INFO: Generation 46 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 47 - Average Fitness: 0.02

fandango:INFO: Generation 47: Increasing mutation rate from 1.000 to 1.000
fandango:INFO: Generation 47: Decreasing crossover rate from 0.100 to 0.100
fandango:INFO: Generation 47 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 48 - Average Fitness: 0.02

fandango:INFO: Generation 48: Increasing mutation rate from 1.000 to 1.000
fandango:INFO: Generation 48: Decreasing crossover rate from 0.100 to 0.100
fandango:INFO: Generation 48 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 49 - Average Fitness: 0.02

fandango:INFO: Generation 49: Increasing mutation rate from 1.000 to 1.000
fandango:INFO: Generation 49: Decreasing crossover rate from 0.100 to 0.100
fandango:INFO: Generation 49 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Generation 50 - Average Fitness: 0.02

fandango:INFO: Generation 50: Increasing mutation rate from 1.000 to 1.000
fandango:INFO: Generation 50: Decreasing crossover rate from 0.100 to 0.100
fandango:INFO: Generation 50 stats -- Best fitness: 0.03, Avg fitness: 0.02, Avg diversity: 0.02, Population size: 100
fandango:INFO: Average fitness of population: 0.02
fandango:INFO: ---------- Done generating  for 50 generations----------
fandango:INFO: Time taken: 26.03 seconds
fandango:ERROR: Population did not converge to a perfect population
fandango:ERROR: Only found 0 perfect solutions, instead of the required 10

As you see, Fandango produces a population of zero. Of course, if the constraint is False, then there can be no success.

Tip

Fandango has a --best-effort option that allows you to still output the final population.

Shaping Inputs with Constraints

Contents

Shaping Inputs with Constraints#

The Limits of Grammars#

Specifying Constraints#

Constraints and DerivationTree types#

Constraints on the Command Line#

How Fandango Solves Constraints#

The Fandango Progress Bar#

Soft Constraints and Optimization#

When Constraints Cannot be Solved#

Constraints and `DerivationTree` types#