Assignment 4: Strings and Coins Due: 20:00, Thu 8 Nov 2018 Full marks: 100 Introduction In this assignment, you will use functions to implement a game called Strings and Coins. At the beginning of the game, there is a network of coins, each connected by four strings. Two players take turns cutting a string in the network. When a cut leaves a coin with no strings connected, the player scores one point and takes an extra turn. Note that the player can get more than two consecutive turns as long as s/he scores again in every turn. The game ends when all strings are cut, and the player with more points wins. It is a draw if two players get the same points. Figure 1 shows an example game network. We use the symbol $ to denote coins,--and I to denote the strings, and # to denote the "wall (that is, the network boundary) In Figure 1(b), the top-left coin is already disconnected (assumed to be by Player 1), and the bottom-right coin is one string from being disconnected. After some | # 4--$--$--# turns | # $ $--# 4--$--$--# # Player 1 score: 0 # I # Player 1 score: 1 Figure 1: (a) Initial network of coins; (b) Network after some turns Program Specification This section describes the game network representation, some necessary functions, and program flow Game Network Representation There are 12 strings initially in the network. Therefore, we use integers 1 to 12 to denote these string positions, as illustrated in Figure 2. The positions are basically ordered top-to-bottom, left-to-right. D (k # Player 1 score: 1 12 Figure 2: Numbers for String Positions To encode the whole network and the players scores in a game, we use a 14-digit integer did2dzd4dzdtdjdgdgd1od11di2d13di4. The first 12 digits di ...d12 are either 0 or 1, denoting whether the string in the corresponding positions 1 to 12 are cut or not. (That is, di0 means the string in positioni is already cut; d1 means position remains uncut.) The last two digits d13 and Copyright 2018 CSE, CUHK Page 1 of 5