The team of Sheldon, Leonard, Howard, and Raj are participating in a Kayak competition. Their entire...

 

Transcribed Image Text:

The team of Sheldon, Leonard, Howard, and Raj are participating in a Kayak competition. Their entire team should cross a river in 34 minutes or less to win. There are only two Kayak's available, each Kayak can seat one person. So, at most two people can row across the river at a time. One member of the team would then have to tow the empty Kayak back to the other riverbank so others could cross. The team begins on the same riverbank with two Kayaks. Each person rows the Kayak at a different pace. Raj takes 2 minutes to row across the river. • Howard takes 4 minutes to row across the river. Leonard takes 10 minutes to row across the river. Sheldon takes 20 minutes to row across the river. For sake of simplicity assume a pair starts in their Kayak at the same time, the two row at the speed of the slower rower and get across together (this assumption does not matter in terms of reaching to the other bank of river since there are only two available Kayaks). Additionally, this would ensure both Kayaks are together on the same bank of the river. Example - If Raj and Sheldon start together, 20 minutes would have passed when they cross the river. If Sheldon then returns in his kayak and tows along the other empty Kayak, another 20 minutes would have passed. The total time would be greater than 34 minutes and they would lose. Your job is to help their team win! Hint: You can model the problem as state space search. A start state, goal state, in between states that would lead to the goal. Name the two banks of river as source 's' and destination 'd'. State can be represented as a group of five elements. Example: Start state: [s,s,s,s,s]. First four elements represent the riverbank (source 's' or destination 'd') where Raj, Howard, Sheldon, and Howard are respectively. Fifth element represents location of the Kayaks. An intermediate state: [d,d,s,s,d] means Raj and Howard on the destination riverbank with Kayaks. Goal state: [d,d,d,d,d] entire team and Kayaks on the destination riverbank. To ensure search does not get stuck in cycles keep track of states visited, only visit a state if it was not previously visited. Compute total time and if it exceeds 34 minutes then do not further explore that path. Write a computer program that implements the solution to above problem. Implement your code in one of the programming languages: JAVA, Python, C++, C#, C, Prolog. Evaluate immediate child states of a parent state from left to right. Your code should print the solution as below: If there is no path that costs 34 minutes or less to the goal your program should print: No solution to the goal exists. If solution is found your program should print the full current path line by line - each state in the current path to the goal, cumulative time at each state, and interpretation of each state. Example: Path to the goal found. [s,s,s,s,s] 0 [d,s,s,d,d] 20 [s,s,s,d,s] 22 At source - Raj Howard Leonard Kayaks At destination - [d,d,d,d,d] 34 At source - Howard Leonard At destination - Raj Sheldon Kayaks At source - Raj Howard Leonard Kayaks At destination - Sheldon <so on and so forth> At source - At destination - Raj Howard Leonard Sheldon Kayaks What to turn in Submit your work electronically as below two separate files. You can upload multiple files on Canvas. 1. Source code. Note that the acceptable files are Python- .py (convert your Jupyter notebook to .py), JAVA - .java, C++.cpp, C-.C, C# - .cs, Prolog-plain text file. 2. Screen shot of your output generated from program run. You will lose points if you do not include screen shot of program run. If you worked as pair, only one member should upload the homework. Names of both members should appear as comment at the top of your source code, another option is to let me know by way of adding comment in canvas. The team of Sheldon, Leonard, Howard, and Raj are participating in a Kayak competition. Their entire team should cross a river in 34 minutes or less to win. There are only two Kayak's available, each Kayak can seat one person. So, at most two people can row across the river at a time. One member of the team would then have to tow the empty Kayak back to the other riverbank so others could cross. The team begins on the same riverbank with two Kayaks. Each person rows the Kayak at a different pace. Raj takes 2 minutes to row across the river. • Howard takes 4 minutes to row across the river. Leonard takes 10 minutes to row across the river. Sheldon takes 20 minutes to row across the river. For sake of simplicity assume a pair starts in their Kayak at the same time, the two row at the speed of the slower rower and get across together (this assumption does not matter in terms of reaching to the other bank of river since there are only two available Kayaks). Additionally, this would ensure both Kayaks are together on the same bank of the river. Example - If Raj and Sheldon start together, 20 minutes would have passed when they cross the river. If Sheldon then returns in his kayak and tows along the other empty Kayak, another 20 minutes would have passed. The total time would be greater than 34 minutes and they would lose. Your job is to help their team win! Hint: You can model the problem as state space search. A start state, goal state, in between states that would lead to the goal. Name the two banks of river as source 's' and destination 'd'. State can be represented as a group of five elements. Example: Start state: [s,s,s,s,s]. First four elements represent the riverbank (source 's' or destination 'd') where Raj, Howard, Sheldon, and Howard are respectively. Fifth element represents location of the Kayaks. An intermediate state: [d,d,s,s,d] means Raj and Howard on the destination riverbank with Kayaks. Goal state: [d,d,d,d,d] entire team and Kayaks on the destination riverbank. To ensure search does not get stuck in cycles keep track of states visited, only visit a state if it was not previously visited. Compute total time and if it exceeds 34 minutes then do not further explore that path. Write a computer program that implements the solution to above problem. Implement your code in one of the programming languages: JAVA, Python, C++, C#, C, Prolog. Evaluate immediate child states of a parent state from left to right. Your code should print the solution as below: If there is no path that costs 34 minutes or less to the goal your program should print: No solution to the goal exists. If solution is found your program should print the full current path line by line - each state in the current path to the goal, cumulative time at each state, and interpretation of each state. Example: Path to the goal found. [s,s,s,s,s] 0 [d,s,s,d,d] 20 [s,s,s,d,s] 22 At source - Raj Howard Leonard Kayaks At destination - [d,d,d,d,d] 34 At source - Howard Leonard At destination - Raj Sheldon Kayaks At source - Raj Howard Leonard Kayaks At destination - Sheldon <so on and so forth> At source - At destination - Raj Howard Leonard Sheldon Kayaks What to turn in Submit your work electronically as below two separate files. You can upload multiple files on Canvas. 1. Source code. Note that the acceptable files are Python- .py (convert your Jupyter notebook to .py), JAVA - .java, C++.cpp, C-.C, C# - .cs, Prolog-plain text file. 2. Screen shot of your output generated from program run. You will lose points if you do not include screen shot of program run. If you worked as pair, only one member should upload the homework. Names of both members should appear as comment at the top of your source code, another option is to let me know by way of adding comment in canvas.

Answer rating: 100% (QA)

This problem can be solved using a depthfirst search alg... View the full answer