讲解：159.271、Computational Thinkin

159.271 Computational ThinkingAssignment 2Semester 1, 2019Your job for this assignment is to finish implementing a game we shall call “Collapse”. Submit both yourcode and your answers to non-code questions via stream.For the code questions (b) and (e), you only need to modify and submit optimizer.py.CollapseThe game works as follows: The player starts in the center of a collapsing building, which consists of a quadraticgrid of (2n + 1) × (2n + 1) rooms. Each room contains 0-9 units of supplies. With each move the player can goup, down, left or right and collect the supplies in the room entered. The entire row or column of rooms he justleft then collapses behind him and can no longer be entered. After 2n moves no further moves can be takenand the game ends. If the player has collected enough supplies to survive till the rescue team gets him after Ddays, he wins. If not he looses.A basic implementation of the game is provided on the course website. Run with the command:> python collapse.pyTo perform a speed test of your implementation, run> python optimizer.pyNote: You can also specify the board size and easy/hard mode. E.g.> python collapse.py 3 hardwill run the game with n = 3 using separate food and water supplies.Tasks [20 points]Currently the number of supplies needed to win the game is only based on n, and depending on how suppliesare distributed (this is done at random) it may be very easy or impossible to win.Your job is to calculate the maximum number of supplies that could be collected, and set the victoryrequirement (number of days till rescue) to this number. You will only need to edit optimizer.py for that.(a) Show that a greedy strategy (starting in the center or at one of the corners) will not work. For this, give a3 × 3 example with a unique optimal solution which includes neither the highest-valued side-room nor thehighest-valued corner room. Use each number from 1 to 8 once (center is empty). [1 point]To illustrate, in the example to the right, the unique optimal solution is7-8 whic代做159.271留学生作业、Computational Thinking作业代写、Python语言作业代写、Pythoh includes both the highest-valued side-room (7) and the highestvaluedcorner room (8). Here a greedy algorithm will find the optimalsolution. You need to create a different example where greedy fails.(b) Implement an algorithm which calculates the maximum number of supplies collectable (as described above).This algorithm should be efficient (≤ 0.1 sec) for n = 20. [8 points]Hint: Use dynamic programming techniques.(c) Analyze the worst case time complexity of your max food implementation, as a function of n. [1 point]Reminder: There are (2n + 1) × (2n + 1) rooms. Not n.To make the game more challenging, supplies are now separated into food and water. Each rooms containseither 0-9 units of food or 0-9 units of water. To survive, a player requires both food and water units equal tothe number D of days till rescue.1(d) Consider the following greedy strategy for dealing with (food, water) pairs instead of just supplies:For each room simply store the partial solution for which min(food, water) is maximal. E.g., giventhe choice of (7,5) and (6,6), only the latter is kept.Show that this strategy is not optimal, i.e., does not maximize min(food, water). [1 point]Hint: A counter-example requires n ≥ 2, but only one quadrant isrelevant (rest can be empty). An example where the strategy doeswork is shown on the right:3W 2W 5F4W 5F 4W@ 2F 4F(e) Implement an algorithm which calculates the maximum number of food and water collectable (i.e., maximizemin(food, water)). This algorithm should be efficient (≤ 1 sec) for n = 20. [8 points]Hint: When considering intermediate results, (food,water) pairs for which better pairs exist can be ignored.E.g. (7,5) is better than (7,4) but incomparable to (6,6).(f) Analyze the worst case time complexity of your advanced algorithm, as a function of n. [1 point]Speed RaceBe among the 3 fastest (correct, ≤ 60 sec) solutions of the advanced version for a size of n = 100 to automaticallygain full marks. Winners and their times will be published on Stream for bragging rights.2转自：http://www.7daixie.com/2019051813955072.html