Comments (5)
This function won't find the fastest route but it returns the first it finds.
from anytree import Node
from collections import deque
#test
def test(paths, entrance, exit, last_move, expected):
result = solve_labyrinth(paths, entrance, exit, last_move)
return result.name["back"] == expected
bad_moves = set()
def solve_labyrinth(paths, entrance, exit, last_move):
result = None
if last_move not in bad_moves:
if entrance == exit:
result = last_move
else:
last_move.children = possible_paths(entrance, paths)
if len(last_move.children) == 0:
if [last_move.siblings] != []:
bad_moves.add(last_move)
undo_move(last_move, paths)
else:
move_stack = deque(last_move.children)
while result == None and len(move_stack) > 0:
current_move = move_stack.pop()
new_pos = make_move(current_move, paths)[0]
new_path = make_move(current_move, paths)[1]
result = solve_labyrinth(new_path, new_pos, exit, current_move)
if result == None:
bad_moves.add(last_move)
undo_move(last_move, paths)
else:
undo_move(last_move, paths)
return result
#create labyrinth
def create_labyrinth():
begin = (2,3) #begin mayn not be in labyrinth, but end has to be!
end = (5, 2)
all_path = {(1, 0), (3, 0), (4, 0), (5, 0),
(0, 1), (1, 1), (2, 1), (3, 1), (5, 1),
(0, 2), (2, 2), (4, 2), (5, 2),
(0, 3), (2, 3), (3, 3), (5, 3),
(0, 4), (4, 4),
(0, 5), (1, 5), (2, 5), (3, 5), (4, 5)}
return all_path, begin, end
def make_move(node, pth):
move= node.name
new_pos = move.get("move")
old_pos = move.get("back")
if old_pos in pth:
pth.remove(old_pos)
return new_pos, pth #returns tuple!!!!!!!!!
def undo_move(node, pth):
move = node.name
old_pos = move.get("back")
pth.add(old_pos)
#check possible paths
def possible_paths(entr, pth):
result = list()
x = entr[0]
y = entr[1]
if (x+1, y) in pth:
result.append(Node({"move": (x+1, y), "back": (x,y)}))
if (x-1, y) in pth:
result.append(Node({"move": (x-1, y), "back": (x,y)}))
if (x, y+1) in pth:
result.append(Node({"move": (x, y+1), "back": (x,y)}))
if (x, y-1) in pth:
result.append(Node({"move": (x, y-1), "back": (x,y)}))
return result
path, entrance, exit = create_labyrinth()
print(test(path, entrance, exit, Node("start"), (3,5))) # True
I tried putting begin = (2,3)
and end = (5,2)
:
print(test(path, entrance, exit, Node("start"), (5,1))) # True
from 2020-2021.
I have replaced your "last_move" with "previous_position". At the end the algorithm returns the position occupied before finding the exit.
from anytree import Node
from collections import deque
paths = [
(1, 0), (3, 0), (4, 0), (5, 0),
(0, 1), (1, 1), (2, 1), (3, 1), (5, 1),
(0, 2), (2, 2), (4, 2), (5, 2),
(0, 3), (2, 3), (3, 3), (5, 3),
(0, 4), (4, 4),
(0, 5), (1, 5), (2, 5), (3, 5), (4, 5)
]
def test_solve_labyrinth(paths, entrance, exit, previous_position,expected):
result = solve_labyrinth(paths,entrance,exit,previous_position)
return result==expected
def solve_labyrinth(paths, entrance, exit, previous_position):
result = None
entrance.children = valid_moves(paths, entrance, previous_position) # generate children
possible_moves = deque(entrance.children)
if len(entrance.children) > 0:
if entrance.name != exit: # keep moving
while result == None and len(possible_moves) > 0:
current_move = possible_moves.pop()
result = solve_labyrinth(paths, current_move, exit, entrance) # recursion
else: # win, provided that you are in the exit box
result = previous_position.name
return result
elif len(entrance.children) <= 0 and entrance.name != exit: # leaf-node lose
return result # backtracking
elif len(entrance.children) <= 0 and entrance.name == exit: # leaf-node win
result = previous_position.name
return result
def valid_moves(paths, current_position, previous_position):
result = list()
x = current_position.name[0]
y = current_position.name[1]
if (x + 1, y) in paths and (x + 1, y) != previous_position.name:
result.append(Node((x + 1, y)))
if (x - 1, y) in paths and (x - 1, y) != previous_position.name:
result.append(Node((x - 1, y)))
if (x, y + 1) in paths and (x, y + 1) != previous_position.name:
result.append(Node((x, y + 1)))
if (x, y - 1) in paths and (x, y - 1) != previous_position.name:
result.append(Node((x, y - 1)))
return result
none_node = Node(None) # previous position of the start position
print(test_solve_labyrinth(paths, Node((2, 3)), (4, 4), none_node,(4,5))) # returns True
print(test_solve_labyrinth(paths, Node((0, 1)), (5, 3), none_node,(5,2))) # returns True
print(test_solve_labyrinth(paths, Node((2, 1)), (4, 2), none_node,(5,2))) # returns True
print(test_solve_labyrinth(paths, Node((2, 1)), (5, 5), none_node,None)) # returns True
from 2020-2021.
from anytree import Node
from collections import deque
# Test case for the algorithm
def test_solve_labirynth(paths,entrance,exit,last_move,expected):
result = solve_labirynth(paths,entrance,exit,last_move)
if (expected==result==None):
return True
elif result!=None:
return (expected == result.name["to"])
else:
return False
def create_labirynth():
paths = set([
(1, 0),(3, 0),(4, 0),(5, 0),
(0, 1),(1, 1),(2, 1),(3, 1),(5, 1),
(0, 2),(2, 2),(4, 2),(5, 2),
(0, 3),(2, 3),(3, 3),(5, 3),
(0, 4),(4, 4),
(0, 5),(1, 5),(2, 5),(3, 5), (4, 5)
])
return paths
def valid_moves(paths,cell):
result = list()
pos_x=cell[0]
pos_y=cell[1]
if (pos_x-1, pos_y) in paths:
result.append(Node({"from": (pos_x, pos_y), "to": (pos_x-1, pos_y)}))
if (pos_x+1, pos_y) in paths:
result.append(Node({"from": (pos_x, pos_y), "to": (pos_x+1, pos_y)}))
if (pos_x, pos_y-1) in paths:
result.append(Node({"from": (pos_x, pos_y), "to": (pos_x, pos_y-1)}))
if (pos_x, pos_y+1) in paths:
result.append(Node({"from": (pos_x, pos_y), "to": (pos_x, pos_y+1)}))
return result
def apply_move(node, paths):
move = node.name
prev_pos = move.get("from")
paths.remove(prev_pos)
def undo_move(node, paths):
move = node.name
curr_pos = move.get("to")
prev_pos = move.get("from")
paths.remove(curr_pos)
paths.add(prev_pos)
def solve_labirynth(paths,entrance,exit,last_move):
result = None
if (exit not in paths): return None
if (entrance==exit): # leaf-win base case
result = last_move
else:
last_move.children = valid_moves(paths,entrance)
if len(last_move.children) == 0: # leaf-lose base case
undo_move(last_move, paths) # backtracking
else: # recursive step
possible_moves = deque(last_move.children)
while result is None and len(possible_moves) > 0:
current_move = possible_moves.pop()
apply_move(current_move, paths)
result = solve_labirynth(paths, current_move.name.get("to"),exit, current_move)
if (result is None) and (last_move!=last_move.root): # If the last_move is back to the root, it means the exit has not been found after trying all the paths
undo_move(last_move, paths) # backtracking
return result
# TEST 1: solvable labirynth
paths=create_labirynth()
entrance=(5,3)
exit=(4,4)
print(test_solve_labirynth(paths,entrance,exit,Node('Start'),exit))
# TEST 2: same labirynth but exit out of paths
entrance=(5,3)
exit=(5,5)
print(test_solve_labirynth(paths,entrance,exit,Node('Start'),None))
# TEST 3: existent but unreachable exit
paths=set([
(1, 0),(3, 0),(4, 0),(5, 0),
(0, 1),(1, 1),(2, 1),(3, 1),(5, 1),
(0, 2),(2, 2),(4, 2),(5, 2),
(0, 3),(2, 3),(3, 3),(5, 3),
(0, 4),(4, 4),
(0, 5),(1, 5),(2, 5),(3, 5)
])
entrance=(5,3)
exit=(4,4)
print(test_solve_labirynth(paths,entrance,exit,Node('Start'),None))
from 2020-2021.
from anytree import Node
from collections import deque
from time import sleep
# Test case for the algorithm
def test_solve_labyrinth(paths, entrance, exit, last_move, expected):
result = solve_labyrinth(paths, entrance, exit, last_move)
if expected == result:
return True
else:
return False
def solve_labyrinth(paths, entrance, exit, last_move):
result = None
if last_move.name["new_position"] == exit: # leaf-win base case
result = last_move.name["old_position"]
else:
if entrance == last_move: # only first case
last_move.children = valid_moves(entrance, paths)
move = last_move.name
street.append(move["new_position"])
paths.remove(move["new_position"])
else:
last_move.children = valid_moves(last_move, paths)
possible_moves = deque(last_move.children)
while result is None and len(possible_moves) > 0:
current_position = possible_moves.pop()
apply_move(current_position, paths)
result = solve_labyrinth(paths, entrance, exit, current_position)
return result
def create_board():
entrance = Node({"new_position": (int(input("starting_x: ")), int(input("starting_y: "))) , "old_position": (None, None)})
paths = {(1, 0), (3, 0), (4, 0), (5, 0), (0, 1), (1, 1), (2, 1), (3, 1), (5, 1),
(0, 2), (2, 2), (4, 2), (5, 2), (0, 3), (2, 3), (3, 3), (5, 3), (0, 4), (4, 4),
(0, 5), (1, 5), (2, 5), (3, 5), (4, 5)}
exit = (int(input("finishing_x: ")), int(input("finishing_y: ")))
return paths, entrance, exit
def valid_moves(last_move, paths):
result = list()
move = last_move.name
x, y = move["new_position"]
if (x - 1, y) in paths:
result.append(Node({"new_position": (x - 1, y), "old_position": (x, y)}))
if (x + 1, y) in paths:
result.append(Node({"new_position": (x + 1, y), "old_position": (x, y)}))
if (x, y - 1) in paths:
result.append(Node({"new_position": (x, y - 1), "old_position": (x, y)}))
if (x, y + 1) in paths:
result.append(Node({"new_position": (x, y + 1), "old_position": (x, y)}))
return result
def apply_move(current_positon, paths):
move = current_positon.name
new_pos = move.get("new_position")
paths.remove(new_pos)
# pegs, holes = create_6x6_square_board()
paths, entrance, exit = create_board()
print(test_solve_labyrinth(paths, entrance, exit, entrance, (5, 0)))
from 2020-2021.
from anytree import Node
from collections import deque
def test_solve_labyrinth(paths, entrance, exit, last_move, expected):
return solve_labyrinth(paths, entrance, exit, last_move) == expected
def valid_moves(entrance, paths):
result = []
x = entrance[0]
y = entrance[1]
if (x,y) in paths:
if (x + 1, y) in paths:
result.append(Node({"move from": (x, y), "to": (x + 1, y)}))
if (x - 1, y) in paths:
result.append(Node({"move from": (x, y), "to": (x - 1, y)}))
if (x, y + 1) in paths:
result.append(Node({"move from": (x, y), "to": (x, y + 1)}))
if (x, y - 1) in paths:
result.append(Node({"move from": (x, y), "to": (x, y - 1)}))
return result
def apply_move(node, paths):
move = node.name
old_pos = move.get("move from")
entrance = move.get("to")
if old_pos in paths:
paths.remove(old_pos)
return entrance, paths, old_pos
def undo_move(node, paths):
move = node.name
old_pos = move.get("move from")
paths.add(old_pos)
def solve_labyrinth(paths, entrance, exit, last_move):
result = None
initial_paths = set()
initial_paths.update(paths)
if entrance not in paths:
return "No access to labyrinth"
if exit not in paths:
return result
if entrance == exit:
result = last_move.name
else:
last_move.children = valid_moves(entrance, paths)
if len(last_move.children) == 0:
undo_move(last_move, paths)
else:
possible_moves = deque(last_move.children)
while result is None and len(possible_moves) > 0:
cur_move = possible_moves.pop()
new_entr = apply_move(cur_move, paths)[0]
paths_updated = apply_move(cur_move, paths)[1]
result = solve_labyrinth(paths_updated, new_entr, exit, cur_move)
if result is None:
undo_move(last_move, paths)
paths.update(initial_paths)
return result
cells = {(1,0), (3,0), (4,0), (5,0),
(0,1), (1,1), (2,1), (3,1), (5,1),
(0,2), (2,2), (4,2), (5,2),
(0,3), (2,3), (3,3), (5,3),
(0,4), (4,4),
(0,5), (1,5), (2,5), (3,5), (4,5)}
print(test_solve_labyrinth(cells, (1,0), (3,3), Node("Start"), {'move from': (2, 3), 'to': (3, 3)})) # True
print(test_solve_labyrinth(cells, (4,4), (5,3), Node("Start"), {'move from': (5, 2), 'to': (5, 3)})) # True
print(test_solve_labyrinth(cells, (0,0), (4,4), Node("Start"), "No access to labyrinth")) # True
print(test_solve_labyrinth(cells, (2,1), (3,6), Node("Start"), None)) # True
from 2020-2021.
Related Issues (20)
- Lecture "Brute-force algorithms", exercise 5 HOT 15
- Lecture "Organising information: unordered structures", exercise 1 HOT 21
- Lecture "Organising information: unordered structures", exercise 2 HOT 19
- Lecture "Organising information: unordered structures", exercise 3 HOT 20
- Lecture "Recursion", exercise 1 HOT 19
- Lecture "Recursion", exercise 2 HOT 20
- Lecture "Divide and conquer algorithms", exercise 1 HOT 19
- Lecture "Divide and conquer algorithms", exercise 2 HOT 17
- Lecture "Divide and conquer algorithms", exercise 3 HOT 5
- Lecture "Dynamic programming algorithms", exercise 1 HOT 21
- Lecture "Dynamic programming algorithms", exercise 2 HOT 19
- Lecture "Organising information: trees", exercise 1 HOT 9
- Lecture "Organising information: trees", exercise 2 HOT 7
- Bonus exercise (AtariGo) HOT 2
- Lecture "Backtracking algorithms", exercise 1 HOT 6
- Lecture "Organising information: graphs", exercise 1 HOT 15
- Lecture "Organising information: graphs", exercise 2 HOT 14
- Lecture "Greedy algorithms", exercise 1 HOT 5
- Lecture "Greedy algorithms", exercise 2 HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from 2020-2021.