algorithm_fridays_week10.py

cyclic_paths = []

def _transform_to_upper(road_map: dict):
  road_map_upper = {}
  for key in road_map.keys():
    road_map_upper[key.upper()] = [subKey.upper() for subKey in road_map[key]]
  return road_map_upper

def _validate(road_map: dict, start: str):
  # Validate map
  if road_map == None or type(road_map) != dict or len(road_map.keys()) < 1:
    return False

  # Validate start point
  if start == None or type(start) != str or start == '':
    return False

  # Transform to uppercase first to avoid key indexing errors
  road_map_upper_cased = _transform_to_upper(road_map)
  start = start.upper()

  # Ensure start point exists in map
  if start not in road_map_upper_cased.keys():
    return False

  # Ensure start point isn't dangling
  if len(road_map_upper_cased[start]) == 0:
    return False

  return True

def _pop(previous_points: list):
  if previous_points and len(previous_points) > 0:
    previous_points.pop()

def _find_cycles(initial_point: str, current_point: str, current_iteration: int, road_map: dict, previous_points: list):
  '''Helper function to perform cyclic check recursively'''
  global cyclic_paths

  # We want to ensure we're not going in cycles forever (an inner cycle)
  if current_point in previous_points and current_point != initial_point:
    return

  # Keep track of previous points passed (track previous paths taken)
  if current_iteration != 0:
    previous_points.append(current_point)

  # Capture cycle if we get back back to our initial point
  if (initial_point == current_point) and (current_iteration != 0):
    cyclic_paths.append(initial_point + ''.join(previous_points.copy()))
    _pop(previous_points)
    return
  else: # Check if any inner path is cyclic
    for point in road_map[current_point]:
      if point in road_map.keys():
        _find_cycles(initial_point, point, current_iteration + 1, road_map, previous_points)
    _pop(previous_points)
    return

# Required Function
def find_cyclic_paths(road_map: dict, start: str):
  global cyclic_paths

  result = _validate(road_map, start)
  if result == False:
    return []

  # Transform to uppercase first to avoid key indexing errors
  road_map_upper_cased = _transform_to_upper(road_map)
  start = start.upper()

  _find_cycles(start, start, 0, road_map_upper_cased, [])
  return cyclic_paths

if __name__ == '__main__':
  road_map = {
    'A': ['B', 'C'],
    'B':  ['A'],
    'C': ['B']
  }
  start = 'A'
  cyclic_paths = find_cyclic_paths(road_map, start)
  print(cyclic_paths)