033: Word Design for DNA Computing on Surfaces

language Essence 1.3
$ prob033.essence: Word Design for DNA Computing on Surfaces
$ Problem details available at http://www.csplib.org/Problems/prob033/

letting Base be new type enum {A,C,G,T},
        Index be domain int(1..8)

$ Notice: The problem specification states that we are trying to find a set of words.
$ We take this literally, and do not allow repeated words.

find words : set of function (total) Index --> Base

maximising |words|

such that

    $ Each word in S has 4 symbols from (C, G)
    forAll w in words . |preImage(w,C)| + |preImage(w,G)| = 4,

    $ Each pair of words in S differ in at least 4 positions
    forAll {w1,w2} subsetEq words .
        (sum i : Index . toInt(w1(i) != w2(i))) >= 4,

    forAll {w1,w2} subsetEq words .
        (sum i : Index .
            $
            $ To decide whether they are identical at index i, we need to inspect the values of w1(9-i) and w2(i).
            $ This is because w1 is reversed, and w2 is the Watson-Crick complement.
            $
            $ Watson-Crick complementing is implemented by listing a set of allowed pairs.
            $ If the pair is a member of the set of allowed pairs, they are identical.
            $
            $ We require that they are not identical (hence the negation) in at least 4 positions.
            $
            toInt(! ((w1(9-i), w2(i)) in {(A,T), (C,G), (G,C), (T,A)}) )
        ) >= 4