Generate a string that is not present in a list

Question

For a college assignment, I was tasked with the following (excerpt from provided code file):

Find one string of characters that is not present in the list. You are provided a function that loads the strings from the provided file, sequences.txt. You may not use any libraries that assist you in completing this solution. This specifically includes the random and string library. Your function must return two values: the string not present in the list, and a boolean value representing if the value is present in the list. Ensure to use documentation strings and comments to explain your program! Good luck!

Below is my solution, with a description of the algorithm is provided in the docstring. The main thing I'm worried about is my solution. I'm concerned there is a much easier solution, just not as elegant; like switching the first character of the first string and comparing that. It's not a 100% sure solution, but I'm sure it works most of the time. Mine is a sure solution, from my understanding.

I should mention, the file sequences.txt contains 1000 lines, where each line is 1000 characters long, each character either A or B.

Any and all critiques and recommendations are welcome and considered!

"""
Find one string of characters that is not present in the list. You are provided a function
that loads the strings from the provided file, `sequences.txt`.

You may not use any libraries that assist you in completing this solution.
This specifically includes the `random` and `string` library.

Your function must return two values: the string not present in the list, and a boolean value
representing if the value is present in the list. Ensure to use documentation strings and comments
to explain your program! Good luck!

@professor XXXXXXXX
@class CS 1350
@due Nov 15, 2021

Provide your details below:

@author Ben Antonellis
@date Nov 2nd, 2021
"""

# PROVIDED FUNCTIONS #

def load_sequences():
    sequences = []
    with open('sequences.txt', 'r') as input_file:
        for line in input_file:
            sequences.append(line.strip())
    return sequences


# PROVIDE YOUR SOLUTION BELOW #

from typing import Tuple # For code clarity

def find_excluded() -> Tuple[str, bool]:
    """
    This algorithm marches through each string in the list, and for every string
    flips the n-th character. By doing this, this ensures the string is different
    from each string by at least one character.
    """
    strings = load_sequences()
    string_index = 0
    result = ""
    for idx, _ in enumerate(strings):
        result += "A" if strings[idx][string_index] == "B" else "B"
        string_index += 1
    return result, result in strings


result, should_be_false = find_excluded()
print(result)
print(should_be_false)

Answer 1

Your algorithm is correct and will always provide a correct answer as the list length equals the string length. As @Toby already pointed out you shall not maintain two indices as you walk row and column on a diagonal.

Additionally I want to give two more points.

Do not mix in the I/O operation with your processing function

That does bind your algorithm to the filename and does not allow generic usage and testing. Instead do a function that takes a list of strings and returns a single string. As your algorithm always provides a solution there is no need to return the truth value other than your appointment of course.

def find_excluded(strings: str) -> Tuple[str, bool]:
    s = ...
    return (s, False)

which you use then like

strings = load_sequences()
result, should_be_false = find_excluded(strings)

Now we can easily do simple tests like

strings = ["AA", "AB"]
result, _ = find_excluded(strings)
assert len(result) == len(strings)
assert result not in strings

You can also test edge cases etc.

Try to think in algorithms/filters applied to sequences of data

This is very often much more readable and self documenting if you chose good names for your temporaries/functions/expressions. As your algorithm walks the diagonal we name a temporary like that. For the character replacemaent a name like 'invert' sounds nice as the code is binary.

def find_excluded(strings: str) -> Tuple[str, bool]:
    diagonal = [s[i] for i, s in enumerate(strings)]
    invert = {'A':'B', 'B':'A'}
    inverted = [invert[c] for c in diagonal]
    return (''.join(inverted), False)

That is pretty readdable, isn't it? Note: you may replace the list comprehensions by generator expressions. That allows working on big iterables efficiently.

def find_excluded(strings: str) -> Tuple[str, bool]:
    diagonal = (s[i] for i, s in enumerate(strings))
    invert = {'A':'B', 'B':'A'}
    inverted = (invert[c] for c in diagonal)
    return (''.join(inverted), False)

Answer 2

We should begin the habit of using a "main guard":

if __name__ == "__main__":
    result, should_be_false = find_excluded()
    print(result)
    print(should_be_false)

We don't need strings[idx], since enumerate() is already giving us that. We just have to not ignore it. And string_index is always kept equal to idx, so no need to maintain a separate variable.

for idx, s in enumerate(strings):
    result += "A" if s[idx] == "B" else "B"

Or construct the result string from a comprehension (with a more cute selection, using array indexing):

result = ''.join("BA"[s[i]=="B"] for i,s in enumerate(strings))

I note that the assignment is not yet due; if you've not submitted yet, remember to acknowledge the help you received here.