[SOLVED] algorithm game Q3 The coin game with DP (20 marks)

Q3 The coin game with DP (20 marks)

Alice and Bob are playing a game using a bunch of coins. The players pick several coins out of the bunch in turn. Each time a player is allowed to pick 1, 2 or 4 coins, and the player that gets the last coin is the winner. Assume that both players are very smart and he/she will try his/her best to work out a strategy to win the game. We suppose that Alice is always the first player to pick. For example, if there are 2 coins, Alice will definitely pick 2 coins and win. If there are 3 coins and Alice is still the first player to pick, no matter she picks 1 or 2 coins, Bob will get the last coin and win the game. Suppose Alice plays first. Given the number of coins, you are required to write a function coingame to calculate the winner of the game, and calculate how many different strategies there are for he/she to win the game. You must use dynamic programming to solve the problem.
Recall that we have studied this exact problem in the tutorial on recursion (week 3). A solution which uses recursion and memoisation is provided in the solutions. We recommend you study this solution and use it as a starting point to design your answer to this question.

Q3.1 (15 marks)
Design and implement a DP agorithm that solves the coin game, returning the name of the winner and the number of ways to win in a tuple (see unit tests).
In[]:
def coingame_dp(n):
#TODO write your program here
pass

We provide unit tests. Your program must pass all tests to receive full marks. For reference, the solution code passes the unit tests in less than .1 seconds. If your code requires a significant longer time to run, then it may be bugged, or your algorithm may not be well designed.
In[]:
import unittest

class TestCoinGameDP(unittest.TestCase):

def setUp(self):
self.results = {}
self.results[1] = (Alice, 1)
self.results[2] = (Alice, 1)
self.results[3] = (Bob, 2)
self.results[4] = (Alice, 3)
self.results[5] = (Alice, 2)
self.results[6] = (Bob, 6)
self.results[7] = (Alice, 8)
self.results[8] = (Alice, 6)
self.results[9] = (Bob, 16)
self.results[10] = (Alice, 22)
self.results[11] = (Alice, 16)
self.results[12] = (Bob, 44)
self.results[13] = (Alice, 60)
self.results[14] = (Alice, 44)
self.results[15] = (Bob, 120)
self.results[16] = (Alice, 164)
self.results[17] = (Alice, 120)
self.results[18] = (Bob, 328)
self.results[19] = (Alice, 448)
self.results[20] = (Alice, 328)
self.results[21] = (Bob, 896)
self.results[22] = (Alice, 1224)
self.results[23] = (Alice, 896)
self.results[24] = (Bob, 2448)
self.results[25] = (Alice, 3344)
self.results[26] = (Alice, 2448)
self.results[27] = (Bob, 6688)
self.results[28] = (Alice, 9136)
self.results[29] = (Alice, 6688)
self.results[30] = (Bob, 18272)
self.results[40] = (Alice, 508992)
self.results[50] = (Alice, 7598336)
self.results[60] = (Bob, 423324672)
self.results[70] = (Alice, 11792304128)
self.results[80] = (Alice, 176037912576)
self.results[90] = (Bob, 9807567290368)
self.results[100] = (Alice, 273203580829696)
self.results[200] = (Alice, 50717410803867800170053763072)
self.results[300] = (Bob, 35137860024320654767123240252452212156923904)
self.results[400] = (Alice, 12172044939985318121217632883037128067112110241728998408192)
self.results[500] = (Alice, 2259613880863432185333407366636641669225956214590624488935828183316430848)
self.results[600] = (Bob, 1565497824047757098853076463514705300760117522938887492905316777579402752568620669206528)
self.results[700] = (Alice, 542301376764817296788256038656063404539679582294584091216307665572051019970248287959790106373831786496)
self.results[800] = (Alice, 100672625231911868509461983049768490801620992125878873798574198482054900530946811919580621963062828844173211809611776)
self.results[900] = (Bob, 69747657808470792993571698891480283998707769118504195166437962610627045243267826073735919482016866969201130852288836034954604314624)
self.results[1000] = (Alice, 24161164758349228765738655081408807771665697276061184615705398268360250725671539630760599013630058315473483253192981901287230756893327309148258304)
self.results[2000] = (Alice, 396661484865945326868439307834743952147359375183296199942277476350636030685911983188276040725126100519050912240086194211364248229388192976926358795949807569036044358610748916606991383805388551853725385163670661596115312596297132009955487413571061758255228860686818380645028683652587503747072)
self.results[3000] = (Bob, 24303551788941075812750660781936541693950975194766470163406311461746332909948113515536719574850375358979208749659490019386072425174586371747257678461784981959351599004508086026515975051856875019010144152617695974608489747173983921877785718594408217616454474607509785631685346581340833813704353586111854925693477708845752408887232107734894838114689602827511755056543490591089878548909730892827589954151163351138464837086413800308889092096)
self.results[4000] = (Alice, 744542452561735048046816573259392546255312264283295089187576849726763617585783303843290947921750259883312818408984114029769116461107542451015314474832379568423331647997727048270788803633152018689353776853995592188502570654921153574518820461334821920954932831112574314327544124367025986234439237317904415702879850348691400871509227872113468020260790385235031774679808807720560302290000065422031694740758872473281156035450525182132290806119907768922158826543771860586540293908633463377017085907083688014367315931128689378012402884562249953699541506104741585013668062169689493384200192)
self.results[5000] = (Alice, 12223388968729854484003335639760244528310369558116862461327206627443193901925949139110283045047025302963900946903525180123196926654382605660037624490502146330512506651027762166466722002957630211257509625155027910678828987824973723127497473790028902881313748571985927714327790592003114991133535700648607569114243298290037445678586721979545726889053327397244643938174471784166267100020484468167553422978790270505275872940256735670772841704535174495116320342303086240071805298083389188287144992018094061270621415554005902244936962611090473246250871518677588141372677702379810510178823140140326866405199473292159621622045939835524870591293539941270830639025464814824565695194020064139419799459569153793582285285267021617127229489152)
self.results[6000] = (Bob, 748930204146981047220328332828627818500639604968645739906754754844174660738182843817829644241165751832790847701053237845610297537136625875558896885557501728508495822446611440957880123424219317987128541681846951627107572500470727983409748139937276038615815070411655619608682531303196641468044739169966900451894102623372254102956552379954244575301920420204914966444061085266698047314217163285675301050418588992521057882804603531529436597467362486906173086096207366794399722990740410114574945984725393084655119994682309954902478520100724012310197897272374077908430311443013459100015793029160572430618417791299847611251454139294979226253618842670990274404315117146875538607185660277213304728575247610292467595424884734632887522303875516567272764071184549926626747598412453536938266741101748836550702990886318306120407673880429891650243945439319558864304000914440725872957718528)
self.results[7000] = (Alice, 22943573673329732131708046425139619936807552411929791404428018567732656944887767969562573832964358245535135772171744222221092635498169099141193653224628939553293796856930050432868898075242289050166728364260274079194307272408706657877434344840206902785966729866743631682966222418197940896395642533286962689052557112027343908967609785872234804191115005726114420976811790557798667839382995697394655253628599603897341094324541611431999491004362798875333443222618840984368740328584973708060686988599468068216685158183435146655978696100364495185829903590658471797145346576306282102047022485620117799683858575556418005111655805996551120884288413790817507876285505250833478210865824743116706402620519157491846481956948145969757511252101513227729583062863706532980778873930836679665907152308396765864863257107535137704124394552318754441918511366848869982958200571658982024331239693510831958089766477721151526322885243409517154023793364186785699673017019070844173068791580319776476778109592675896568611908890657809742917485461504)
self.results[8000] = (Alice, 376671906856198364890418954716617045463584557745559258227503146622262017561245444774066362158736264849127998115162131031133463155933223067768192318192322058611303140164898544780318819595111742264977594710874510663223204127858472098764870245165394778472320435835833853899417355213802455871364710599532777823033476219651483607581906394471281395375703363034964185772032893651059539947512212238018755580779270148059974228552960853039866291834750643675557184167920639020283704063249540262694084700860132197910446054879676639591474118084196192271220051845815326352859884845018392896018721680203855521997619642898467504117221807777172585261979018383631832103116165839038267278839410507481090203646073545557830389312521599144998261477037680117456085290284740960452447872368302765706435336321260931515507745847722345538430684986027707783925672286625696811040070067717042995754403398405483220267904826233845551873156706990320436469693264104759971059157415528029076296470783685265755453246458363550372081565101234989059311926588676303444711974839894707590512155600448383121526089054717013823247958837375757013486395867459706700832866125986759031363399354744359895878416203776)
self.results[9000] = (Bob, 23078785173238145502007095497817479715879683842709826039761165819045193113231328199247086180022059321731980822957889995398499038788690487283902136851282867361174575635296501597195009104274611544305987524342763558083675908534602942709163632338792207471597224489349000873020874263219223362990141319707257261294713424281788190817308559894781621243061608055950655266196901832770559928739785081157947775753863577573530231167477254619554952702292680340244281710839489908045345164950362759084893645626928023535902469917704264318898179273948814204353987667431734331063032011977538931837814807305049184217392758801252859797346138698791759447882833919425254046266875315041350144386994576690911488901390250726996845190761069005650492676068683611730379562943372812233066010744346045150467448272328887225778476093262080554379197111090229090239356888954248022255190712383894391797131187456437225007401448353688729673685268077873074350687142102892824162397564951240253719087208782264627477722809586168668701302706991022558743008740154427414747770281538895030632974953613421193708790268133342797403994220983150924720237704679904104799309938701970764632224822373852056780576958399139362716209445610383026773945722482954827353592679394048323331229398152127546657563356846158382219911916825090352700352901116329100003843952869376)
self.results[10000] = (Alice, 707021568874020877025723682789631973531064312499959637094986151237944838029682769809467732631358600650793902391117731557963898064829101939240046060562498207171818141815307062862315005940715230326651910296602428693421246087775197809119705174505759600125301569534436432653072639059750613356398490545076771970235089424576215784821133750745058107141403069827288119393306127966541223511661972594529964810215427692050331698558449240526980295323883153653597141321130673008627694863567136384340466551030260053919590734879339270515690932266831658240619204517640711303977481215563912132280942734521481003880313766913515990006766822256768709678593841869269199991442029334501808621697593581579202444728218246947141992855177702297374308370032696632722992329355380674849516587332827655602784203636926058223384105240196082873411624594966291709071867130182047070177804867182328114658964617001109956002633693294882215281889704426910512074628419110983446567547329015871749512066120893066634257450989881807554917547996900978082030286510176758099860620634597169400243838903014801389432765179242630621682358461409511700594316525837237239301463988797952243489404239948950897636898721726790738919399909185651379378877936917507918205958021878993560328028259931427229706687833679732083121501760465623698970563494463591575666700995710926065477008198025224636632571716623405469639960589229467625143044612472874745560162475919830283050403663754471832210440053127522516392824279138304)

def testcoingame_dp(self):
for key in self.results:
self.assertEqual(coingame_dp(key), self.results[key])
In[]:
testgame = TestCoinGameDP()
suite = unittest.TestLoader().loadTestsFromModule(testgame)
unittest.TextTestRunner().run(suite)

Q3.2 (5 marks)
What is the worst-case runtime complexity of your algorithm? Prove your answer.

(write your answer here)