Due Wednesday 10-Feb, at 8pm 10pm
hw3.py file includes test functions to help you test on your own before
you submit to Gradescope. When you run your file, problems will be tested in order. If
you wish to temporarily bypass specific tests (say, because you have not yet completed
some functions), you can comment out individual test function calls at the bottom
of your file in main(). However, be sure to uncomment and test everything together
before you submit! Ask a CA if you need help with this.Do not use string indexing, lists, list indexing, or recursion this week. The autograder will reject your submission entirely if you do.
Starting with this assignment, we will be grading your code based on whether it follows the 15-112 style guide. We may deduct up to 10 points from your overall grade for style errors. We highly recommend that you try to write clean code with good style all along, rather than fixing your style issues at the end. Good style helps you code faster and with fewer bugs. It is totally worth it. In any case, style grading starts this week, so please use good style from now on!
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:
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:
| Start with an empty board | - - - - - |
| Player 1, at position 4, places a 2 | - - - 2 - |
| Player 2, at position 1, places a 2 | 2 - - 2 - |
| Player 1, at position 3, places a 1 | 2 - 1 2 - |
| Player 2, at position 2, places a 1 And Player 2 wins!!! |
2 1 1 2 - |
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, 1]
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.
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 0 is a good idea for these, only that can lead to some oddness due to leading 0's not being displayed. For example, if 0's were the empty spaces, then the board above would be represented like the values in the third column of this table:
| Start with an empty board | - - - - - | 0 |
| Player 1, at position 4, places a 2 | - - - 2 - | 20 |
| Player 2, at position 1, places a 2 | 2 - - 2 - | 20020 |
| Player 1, at position 3, places a 1 | 2 - 1 2 - | 20120 |
| Player 2, at position 2, places a 1 And Player 2 wins!!! |
2 1 1 2 - | 21120 |
See how the board is initially 0, even though it represents 5 blank spaces? This works, because 0 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 0, we will use 8 to represent a blank space. Thus, here are the integer representations of the boards in the example game:
| Start with an empty board | - - - - - | 88888 |
| Player 1, at position 4, places a 2 | - - - 2 - | 88828 |
| Player 2, at position 1, places a 2 | 2 - - 2 - | 28828 |
| Player 1, at position 3, places a 1 | 2 - 1 2 - | 28128 |
| Player 2, at position 2, places a 1 And Player 2 wins!!! |
2 1 1 2 - | 21128 |
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: offboard! | Player 1 played a piece into a position not on the board, and 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 preceding cases applies. |
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:
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.
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:
At the next-higher level, we need some functions
that use the lower-level functions you just wrote to perform the individual
steps of game play:
And that finally leads to the top-level function
that uses all the preceding functions to actually play the game:
We haven't actually covered strings yet, but you need them (a little bit) for this problem, especially when returning from the play112() function. Consider the following sample code for a hint of how to do this easily:
And that's it! Good luck!