Skip to content

Instantly share code, notes, and snippets.

What would you like to do?
An implementation of String Search using the SDS Library.
import sds
import random
import functools
def microtest(hyp, offset, search_space, model):
""" Performs a partial evaluation of a hypothesis.
- hyp: A location in the search space.
- offset: The part of the hypothesis to be evaluated.
- search_space: The full search space.
- model: The target to be found in the search space.
Returns True if search_space[hyp + offset] == model[offset]
search_space_index = hyp + offset
return (
search_space_index < len(search_space) # avoid out of bounds index errors
and search_space[search_space_index] == model[offset]
def make_microtests(search_space, model):
""" Generate a list of functions representing all the partial evaluations
for the given search space and model.
search_space: The large search space string.
model: The small target string.
Returns a list of functions: (hyp) -> Boolean
return [
microtest, offset=offset, search_space=search_space, model=model
for offset in range(len(model))
def main():
agent_count = 50
rng = random.Random()
max_iterations = 100
model = "hello"
search_space = "xxxxxhexlodxxxsakllajadsweklhheaekfjllkahelehlehlehlexxx"
swarm = sds.Swarm(agent_count=agent_count)
microtests = make_microtests(search_space, model)
hypotheses = range(len(search_space))
# DH is the mode of hypothesis selection.
# DH_uniform is uniformly random hypothesis selection.
DH = sds.DH_uniform(hypotheses=hypotheses, rng=rng)
# D is the mode of diffusion.
# D_passive is passive diffusion.
D = sds.D_passive(DH=DH, swarm=swarm, rng=rng)
# TM is the mode of microtest selection.
# TM_uniform is uniformly random microtest selection.
TM = sds.TM_uniform(microtests, rng=rng)
# T is the mode of testing.
# T_boolean is boolean testing.
T = sds.T_boolean(TM=TM)
# I is the mode of iterations.
# I_sync is synchronous iteration.
I = sds.I_sync(D=D, T=T, swarm=swarm)
# H is the mode of halting.
# H_fixed is fixed number of iterations halting.
H = sds.H_fixed(iterations=max_iterations)
# SDS executes the variant defined as a combination of I and H
sds.SDS(I=I, H=H)
# The state of the swarm is now updated
print("All clusters", swarm.clusters.most_common())
print("Largest cluster", swarm.largest_cluster)
if __name__ == "__main__":
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment