[SOLVED] 代写 software Recursion Alchemists

Recursion Alchemists

Introduction
My fellow alchemists, it is time for us to cast our recursive spells to make magic potions! In front of you are some containers (test tube, flask, etc.) stored in 2D arrays. You will need to fill them up with potions and be careful not to spill out of the containers! Please pay special attention to the

Summon/Download Skeleton (Code)
Containers
You have many 2D arrays and each of them is with size ARRAY_SIZE tall by ARRAY_SIZE + 1 wide. Each array contains one or more containers. The surface of a container is marked with the WALL const symbols (const char WALL = ‘*’;). On the top of each container, a pair of RIM const symbols (const char RIM = ‘T’;) are used to mark the rim of the container. There are two other symbols: EMPTY (const char EMPTY = ‘ ‘;) and POTION (const char POTION = ‘o’;) which represents the empty space and magic potion respectively.
Not every container is valid to be used. Only containers that fulfill all the following conditions will be valid for the grading of this assignment:
•A container has exactly two RIM symbols. These symbols must be on the same row.
•Any part of a container will not appear in row 0.
•The RIM symbols must be placed at the top row of a container. No WALL symbol of that container will be placed at a higher row (smaller row number) than the RIM symbols.
•The two RIM symbols are separated by one or more white spaces (‘ ‘) and there should be no WALL symbol in between.
•If a container is “broken” (i.e. has opening(s) other than the one enclosed by the RIM symbols), the opening must be placed lower than the RIM symbols of that container (i.e. with higher row numbers). Thus, it is impossible to fully fill a broken container.
Here are some examples of valid container (letter spacing is stretched for illustration purpose only):
012345678901
0
1
2
3
4T T
5* *
6* *
7* *
8* *
9 *
0
1

012345678901
0
1
2
3
4 T T
5 * ****
6 ** * *
7 * ** *
8 **
9 ********
0
1

012345678901
0
1
2
3
4 T T
5 * *
6 **
7 * *
8 **
9 *********
0
1

012345678901
0
1
2
3
4 T T
5*
6
7
8
9
0
1

012345678901
0
1
2
3
4 T T
5 ***
6 **
7 * *
8 **
9 *********
0
1

012345678901
0
1
2
3
4 TT
5 *
6 *
7 *
8 *
9 **********
0
1

Filling Potion
Potion should be fully filled into these containers after calling the recursive functions. Potion is denoted by the POTION symbol (const char POTION = ‘o’;). The following examples show what the containers look like after filling up with potions. (In these example, let’s assume that the potions are pouring from the position shaded with yellow colour.) You can see that the potion filled should not exceed the rim of a container.
012345678901
0
1
2
3
4ToT
5*o*
6*o*
7*o*
8*o*
9 *
0
1

012345678901
0
1
2 T T
3 * *
4 ***ToT
5*o*
6*o*
7 *ooo*
8*ooooo*
9 *********
0
1

012345678901
0
1
2
3
4 ToooT
5 *ooo*
6 *oooo*
7 *ooooo*
8 *oooooo*
9 *********
0
1

012345678901
0
1
2
3
4 ToT
5 ***
6 **
7 * *
8 **
9 *********
0
1

Spilling out
If the potion is not filled right above the space between the RIM symbols (in the above examples, row 4 column 6 is the space between the rim symbols), the potion will be spilled out above and somehow reach the bottom row of the array (row ARRAY_SIZE – 1 (i.e. 11)), or the side edge of the array (col 0 or col ARRAY_SIZE – 1).
Or, when a container has more than one opening, also known as “broken”, potion will be spilled out too.
spill out: broken container
012345678901
0
1
2
3
4T T
5* *
6* *
7*
8* *
9 *
0
1

spill out: drop outside
012345678901
0
1
2
3
4T T
5* *
6* *
7* *
8* *
9 *
0
1

spill out: drop outside
012345678901
0
1
2
3
4T T
5* *
6* *
7* *
8* *
9 *
0
1

spill out: broken container
012345678901
0
1
2
3
4 T T
5****** ******
6*
7*************
8
9
0
1

Tasks
There are four functions for you to complete. Each of these functions has to be implemented as a recursive function. You are NOT allowed to change the function prototype (you cannot change the return type nor add parameters with default values).
•cleanup() — to clean up the container(s)
Assumptions for calling the function cleanup() in the main function or the grading process:
•The array given is with size ARRAY_SIZE + 1 wide and ARRAY_SIZE tall.
•The array contains only EMPTY, WALL, RIM, POTION symbols.
•
•warmup_fill() — to fill a container with RIM level given
Assumptions for calling the function warmup_fill() in the main function or the grading process:
•The array given is with size ARRAY_SIZE + 1 wide and ARRAY_SIZE tall.
•The array contains only EMPTY, WALL, RIM symbols. No POTION symbol.
•An array can have more than one containers.
•An array can only have valid containers.
•A container has exactly one opening which is enclosed by the RIM symbols.
•There is only 1 space between the RIM symbols of a container.
•Potion is always poured from row = 0, col = x, where the opening of at least one container is at col = x.
•From the position of where the potion is dropped on to the opening of the container to be filled, there are only EMPTY symbols.
•Spilling out would never happen.
•All containers are empty (i.e. no POTION symbol) before calling the function.
•The value for rim_level is always given correctly to label the rim level of the intended container.
•The following would NOT happen when testing warmup_fill
❌ The array has an invalid container. (The RIM symbols are not at the top of the container.) 012345678901
•0
•1
•2***
•3* *
•4T T * *
•5* * * *
•6* * * *
•7* *** *
•8* *
•9*******
•0
•1
•


❌ The array has an “broken” container with more than one opening. (Another opening at row 7 and col 4). 012345678901
•0
•1
•2
•3
•4T T
•5* *
•6* *
•7 *
•8* *
•9 *********
•0
•1
•


❌ A non-EMPTY symbol is placed at row 2 col 6, which blocks the potion poured.
•❌ The container at row 2 col 6 is invalid. Array can contain only valid container(s). 012345678901
•0
•1
•2 *
•3
•4T T
•5* *
•6* *
•7 * *
•8* *
•9 *********
•0
•1
•


❌ A non-EMPTY symbol is placed at row 2 col 6, which blocks the potion poured. The container at row 2 col 6 is valid. 012345678901
•0
•1 T T
•2 *****
•3
•4T T
•5* *
•6* *
•7 * *
•8* *
•9 *********
•0
•1
•
•
simple_fill() — to fill a container with NO rim level given
Assumptions for calling the function simple_fill() in the main function or the grading process:
(They are exactly the same as warmup_fill except that there is no rim_level supplied.)
•The array given is with size ARRAY_SIZE + 1 wide and ARRAY_SIZE tall.
•The array contains only EMPTY, WALL, RIM symbols. No POTION symbol.
•An array can have more than one containers.
•An array can only have valid containers.
•A container has exactly one opening which is enclosed by the RIM symbols.
•There is only 1 space between the RIM symbols of a container.
•Potion is always poured from row = 0, col = x, where the opening of at least one container is at col = x.
•From the position of where the potion is dropped to the opening of the container to be filled, there are only EMPTY symbols.
•Spilling out would never happen.
•All containers given are empty (array has no POTION symbol) before calling the function.
•The arrays that will not be tested for warmup_fill() will also NOT be tested for simple_fill
Do you want to try this case before saying you are done?
012345678901
•0
•1T T T T
•2 * *
•3
•4T T
•5* *
•6 *
•7
•8
•9
•0
•1
•
•
advanced_fill() — to fill a container with NO rim level given, but also handling wide-rim container(s) and spilling out
This task is rather difficult to finish it perfectly. We expect a small portion of students can finish it.
Assumptions for calling the function advanced_fill() in the main function or the grading process:
•The array given is with size ARRAY_SIZE + 1 wide and ARRAY_SIZE tall.
•The array contains only EMPTY, WALL, RIM symbols. No POTION symbol.
•An array can have more than one containers. An array contains exactly one container.
•An array can only have valid containers.
•A container has exactly one opening which is enclosed by the rim symbol. The container may be broken.
•The space between the RIM of a container is always 1. The width of the opening can be larger than 1.
•Potion is always poured from row = 0, col = x, where the opening of at least one container is at col = x. Potion is always poured from row = 0.
•From the position of where the potion is dropped to the opening of the container to be filled, there are only EMPTY symbols.
•Spill out condition would never happen. Spilling out may happen. If spilling out occurs, all POTION symbols should be removed.
•The container is empty (array has no POTION symbol) before calling the function.
•The following would NOT happen when testing advanced_fill
❌ The array has more than one container. 012345678901
•0
•1
•2
•3
•4T T
•5* *
•6***** *
•7 *
•8T T** *
•9* **********
•0***
•1
•


❌ The array has an invalid container. The second opening is not lower than the RIM symbols. (If the WALL symbols at (row 4, col 9) and (row 4, col 11) are removed, it will then be valid with spilling out.) 012345678901
•0
•1
•2
•3
•4 T T **
•5 * * **
•6 * ****
•7**
•8 * **
•9*********
•0
•1
•


❌ The container at row 2 col 6 is invalid. (Note: array can contain only valid containers.) 012345678901
•0
•1
•2 *
•3
•4T T
•5* *
•6* *
•7 * *
•8* *
•9 *********
•0
•1
•
Grading and Dos/Donts
The points allocated for each of the functions are given below. For the cleanup() function we will check the return value. For the rest of the functions, we will not. During grading, we will use some other arrays such that the outputs of the functions will be unique and well defined. We will prepare a number of test cases for each functions. Each test case will give you certain points.
Functions
Marks
cleanup()
20
warmup_fill()
36
simple_fill()
28
advanced_fill()
16
Even your solution may not work for ALL cases, you still should try for getting partial credits.
Exception: if your advanced_fill() always detect spill out and not filling the container regardless what container it is, no points will be given.
You should also pay attention to the following rules:
•You must not change the function prototype, including the return type of the function, or adding parameters with or without default values, or deleteing parameters.
•You must use recursion to implement all four functions.
•You must not use any loop (for loop, while loop, do-while loop, or goto).
•You must not use or define any non-const global variables.
•You must not use or define any static variables (i.e. the keyword static).
•You may create your own helper functions.
•You may call other recursive functions in different parts.
Sample Program
Compare your output against the demo program so that you will know if you obtain the correct basic testing results.
Sample Program
Submission
Deadline
23:59:00, Nov 10 (Sun), 2019
Canvas Submission
1. Submit only the file “pa2.cpp” through CANVAS to the folder “Assignment2”. The filename has to be exactly the same and you should NOT zip/compress the file.
2. Make sure your source file can be successfully compiled. It is required that your program can be compiled and run successfully in the pre-installed Eclipse environment on our lab machines. If we cannot even compile your source file, your work will not be graded. Therefore, you should at least put in dummy implementations to the parts that you cannot finish so that there will be no compilation error.
3. Make sure you actually upload the correct version of your source files – we only grade what you upload. Some students in the past submitted an empty file or a wrong file or an exe file which is worth zero mark. So you are advised to download and double-check the file you submit.
4. You may submit your file multiple times, but only the latest version will be graded.
5. Submit early to avoid any last-minute problem. Only canvas submissions will be accepted.
6. Note: Canvas may append a number to the filename of the file you submit. E.g., pa1-1.cpp. It is OK as long as you have named your file as pa1.cpp when you submit it.
Late Submission Policy
There will be a penalty of -1 point (out of a maximum 100 points) for every minute you are late. For instance, since the deadline of assignment 2 is 23:59:00 on Nov 10, if you submit your solution at 1:00:00 on Nov 11, there will be a penalty of -61 points for your assignment. However, the lowest grade you may get from an assignment is zero: any negative score after the deduction due to late penalty will be reset to zero. However, all submissions will be subject to our plagiarism detection software, and you will get the cheating penalty as described in Honor Code if you cheat and get caught.
FAQ
•Can my required function calls a helper function which is recursive but my function is not recursive?
•
•Answer: No. Your required function must be a recursive function. It can call a helper function where the helper function can be a recursive function or a non recursive function.
•In the funciton cleanup, do I need to manually print how many POTION symbols be cleaned up? I don’t see any code there but there is a line in the demo program showing that..
•
•Answer: No you don’t. Printing is not required in all functions. The demo program and the skeleton is slightly different. You are required to check the return value of cleanup on your own by modifying the main or the function fill.
•Will the variable ARRAY_SIZE change?
•
•Yes, we might change the value ARRAY_SIZE when we grade the program. So make sure your code works with a different value of ARRAY_SIZE. Do not hard code!
Hint
The assignment is not easy. We are here to provide you some hints to begin with. Hopefully these allow you to bridge the gap.

cleanup:
There are two important issues you need to take care:
1) The direction of the recursion: if you attempt to recursively walk to four direction up/down/left/right, it would end up in a stack-overflow and lead to a segmentation fault. It is due to a ping-pong effect as explained at lab. Instead you should go to only right and down to avoid this ping-pong effect.

2) The use of return value. The function should return the number of POTION symbols cleaned up. In a recursive call, you need to compute this by looking at the two numbers returned from right/down recursive calls.

advanced_fill:

We suggest you complete the function in two phases and using the return value:
1. Try filling a non-broken container: Evolved from simple_fill(), your function should be able to detect where the rim is and when to start filling POTION and when to stop.
You may also consider returning different integer values to represent different status/actions.
Then, you may use the returned value from the recursive call(s) to judge whether to continue to fill with potion or what to do next.
2. When to cleanup: You may also consider using the return value of your function to know if it spills out and call the function cleanup appropriately.