hamx0r · August 26, 2024 02:25
diff --git a/Reuleauxs_labyrinth.py b/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")
	"""
	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")