<reponame>mawillcockson/coding_challenges<filename>leetcode/problems/003_longest_substring_without_repeating_characters/test_solution.py
"""
tests the solution in the named file
"""
import sys
from argparse import ArgumentParser
from importlib import import_module
from itertools import chain, starmap
from pathlib import Path
from pprint import pformat
from random import choices, randint, sample
from string import ascii_letters, digits, punctuation
from typing import Callable, List, NamedTuple, Optional


class Parameters(NamedTuple):
    "parameters passed as star-args to the function under test"
    s: str


class Answer(NamedTuple):
    """
    the temporary output of the function under test to make it easier to assess
    answers
    """

    substring: str
    length: int


class TestCase(NamedTuple):
    "a test case"
    case: Parameters
    correct_answer: Answer


Function = Callable[[str], Answer]

TEST_CASES = [
    ("abcabcbb", "abc"),
    ("bbbbb", "b"),
    ("pwwkew", "wke"),
    ("", ""),
    ("abcdefghijklmnop", "abcdefghijklmnop"),
    ("12134", "2134"),  # force backtracking
]
LONGEST_STRING = 50_000
ALL_CHARACTERS = list(set(ascii_letters + digits + punctuation))


def make_test_case(
    s: Optional[str] = None, correct_answer: Optional[str] = None
) -> TestCase:
    # pylint: disable=invalid-name
    """
    generate a random test case, or make one from inputs
    """
    # ^ is bitwise XOR, and works with booleans
    if (s is None) ^ (correct_answer is None):
        raise ValueError(
            "either both 's' and 'correct_answer' need to be given, or neither"
        )

    if s is not None and correct_answer is not None:
        return TestCase(
            Parameters(s=s),
            correct_answer=Answer(substring=correct_answer, length=len(correct_answer)),
        )

    if randint(0, 1):
        return short_test_case()
    return long_test_case()


def long_test_case(max_length: int = LONGEST_STRING) -> TestCase:
    """
    same algorithm as short_test_case, except this relies on the substring
    being more unique than long:

    if the whole string is generated by placing proper prefixes (i.e. a proper
    prefix will never be the whole substring) of the chosen substring in front
    of the substring, and proper suffixes after, no substring can be longer,
    and the substrings can't form a longer substring through combining with
    adjacent substrings, I think...

    essentially, given the substring 123, the longest prefix can be 12, and the
    longest suffix can be 23, so the resulting string will look like:
    ...121212121232323232323...

    no unique substring will be longer than 123

    maximum length is unlimited
    """
    # select a random sample of characters
    substring_length = randint(0, len(ALL_CHARACTERS))
    if not substring_length:
        return TestCase(
            case=Parameters(s=""), correct_answer=Answer(substring="", length=0)
        )

    substring = sample(ALL_CHARACTERS, k=substring_length)

    # how many more characters should we add?
    remaining_length = randint(0, max_length - substring_length)

    # select prefix and suffix length
    prefix_end_index = randint(0, substring_length - 1)
    prefix = substring[: prefix_end_index - 1]  # list[:end] doesn't include end
    suffix_start_index = randint(1, substring_length)
    suffix = substring[suffix_start_index:]

    # choose how many prefixes and suffixes there will be by choosing how many
    # prefixes, then filling the rest out with suffixes
    if prefix:
        possible_number_of_prefixes = remaining_length // len(prefix)
        if possible_number_of_prefixes:
            number_of_prefixes = randint(0, possible_number_of_prefixes)
            remaining_length -= number_of_prefixes * len(prefix)
            whole_string: "List[str]" = prefix * number_of_prefixes
        else:
            whole_string = []
    else:
        whole_string = []

    whole_string.extend(substring)

    if suffix:
        possible_number_of_suffixes = remaining_length // len(suffix)
        if possible_number_of_suffixes:
            number_of_suffixes = randint(0, possible_number_of_suffixes)
            whole_string.extend(suffix * number_of_suffixes)

    case = Parameters(s="".join(whole_string))
    correct_answer = Answer(substring="".join(substring), length=substring_length)
    return TestCase(case=case, correct_answer=correct_answer)


def short_test_case() -> TestCase:
    "maximum possible total string length is 280"
    # The substring is guaranteed to be the longest unique substring if it's
    # the longest substring within a string of characters all pulled from that
    # substring

    # draw a random sample of unique characters from a pool
    substring_length = randint(0, len(ALL_CHARACTERS))
    if not substring_length:
        return TestCase(
            case=Parameters(s=""), correct_answer=Answer(substring="", length=0)
        )

    substring = sample(ALL_CHARACTERS, k=substring_length)

    # this substring will be placed within a longer string, and in order for it
    # to be the longest, it must be longer than both the substring in front of
    # it, and the substring after it
    pre_substring_length = randint(0, substring_length - 1)
    post_substring_length = randint(0, substring_length - 1)

    # those substrings can take characters from anywhere, since even if they're
    # unique, they won't be the longest
    pre_substring = choices(ALL_CHARACTERS, k=pre_substring_length)
    post_substring = choices(ALL_CHARACTERS, k=post_substring_length)

    # then, add characters from that substring until
    whole_string: List[str] = []
    whole_string.extend(pre_substring)
    whole_string.extend(substring)
    whole_string.extend(post_substring)

    case = Parameters(s="".join(whole_string))
    correct_answer = Answer(substring="".join(substring), length=substring_length)
    return TestCase(case=case, correct_answer=correct_answer)


def test(function: Function) -> None:
    "performs tests on the function to simulate the LeetCode submission"
    for case_index, test_case in enumerate(
        chain(
            starmap(make_test_case, TEST_CASES),
            # (short_test_case() for _ in range(100)),
            (long_test_case() for _ in range(10_000)),
        )
    ):
        case_number = (
            str(case_index + 1) if case_index + 1 <= len(TEST_CASES) else "random"
        )
        if case_number != "random":
            print(f"test #{case_number}")

        case = test_case.case
        correct_answer = test_case.correct_answer

        answer = function(*case)
        if not answer or answer != correct_answer:
            print(f"failure for case #{case_number}:")
            print(f"case:\n{pformat(case)}")
            print(f"correct answer:\n{correct_answer}")
            print(f"answer:\n{answer}")
            # breakpoint()  # pylint: disable=forgotten-debug-statement
            sys.exit(1)

    print("passed")


if __name__ == "__main__":
    parser = ArgumentParser()
    parser.add_argument("file", help="filename of python file to test")
    args = parser.parse_args()
    path = Path(args.file)  # type: ignore
    if not path.is_file():
        print(f"{path} is not a file")
        sys.exit(1)

    sys.path.append(str(path.parent))
    module = import_module(path.stem)
    test(module.Solution().lengthOfLongestSubstring)  # type: ignore

"""
tests the solution in the named file
"""
import sys
from argparse import ArgumentParser
from importlib import import_module
from itertools import chain, starmap
from pathlib import Path
from pprint import pformat
from random import choices, randint, sample
from string import ascii_letters, digits, punctuation
from typing import Callable, List, NamedTuple, Optional


class Parameters(NamedTuple):
    "parameters passed as star-args to the function under test"
    s: str


class Answer(NamedTuple):
    """
    the temporary output of the function under test to make it easier to assess
    answers
    """

    substring: str
    length: int


class TestCase(NamedTuple):
    "a test case"
    case: Parameters
    correct_answer: Answer


Function = Callable[[str], Answer]

TEST_CASES = [
    ("abcabcbb", "abc"),
    ("bbbbb", "b"),
    ("pwwkew", "wke"),
    ("", ""),
    ("abcdefghijklmnop", "abcdefghijklmnop"),
    ("12134", "2134"),  # force backtracking
]
LONGEST_STRING = 50_000
ALL_CHARACTERS = list(set(ascii_letters + digits + punctuation))


def make_test_case(
    s: Optional[str] = None, correct_answer: Optional[str] = None
) -> TestCase:
    # pylint: disable=invalid-name
    """
    generate a random test case, or make one from inputs
    """
    # ^ is bitwise XOR, and works with booleans
    if (s is None) ^ (correct_answer is None):
        raise ValueError(
            "either both 's' and 'correct_answer' need to be given, or neither"
        )

    if s is not None and correct_answer is not None:
        return TestCase(
            Parameters(s=s),
            correct_answer=Answer(substring=correct_answer, length=len(correct_answer)),
        )

    if randint(0, 1):
        return short_test_case()
    return long_test_case()


def long_test_case(max_length: int = LONGEST_STRING) -> TestCase:
    """
    same algorithm as short_test_case, except this relies on the substring
    being more unique than long:

    if the whole string is generated by placing proper prefixes (i.e. a proper
    prefix will never be the whole substring) of the chosen substring in front
    of the substring, and proper suffixes after, no substring can be longer,
    and the substrings can't form a longer substring through combining with
    adjacent substrings, I think...

    essentially, given the substring 123, the longest prefix can be 12, and the
    longest suffix can be 23, so the resulting string will look like:
    ...121212121232323232323...

    no unique substring will be longer than 123

    maximum length is unlimited
    """
    # select a random sample of characters
    substring_length = randint(0, len(ALL_CHARACTERS))
    if not substring_length:
        return TestCase(
            case=Parameters(s=""), correct_answer=Answer(substring="", length=0)
        )

    substring = sample(ALL_CHARACTERS, k=substring_length)

    # how many more characters should we add?
    remaining_length = randint(0, max_length - substring_length)

    # select prefix and suffix length
    prefix_end_index = randint(0, substring_length - 1)
    prefix = substring[: prefix_end_index - 1]  # list[:end] doesn't include end
    suffix_start_index = randint(1, substring_length)
    suffix = substring[suffix_start_index:]

    # choose how many prefixes and suffixes there will be by choosing how many
    # prefixes, then filling the rest out with suffixes
    if prefix:
        possible_number_of_prefixes = remaining_length // len(prefix)
        if possible_number_of_prefixes:
            number_of_prefixes = randint(0, possible_number_of_prefixes)
            remaining_length -= number_of_prefixes * len(prefix)
            whole_string: "List[str]" = prefix * number_of_prefixes
        else:
            whole_string = []
    else:
        whole_string = []

    whole_string.extend(substring)

    if suffix:
        possible_number_of_suffixes = remaining_length // len(suffix)
        if possible_number_of_suffixes:
            number_of_suffixes = randint(0, possible_number_of_suffixes)
            whole_string.extend(suffix * number_of_suffixes)

    case = Parameters(s="".join(whole_string))
    correct_answer = Answer(substring="".join(substring), length=substring_length)
    return TestCase(case=case, correct_answer=correct_answer)


def short_test_case() -> TestCase:
    "maximum possible total string length is 280"
    # The substring is guaranteed to be the longest unique substring if it's
    # the longest substring within a string of characters all pulled from that
    # substring

    # draw a random sample of unique characters from a pool
    substring_length = randint(0, len(ALL_CHARACTERS))
    if not substring_length:
        return TestCase(
            case=Parameters(s=""), correct_answer=Answer(substring="", length=0)
        )

    substring = sample(ALL_CHARACTERS, k=substring_length)

    # this substring will be placed within a longer string, and in order for it
    # to be the longest, it must be longer than both the substring in front of
    # it, and the substring after it
    pre_substring_length = randint(0, substring_length - 1)
    post_substring_length = randint(0, substring_length - 1)

    # those substrings can take characters from anywhere, since even if they're
    # unique, they won't be the longest
    pre_substring = choices(ALL_CHARACTERS, k=pre_substring_length)
    post_substring = choices(ALL_CHARACTERS, k=post_substring_length)

    # then, add characters from that substring until
    whole_string: List[str] = []
    whole_string.extend(pre_substring)
    whole_string.extend(substring)
    whole_string.extend(post_substring)

    case = Parameters(s="".join(whole_string))
    correct_answer = Answer(substring="".join(substring), length=substring_length)
    return TestCase(case=case, correct_answer=correct_answer)


def test(function: Function) -> None:
    "performs tests on the function to simulate the LeetCode submission"
    for case_index, test_case in enumerate(
        chain(
            starmap(make_test_case, TEST_CASES),
            # (short_test_case() for _ in range(100)),
            (long_test_case() for _ in range(10_000)),
        )
    ):
        case_number = (
            str(case_index + 1) if case_index + 1 <= len(TEST_CASES) else "random"
        )
        if case_number != "random":
            print(f"test #{case_number}")

        case = test_case.case
        correct_answer = test_case.correct_answer

        answer = function(*case)
        if not answer or answer != correct_answer:
            print(f"failure for case #{case_number}:")
            print(f"case:\n{pformat(case)}")
            print(f"correct answer:\n{correct_answer}")
            print(f"answer:\n{answer}")
            # breakpoint()  # pylint: disable=forgotten-debug-statement
            sys.exit(1)

    print("passed")


if __name__ == "__main__":
    parser = ArgumentParser()
    parser.add_argument("file", help="filename of python file to test")
    args = parser.parse_args()
    path = Path(args.file)  # type: ignore
    if not path.is_file():
        print(f"{path} is not a file")
        sys.exit(1)

    sys.path.append(str(path.parent))
    module = import_module(path.stem)
    test(module.Solution().lengthOfLongestSubstring)  # type: ignore
tests the solution in the named file the temporary output of the function under test to make it easier to assess     answers # force backtracking # pylint: disable=invalid-name generate a random test case, or make one from inputs # ^ is bitwise XOR, and works with booleans same algorithm as short_test_case, except this relies on the substring     being more unique than long:      if the whole string is generated by placing proper prefixes (i.e. a proper     prefix will never be the whole substring) of the chosen substring in front     of the substring, and proper suffixes after, no substring can be longer,     and the substrings can't form a longer substring through combining with     adjacent substrings, I think...      essentially, given the substring 123, the longest prefix can be 12, and the     longest suffix can be 23, so the resulting string will look like:     ...121212121232323232323...      no unique substring will be longer than 123      maximum length is unlimited # select a random sample of characters # how many more characters should we add? # select prefix and suffix length # list[:end] doesn't include end # choose how many prefixes and suffixes there will be by choosing how many # prefixes, then filling the rest out with suffixes # The substring is guaranteed to be the longest unique substring if it's # the longest substring within a string of characters all pulled from that # substring # draw a random sample of unique characters from a pool # this substring will be placed within a longer string, and in order for it # to be the longest, it must be longer than both the substring in front of # it, and the substring after it # those substrings can take characters from anywhere, since even if they're # unique, they won't be the longest # then, add characters from that substring until # (short_test_case() for _ in range(100)), #{case_number}") #{case_number}:") # breakpoint()  # pylint: disable=forgotten-debug-statement # type: ignore # type: ignore