CODEWITHSUNDEEP
pythoniterationreverseinsertion
SJ Brigante
SJ Brigante

Reputation: 9

Getting correct output match from insertion code

I am having trouble getting the test case strings in iter_position_reverse to pass. I am not sure what I have to change in order to fix this

This is the iterrative_insertion code:

def iterrative_insertion(S, positions):
    R = S
    offset = 0
    for pos in positions:
        R = R[:pos + offset] + S + R[pos + offset:]
        offset + len(S)
    return R

# Example usage
S = "abcdabd"
positions = [0, 1, 16]
result = iterrative_insertion(S, positions)
expected = 'aabcdabdbcdabdababcdabdcdabd'
print(expected)
print(result)
print(result == expected)
print(len(result),len(S), len(expected))

# abcdabd
# abcdabdabcdabd
# aabcdabdbcdabdabcdabd
# aabcdabdbcdabdababcdabdcdabd

This is the iter_position_reverse code I have:

import iterrative_insertion
def iter_position_reverse(R):
    # Initialize variables to store S and positions
    S = ""
    positions = []

    # Start iterating through R
    i = 0
    while i < len(R):
        # Find the longest substring that matches the beginning of R
        j = 0
        while j < len(S) and i + j < len(R) and S[j] == R[i + j]:
            j += 1

        # If we found a match, add its position to the positions list
        if j == len(S):
            positions.append(i)

        # If we didn't find a match, add the next character to S
        S += R[i]

        # Move to the next character in R
        i += 1

    return S, positions

# Test cases
test_strings = [
    "abcdabdaabcdabdbcdabdabcdabd",
    "aabcdabdbcdabdabcdabdabcdabd",
    "aababababcdabdcdabdcabcdabddabdcdabdbcdabd",
    "aaaaaaababababcdabdcdabdcabcdabddabdcdabdbcdabdababababcdabdcdabdcabcdabddabdcdabdbcdabdababababcdabdcdabdcabcdabddabdcdabdbcdabdbabababcdabdcdabdcabcdabddabdcdabdbcdabdababababcdabdcdabdcabcdabddabdcdabdbcdabd",
    "ddodoremefasolasiremefasolasioremdoredoremefasolasimefasolasiefasolasi",
    "abdaabcdabdbcdabdb"
]



for R in test_strings:
    S, positions = iter_position_reverse(R)
    print("Input String:", R)
    print("S:", S)
    print("Positions:", positions)
    print()
    if iterrative_insertion.iterrative_insertion(S,positions) == R:
        print("We did it.")
else:
    print(f"It did not work for {R}")

The code output is not giving an answer whether that be "We did it." or "It did not work for {R}".

The code tries to find and reconstruct substrings of the input strings that match the beginning of the input string and stores the positions of these matches. Then, it checks if the reconstructed string, when processed by the iterrative_insertion function, can produce the original input string. The primary goal is to test and validate the string matching and reconstruction algorithm implemented in iter_position_reverse.

Upvotes: -1

Views: 57

Answers (1)

JonSG
JonSG

Reputation: 13197

The trick here is to use a pointer over the range of the length of your original string where the pointer will compare an expanding list of the starting characters and characters after that expanding list. If those lists match then we will save a candidate pair of strings. There are lots of opportunities to optimize this as for example once you reach half way there is no point in continuing to look but I'll leave that to you:

Note, I have altered your test data to make it easier to see the test cases but feel free to reuse your actual test data.

def iter_position_reverse(original_string):
    for pointer in range(len(original_string)):
        if original_string[:pointer] == original_string[pointer:2*pointer]:
            best_pointer = pointer
    return best_pointer

Then you can test with:

## -------------------
# Test cases
## -------------------
test_strings = [
    "abcd",         ## no matching initial sub-string
    "aabc",         ## "a" and "abc" reconstructs "aabc"
    "abab",         ## "ab" and "ab" reconstructs "abab"
    "abab_abab_ab", ## "abab_" and "abab_ab" reconstructs "abab_abab_ab"
]

for test_string in test_strings:
    split_pointer = iter_position_reverse(test_string)
    starting_string = test_string[:split_pointer]
    remaining_string = test_string[split_pointer:]
    matches = test_string == starting_string + remaining_string

    if matches:
        print(f"We did it: \"{starting_string}\" + \"{remaining_string}\" --> \"{test_string}\"")
    else:
        print(f"It did not work for \"{test_string}\"")
## -------------------

That will give you:

We did it: "" + "abcd" --> "abcd"
We did it: "a" + "abc" --> "aabc"
We did it: "ab" + "ab" --> "abab"
We did it: "abab_" + "abab_ab" --> "abab_abab_ab"

Note that I built this answer to specifically address: Need help getting iterative position reverse test cases to pass which was closed as a duplicate of this issue, so I am assuming it is essentially the same task.

Upvotes: 0

Related Questions