-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathsolver.py
182 lines (151 loc) · 6.6 KB
/
solver.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
"""
CSC148, Winter 2021
Assignment 2: Automatic Puzzle Solver
==============================
This code is provided solely for the personal and private use of
students taking the CSC148 course at the University of Toronto.
Copying for purposes other than this use is expressly prohibited.
All forms of distribution of this code, whether as given or with
any changes, are expressly prohibited.
Authors: Diane Horton, Jonathan Calver, Sophia Huynh,
Maryam Majedi, and Jaisie Sin.
All of the files in this directory are:
Copyright (c) 2021 Diane Horton, Jonathan Calver, Sophia Huynh,
Maryam Majedi, and Jaisie Sin.
=== Module Description ===
This module contains the abstract Solver class and its two subclasses, which
find solutions to puzzles, step by step.
"""
from __future__ import annotations
from typing import List, Optional, Set
# You may remove this import if you don't use it in your code.
from adts import Queue
from puzzle import Puzzle
class Solver:
""""
A solver for full-information puzzles. This is an abstract class
and purely provides the interface for our solve method.
"""
# You may NOT change the interface to the solve method.
# Note the optional parameter seen and its type.
# Your implementations of this method in the two subclasses should use seen
# to keep track of all puzzle states that you encounter during the
# solution process.
def solve(self, puzzle: Puzzle,
seen: Optional[Set[str]] = None) -> List[Puzzle]:
"""
Return a list of puzzle states representing a path to a solution of
<puzzle>. The first element in the list should be <puzzle>, the
second element should be a puzzle that is in <puzzle>.extensions(),
and so on. The last puzzle in the list should be such that it is in a
solved state.
In other words, each subsequent item of the returned list should take
the puzzle one step closer to a solution, which is represented by the
last item in the list.
Return an empty list if the puzzle has no solution.
<seen> is either None (default) or a set of puzzle states' string
representations, whose puzzle states can't be any part of the path to
the solution.
"""
raise NotImplementedError
# TODO (Task 2): implement the solve method in the DfsSolver class.
# Your solve method MUST be a recursive function (i.e. it must make
# at least one recursive call to itself)
# You may NOT change the interface to the solve method.
class DfsSolver(Solver):
""""
A solver for full-information puzzles that uses
a depth first search strategy.
"""
def solve(self, puzzle: Puzzle,
seen: Optional[Set[str]] = None) -> List[Puzzle]:
"""
Return a list of puzzle states representing a path to a solution of
<puzzle>. The first element in the list should be <puzzle>, the
second element should be a puzzle that is in <puzzle>.extensions(),
and so on. The last puzzle in the list should be such that it is in a
solved state.
In other words, each subsequent item of the returned list should take
the puzzle one step closer to a solution, which is represented by the
last item in the list.
Return an empty list if the puzzle has no solution.
<seen> is either None (default) or a set of puzzle states' string
representations, whose puzzle states can't be any part of the path to
the solution.
"""
if seen is None:
seen = set()
if puzzle.__str__() in seen:
return []
elif puzzle.fail_fast():
seen.add(puzzle.__str__())
return []
elif puzzle.is_solved():
return [puzzle]
else:
lst = [puzzle]
seen.add(puzzle.__str__())
for p in puzzle.extensions():
lst.extend(self.solve(p, seen))
if lst[-1].is_solved():
return lst
return []
# TODO (Task 2): implement the solve method in the BfsSolver class.
# Hint: You may find a Queue useful here.
class BfsSolver(Solver):
""""
A solver for full-information puzzles that uses
a breadth first search strategy.
"""
def solve(self, puzzle: Puzzle,
seen: Optional[Set[str]] = None) -> List[Puzzle]:
"""
Return a list of puzzle states representing a path to a solution of
<puzzle>. The first element in the list should be <puzzle>, the
second element should be a puzzle that is in <puzzle>.extensions(),
and so on. The last puzzle in the list should be such that it is in a
solved state.
In other words, each subsequent item of the returned list should take
the puzzle one step closer to a solution, which is represented by the
last item in the list.
Return an empty list if the puzzle has no solution.
<seen> is either None (default) or a set of puzzle states' string
representations, whose puzzle states can't be any part of the path to
the solution.
"""
if seen is None:
seen = set()
if puzzle.is_solved():
return [puzzle]
if puzzle.__str__() in seen or puzzle.fail_fast():
return []
adt = Queue()
adt.enqueue([puzzle])
while not adt.is_empty():
curr = adt.dequeue()
for item in curr[-1].extensions():
if item.__str__() in seen:
pass
elif item.__str__() not in seen and item.is_solved():
return curr + [item]
elif item.fail_fast():
seen.add(item.__str__())
else:
temp = curr[:] + [item]
adt.enqueue(temp)
seen.add(item.__str__())
if adt.is_empty():
return []
if __name__ == "__main__":
import python_ta
python_ta.check_all(config={'pyta-reporter': 'ColorReporter',
'allowed-io': [],
'allowed-import-modules': ['doctest',
'python_ta',
'typing',
'__future__',
'puzzle',
'adts'],
'disable': ['E1136'],
'max-attributes': 15}
)