Starting from:
$40
COP3502c Project 2- Rescue Mission Solution
Objective
Give practice with binary search in C.
Story
You will send a team to save them, but the rescue team will only be able to be sent once to a single location and takes 1 hour to arrive, so you must determine the exact location of the ship. Luckily you are able to borrow a satellite that passes over the ocean every hour. It can take a photo of only 1 nautical mile, but you can use this to determine if the ship has passed the location by picking up the traces of a wake, if the ship is at that location by picking up the picture of the ship, or if the ship has not yet reached that location by picking up nothing in the picture.
You want to ensure that the ship is not stranded for too long. The ship has to be rescued in 24 hours (at most 23 pictures). Keep in mind that after the last picture the ship will move for a full hour while you launch the rescue team. Finally, your first photo will be exactly 1 hour after the initial distress signal was sent.
Problem
Write a program that when given the maximum starting speed of the ship and the maximum x coordinate, can ask for information at specific x-coordinates at most 23 times, and can at any point after a query can report the current location of the ship.
Input
Input will begin with a line containing 2 integers, S and L (1 ≤ S, L ≤ 100), representing the maximum possible speed of the ship in Knots and the maximum possible starting coordinate of the ship, respectively. Following this will be multiple lines. Each line contains a single response
to one of your queries. The responses will be one of the following strings
● Wake - The ship has already passed by
● No Wake - The ship has not passed this location as of yet
● Boat! - The ship was captured in the photo
The testing system will allow you to read the response only after your program prints the query and flushes the standard output (use fflush(stdout)).
Output
To make the queries your program should print to standard output. To ask for a photo of a location your program should output “? x” where x is the location to take the photo. To send the rescue team your program should output “! x” where x is the location of the ship. Your program must flush the output (use fflush(stdout)) after each query and after your command to send the rescue team.
Sample Input Sample Output
3 3
No Wake
Wake
Wake
Wake
Boat! ? 3
? 1
? 3
? 5
? 10
! 12
5 2
Wake
Wake
Wake
Wake
Wake ? 1
? 5
? 11
? 18
? 26
! 32
Explanation Case 1
The boat has a speed of 2. Additionally the boat started at position 0.
By the time the first picture happens the boat has moved to position 2.
The sample took the picture at position 3. At that location there is no boat and no wake.
When the next picture is taken the boat moves to position 4.
This picture is taken at position 1. There is no boat, but there is a wake.
When the next picture is taken the boat moves to position 6.
The next picture is taken at position 3. At that location there is no boat, but there is now a wake.
When the next picture is taken the boat moves to position 8.
The next picture is taken at position 5. At that location there is no boat, but there is now a
wake.
When the next picture is taken the boat moves to position 8.
The final picture is taken at position 10. At that location there is a boat.
The rescue team is now sent out. At this point the boat has moved to position 12. Luckily, the sample requests to send the team to that position.
Case 2
The boat started at position 2 with a speed of 5.
The ship will be at location 7 during the first picture. The picture is taken at location 1. There is a wake at that point.
The ship will be at location 12 during the second picture. The picture is taken at location 5.
There is a wake at that point.
The ship will be at location 17 during the third picture. The picture is taken at location 11. There is a wake at that point.
The ship will be at location 22 during the fourth picture. The picture is taken at location 18.
There is a wake at that point.
The ship will be at location 27 during the fifth picture. The picture is taken at location 26. There is a wake at that point.
The ship will be at location 32 when the sample sends out the rescue team. The rescue team is sent to location 32. There ship is at that location.
Hints
FLUSH Your Output: After every printf remember to fflush(stdout).
Track ALL Possibilities: Keep track of all the possible boats that exist. There should be 1 possibility for every combination of speed and starting location. When your program takes a photo and gets feedback. Eliminate all the boats that would have generated a different output.
Possibility Storage: You can store the possibilities in a 2D grid, indexed by the initial parameters of the ship, that contains a 0/1 indicating whether that possibility is still valid.
The Midpoint: Your program should guess the “midpoint”. The midpoint is a bit unusual in this problem. At each time the photo is taken there is a list of possible locations that the ship could be (based on the speed/location combinations that have not been invalidated).
The midpoint should be the ship location that roughly splits the “search space” (the location of all remaining valid combinations) in half.
Midpoint Candidates: Don’t guess random valid ship locations. Instead loop through the list of ship locations and check if that ship location works as a “midpoint”. The midpoints should only be considered from the still valid ships.
Extension: This problem was made easier from an alternative version where the max speed and location could be up to 1000. If you finish the version of the problem for homework try to consider how you could efficiently solve the problem for larger bounds.
Grading Criteria
● Good comments, whitespace, and variable names
○ 15 points
● Use standard input/output
○ 5 points
● No extra input output (e.g. input prompts, “Please enter the number of friends:”) ○ 5 points
● Flush your output every time your print
○ 5 points
● Track the valid ship combinations
○ 10 points
● Check the effectiveness of a possible midpoint
○ 5 points
● “Move” the ships after each photo
○ 5 points
● Programs will be tested on 10 cases
○ 5 points each
○ 6 of these cases will have fixed values
○ 4 of these cases will be adversarial
■ Without being certain of the location of the ship you will get the case wrong
No points will be awarded to programs that do not compile using “gcc -std=gnu11 -lm”.
Sometimes a requested technique will be given, and solutions without the requested technique will have their maximum points total reduced. For this problem use a binary search. Without this programs will earn at most 50 points!
Any case that causes a program to return a non-zero return code will be treated as wrong. Additionally, any case that takes longer than the maximum allowed time (the max of {5 times my solutions time, 10 seconds}) will also be treated as wrong.
No partial credit will be awarded for an incorrect case.
Give practice with binary search in C.
Story
You will send a team to save them, but the rescue team will only be able to be sent once to a single location and takes 1 hour to arrive, so you must determine the exact location of the ship. Luckily you are able to borrow a satellite that passes over the ocean every hour. It can take a photo of only 1 nautical mile, but you can use this to determine if the ship has passed the location by picking up the traces of a wake, if the ship is at that location by picking up the picture of the ship, or if the ship has not yet reached that location by picking up nothing in the picture.
You want to ensure that the ship is not stranded for too long. The ship has to be rescued in 24 hours (at most 23 pictures). Keep in mind that after the last picture the ship will move for a full hour while you launch the rescue team. Finally, your first photo will be exactly 1 hour after the initial distress signal was sent.
Problem
Write a program that when given the maximum starting speed of the ship and the maximum x coordinate, can ask for information at specific x-coordinates at most 23 times, and can at any point after a query can report the current location of the ship.
Input
Input will begin with a line containing 2 integers, S and L (1 ≤ S, L ≤ 100), representing the maximum possible speed of the ship in Knots and the maximum possible starting coordinate of the ship, respectively. Following this will be multiple lines. Each line contains a single response
to one of your queries. The responses will be one of the following strings
● Wake - The ship has already passed by
● No Wake - The ship has not passed this location as of yet
● Boat! - The ship was captured in the photo
The testing system will allow you to read the response only after your program prints the query and flushes the standard output (use fflush(stdout)).
Output
To make the queries your program should print to standard output. To ask for a photo of a location your program should output “? x” where x is the location to take the photo. To send the rescue team your program should output “! x” where x is the location of the ship. Your program must flush the output (use fflush(stdout)) after each query and after your command to send the rescue team.
Sample Input Sample Output
3 3
No Wake
Wake
Wake
Wake
Boat! ? 3
? 1
? 3
? 5
? 10
! 12
5 2
Wake
Wake
Wake
Wake
Wake ? 1
? 5
? 11
? 18
? 26
! 32
Explanation Case 1
The boat has a speed of 2. Additionally the boat started at position 0.
By the time the first picture happens the boat has moved to position 2.
The sample took the picture at position 3. At that location there is no boat and no wake.
When the next picture is taken the boat moves to position 4.
This picture is taken at position 1. There is no boat, but there is a wake.
When the next picture is taken the boat moves to position 6.
The next picture is taken at position 3. At that location there is no boat, but there is now a wake.
When the next picture is taken the boat moves to position 8.
The next picture is taken at position 5. At that location there is no boat, but there is now a
wake.
When the next picture is taken the boat moves to position 8.
The final picture is taken at position 10. At that location there is a boat.
The rescue team is now sent out. At this point the boat has moved to position 12. Luckily, the sample requests to send the team to that position.
Case 2
The boat started at position 2 with a speed of 5.
The ship will be at location 7 during the first picture. The picture is taken at location 1. There is a wake at that point.
The ship will be at location 12 during the second picture. The picture is taken at location 5.
There is a wake at that point.
The ship will be at location 17 during the third picture. The picture is taken at location 11. There is a wake at that point.
The ship will be at location 22 during the fourth picture. The picture is taken at location 18.
There is a wake at that point.
The ship will be at location 27 during the fifth picture. The picture is taken at location 26. There is a wake at that point.
The ship will be at location 32 when the sample sends out the rescue team. The rescue team is sent to location 32. There ship is at that location.
Hints
FLUSH Your Output: After every printf remember to fflush(stdout).
Track ALL Possibilities: Keep track of all the possible boats that exist. There should be 1 possibility for every combination of speed and starting location. When your program takes a photo and gets feedback. Eliminate all the boats that would have generated a different output.
Possibility Storage: You can store the possibilities in a 2D grid, indexed by the initial parameters of the ship, that contains a 0/1 indicating whether that possibility is still valid.
The Midpoint: Your program should guess the “midpoint”. The midpoint is a bit unusual in this problem. At each time the photo is taken there is a list of possible locations that the ship could be (based on the speed/location combinations that have not been invalidated).
The midpoint should be the ship location that roughly splits the “search space” (the location of all remaining valid combinations) in half.
Midpoint Candidates: Don’t guess random valid ship locations. Instead loop through the list of ship locations and check if that ship location works as a “midpoint”. The midpoints should only be considered from the still valid ships.
Extension: This problem was made easier from an alternative version where the max speed and location could be up to 1000. If you finish the version of the problem for homework try to consider how you could efficiently solve the problem for larger bounds.
Grading Criteria
● Good comments, whitespace, and variable names
○ 15 points
● Use standard input/output
○ 5 points
● No extra input output (e.g. input prompts, “Please enter the number of friends:”) ○ 5 points
● Flush your output every time your print
○ 5 points
● Track the valid ship combinations
○ 10 points
● Check the effectiveness of a possible midpoint
○ 5 points
● “Move” the ships after each photo
○ 5 points
● Programs will be tested on 10 cases
○ 5 points each
○ 6 of these cases will have fixed values
○ 4 of these cases will be adversarial
■ Without being certain of the location of the ship you will get the case wrong
No points will be awarded to programs that do not compile using “gcc -std=gnu11 -lm”.
Sometimes a requested technique will be given, and solutions without the requested technique will have their maximum points total reduced. For this problem use a binary search. Without this programs will earn at most 50 points!
Any case that causes a program to return a non-zero return code will be treated as wrong. Additionally, any case that takes longer than the maximum allowed time (the max of {5 times my solutions time, 10 seconds}) will also be treated as wrong.
No partial credit will be awarded for an incorrect case.
1 file (152.1KB)
