A simple Python3 implementation of SDS String Search.

simple_sds.py

import random
from collections import Counter

search_space = "xxxhelxxxelloxxxxxxhelloxxxxx"

model = "hello"

tests = [
    lambda hyp: search_space[hyp] == model[0],
    lambda hyp: search_space[hyp + 1] == model[1],
    lambda hyp: search_space[hyp + 2] == model[2],
    lambda hyp: search_space[hyp + 3] == model[3],
    lambda hyp: search_space[hyp + 4] == model[4],
]

class Agent:
    
    def __init__(self, hyp, active):
        
        self.hyp = hyp
        
        self.active = active


def diffusion_phase(swarm):

    for agent in swarm:

        if not agent.active:

            polled_agent = random.choice(swarm)

            if polled_agent.active:

                agent.hyp = polled_agent.hyp

            else:

                agent.hyp = random.randint(0, len(search_space) - len(model))


def test_phase(swarm):

    for agent in swarm:

        test_function = random.choice(tests)

        agent.active = test_function(agent.hyp)


def run(swarm, iterations):

    for iteration in range(iterations):

        diffusion_phase(swarm)

        test_phase(swarm)


def count_clusters(swarm):

    return Counter([agent.hyp for agent in swarm if agent.active])


def main():

    agent_count = 100

    swarm = [Agent(hyp=None, active=False) for x in range(agent_count)]

    run(swarm, iterations=1000)

    clusters = count_clusters(swarm)

    out_template = (
        "There are {count} active agents ({activity:.0f}% of swarm) at position {hyp}."
    )

    for hyp, count in clusters.most_common():

        print(
            out_template.format(
                count=count, activity=(count * 100) / agent_count, hyp=hyp
            )
        )


if __name__ == "__main__":

    main()