text: """
  Problem:
  
  You are given a circular lock with three wheels, each of which display the numbers 0
  through 9 in order. Each of these wheels rotate clockwise and counterclockwise.
  
  In addition, the lock has a certain number of "dead ends", meaning that if you turn the
  wheels to one of these combinations, the lock becomes stuck in that state and cannot be
  opened.
  
  Let us consider a "move" to be a rotation of a single wheel by one digit, in either
  direction. Given a lock initially set to 000, a target combination, and a list of dead
  ends, write a function that returns the minimum number of moves required to reach the
  target state, or None if this is impossible.
  """
  
  from sys import maxsize
  from typing import List, Tuple, Set
  
  
  def turn_wheel_up(val: int) -> int:
      return (val + 1) % 10
  
  
  def turn_wheel_down(val: int) -> int:
      return (val - 1 + 10) % 10
  
  
  def get_min_moves_helper(
      curr: List[int],
      pattern: List[int],
      dead_ends: Set[Tuple[int, int, int]],
      seen: Set[str],
      accumulator: int = 0,
  ) -> int:
      if curr == pattern:
          return accumulator
      curr_val = "".join([str(x) for x in curr])
      if curr_val in seen:
          # if a loop back occours, the target pattern cannot be reached
          return maxsize
      seen.add(curr_val)
  
      moves = []
      for i in range(3):
          temp = curr.copy()
          if temp[i] != pattern[i]:
              temp[i] = turn_wheel_up(temp[i])
              if tuple(temp) not in dead_ends:
                  moves.append(temp)
          temp = curr.copy()
          if temp[i] != pattern[i]:
              temp[i] = turn_wheel_down(temp[i])
              if tuple(temp) not in dead_ends:
                  moves.append(temp)
  
      temp = maxsize
      for move in moves:
          temp = min(
              temp, get_min_moves_helper(move, pattern, dead_ends, seen, accumulator + 1),
          )
      return temp
  
  
  def get_min_moves(pattern, dead_ends):
      result = get_min_moves_helper([0, 0, 0], pattern, dead_ends, set())
      if result == maxsize:
          return None
      return result
  
  
  if __name__ == "__main__":
      print(get_min_moves([3, 4, 5], set([])))
      print(get_min_moves([3, 4, 5], set([(0, 0, 1), (0, 1, 0), (1, 0, 0)])))
      print(
          get_min_moves(
              [3, 4, 5],
              set([(0, 0, 1), (0, 1, 0), (1, 0, 0), (0, 0, 9), (0, 9, 0), (9, 0, 0)]),
          )
      )
  
  
  """
  SPECS:
  
  TIME COMPLEXITY: O(n ^ n)
  SPACE COMPLEXITY: O(n ^ n)
  [n = max(pattern)]
  """
  
  