-
Notifications
You must be signed in to change notification settings - Fork 0
/
experiment.py
137 lines (125 loc) · 6.74 KB
/
experiment.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
"""
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 experiment code that tries using the two solvers
on a couple of puzzles and prints a summary as a markdown table.
Feel free to add more samples here to explore how your solvers perform
under various conditions.
This file is NOT graded and is provided purely as a way for you to further
explore and develop your code if you wish to.
Things you might explore:
- implementing another puzzle type of your choice
- solving puzzles with different properties
- exploring how implementing fail_fast changes the time taken to solve puzzles
- implementing your own custom solver to try to get better performance
"""
from timeit import timeit
from solver import BfsSolver, DfsSolver
from sudoku_puzzle import SudokuPuzzle
from word_ladder_puzzle import WordLadderPuzzle
from expression_tree import ExprTree, construct_from_list
from expression_tree_puzzle import ExpressionTreePuzzle
import sys
sys.setrecursionlimit(4000)
if __name__ == '__main__':
a = [['+'], [3, '*', 'a', '+'], ['b', 'c'], [5, 'd']]
tree = construct_from_list(a)
tree1 = ExpressionTreePuzzle(tree, 107)
a = [['+'], [3, '*', 'a', '+'], ['b', 'c'], [5, 'd']]
tree = construct_from_list(a)
tree2 = ExpressionTreePuzzle(tree, 11)
unsolved = [[' ', '2', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
[' ', ' ', ' ', '6', ' ', ' ', ' ', ' ', '3'],
[' ', '7', '4', ' ', '8', ' ', ' ', ' ', ' '],
[' ', ' ', ' ', ' ', ' ', '3', ' ', ' ', '2'],
[' ', '8', ' ', ' ', '4', ' ', ' ', '1', ' '],
['6', ' ', ' ', '5', ' ', ' ', ' ', ' ', ' '],
[' ', ' ', ' ', ' ', '1', ' ', '7', '8', ' '],
['5', ' ', ' ', ' ', ' ', '9', ' ', ' ', ' '],
[' ', ' ', ' ', ' ', ' ', ' ', ' ', '4', ' ']]
words = {'china', 'chins', 'cains', 'carns', 'cares',
'carer', 'cater', 'eater', 'ester', 'aster',
'poops', 'dicks', 'japan', 'whipwhip', 'naenae'
'chips', 'dads', 'chooch', 'dbaby', 'kares',
'dares', 'wears', 'pears', 'lairs'}
from_word = 'china'
to_word = 'aster'
slide_example = WordLadderPuzzle(from_word, to_word, words)
puzzles = [SudokuPuzzle(4,
[["1", " ", " ", "2"],
[" ", " ", " ", "1"],
[" ", " ", " ", " "],
[" ", " ", "2", " "]],
{"1", "2", "3", "4"}),
SudokuPuzzle(9,
[[" ", " ", " ", "7", " ", "8", " ", "1", " "],
[" ", " ", "7", " ", "9", " ", " ", " ", "6"],
["9", " ", "3", "1", " ", " ", " ", " ", " "],
["3", "5", " ", "8", " ", " ", "6", " ", "1"],
[" ", " ", " ", " ", " ", " ", " ", " ", " "],
["1", " ", "6", " ", " ", "9", " ", "4", "8"],
[" ", " ", " ", " ", " ", "1", "2", " ", "7"],
["8", " ", " ", " ", "7", " ", "4", " ", " "],
[" ", "6", " ", "3", " ", "2", " ", " ", " "]],
{"1", "2", "3", "4", "5", "6", "7", "8", "9"}),
# SudokuPuzzle(9,
# [["2", " ", " ", "8", " ", "1", " ", " ", " "],
# [" ", " ", " ", " ", " ", " ", " ", "4", "3"],
# ["5", " ", " ", " ", " ", "6", " ", " ", " "],
# [" ", " ", "5", " ", "7", " ", "8", " ", " "],
# [" ", " ", " ", " ", " ", " ", "1", " ", " "],
# [" ", "2", " ", " ", "3", " ", " ", " ", " "],
# ["6", " ", " ", " ", " ", " ", " ", "7", "5"],
# [" ", " ", "3", "4", " ", " ", " ", " ", " "],
# [" ", " ", " ", "2", " ", " ", "6", " ", " "]],
# {"1", "2", "3", "4", "5", "6", "7", "8", "9"})
slide_example,
WordLadderPuzzle("same", "cost"),
WordLadderPuzzle("perked", "manors"),
WordLadderPuzzle("stashes", "cheesed"),
WordLadderPuzzle("clearing", "scuffing"),
WordLadderPuzzle("smocking", "drilling"),
WordLadderPuzzle("revealed", "muttered"),
WordLadderPuzzle("tiro", "hunk"),
WordLadderPuzzle("rho", "nut"),
WordLadderPuzzle("rho", "yak"),
tree1,
tree2,
ExpressionTreePuzzle(construct_from_list([['+'],
[3, '*', 'a', '+'],
['a', '+'], ['b', 9],
[2, 9]]), 129),
ExpressionTreePuzzle(construct_from_list([['+'],
[3, '*', 'a', '+'],
['a', '+'], ['b', 'c'],
[2, 9]]), 129),
ExpressionTreePuzzle(construct_from_list([['+'],
[3, '*', 'a', '+'],
['a', '+'], ['b', 'c'],
[2, 'd']]), 129)
]
headers = ["Puzzle Type", "Solver", "len(sol)", "time"]
print("|".join(headers))
print("|".join(["-" * len(header) for header in headers]))
for puzzle in puzzles:
for solver in [DfsSolver, BfsSolver]:
puzzle_solver = solver()
sol = puzzle_solver.solve(puzzle)
n_samples = 1
duration = timeit('puzzle_solver.solve(puzzle)',
globals=globals(),
number=n_samples) / n_samples
print(f"{type(puzzle).__name__[:-6]:>11}|{solver.__name__[:-6]:>6}|"
f"{len(sol) if sol else -1:>8}|{duration:2.5f}")