Examples of Specifications and Synthesized Programs

Even parity checking
Description
Determine if a list of boolean values has an even number of true-values.
Author
Roland Olsson (inspired by several papers at GP-98 discussing this problem).
Complexity
36 bits
Creation time
12 seconds on a 200 MHz PentiumPro
The best individual
The genealogical chain leading to the best individual
The specification file
The log file

Reversing a list
Description
Reverse a list of integers.
Author
Roland Olsson
Complexity
47 bits
Creation time
570 seconds on a 200 MHz PentiumPro
The best individual
The genealogical chain leading to the best individual
The specification file
The log file

Duplicate checking
Description
Determine if a list is a set i.e., does not contain duplicates.
Author
Roland Olsson
Complexity
65 bits
Creation time
116 seconds on a 200 MHz PentiumPro
The best individual
The genealogical chain leading to the best individual
The specification file
The log file

List delete min
Description
Delete the minimum element from a list.
Author
Roland Olsson
Complexity
73 bits
Creation time
3905 seconds on a 200 MHz PentiumPro
The best individual
The genealogical chain leading to the best individual
The specification file
The log file

Cartesian product
Description
Given two lists Xs and Ys, compute a list of all pairs (X,Y) such that X is in Xs and Y is in Ys.
Author
Roland Olsson
Complexity
78 bits
Creation time
978 seconds on a 200 MHz PentiumPro
The best individual
The genealogical chain leading to the best individual
The specification file
The log file

Intersecting two lists
Description
Given two lists Xs and Ys, find all elements that occur in both Xs and Ys.
Author
Roland Olsson
Complexity
88 bits
Creation time
45636 seconds on a 200 MHz PentiumPro
The best individual
The genealogical chain leading to the best individual
The specification file
The log file

String comparison
Description
This problem was inspired by the C library function strcmp. Assume that the input is two strings X and Y. If X is less than Y, return less. If X is equal to Y, return equal. If X is greater than Y, return greater.
Author
Roland Olsson
Complexity
93 bits
Creation time
49762 seconds on a 200 MHz PentiumPro
The best individual
The genealogical chain leading to the best individual
The specification file
The log file

Sorting a list
Description
Sort a list of integers in ascending order.
Author
Roland Olsson
Complexity
96 bits
Creation time
1529 seconds on a 200 MHz PentiumPro
The best individual
The genealogical chain leading to the best individual
The specification file
The log file

Permutation checking
Description
Given two lists Xs and Ys, determine if Xs is a permutation of Ys.
Author
Roland Olsson
Complexity
100 bits
Creation time
58849 seconds on a 200 MHz PentiumPro
The best individual
The genealogical chain leading to the best individual
The specification file
The log file

Locating a substring
Description
This problem was inspired by the C library function strstr. Assume that the input is two strings X and Y. If Y does not occur in X, return none. If Y occurs in X, return the longest suffix of X that starts with Y.
Author
Roland Olsson
Complexity
103 bits
Creation time
499352 seconds on a 200 MHz PentiumPro
The best individual
The genealogical chain leading to the best individual
The specification file
The log file

Binary search tree insertion
Description
Insert an element into a binary search tree of integers.
Author
Roland Olsson
Complexity
115 bits
Creation time
12271 seconds on a 200 MHz PentiumPro
The best individual
The genealogical chain leading to the best individual
The specification file
The log file

Multiplying unsigned binary numbers
Description
Multiply two natural numbers of arbitrary length and in binary form. Note that the specification contains an auxiliary adding function which was synthesized by the ADATE system before the specification was written.
Author
Roland Olsson
Complexity
117 bits
Creation time
44726 seconds on a 200 MHz PentiumPro
The best individual
The genealogical chain leading to the best individual
The specification file
The log file

Simplifying a polynomial
Description
Given a polynomial represented as a list of coefficient-exponent pairs, return an equivalent polynomial without duplicate exponents.
Author
Roland Olsson
Complexity
126 bits
Creation time
74589 seconds on a 200 MHz PentiumPro
The best individual
The genealogical chain leading to the best individual
The specification file
The log file

Transposing a matrix
Description
Transpose a matrix represented as a list of lists such that each sublist is a row in the matrix.
Author
Roland Olsson
Complexity
155 bits
Creation time
41789 seconds on a 200 MHz PentiumPro
The best individual
The genealogical chain leading to the best individual
The specification file
The log file

Permuting a list
Description
Compute a list of lists containing all permutations of a given list. Note that the output evaluation function is defined using the synthesized program for duplicate checking and the synthesized program for permutation checking.
Author
Roland Olsson
Complexity
163 bits
Creation time
403808 seconds on a 200 MHz PentiumPro
The best individual
The genealogical chain leading to the best individual
The specification file
The log file

Binary search tree deletion
Description
The input is an integer X and a binary search tree Xs. The output is a binary search tree with the same elements as Xs but with one occurrence of X removed if there is any X in Xs.
Author
Roland Olsson
Complexity
169 bits
Creation time
341670 seconds on a 200 MHz PentiumPro
The best individual
The genealogical chain leading to the best individual
The specification file
The log file

Path finding
Description
Assume that a directed graph is represented as a list of node pairs such that each pair represents an edge in the graph. The input ia a start node, a goal node and the graph. The output is none if there is no path from the start node to the goal node. The output is some Xs if there is a path Xs from the start node to the goal node. This path is represented as a list of nodes.
Author
Roland Olsson. The problem was suggested by Ulf Nilsson.
Complexity
192 bits
Creation time
815421 seconds on a 200 MHz PentiumPro
The best individual
The genealogical chain leading to the best individual
The specification file
The log file

Adding unsigned binary numbers
Description
Add two natural numbers of arbitrary length and in binary form.
Author
Roland Olsson
Complexity
194 bits
Creation time
740439 seconds on a 200 MHz PentiumPro
The best individual
The genealogical chain leading to the best individual
The specification file
The log file

Intersecting two rectangles
Description
This problem is the same as finding the overlap between two windows in a GUI. Assume that the input is two parallel rectangles A and B. If A and B do not overlap, return none. If A overlaps B, return the overlap.
Author
Roland Olsson
Complexity
239 bits
Creation time
220926 seconds on a 200 MHz PentiumPro
The best individual
The genealogical chain leading to the best individual
The specification file
The log file