CMU 15-112: Fundamentals of Programming and Computer Science
Homework 5 (Due Saturday 15-Feb at 8pm)
(with portions due in lab on Friday 14-Feb)

---

This hw has two distinct goals: to reinforce this unit's material on 2d lists, and also to start preparing for midterm1.

---

• Portions of this hw are due before the main Saturday deadline.
• This homework is solo. You must not collaborate with anyone (besides current course TA's and faculty) in any way. See the syllabus for more details.
• To start:
  1. Create a folder named 'unit5'
  2. Download both of these files into that folder:
     1. hw5.py
     2. cs112_s20_unit5_linter.py
  3. Edit hw5.py using VSCode
  4. When you have completed and fully tested hw5, submit hw5.py to Autolab. For this hw, you may submit up to 7 times, but only your last submission counts.
• Do not use recursion in this unit.
• Do not hardcode the test cases in your solutions.

---

Also note:

• Friday lab is required this week.
• 40 required points, so do 60 points of mild, medium, and/or spicy.

---

Required Problems

1. f19-midterm1 [20 pts] [solo] [manually graded] [due at the start of lab on Friday 14-Feb]
   Print a physical copy of f19-midterm1. Then, in a single 80-minute sitting (which will be unproctored, but it's probably best for you to make it somewhat close to real exam conditions), take the exam, handwriting your solutions directly on the printed copy, which you will submit for credit. This will be graded by effort, not correctness, but try your best. This will also be submitted right at the start of lab on Friday 14-Feb, so be sure to do this before then.


2. Friday Midterm1 Prep Lab [10 pts]
   Friday lab is required this week. In Friday lab, the TA's will review a subset of solutions from f19-midterm1 and f19-extra-practice5-ct-and-roc. Grading will be based on attendance and participation.


3. CokeMachine Class [10 pts] [solo] [autograded] [due Sat 15-Feb at 8pm]
   In the hw5.py file, write the CokeMachine class so that the following test code passes (and without hardcoding any cases, so any similar code would also pass):

   def testCokeMachineClass():
       print('Testing CokeMachine class...', end='')
       cm1 = CokeMachine(100, 125) # make a CokeMachine holding 100 bottles
                                   # that each cost 125 cents ($1.25)
       assert(cm1.getBottleCount() == 100)
       assert(cm1.isEmpty() == False)
       assert(cm1.getBottleCost() == 125)  # $1.25 (125 cents)
       assert(cm1.getPaidValue() == 0)     # starts with no coins inserted
   
       # insert a dollar
       change = cm1.insert(100)  # we paid $1.00, it costs $1.25, so change == -1
                                 # to indicate that not only is there no change,
                                 # but we still owe money
       assert(change == -1)
       assert(cm1.stillOwe() == 25)
   
       # insert a dime more
       change = cm1.insert(10)
       assert(change == -1)
       assert(cm1.stillOwe() == 15)
   
       # and insert a quarter more.  Here, we finally pay enough, so we get a
       # bottle and some change!
       change = cm1.insert(25)
       assert(change == 10)
       assert(cm1.stillOwe() == 125)      # this is for the NEXT bottle
       assert(cm1.getBottleCount() == 99) # because we just got one!
   
       # second instance
       cm2 = CokeMachine(2, 50) # 2 bottles, $0.50 each
   
       # buy a couple bottles
       change = cm2.insert(25)
       assert(change == -1)
       assert(cm2.stillOwe() == 25)
       change = cm2.insert(25)
       assert(change == 0) # bought with exact change
       assert(cm2.isEmpty() == False)
       assert(cm2.getBottleCount() == 1)
       change = cm2.insert(100) # overpaid by $0.50
       assert(change == 50)
       assert(cm2.isEmpty() == True)
       assert(cm2.getBottleCount() == 0)
   
       # cannot buy anything more -- the machine is empty.
       # this is signified by returning -999 as the change
       change = cm2.insert(50)
       assert(change == -999)
       assert(cm2.isEmpty() == True)
       assert(cm2.getBottleCount() == 0)
   
       # addBottles method
       cm2.addBottles(50)
       assert(cm2.isEmpty() == False)
       assert(cm2.getBottleCount() == 50)
       change = cm2.insert(50)
       assert(change == 0)
       assert(cm2.getBottleCount() == 49)
   
       # independence of two instances
       assert(cm1.getBottleCount() == 99)
       assert(cm2.getBottleCount() == 49)
   
       print('Passed')
   

Mild Problem

4. isKingsTour(board) [20 pts] [solo] [autograded] [due Sat 15-Feb at 8pm]
   Background: in Chess, a King can move from any square to any adjacent square in any of the 8 possible directions. A King's Tour is a series of legal King moves so that every square is visited exactly once. We can represent a Kings Tour in a 2d list where the numbers represent the order the squares are visited, going from 1 to N². For example, consider these 2d lists:

      [ [  3, 2, 1 ],        [ [  1, 2, 3 ],      [ [ 3, 2, 1 ],
        [  6, 4, 9 ],          [  7, 4, 8 ],        [ 6, 4, 0 ],
        [  5, 7, 8 ] ]         [  6, 5, 9 ] ]       [ 5, 7, 8 ] ]
   

   The first is a legal Kings Tour but the second is not, because there is no way to legally move from the 7 to the 8, and the third is not, because it contains a 0 which is out of range. Also, this should work not just for 3x3 boards but for any NxN board. For example, here is a legal Kings Tour in a 4x4 board:

       [ [  1, 14, 15, 16],
         [ 13,  2,  7,  6],
         [ 12,  8,  3,  5],
         [ 11, 10,  9,  4]
       ]
   

   With this in mind, write the function isKingsTour(board) that takes a 2d list of integers, which you may assume is NxN for some N>0, and returns True if it represents a legal Kings Tour and False otherwise.

Medium Problem

5. isLegalSudoku(board) [40 pts] [solo] [autograded] [due Sat 15-Feb at 8pm]
   This problem involves the game Sudoku, though we will generalize it to the N²xN² case, where N is a positive integer (and not just the 3²x3² case which is most commonly played). First, read the top part (up to History) of the Wikipedia page on Sudoku so we can agree on the rules. As for terminology, we will refer to each of the N² different N-by-N sub-regions as "blocks". The following figure shows each of the 9 blocks in a 3²x3² puzzle highlighted in a different color:
   
   
   Note: this example is 3²x3² but your code must work for arbitrary sizes (N²xN² for arbitrary N). For our purposes, we will number the blocks from 0 to N²-1 (hence, 0 to 8 in the figure), with block 0 in the top-left (in light blue in the figure), moving across and then down (so, in the figure, block 1 is yellow, block 2 is maroon, block 3 is red, block 4 is pink, block 5 is gray, block 6 is tan, block 7 is green, and block 8 is sky blue). We will refer to the top row as row 0, the bottom row as row (N²-1), the left column as column 0, and the right column as column (N²-1).
   
   A Sudoku is in a legal state if all N⁴ cells are either blank or contain a single integer from 1 to N² (inclusive), and if each integer from 1 to N² occurs at most once in each row, each column, and each block. A Sudoku is solved if it is in a legal state and contains no blanks.
   
   We will represent a Sudoku board as an N²xN² 2d list of integers, where 0 indicates that a given cell is blank. For example, here is how we would represent the 3²x3² Sudoku board in the figure above:

   [
     [ 5, 3, 0, 0, 7, 0, 0, 0, 0 ],
     [ 6, 0, 0, 1, 9, 5, 0, 0, 0 ],
     [ 0, 9, 8, 0, 0, 0, 0, 6, 0 ],
     [ 8, 0, 0, 0, 6, 0, 0, 0, 3 ],
     [ 4, 0, 0, 8, 0, 3, 0, 0, 1 ],
     [ 7, 0, 0, 0, 2, 0, 0, 0, 6 ],
     [ 0, 6, 0, 0, 0, 0, 2, 8, 0 ],
     [ 0, 0, 0, 4, 1, 9, 0, 0, 5 ],
     [ 0, 0, 0, 0, 8, 0, 0, 7, 9 ]
   ]
   

   With this description in mind, your task is to write some functions to indicate if a given Sudoku board is legal. To make this problem more approachable, we are providing a specific design for you to follow. And to make the problem more gradeable, we are requiring that you follow the design! So you should solve the problem by writing the following functions in the order given:
   
   areLegalValues(values)
   This function takes a 1d list of values, which you should verify is of length N² for some positive integer N and contains only integers in the range 0 to N² (inclusive). These values may be extracted from any given row, column, or block in a Sudoko board (and, in fact, that is exactly what the next few functions will do -- they will each call this helper function). The function returns True if the values are legal: that is, if every value is an integer between 0 and N², inclusive, and if each integer from 1 to N² occurs at most once in the given list (0 may be repeated, of course). Note that this function does not take a 2d Sudoku board, but only a 1d list of values that presumably have been extracted from some Sudoku board.
   
   isLegalRow(board, row)
   This function takes a Sudoku board and a row number. The function returns True if the given row in the given board is legal (where row 0 is the top row and row (N²-1) is the bottom row), and False otherwise. To do this, your function must create a 1d list of length N² holding the values from the given row, and then provide these values to the areLegalValues function you previously wrote. (Actually, because areLegalValues is non-destructive, you do not have to copy the row; you may use an alias.)
   
   isLegalCol(board, col)
   This function works just like the isLegalRow function, only for columns, where column 0 is the leftmost column and column (N²-1) is the rightmost column. Similarly to isLegalRow, this function must create a 1d list of length N² holding the values from the given column, and then provide these values to the areLegalValues function you previously wrote.
   
   isLegalBlock(board, block)
   This function works just like the isLegalRow function, only for blocks, where block 0 is the left-top block, and block numbers proceed across and then down, as described earlier. Similarly to isLegalRow and isLegalCol, this function must create a 1d list of length N² holding the values from the given block, and then provide these values to the areLegalValues function you previously wrote.
   
   isLegalSudoku(board)
   This function takes a Sudoku board (which you may assume is a N²xN² 2d list of integers), and returns True if the board is legal, as described above. To do this, your function must call isLegalRow over every row, isLegalCol over every column, and isLegalBlock over every block. See how helpful those helper functions are? Seriously, this exercise is a very clear demonstration of the principle of top-down design and function decomposition.

Spicy Problem

6. playSimplifiedChess [60 pts] [solo] [manually graded] [due Sat 15-Feb at 8pm]
   Note: since this problem is manually graded, if you do this, your autolab score will at first show as 40/100. Don't worry, when we enter your playSimplifiedChess grades, you'll get all the points you earned!
   
   First, carefully read about Simplified Chess here. Then, write an interactive game of Simplified Chess that allows two players (both human) to play against each other. Your game should use the console for input and output (so, print your output, and use the input function to get your input). You may wish to use uppercase for one color and lowercase for another, but there are other reasonable conventions. You have to decide how to print the board, and how to get user input, that makes the game fun and playable.
   
   For an additional 5 points of spicy points (not bonus, but spicy points), you should do this fun and compelling suggestion and read about the curses module. You can use this to do really cool things in a console window (a "shell" or a "terminal"). With curses, you can convert the console window into something approximating a graphical experience. Give it a try! It will definitely improve the user experience of your console-based game!
   
   Have fun!!!!

---