diff options
Diffstat (limited to 'test_cases/q1')
-rw-r--r-- | test_cases/q1/CONFIG | 2 | ||||
-rw-r--r-- | test_cases/q1/graph_backtrack.solution | 7 | ||||
-rw-r--r-- | test_cases/q1/graph_backtrack.test | 32 | ||||
-rw-r--r-- | test_cases/q1/graph_bfs_vs_dfs.solution | 7 | ||||
-rw-r--r-- | test_cases/q1/graph_bfs_vs_dfs.test | 30 | ||||
-rw-r--r-- | test_cases/q1/graph_infinite.solution | 7 | ||||
-rw-r--r-- | test_cases/q1/graph_infinite.test | 30 | ||||
-rw-r--r-- | test_cases/q1/graph_manypaths.solution | 7 | ||||
-rw-r--r-- | test_cases/q1/graph_manypaths.test | 39 | ||||
-rw-r--r-- | test_cases/q1/pacman_1.solution | 40 | ||||
-rw-r--r-- | test_cases/q1/pacman_1.test | 27 |
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% +% %%%%%%%%%%%%%%%%%%%%%%% %%%%%%%% % +% %% % % %%%%%%% %% % +% %% % % % % %%%% %%%%%%%%% %% %%%%% +% %% % % % % %% %% % +% %% % % % % % %%%% %%% %%%%%% % +% % % % % % %% %%%%%%%% % +% %% % % %%%%%%%% %% %% %%%%% +% %% % %% %%%%%%%%% %% % +% %%%%%% %%%%%%% %% %%%%%% % +%%%%%% % %%%% %% % % +% %%%%%% %%%%% % %% %% %%%%% +% %%%%%% % %%%%% %% % +% %%%%%% %%%%%%%%%%% %% %% % +%%%%%%%%%% %%%%%% % +%. %%%%%%%%%%%%%%%% % +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +""" + |