FIT2004 S2/2019: Assignment 2Nathan CompanezDEADLINE: Friday 6th September 2019 23:55:00 AESTLATE SUBMISSION PENALTY: 10% penalty per day. Submissions more than 7 dayslate are generally not accepted. The number of days late is rounded up, e.g. 5 hours latemeans 1 day late, 27 hours late is 2 days late. For special consideration, please completeand send the in-semester special consideration form with appropriate supporting documentbefore the deadline to [email protected] CRITERIA: It is required that you implement this exercise strictlyusing Python programming language (version should not be earlier than 3.5). Thispractical work will be marked on the time complexity, space complexity and functionalityof your program.Your program will be tested using automated test scripts. It is therefore critically impor-tant that you name your files and functions as specified in this document. If you do not, itwill make your submission difficult to mark, and you will be penalised.SUBMISSION REQUIREMENT: You will submit a zipped file (namedstudentId_A2.zip, e.g. if your student id is XXXX, the name of zipped file must beXXXX_A2.zip). It should contain a single python file, assignment2.py, and a single pdffile, description.pdfPLAGIARISM: The assignments will be checked for plagiarism using an advanced pla-giarism detector. Last year, many students were detected by the plagiarism detector andalmost all got zero mark for the assignment and, as a result, many failed the unit. “Helping”others is NOT ACCEPTED. Please do not share your solutions partially or/and completelyto others. If someone asks you for help, ask them to visit us during consultation hours forhelp.1StoryNathan showed up to last week’s games night expecting a glorious victory, and sweet re-venge on all his friends. Alas, even with the help of your algorithm, he lost. Someone elsehad an even faster algorithm! But that is a problem for another time.A new week, a new game. This time, the group will be playing the game Snake-words.Nathan again has requested your help, and has actually invited you to come along in casethe algorithm needs modifications on the night.The two of you arrive early, and the host this week invites you to play a quick game,called the coin taking game before the other guests arrive. Nathan agrees, but you de-cline politely so you can work on your Snake-words algorithm.After Nathan has lost several times, you realise that the coin taking game is a perfectcandidate for a technique you have just learnt, and decide to code up a solution for it inaddition to your Snake-words algorithm.BackgroundCoin taking gameThis game is played between 2 players, player 1 and player 2. There are two piles of coins.The values of a coin can be any integer. Both players know the values of all coins in bothpiles. Player 1 makes the first move, and play alternates between the players. A moveconsists of taking a coin from the top of either of the piles (either player can take fromeither pile). The game ends when both piles are empty. A player’s score is the sum of thevalues of all the coins they took during the game. The player with the higher score wins.Snake-wordsThis game is played on n× n grid of lowercase English letters, and involves finding wordsin this grid. We say this grid contains a word if the word exists as a chain in the grid.A chain is a sequence of letters a1, a2, …an in the grid which are sequentially adjacent. Inother words, the i+1th letter is vertically, horizontally or diagonally adjacent to the ith letter.You may not use the same grid cell for letter i and letter i + 1, however, you are allowedto re-use a letter in a chain.2Algorithm Descriptions (2 mark)For each of the two tasks, you must also write a brief description of your algorithm. The totallength should be no more than 500 words.These two descriptions will be submitted in the pdf file descriptions.pdf mentioned in the”Submission Requirement” section. These descriptions should explain the steps your algorithmtakes to solve the problem, and the complexity of each step. Please try to keep these descriptionsat a fairly high level, talk about your data structures and algorithms, not individual variablesor lines of code.1 Winning the coin taking gameIn this task you will write a function best_score(pile1, pile2) to determine optimal playfor the coin taking game. It will determine the highest score which can be achieved by player1, assuming that both players play optimally.1.1 InputTwo lists, pile1 and pile2. These lists contain integers which represent the values of the coinsin the game. The numbers in pile1 are the values of coins in the first pile, where pile1[i]is the value of the coin with i coins beneath it in the pile. pile2 represents the coins in thesecond pile in the same way. The piles may be empty.1.2 OutputA tuple with two elements. The first is a single number which represents the highest scorewhich player 1 can achieve. The second represents the choices made by both players during thegame (assuming optimal play).The choices are represented by a list containing only the numbers 1 and 2, where a 1 indicatesthat the player took the top coin from pile1 on their turn, and 2 indicates that the playertook the top coin from pile2 on their turn.If multiple sequences of choices are optimal, any of these sequences is acceptable.Example:• Calling best_score([20,5], [1]) would return (21, [2,1,1]). It is optimal for player1 to take the coin of value 1, forcing player 2 to take the coin of value 5, which allowsplayer 1 to take the coin of value 20.• Calling best_score([1,2,3], [1]) would return (4, [1,1,1,2])• Calling best_score([5,8,2,4,1,10,2], [6,2,4,5,6,9,8]) would return (42, [2, 2,2, 2, 2, 1, 1, 1, 2, 2, 1, 1, 1, 1])31.3 Complexitybest_score must run in O(NM), where• N is the number of elements in pile1• M is the number of elements in pile2best_score should use no more than O(NM) auxiliary space42 Finding Snakey wordsYou need to be able to find a word in a given Snake-words grid. To do this, you will write afunction is_in(grid, word)2.1 Inputgrid is a list of length N , each element of which is a list of length N . The elements of theinternal lists are all single lowercase english alphabet characters (a-z). grid[i][j] representsthe letter in the ith row and jth column of grid.In other words, grid is a N ×N table of letters, represented as a list of lists.word is a sequence of lowercase English characters (a-z). A word does not contain any kind ofpunctuation or other non-alphabet symbols.2.2 OutputIf grid does not contain word (as described in the Background section) then is_in shouldreturn False. If grid does contain word, is_in should return a list of tuples, which repre-sent the grid cells that correspond to the word. The ith tuple corresponds to (row, column)of the ith letter of word in grid.If a word appears in multiple different ways in the grid, any of the ways it can appear areacceptable answersExample:If the following variables were defined:grid = [[‘a’,‘b’,‘c’,‘d’],[‘e’,‘a’,‘p’,‘f’],[‘e’,‘p’,‘g’,‘h’],[‘l’,‘i’,‘j’,‘k’]]word1 = ‘apple’word2 = ‘xylophone’is_in(grid, word1) should return [(1,1), (1,2), (2,1), (3,0), (2,0)]For your reference, the word’s position in the grid is shown belowis_in(grid, word2) should return False2.3 Complexityis_in must run in O(KN2), where5• K is the number of characters in word• N is the length of grid (this means that there are N2 elements in grid)is_in should use no more than O(KN2) auxiliary spaceWarningFor all assignments in this unit, you may not use python dictionaries or sets. For all assignmentsin this unit, please ensure that you carefully check the complexity of each python function thatyou use. Common examples which cause students to lose marks are list slicing, inserting ordeleting elements in a list, using the in keyword to check for membership of an iterable, orbuilding a string using repeated concatenation of characters. These are just a few examples, sobe careful. Remember, you are responsible for the complexity of
every line of code you write!6
