initial commit

11 files changed, 228 insertions, 0 deletions

diff --git a/test_cases/q1/CONFIG b/test_cases/q1/CONFIG
new file mode 100644
index 0000000..ad7e38a
--- /dev/null
+++ b/test_cases/q1/CONFIG
@@ -0,0 +1,2 @@
+max_points: "3"
+class: "PassAllTestsQuestion"
diff --git a/test_cases/q1/graph_backtrack.solution b/test_cases/q1/graph_backtrack.solution
new file mode 100644
index 0000000..c52850c
--- /dev/null
+++ b/test_cases/q1/graph_backtrack.solution
@@ -0,0 +1,7 @@
+# This is the solution file for test_cases/q1/graph_backtrack.test.
+# This solution is designed to support both right-to-left
+# and left-to-right implementations.
+solution: "1:A->C 0:C->G"
+expanded_states: "A D C"
+rev_solution: "1:A->C 0:C->G"
+rev_expanded_states: "A B C"
diff --git a/test_cases/q1/graph_backtrack.test b/test_cases/q1/graph_backtrack.test
new file mode 100644
index 0000000..05640a0
--- /dev/null
+++ b/test_cases/q1/graph_backtrack.test
@@ -0,0 +1,32 @@
+class: "GraphSearchTest"
+algorithm: "depthFirstSearch"
+
+diagram: """
+ B   
+ ^
+ |
+*A --> C --> G
+ |
+ V
+ D
+
+A is the start state, G is the goal.  Arrows mark 
+possible state transitions.  This tests whether
+you extract the sequence of actions correctly even
+if your search backtracks.  If you fail this, your
+nodes are not correctly tracking the sequences of
+actions required to reach them.
+"""
+# The following section specifies the search problem and the solution.
+# The graph is specified by first the set of start states, followed by
+# the set of goal states, and lastly by the state transitions which are
+# of the form: 
+#      <start state> <actions> <end state> <cost>
+graph: """
+start_state: A
+goal_states: G
+A 0:A->B B 1.0
+A 1:A->C C 2.0
+A 2:A->D D 4.0
+C 0:C->G G 8.0
+"""
diff --git a/test_cases/q1/graph_bfs_vs_dfs.solution b/test_cases/q1/graph_bfs_vs_dfs.solution
new file mode 100644
index 0000000..0680f92
--- /dev/null
+++ b/test_cases/q1/graph_bfs_vs_dfs.solution
@@ -0,0 +1,7 @@
+# This is the solution file for test_cases/q1/graph_bfs_vs_dfs.test.
+# This solution is designed to support both right-to-left
+# and left-to-right implementations.
+solution: "2:A->D 0:D->G"
+expanded_states: "A D"
+rev_solution: "0:A->B 0:B->D 0:D->G"
+rev_expanded_states: "A B D"
diff --git a/test_cases/q1/graph_bfs_vs_dfs.test b/test_cases/q1/graph_bfs_vs_dfs.test
new file mode 100644
index 0000000..155e1fe
--- /dev/null
+++ b/test_cases/q1/graph_bfs_vs_dfs.test
@@ -0,0 +1,30 @@
+# Graph where BFS finds the optimal solution but DFS does not
+class: "GraphSearchTest"
+algorithm: "depthFirstSearch"
+
+diagram: """
+/-- B
+|   ^
+|   |
+|  *A -->[G]
+|   |     ^
+|   V     |
+\-->D ----/
+
+A is the start state, G is the goal.  Arrows
+mark possible transitions
+"""
+# The following section specifies the search problem and the solution.
+# The graph is specified by first the set of start states, followed by
+# the set of goal states, and lastly by the state transitions which are
+# of the form: 
+#      <start state> <actions> <end state> <cost>
+graph: """
+start_state: A
+goal_states: G
+A 0:A->B B 1.0
+A 1:A->G G 2.0
+A 2:A->D D 4.0
+B 0:B->D D 8.0
+D 0:D->G G 16.0
+"""
diff --git a/test_cases/q1/graph_infinite.solution b/test_cases/q1/graph_infinite.solution
new file mode 100644
index 0000000..82203ee
--- /dev/null
+++ b/test_cases/q1/graph_infinite.solution
@@ -0,0 +1,7 @@
+# This is the solution file for test_cases/q1/graph_infinite.test.
+# This solution is designed to support both right-to-left
+# and left-to-right implementations.
+solution: "0:A->B 1:B->C 1:C->G"
+expanded_states: "A B C"
+rev_solution: "0:A->B 1:B->C 1:C->G"
+rev_expanded_states: "A B C"
diff --git a/test_cases/q1/graph_infinite.test b/test_cases/q1/graph_infinite.test
new file mode 100644
index 0000000..692ac05
--- /dev/null
+++ b/test_cases/q1/graph_infinite.test
@@ -0,0 +1,30 @@
+# Graph where natural action choice leads to an infinite loop
+class: "GraphSearchTest"
+algorithm: "depthFirstSearch"
+
+diagram: """
+ B <--> C
+ ^     /|
+ |    / |
+ V   /  V
+*A<-/  [G]
+
+A is the start state, G is the goal.  Arrows mark 
+possible state transitions.
+"""
+# The following section specifies the search problem and the solution.
+# The graph is specified by first the set of start states, followed by
+# the set of goal states, and lastly by the state transitions which are
+# of the form: 
+#      <start state> <actions> <end state> <cost>
+graph: """
+start_state: A
+goal_states: G
+A 0:A->B B 1.0
+B 0:B->A A 2.0
+B 1:B->C C 4.0
+C 0:C->A A 8.0
+C 1:C->G G 16.0
+C 2:C->B B 32.0
+"""
+
diff --git a/test_cases/q1/graph_manypaths.solution b/test_cases/q1/graph_manypaths.solution
new file mode 100644
index 0000000..34b5a82
--- /dev/null
+++ b/test_cases/q1/graph_manypaths.solution
@@ -0,0 +1,7 @@
+# This is the solution file for test_cases/q1/graph_manypaths.test.
+# This solution is designed to support both right-to-left
+# and left-to-right implementations.
+solution: "2:A->B2 0:B2->C 0:C->D 2:D->E2 0:E2->F 0:F->G"
+expanded_states: "A B2 C D E2 F"
+rev_solution: "0:A->B1 0:B1->C 0:C->D 0:D->E1 0:E1->F 0:F->G"
+rev_expanded_states: "A B1 C D E1 F"
diff --git a/test_cases/q1/graph_manypaths.test b/test_cases/q1/graph_manypaths.test
new file mode 100644
index 0000000..953c4eb
--- /dev/null
+++ b/test_cases/q1/graph_manypaths.test
@@ -0,0 +1,39 @@
+class: "GraphSearchTest"
+algorithm: "depthFirstSearch"
+
+diagram: """
+    B1          E1
+   ^  \        ^  \
+  /    V      /    V
+*A --> C --> D --> F --> [G]
+  \    ^      \    ^
+   V  /        V  /
+    B2          E2
+
+A is the start state, G is the goal.  Arrows mark 
+possible state transitions.  This graph has multiple
+paths to the goal, where nodes with the same state 
+are added to the fringe multiple times before they
+are expanded.
+"""
+# The following section specifies the search problem and the solution.
+# The graph is specified by first the set of start states, followed by
+# the set of goal states, and lastly by the state transitions which are
+# of the form: 
+#      <start state> <actions> <end state> <cost>
+graph: """
+start_state: A
+goal_states: G
+A 0:A->B1 B1 1.0
+A 1:A->C C 2.0
+A 2:A->B2 B2 4.0
+B1 0:B1->C C 8.0
+B2 0:B2->C C 16.0
+C 0:C->D D 32.0
+D 0:D->E1 E1 64.0
+D 1:D->F F 128.0
+D 2:D->E2 E2 256.0
+E1 0:E1->F F 512.0
+E2 0:E2->F F 1024.0
+F 0:F->G G 2048.0
+"""
diff --git a/test_cases/q1/pacman_1.solution b/test_cases/q1/pacman_1.solution
new file mode 100644
index 0000000..82a670c
--- /dev/null
+++ b/test_cases/q1/pacman_1.solution
@@ -0,0 +1,40 @@
+# This is the solution file for test_cases/q1/pacman_1.test.
+# This solution is designed to support both right-to-left
+# and left-to-right implementations.
+# Number of nodes expanded must be with a factor of 1.0 of the numbers below.
+solution: """
+West West West West West West West West West West West West West West
+West West West West West West West West West West West West West West
+West West West West West South South South South South South South
+South South East East East North North North North North North North
+East East South South South South South South East East North North
+North North North North East East South South South South East East
+North North East East East East East East East East South South South
+East East East East East East East South South South South South South
+South West West West West West West West West West West West West West
+West West West West South West West West West West West West West West
+"""
+expanded_nodes: "146"
+rev_solution: """
+South South West West West West South South East East East East South
+South West West West West South South East East East East South South
+West West West West South South South East North East East East South
+South South West West West West West West West North North North North
+North North North North West West West West West West West North North
+North East East East East South East East East North North North West
+West North North West West West West West West West West West West
+West West West West West West West West West West West West West West
+South South South South South South South South South East East East
+North North North North North North North East East South South South
+South South South East East North North North North North North East
+East South South South South East East North North North North East
+East East East East South South West West West South South East East
+East South South West West West West West West South South West West
+West West West South West West West West West South South East East
+East East East East East North East East East East East North North
+East East East East East East North East East East East East South
+South West West West South West West West West West West South South
+West West West West West South West West West West West West West West
+West
+"""
+rev_expanded_nodes: "269"
diff --git a/test_cases/q1/pacman_1.test b/test_cases/q1/pacman_1.test
new file mode 100644
index 0000000..6ae5412
--- /dev/null
+++ b/test_cases/q1/pacman_1.test
@@ -0,0 +1,27 @@
+# This is a basic depth first search test
+class: "PacmanSearchTest"
+algorithm: "depthFirstSearch"
+
+# The following specifies the layout to be used 
+layoutName: "mediumMaze"
+layout: """
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%                                 P%
+% %%%%%%%%%%%%%%%%%%%%%%% %%%%%%%% %
+% %%   %   %      %%%%%%%   %%     %
+% %% % % % % %%%% %%%%%%%%% %% %%%%%
+% %% % % % %             %% %%     %
+% %% % % % % % %%%%  %%%    %%%%%% %
+% %  % % %   %    %% %%%%%%%%      %
+% %% % % %%%%%%%% %%        %% %%%%%
+% %% %   %%       %%%%%%%%% %%     %
+%    %%%%%% %%%%%%%      %% %%%%%% %
+%%%%%%      %       %%%% %% %      %
+%      %%%%%% %%%%% %    %% %% %%%%%
+% %%%%%%      %       %%%%% %%     %
+%        %%%%%% %%%%%%%%%%% %%  %% %
+%%%%%%%%%%                  %%%%%% %
+%.         %%%%%%%%%%%%%%%%        %
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+"""
+