python/double_decker_train_problem.py

"""
Double decker train problem:

               |^^^^^^^^^^^^^^|   |^^^^^^^^^^^^^^|
               | Double cargo |   |       wagon  |
   ~~~~ ____   |--------------|   |--------------|
  Y_,___|[]|   | Double       |   | cargo wagon  |
 {|_|_|_|PU|_,_|______________|_,_|______________|
//oo---OO=OO     O-O      O-O ^     O-O      O-O ^

This is a deceptively simple programming puzzle where you get to make an ordering of rail wagons.
Each wagon has two floors and there is text on the outside of the top and bottom floor.
When your chosen wagons are linked together, the whole text on the top should match the whole bottom.
Output an empty list only when there is no non-empty choice of wagons with matching text.
Your ordering may include any wagon any number of times.

Example: (illustrated above)
    Input wagons: [("Double cargo ", "Double "), ("wagon", "cargo wagon")]
    Output ordering: [0, 1]

    Explanation:
    Both the top and bottom will read "Double cargo wagon" when concatenated.
    Note that there is no need to mutate whitespace characters in the input.
"""

from typing import Callable, List, Optional, Tuple

Wagon = Tuple[str, str]


MAX_LENGTH = 10

def my_solver(wagons: List[Wagon]) -> List[int]:
    # Handle empty wagon case
    for i, wagon in enumerate(wagons):
        if wagon[0] + wagon[1] == "":
            return [i]
    return solve("", "", [], prepare(wagons))

def prepare(wagons: List[Wagon]) -> List[Tuple[int, Wagon]]:
    seen = set()
    prepared = []
    for i, wagon in enumerate(wagons):
        if wagon in seen:
            continue
        prepared.append((i, wagon))
        seen.add(wagon)
    return prepared

def solve(top_text: str, bottom_text: str, ordering: List[int], wagons: List[Tuple[int, Wagon]]) -> List[int]:
    if len(top_text) == 0 and len(bottom_text) == 0 and len(ordering) > 0:
        return ordering
    if len(ordering) > MAX_LENGTH:
        return []

    for z, (i, wagon) in enumerate(wagons):
        top = top_text + wagon[0]
        bottom = bottom_text + wagon[1]
        reordered = wagons[:z] + wagons[z+1:] + [(i, wagon)]
        if top.startswith(bottom):
            solution = solve(top[len(bottom):], "", [*ordering, i], reordered)
            if len(solution) > 0:
                return solution
        if bottom.startswith(top):
            solution = solve("", bottom[len(top):], [*ordering, i], reordered)
            if len(solution) > 0:
                return solution

    return []

def check_ordering(wagons: List[Wagon], ordering: List[int]) -> bool:
    """Checks if the text on top matches the text on the bottom"""
    sentence0 = ""
    sentence1 = ""
    for i in ordering:
        assert 0 <= i < len(wagons), f"wagon index out of range: {i}"
        sentence0 += wagons[i][0]
        sentence1 += wagons[i][1]
    return sentence0 == sentence1


def run_test_case(
    wagons: List[Wagon],
    example_ordering: List[int],
    ordering: List[int],
) -> str:
    if ordering == []:
        if example_ordering == []:
            return "PASS"
        return "You falsely claimed it was impossible."

    if check_ordering(wagons, ordering):
        if example_ordering == []:
            return "PASS (and the problem setter is a dummy)"
        return "PASS"

    sentence0 = ""
    sentence1 = ""
    for i in ordering:
        assert 0 <= i < len(wagons), f"wagon index out of range: {i}"
        sentence0 += wagons[i][0]
        sentence1 += wagons[i][1]

    # return f"Your selected wagons had different sentences on the top and bottom.\n{ordering}\n{sentence0!r}\n{sentence1!r}"

    return "Your selected wagons had different sentences on the top and bottom."


def run_test_cases(solver: Callable[[List[Wagon]], List[int]]):
    test_cases: Tuple[List[Wagon], List[int]] = [
        ([("Double cargo ", "Double "), ("wagon", "cargo wagon")], [0, 1]),
        ([("wagon", "cargo wagon"), ("Double cargo ", "Double ")], [1, 0]),
        ([("Hello ", "Hello"), ("World", " World")], [0, 1]),
        ([("", "")], [0]),
        ([(".", "-.."), (".-", ".."), ("--.", "--")], [2, 1, 2, 0]),
        ([("bc", "ca"), ("a", "ab"), ("ca", "a"), ("abc", "c")], [1, 0, 1, 3]),
        ([("yy", "y"), ("xy", "yx"), ("z", "yz")], [0, 1, 1, 1, 1, 1, 2]),
        ([("", "42"), ("42", "")], [1, 0]),
        ([("aaaa", ""), ("", "a")], [0, 1, 1, 1, 1]),
        ([], []),
        ([("0", "1")], []),
        ([("0", "1"), (" ", "  ")], []),
        ([("", " ")], []),
        ([("aa", "a"), ("aa", "a"), ("b", "ab")], [0, 2]),
        ([("aa", ""), ("ab", ""), ("", "aa")], [0, 2]),
        ([("aa", ""), ("ab", "")], []),
        ([("ab", "a"), ("ab", "b")], []),
        ([("aaaa", ""), ("", "a")], [0, 1, 1, 1, 1]),
        ([("ab"*1000, ""), ("a", "ab"), ("b", "ab")], [0] + [1,2]*1000),
        ([("a"*(2**4*3**5), ""), ("", "aa"), ("", "aaa")], [0]+[1]*2**4 +[2]*3**5),

        # ([("ab", "a"), ("ab", "b")], []),
        # TODO: add more test cases
    ]
    for i, (wagons, example_ordering) in enumerate(test_cases):
        print(f"Test case {i:>2}: ", end="")
        if not check_ordering(wagons, example_ordering):
            sentence0 = ""
            sentence1 = ""
            for i in example_ordering:
                assert 0 <= i < len(wagons), f"wagon index out of range: {i}"
                sentence0 += wagons[i][0]
                sentence1 += wagons[i][1]
            print(sentence0)
            print(sentence1)


        assert check_ordering(wagons, example_ordering), "example is invalid, dummy."

        print(run_test_case(wagons, example_ordering, solver(wagons)))


run_test_cases(my_solver)