Triangular labyrinth calculator

Reuleauxs_labyrinth.py

"""
Given a labyrinth bounded in Reuleaux's Triangle (or any triangle), let each V be any of the 3 vertices
and C be any of the 7 circuits.   There are 3*7=21 segments in this labyrinth, and a path through it can be described
by going from one point (v_i, c_j) to some other point (v_k, c_l) where the following rules apply:

1.  From a given starting point, one can either
   a. traverse along the same circuit but different vertice (ie j = l), or
   b. switch back along a neighboring circuit (ie l = c +/- 1)
2. Each segment can be traversed only once, implying points can be arrived at more than once only if as a switchback
   in a neighboring tridant

Each segment is lettered A-U starting with the bottom inner segment and spiraling clockwise.   A Vector is a letter
indicating a traversal of a Segment: capital for clockwise, lower case for counter clockwise

"""
# Make list of all points in labyrinth
POINTS = []
for v in range(3):
    for c in range(7):
        POINTS.append((v, c))

SEGMENTS = [chr(c) for c in range(97, 97+21)]  # a-u.  Cap letters are 65:86
CIRCUITS = [(a, b, c) for a, b, c in zip(*[iter(SEGMENTS)]*3)]
CIRCUITS_DICT = {}
for s in SEGMENTS:
    for c in CIRCUITS:
        if s in c:
            CIRCUITS_DICT[s] = c

SOLUTION_COUNT = 0
DEAD_ENDS = 0
HEARTLESS_SOLUTIONS = 0
def next_vector_options(previous_vector, remaining_segments):
    """ For a given vector (segment with direction), return options for next vector """
    vector_options = []
    # Find which circuit we're in
    circuit = CIRCUITS_DICT[previous_vector.lower()]

    # lower case = counterclockwise = subtraction.  upper case is opposite
    direction = -1 if ord(previous_vector) > 96 else 1
    case = str.upper if direction > 0 else str.lower
    idx = circuit.index(previous_vector.lower())

    # Next option in same circuit will be adding 1 % 3 if capital, or subtracting if lower case
    vector_options.append(case(circuit[(idx + direction) % 3]))


    # there are 1-2 switchback vector options too in neighboring circuits at same idx, opposite capitalization
    inner_circuit = CIRCUITS_DICT.get(chr(ord(previous_vector.lower()) - 3))
    if inner_circuit:
        # Swap capitalization to indicate reversing direction
        if direction > 0:
            vector_options.append(inner_circuit[idx].lower())
        else:
            vector_options.append(inner_circuit[idx].upper())


    outer_circuit = CIRCUITS_DICT.get(chr(ord(previous_vector.lower()) + 3))
    if outer_circuit:
        # Swap capitalization to indicate reversing direction
        if direction > 0:
            vector_options.append(outer_circuit[idx].lower())
        else:
            vector_options.append(outer_circuit[idx].upper())

    # Remove vector options which aren't in remaining segments
    resp = []
    for v in vector_options:
        if v.lower() in remaining_segments:
            resp.append(v)

    return resp


def follow_path(previous_vector, remaining_segments: list, vectors_traversed: list):
    """ From previous_vector, explore all options recursively """
    vectors_traversed.append(previous_vector)
    try:
        remaining_segments.pop(remaining_segments.index(previous_vector.lower()))
    except Exception:
        if len(vectors_traversed) < 21:
            print(f"Previous vector {previous_vector} not in remaining_segments {''.join(remaining_segments)}")

    if not remaining_segments:
        # we finished the labyrinth, but at the center?
        if previous_vector in CIRCUITS[0]:
            print(f"Found solution: {''.join(vectors_traversed)}")
            global SOLUTION_COUNT
            SOLUTION_COUNT += 1
            return vectors_traversed
        else:
            global HEARTLESS_SOLUTIONS
            HEARTLESS_SOLUTIONS += 1
    next_points = next_vector_options(previous_vector, remaining_segments)

    if not next_points:
        # We don't have any legal next_points, and apparently we have remaining_segments, so give up
        # print(f"Giving up after path {''.join(vectors_traversed)}")
        global DEAD_ENDS
        DEAD_ENDS += 1
        return None

    for np in next_points:


        # print(f"Exploring path starting {vectors_traversed} with {np} next")
        follow_path(np, remaining_segments.copy(), vectors_traversed.copy())


def main():
    # Iterate through each segment as a starting point
    # these options are mirrors (opposite case) or translations (different starting vertex), so no need to try ALL
    # starting points
    for starting_point in list('ADGJMPS'):
        remaining_segments = SEGMENTS.copy()
        # For each point, iterate through each prospective point and call recursively
        # for branch in next_options(starting_point, remaining_points):

        result = follow_path(starting_point, remaining_segments, [])
    print(f"Found {SOLUTION_COUNT} valid solutions, {HEARTLESS_SOLUTIONS} heartless solutions and {DEAD_ENDS} dead ends")


if __name__ == "__main__":
    main()

    print("done")