fork download 
  1. from collections import namedtuple
  2.  
  3. Explorer = namedtuple('Explorer', 'row,col,direction')
  4.  
  5. movement = { '>': (0,1), '<': (0,-1), '^': (-1,0), 'V': (1,0) }
  6.  
  7. turns = {'>': ('V', '<', '^'), 'V': ('<', '^', '>'),
  8.          '<': ('^', '>', 'V'), '^': ('>', 'V', '<')}
  9.  
  10. def turn_right(direction):
  11.     return turns[direction][0]
  12.  
  13. def turn_around(direction):
  14.     return turns[direction][1]
  15.  
  16. def turn_left(direction):
  17.     return turns[direction][2]
  18.  
  19. def move(row, col, direction, spaces=1):
  20.     r = row + movement[direction][0]*spaces
  21.     c = col + movement[direction][1]*spaces
  22.     return r, c
  23.  
  24. def navigate(maze):
  25.     maze = maze.splitlines()
  26.     # Find explorer
  27.     for r, row in enumerate(maze):
  28.         for c, cell in enumerate(row):
  29.             if cell in '><^V':
  30.                 explorer = Explorer(r, c, cell)
  31.                 break
  32.     states = {explorer}
  33.  
  34.     r, c = explorer.row, explorer.col
  35.     d = explorer.direction
  36.     while True:
  37.         # Keep moving according to the rules until we reach
  38.         # the exit or a repeated state
  39.         for i in range(6):
  40.             if maze[r][c] == 'E':
  41.                 return True
  42.             next_r, next_c = move(r,c,d)
  43.             if maze[next_r][next_c] == '#':
  44.                 # If a wall is in my way I turn to the right
  45.                 next_r, next_c = move(r,c,turn_right(d))
  46.                 if maze[next_r][next_c] == '#':
  47.                     # if that not possible I turn to the left
  48.                     next_r, next_c = move(r, c, turn_left(d))
  49.                     if maze[next_r][next_c] == '#':
  50.                         # if that is not possible I turn back from where I came
  51.                         d = turn_around(d)
  52.                         next_r, next_c = move(r, c, d)
  53.                     else:
  54.                         d = turn_left(d)
  55.                 else:
  56.                     d = turn_right(d)
  57.             r, c = next_r, next_c
  58.         d = turn_right(turn_right(d))
  59.         if Explorer(r, c, d) in states:
  60.             # We've seen this before. The maze can't be solved.
  61.             return False
  62.         states.add(Explorer(r, c, d))
  63.  
  64.  
  65. mazes = [
  66. '''#######
  67. #>   E#
  68. #######''',
  69.  
  70. '''#####E#
  71. #<    #
  72. #######''',
  73.  
  74. '''##########
  75. #>      E#
  76. ##########''',
  77.  
  78. '''#####E#
  79. ##### #
  80. #>    #
  81. ##### #
  82. #######''',
  83.  
  84. '''#####E#
  85. ##### #
  86. ##### #
  87. ##### #
  88. ##### #
  89. #>    #
  90. ##### #
  91. #######''']
  92.  
  93. challenges = ['''#########
  94. #E ######
  95. ##      #
  96. ##### # #
  97. #>    ###
  98. ##### ###
  99. ##### ###
  100. ##### ###
  101. ##### ###
  102. ##### ###
  103. ##### ###
  104. #########''',
  105.  
  106. '''#########
  107. #E ######
  108. ##      #
  109. ## ## # #
  110. ##### # #
  111. #>    ###
  112. ##### ###
  113. ##### ###
  114. ##### ###
  115. ##### ###
  116. ##### ###
  117. ##### ###
  118. #########''']
  119.  
  120. for maze in mazes:
  121.     print(navigate(maze))
  122. for maze in challenges:
  123.     print(navigate(maze))
Success #stdin #stdout 0.01s 28384KB
comments ()
stdin 
Standard input is empty
stdout 
True
True
False
True
False
False
True
https://ideone.com/cQaGHo
language:
Python 3 (python  3.12)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!