Dijkstra, /Notes on Structured Programming/, pp 63-66 (On Grouping and Sequencing)

dijkstra-p63.py

#!/usr/bin/env python2
"""
Dijkstra, /Notes on Structured Programming/, pp 63-66

The problem is to construct a program generating non-empty sequnces of 0s, 1s,
and 2s, without non-empty, element-wise equal, adjoining subsequences,
generating those lines in alphabetical order until a sequence of length 100
(i.e., of 100 digits) has been generated.

The start of the list of sequences to be generated is:

    0
    01
    010
    0102
    01020
    010201
    0102010
    0102012
    ...

"""

def valid(sequence):
    l = len(sequence)
    if l < 2:
        return True

    i = 1
    while i < (l/2 + 1):
        if sequence[-i*2:-i] == sequence[-i:]:
            return False
        i += 1

    return True

def increment(sequence):
    while sequence[-1] == "2":
        sequence = sequence[:-1]

    r = sequence[:-1] + str(int(sequence[-1]) + 1)
    return r

def nextSolution(sequence):
    sequence += "0"

    while not valid(sequence):
        sequence = increment(sequence)

    return sequence

def solver(length=100):
    sequence = ""

    while True:
        sequence = nextSolution(sequence)
        if len(sequence) <= length:
            yield sequence
        else:
            raise StopIteration

def test():
    """
    Test sequences from Dijkstra, p 64.

    Violate PEP8 for readability
    """

    # test validity checker
    assert(    valid("0"))
    assert(not valid("00"))
    assert(    valid("01"))
    assert(    valid("010"))
    assert(not valid("0100"))
    assert(not valid("0101"))
    assert(    valid("0102"))
    assert(    valid("01020"))
    assert(not valid("010200"))
    assert(    valid("010201"))
    assert(    valid("0102010"))
    assert(not valid("01020100"))
    assert(not valid("01020101"))
    assert(not valid("01020102"))
    assert(not valid("0102011"))
    assert(    valid("0102012"))

    # test sequence generator
    expected = [
        "0",
        "01",
        "010",
        "0102",
        "01020",
        "010201",
        "0102010",
        "0102012"]

    s = solver(7)
    for sequence in expected:
        assert(sequence == s.next())

    print "Tests pass"

if __name__ == "__main__":
    test()

    solutions = list(solver(100))
    assert(len(solutions[-1]) == 100)

    print 'Sequences up to 100 digits in length:'
    print '\n'.join(solutions)