In python3

anything but string indexing, lists, list indexing, or recursion

camelCase please

4. The 112 Game [70 pts] Note: This is a long problem with many parts. Carefully read this entire writeup first! Your goal is reading is to make sure you understand all of the following: 1. How to play the game (on paper, for example). 2. How the game information will be stored on the computer. 3. How all the functions described here fit together into a cohesive design. Game Play In this problem, we will implement a version of the world-famous and endlessly amusing 112 game. Here is how the game works: Start with a board with N positions, something like a 1xN tic-tac-toe board with all positions empty. There are two players who alternate turns. On each turn, the current player must place either a 1 or a 2 in any unoccupied position. If the move results in the number 112 among any three contiguous positions, then the player who just moved wins the game. If the board is full without any 112's, then it is a tie. So, for example, here is a short game on a board of size 5: 2 2 1 2 - Start with an empty board Player 1, at position 4 places a 2 Player 2, at position 1, places a 22 Player 1, at position 3, places a 12 - Player 2, at position 2places a 1 2 1 1 2 And Player 2 wins!!! Specifying a Match Now, while it would be interesting to write an interactive game (either text-based in the console or with graphics) that people could play, here we will instead slightly adapt the problem so that a computer autograder can easily autograde it. So instead of playing a game interactively, we will write a function called play112 that takes a specification of a game and simply returns the outcome of that game. A game specification has to include the size of the board, which we will restrict to being an integer between 1 and 9 inclusive, and then a series of moves, which will be two values -- the position (an integer from 1 to boardSize, where 1 is the leftmost position) and the value to place there (either a 1 or a 2). The natural representation in Python for this would be a list. So the game above would be represented by this list: [5, 4, 2, 1,2,3,1,2,11 This list indicates that the board is of size 5, then specifies each move -- at position 4 place a 2 at position 1 place a 2, and so on. The list does not include the player numbers, because we know these alternate, starting from player 1. Using a list this way is natural, only we have not yet covered lists. We need to find a different, less natural, less ideal, but workable way to represent these values using the types that we currently know. We do have integers. So we can represent that same list of digits (and notice they are all single digits, and then all are non-zero) as a single integer value: 542123121 Again, this may not be ideal, but it definitely works. Storing the Board Now that we can specify game play, we also need a way to store the board as the game progresses. Again, we are limited to integers, so we will store the entire board as a single integer. We need to store 1's and 2's where they were played, but we also need to store empty values. It may seem like o is a good idea for these, only that can lead to some oddness due to leading O's not being displayed. For example, if o's were the empty spaces, then the board above would be represented like the values in the third column of this table: 0 Start with an empty board Player 1 at position 4 places a - 1 - 2 - 12 2 - - 2 - 20020 2 - 1 2 - Player 2, at position 1, places a 2 Player 1, at position 3 places a 20120 1 Player 2, at position 2, places a 1 2 1 1 2 - 21120 And Player 2 wins!!! See how the board is initially o, even though it represents 5 blank spaces? This works, because o is the same as 00000, but it's not necessarily intuitive. It's also worth noting that we are only talking about intuitive for the programmer (that is, you!). Users would never know how you chose to represent the board internally in your program. Even so, good decisions here will lead to clearer, easier to understand, easier to debug code. In any case, for these reasons, instead of O, we will use 3 to represent a blank space. Thus, here are the integer representations of the boards in the example game: 88888 - 2 - 1 88828 2- - 2 - 28828 Start with an empty board Player 1, at position 4 places a 12 Player 2, at position 1, places a 2 Player 1, at position 3, places a 1 Player 2, at position 2, places a 1 And Player 2 wins!!! 2 - 1 2 - 28128 2 1 1 2 - 21128 Return values from play112 Now that we have a game specification, and a way to store a board, what should play112(542123121) return? Any call to play112 will return a single string (ok, we'll bend our limitation about strings just so we can more easily autograde) composed of two parts: the board as it existed at the end of the game, and then the result of the game. And so: play112(542123121) returns: "21128: Player 2 wins!" Compare this result to the table above to confirm that 21128 represents the last board of the game, and also that Player 2 in fact won. Ok, so now we are ready for a formal problem description. Here it is: write the function play112(gameSpec). It takes a gameSpec as defined above, and it returns a string composed of the final board, a colon (), a space, and then the outcome of the game. Note that your code must match this spec exactly, character-for-character (no extra spaces, no incorrect upper or lower cases, etc). Here are the possible outcomes of the game: Player 1 wins! Player 1 played a move that generated 112, and won! Player 2 wins! Player 2 played a move that generated 112, and won! Player 1: move must be 1 or 2 Player 1 played a piece other than a 1 or 2, and lost. Player 2: move must be 1 or 2 Player 2 played a piece other than a 1 or 2, and lost. Player 1: occupied! Player 1 played a piece into an occupied position, and lost. Player 2: occupied! Player 2 played a piece into an occupied position, and lost. Player 1 played a piece into a position not on the board, and Player 1: offboard! lost. Player 2: offboard! Player 2 played a piece into a position not on the board, and lost. Tie! Neither player has won or lost, and the board is full. Unfinished! None of the preced cases ies. Note that the game stops immediately after a win or loss, even if the game specification contains more moves. Here is a test function for you: def testPlay112): print("Testing play1120)...", end="") assert(play1125) == "88888: Unfinished!") assert(play112 521) == "81888: Unfinished!") assert (play112 52112 ) == "21888: Unfinished!") assert(play1125211231) == "21188: Unfinished!") assert(play112 521123142 ) == "21128: Player 2 wins!") assert(play112 521123151 ) == "21181: Unfinished!") assert(play112 52112315142 ) == "21121: Player 1 wins!") assert(play112 523 ) == "88888: Player 1: move must be 1 or 2!") assert(play112 51223 ) == "28888: Player 2: move must be 1 or 2!") assert (play112 51211 ) "28888: Player 2: occupied !") assert(play112 5122221 ) == "22888: Player 1: occupied!") assert(play11251261 ) == "28888: Player 2: offboard!") assert(play112 51122324152) == "12212: Tie!") print('Passed!' == Study the test function carefully. Manually confirm every single line of it, so that you understand why each given call to play112 produces the expected result. Helper Functions and Top Down Design So now what? At this stage of the course, this is a daunting task, perhaps too daunting without some more guidance. But it gives you your first real taste of what we are trying to teach you. This course is not about how a mod operator or a for loop works. Instead, this course is meant to teach you how to solve problems. And that requires higher-level design, abstraction, problem-solving, and so on. In particular, given a problem such as this, we will use a top-down design approach. So we will try to break this problem down into smaller parts, and to break those down into even smaller parts, until we get to problems small enough that we can fairly easily write and test them. For this problem, we will provide the entire design for you, and you must use this design. The autograder will expect you to write every function specified here in just the way it is specified. Of course in the future, you will need to do this sort of design yourself. Along with each helper function below, we have also included some testcases that could be useful to test your code. You should add these to the appropriate place in the provided skeleton code for this assignment, and use it to test as you write each function. At the lowest level, we will need some functions that do some basic manipulations of our board: o makeBoard(moves) Write the function makeBoard(moves) that takes a positive integer number of moves, and returns an empty board (all 8's) for a game with that many moves. Here are some sample test cases for you: assert(makeBoard(1) == 8) assert(makeBoard(2) assert(makeBoard (3) 888) o digitCount(n) Write the function digitCount(n) that takes a possibly-negative int value n and returns the number of digits inn. Test cases: assert (digitCount() 1) assert (digitCount(5) digitCount(-5) 1) assert(digitCount(42) digitCount(-42) 2) assert (digitCount(121) == digitCount(-121) 3) o getKthDigit(n, k) Write the function getKthDigitin, k) that takes a possibly-negative int value n and a non-negative int value k, and returns the kth digit of n, counting right-to-left, and O-based (so the oth digit is the rightmost digit that is the 1's digit). Test cases: assert (getKthDigit(789, 0) getKthDigit(-789, 0) 9) assert (getKthDigit(789, 1) getKthDigit(-789, 1) assert (getKthDigit(789, 2) getKthDigit(-789, 2) 7) assert (getKthDigit(789, 3) getKthDigit(-789, 3) 0) assert (getKthDigit(789, 4) getKthDigit(-789, 4) == 0) == 88) == == == == == SE o setKthDigit(n, k, d) Write the function setKthDigitin, k, d) that takes a non-negative int n, a non-negative int k, and an int d where 0