Creating a program to solve the string solution problem

this ipython notebook assumes some familiarity with python, please check the intro guide or speak with chris haack if you need more help getting started. All code in this project will be using python3.

In [1]:
# helpers.py should be in the zip package which you can download from the website
from helpers import *

A Simple Solver

step1 figure out which seed generated the string

say we have a binary string as given in problem 1. We need to figure out which of the possible strings could be the original seed.

In the file helpers I have inserted a function which you can use to do that. find_start_string() note you can assume this function is corect. the function takes O(N) time. (the function works by assigning the first character to a variable a. Then it checks to see if any of the internal characters are of opposite parity and assigns that to a variable b. then it also collects data on the last char to see if it is the same as the first one. if the last char is the same as the first one the start string will be aba, otherwise it is ab.)

In [2]:
s = '010101'
find_start_string(s)
Out[2]:
'01'

step2 generate possible duplications.

the next part of this program will need to generate all of the possible duplications.

step2.a write a function that duplicate a string.

this function is also contained in the helpers folder. ''' this function duplicates a string s, with duplication length duplen at pos = pos for example s = 000111 duplen =2 pos = 2 gives 00010111

In [3]:
s = '000111'
s = duplicate(2, 2, s)
print(s)
00010111

Step 2.b write a function that generates all the possible duplications from a given string

note we use max length to not generate strings that are longer than the string we are trying to get to.

In [7]:
def gen_paths(s, maxLen):
    '''generates all the possible paths from a string that are below length maxlen'''
    paths = []
    for i in range(len(s)):
        pos = i
        for j in range(1, len(s) + 1):
            dupLen = j
            if dupLen + pos <= len(s):
                path = duplicate(pos, dupLen, s)
                if len(path) < maxLen + 1:
                    paths.append(path)
    return paths

print(gen_paths('101', 7))
['1101', '10101', '101101', '1001', '10101', '1011']

step 3 find the path

The function solve does a couple of things

First it calls findStartString on s so that it knows where to start from. It initializes a list of current_paths that it has seen called curr_paths. After that it initializes two variables cnt, which is how long the path is and l which is the len of the string.

The next thing it does is loop until it has found the string in the current paths

if the string s is in the current paths it prints the amount of steps and breaks out of the loop. if it is not then it goes through the list of current paths and then adds all of the paths to a list of next_paths. Once it has finished that it sets the current paths to the list of next_paths and increments the counter by 1.

a simple run of the algorithm to solve s = 1011011

start with seed 101

initalize list curr_paths to [101]

set cnt to 0

check if s (1011011) in curr_paths ([101]) (false)

for each path in curr_path generate the possible paths and add to next_paths:

generate paths for 101 -> next_paths = [1101, 1001, 1011, 10101, 10101, 101101]

set curr_paths = to next_paths

increment cnt to 1.

set next_paths to [],

check to see if s in curr_paths([1101, 1001, 1011, 10101, 10101, 101101])

for each path in curr_path generate the possible paths and add to next_paths:

generate paths for 1101, 1001, 1011, 10101, 10101, 101101 -> next_paths = [very large list with 1011011 in it]

set curr_paths = to next_paths

increment cnt to 2.

set next_paths to []

check to see if s in curr_paths (true)

print cnt (cnt = 2).

In [8]:
def solve(s):
    start_string = find_start_string(s)
    curr_paths = [start_string]
    cnt = 0
    l = len(s)
    while(True):
        next_paths = []
        if s in curr_paths:
            print(cnt)
            break
        for path in curr_paths:
            next_paths += gen_paths(path, l)
        curr_paths = next_paths
        cnt += 1
solve('1011011')
2
In [ ]: