diff options
Diffstat (limited to 'test_cases/q3')
21 files changed, 433 insertions, 0 deletions
diff --git a/test_cases/q3/CONFIG b/test_cases/q3/CONFIG new file mode 100644 index 0000000..e5332c3 --- /dev/null +++ b/test_cases/q3/CONFIG @@ -0,0 +1,2 @@ +class: "PassAllTestsQuestion" +max_points: "3" diff --git a/test_cases/q3/graph_backtrack.solution b/test_cases/q3/graph_backtrack.solution new file mode 100644 index 0000000..d150cb7 --- /dev/null +++ b/test_cases/q3/graph_backtrack.solution @@ -0,0 +1,7 @@ +# This is the solution file for test_cases/q3/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 B C D" +rev_solution: "1:A->C 0:C->G" +rev_expanded_states: "A B C D" diff --git a/test_cases/q3/graph_backtrack.test b/test_cases/q3/graph_backtrack.test new file mode 100644 index 0000000..a74bd9e --- /dev/null +++ b/test_cases/q3/graph_backtrack.test @@ -0,0 +1,32 @@ +class: "GraphSearchTest" +algorithm: "uniformCostSearch" + +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/q3/graph_bfs_vs_dfs.solution b/test_cases/q3/graph_bfs_vs_dfs.solution new file mode 100644 index 0000000..5dfffca --- /dev/null +++ b/test_cases/q3/graph_bfs_vs_dfs.solution @@ -0,0 +1,7 @@ +# This is the solution file for test_cases/q3/graph_bfs_vs_dfs.test. +# This solution is designed to support both right-to-left +# and left-to-right implementations. +solution: "1:A->G" +expanded_states: "A B" +rev_solution: "1:A->G" +rev_expanded_states: "A B" diff --git a/test_cases/q3/graph_bfs_vs_dfs.test b/test_cases/q3/graph_bfs_vs_dfs.test new file mode 100644 index 0000000..87aa465 --- /dev/null +++ b/test_cases/q3/graph_bfs_vs_dfs.test @@ -0,0 +1,30 @@ +# Graph where BFS finds the optimal solution but DFS does not +class: "GraphSearchTest" +algorithm: "uniformCostSearch" + +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/q3/graph_infinite.solution b/test_cases/q3/graph_infinite.solution new file mode 100644 index 0000000..c6cd195 --- /dev/null +++ b/test_cases/q3/graph_infinite.solution @@ -0,0 +1,7 @@ +# This is the solution file for test_cases/q3/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/q3/graph_infinite.test b/test_cases/q3/graph_infinite.test new file mode 100644 index 0000000..80d807f --- /dev/null +++ b/test_cases/q3/graph_infinite.test @@ -0,0 +1,30 @@ +# Graph where natural action choice leads to an infinite loop +class: "GraphSearchTest" +algorithm: "uniformCostSearch" + +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/q3/graph_manypaths.solution b/test_cases/q3/graph_manypaths.solution new file mode 100644 index 0000000..628568f --- /dev/null +++ b/test_cases/q3/graph_manypaths.solution @@ -0,0 +1,7 @@ +# This is the solution file for test_cases/q3/graph_manypaths.test. +# This solution is designed to support both right-to-left +# and left-to-right implementations. +solution: "1:A->C 0:C->D 1:D->F 0:F->G" +expanded_states: "A B1 C B2 D E1 F E2" +rev_solution: "1:A->C 0:C->D 1:D->F 0:F->G" +rev_expanded_states: "A B1 C B2 D E1 F E2" diff --git a/test_cases/q3/graph_manypaths.test b/test_cases/q3/graph_manypaths.test new file mode 100644 index 0000000..8c39dc7 --- /dev/null +++ b/test_cases/q3/graph_manypaths.test @@ -0,0 +1,39 @@ +class: "GraphSearchTest" +algorithm: "uniformCostSearch" + +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/q3/ucs_0_graph.solution b/test_cases/q3/ucs_0_graph.solution new file mode 100644 index 0000000..b8c1509 --- /dev/null +++ b/test_cases/q3/ucs_0_graph.solution @@ -0,0 +1,7 @@ +# This is the solution file for test_cases/q3/ucs_0_graph.test. +# This solution is designed to support both right-to-left +# and left-to-right implementations. +solution: "Right Down Down" +expanded_states: "A B D C G" +rev_solution: "Right Down Down" +rev_expanded_states: "A B D C G" diff --git a/test_cases/q3/ucs_0_graph.test b/test_cases/q3/ucs_0_graph.test new file mode 100644 index 0000000..e8f3d4c --- /dev/null +++ b/test_cases/q3/ucs_0_graph.test @@ -0,0 +1,39 @@ +class: "GraphSearchTest" +algorithm: "uniformCostSearch" + +diagram: """ + C + ^ + | 2 + 2 V 4 +*A <----> B -----> [H] + |1 + 1.5 V 2.5 + G <----- D -----> E + | + 2 | + V + [F] + +A is the start state, F and H is the goal. Arrows mark possible state +transitions. The number next to the arrow is the cost of that transition. +""" +# 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: H F +A Right B 2.0 +B Right H 4.0 +B Down D 1.0 +B Up C 2.0 +B Left A 2.0 +C Down B 2.0 +D Right E 2.5 +D Down F 2.0 +D Left G 1.5 +""" + diff --git a/test_cases/q3/ucs_1_problemC.solution b/test_cases/q3/ucs_1_problemC.solution new file mode 100644 index 0000000..dc8fc4c --- /dev/null +++ b/test_cases/q3/ucs_1_problemC.solution @@ -0,0 +1,22 @@ +# This is the solution file for test_cases/q3/ucs_1_problemC.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.1 of the numbers below. +solution: """ +West West West West West West West West West South South East East +South South South West West West North West West West West 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: "269" +rev_solution: """ +West West West West West West West West West South South East East +South South South West West West North West West West West 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 +""" +rev_expanded_nodes: "269" diff --git a/test_cases/q3/ucs_1_problemC.test b/test_cases/q3/ucs_1_problemC.test new file mode 100644 index 0000000..1ce714d --- /dev/null +++ b/test_cases/q3/ucs_1_problemC.test @@ -0,0 +1,28 @@ +class: "PacmanSearchTest" +algorithm: "uniformCostSearch" +points: "0.5" + +# The following specifies the layout to be used +layoutName: "mediumMaze" +layout: """ +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% P% +% %%%%%%%%%%%%%%%%%%%%%%% %%%%%%%% % +% %% % % %%%%%%% %% % +% %% % % % % %%%% %%%%%%%%% %% %%%%% +% %% % % % % %% %% % +% %% % % % % % %%%% %%% %%%%%% % +% % % % % % %% %%%%%%%% % +% %% % % %%%%%%%% %% %% %%%%% +% %% % %% %%%%%%%%% %% % +% %%%%%% %%%%%%% %% %%%%%% % +%%%%%% % %%%% %% % % +% %%%%%% %%%%% % %% %% %%%%% +% %%%%%% % %%%%% %% % +% %%%%%% %%%%%%%%%%% %% %% % +%%%%%%%%%% %%%%%% % +%. %%%%%%%%%%%%%%%% % +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +""" +leewayFactor: "1.1" +#costFn: "lambda pos: 1" diff --git a/test_cases/q3/ucs_2_problemE.solution b/test_cases/q3/ucs_2_problemE.solution new file mode 100644 index 0000000..d84245f --- /dev/null +++ b/test_cases/q3/ucs_2_problemE.solution @@ -0,0 +1,22 @@ +# This is the solution file for test_cases/q3/ucs_2_problemE.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.1 of the numbers below. +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 East East East East South South South +West West West West West West West North 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: "260" +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 East East East East South South South +West West West West West West West North 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 +""" +rev_expanded_nodes: "260" diff --git a/test_cases/q3/ucs_2_problemE.test b/test_cases/q3/ucs_2_problemE.test new file mode 100644 index 0000000..3c609f2 --- /dev/null +++ b/test_cases/q3/ucs_2_problemE.test @@ -0,0 +1,28 @@ +class: "PacmanSearchTest" +algorithm: "uniformCostSearch" +points: "0.5" + +# The following specifies the layout to be used +layoutName: "mediumMaze" +layout: """ +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% P% +% %%%%%%%%%%%%%%%%%%%%%%% %%%%%%%% % +% %% % % %%%%%%% %% % +% %% % % % % %%%% %%%%%%%%% %% %%%%% +% %% % % % % %% %% % +% %% % % % % % %%%% %%% %%%%%% % +% % % % % % %% %%%%%%%% % +% %% % % %%%%%%%% %% %% %%%%% +% %% % %% %%%%%%%%% %% % +% %%%%%% %%%%%%% %% %%%%%% % +%%%%%% % %%%% %% % % +% %%%%%% %%%%% % %% %% %%%%% +% %%%%%% % %%%%% %% % +% %%%%%% %%%%%%%%%%% %% %% % +%%%%%%%%%% %%%%%% % +%. %%%%%%%%%%%%%%%% % +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +""" +leewayFactor: "1.1" +costFn: "lambda pos: .5 ** pos[0]" diff --git a/test_cases/q3/ucs_3_problemW.solution b/test_cases/q3/ucs_3_problemW.solution new file mode 100644 index 0000000..e04325d --- /dev/null +++ b/test_cases/q3/ucs_3_problemW.solution @@ -0,0 +1,34 @@ +# This is the solution file for test_cases/q3/ucs_3_problemW.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.1 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 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 South South West West West West South South West West West West +West South West West West West West West West West West +""" +expanded_nodes: "173" +rev_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 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 South South West West West West South South West West West West +West South West West West West West West West West West +""" +rev_expanded_nodes: "173" diff --git a/test_cases/q3/ucs_3_problemW.test b/test_cases/q3/ucs_3_problemW.test new file mode 100644 index 0000000..fbc2fad --- /dev/null +++ b/test_cases/q3/ucs_3_problemW.test @@ -0,0 +1,28 @@ +class: "PacmanSearchTest" +algorithm: "uniformCostSearch" +points: "0.5" + +# The following specifies the layout to be used +layoutName: "mediumMaze" +layout: """ +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% P% +% %%%%%%%%%%%%%%%%%%%%%%% %%%%%%%% % +% %% % % %%%%%%% %% % +% %% % % % % %%%% %%%%%%%%% %% %%%%% +% %% % % % % %% %% % +% %% % % % % % %%%% %%% %%%%%% % +% % % % % % %% %%%%%%%% % +% %% % % %%%%%%%% %% %% %%%%% +% %% % %% %%%%%%%%% %% % +% %%%%%% %%%%%%% %% %%%%%% % +%%%%%% % %%%% %% % % +% %%%%%% %%%%% % %% %% %%%%% +% %%%%%% % %%%%% %% % +% %%%%%% %%%%%%%%%%% %% %% % +%%%%%%%%%% %%%%%% % +%. %%%%%%%%%%%%%%%% % +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +""" +leewayFactor: "1.1" +costFn: "lambda pos: 2 ** pos[0]" diff --git a/test_cases/q3/ucs_4_testSearch.solution b/test_cases/q3/ucs_4_testSearch.solution new file mode 100644 index 0000000..b8c5303 --- /dev/null +++ b/test_cases/q3/ucs_4_testSearch.solution @@ -0,0 +1,12 @@ +# This is the solution file for test_cases/q3/ucs_4_testSearch.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 2.0 of the numbers below. +solution: """ +West East East South South West West +""" +expanded_nodes: "14" +rev_solution: """ +West East East South South West West +""" +rev_expanded_nodes: "13" diff --git a/test_cases/q3/ucs_4_testSearch.test b/test_cases/q3/ucs_4_testSearch.test new file mode 100644 index 0000000..a16c6d8 --- /dev/null +++ b/test_cases/q3/ucs_4_testSearch.test @@ -0,0 +1,16 @@ +class: "PacmanSearchTest" +algorithm: "uniformCostSearch" +points: "0.5" + +# The following specifies the layout to be used +layoutName: "testSearch" +layout: """ +%%%%% +%.P % +%%% % +%. % +%%%%% +""" +searchProblemClass: "FoodSearchProblem" +leewayFactor: "2" + diff --git a/test_cases/q3/ucs_5_goalAtDequeue.solution b/test_cases/q3/ucs_5_goalAtDequeue.solution new file mode 100644 index 0000000..7d6c982 --- /dev/null +++ b/test_cases/q3/ucs_5_goalAtDequeue.solution @@ -0,0 +1,7 @@ +# This is the solution file for test_cases/q3/ucs_5_goalAtDequeue.test. +# This solution is designed to support both right-to-left +# and left-to-right implementations. +solution: "1:A->B 0:B->C 0:C->G" +expanded_states: "A B C" +rev_solution: "1:A->B 0:B->C 0:C->G" +rev_expanded_states: "A B C" diff --git a/test_cases/q3/ucs_5_goalAtDequeue.test b/test_cases/q3/ucs_5_goalAtDequeue.test new file mode 100644 index 0000000..72b35bc --- /dev/null +++ b/test_cases/q3/ucs_5_goalAtDequeue.test @@ -0,0 +1,29 @@ +class: "GraphSearchTest" +algorithm: "uniformCostSearch" + +diagram: """ + 1 1 1 +*A ---> B ---> C ---> [G] + | ^ + | 10 | + \---------------------/ + +A is the start state, G is the goal. Arrows mark possible state +transitions. The number next to the arrow is the cost of that transition. + +If you fail this test case, you may be incorrectly testing if a node is a goal +before adding it into the queue, instead of testing when you remove the node +from the queue. See the algorithm pseudocode in lecture. +""" + +graph: """ +start_state: A +goal_states: G +A 0:A->G G 10.0 +A 1:A->B B 1.0 +B 0:B->C C 1.0 +C 0:C->G G 1.0 +""" +# We only care about the solution, not the expansion order. +exactExpansionOrder: "False" + |