CMU 15-112: Fundamentals of Programming and Computer Science
Homework 5 (Due Sat 2-Oct at 8pm ET)
(Optional Early Bird Bonus for Part A is Due Thu 30-Sep at 10pm ET)

1. Read the "Important Notes" at the top of hw1. The same general rules apply to this hw regarding solo, early-bird bonus, sample solution videos, etc.
2. Except: everyone must attend this week's Friday Lab, even if you qualify for the early-bird bonus. For this reason, the early-bird bonus is worth +2 points this week instead of +1.
3. 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.
4. Except: Friday's Lab will be collaborative. You will submit that portion in a separate file under the hw5-lab entry in Autolab. Everything you submit to hw5-eb and to hw5 must be entirely solo.
5. Also, if you attempt the Kepler's Polygons bonus, that part will also be submitted in a separate file under the hw5-kepler entry in Autolab.
6. You will need these starter files:
   1. hw5.py
   2. cs112_f21_week5_linter.py
7. For this hw, you may submit up to 6 times to the early-bird submission and up to 6 more times for the main hw submission, but only your last submission counts.
8. Do not use recursion this week.
9. Do not hardcode the test cases in your solutions.
10. As always, all your functions must be non-destructive unless the problem specifically indicates otherwise.
11. Also, if Python happens to provide a function that basically outright solves a problem, such as statistics.median() for the median problem in hw4, do not use that function. Naturally, we are looking for you to write the core logic of the problem.

1. removeRowAndCol (non-destructive and destructive) [10 pts; 5 pts each]
   Here we will write removeRowAndCol twice -- once non-destructively, and then again destructively. Note that neither of these versions may call nor essentially duplicate the other version. So in particular, your nondestructive version may not do this:

       L = copy.deepcopy(L)
       doDestructiveVersion(L)
       return L
   

   Instead, do not use copy.deepcopy and directly construct the modified 2d list.
   
   Both functions take a rectangular list L and two ints, row and col. In both cases, the goal is to obtain a version of the list that has the given row and given column removed. You may assume that row and col are both legal values (that is, they are non-negative integers that are smaller than the largest row and column, respectively). For example, the list shown to the left would lead to the result shown on the right when called with the row 1 and the column 2.
   
   

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

   
   nondestructiveRemoveRowAndCol(L, row, col): the non-destructive version should return a new list, and should not modify the provided list at all.
   
   destructiveRemoveRowAndCol(L, row, col): the destructive version should modify the original list, and should return None.


2. matrixMultiply(m1, m2) [7.5 pts]
   Write the function matrixMultiply(m1, m2) that takes two 2d lists (that we will consider to be matrices) and returns a new 2d list that is the result of multiplying the two matrices. Return None if the two matrices cannot be multiplied for any reason (such as if their dimensions do not match).
   
   If you are unsure about how to multiply matrices, the internet is full of good tutorials (such as this one, among many).


3. isKingsTour(board) [7.5 pts]
   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.

5. Friday Lab [10 pts]
   Attend your Friday lab (in your assigned recitation time). To receive full credit, you must show up on time, stay the whole time, be focused and uni-tasking (not multi-tasking), and fully participating. Note that this week, everyone must attend Friday Lab, even if you received the Early Bird Bonus.


6. isMagicSquare(L) [15 pts]
   Write the function isMagicSquare(L) that takes an arbitrary list (that is, a possibly-empty, possibly-ragged, possibly-2d list of arbitrary values) and returns True if it is a magic square and False otherwise, where a magic square has these properties:
   1. The list is 2d, non-empty, square, and contains only integers, where no integer occurs more than once in the square.
   2. Each row, each column, and each of the 2 diagonals each sum to the same total. Note that we are not requiring that the integers are strictly in the range from 1 to n for some n. We are just requiring that the integers are unique and that the sums are all the same.
   If you are curious, you can optionally see here for more details, including this sample magic square:
   


7. wordSearchWithIntegerWildCards(board, word) [15 pts]
   Here we will modify wordSearch so that we can include positive integers in the board, like so (see board[1][1]):

       board = [ [ 'p', 'i', 'g' ],
                 [ 's',   2, 'c' ],
               ]
   

   When matching a word, a positive integer on the board matches exactly that many letters in the word. So the board above contains the word "cow" starting from [1,2] heading left, since the 2 matches "ow". It also contains the word "cows" for the same reason. To make this work, of the three functions in our wordSearch solution, the outer two do not have to change (except a slight renaming), but the innermost one does. Rewrite the innermost function here so that it works as described.


8. isLegalSudoku(board) [15 pts]
   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) [3 pts]
   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) [3 pts]
   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) [3 pts]
   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) [3 pts]
   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) [3 pts]
   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.


9. Friday Lab: lightsOut! [20 pts] [collaborative] [submitted separately!]
   We will provide a separate starter file and full instructions for this part of the assignment in Friday's Lab. This part of the hw, and only this part, is collaborative. Also, this part will be submitted in a separate file under the Autolab entry 'hw5-lab'. There is no starter file for this part, and there is no linter, but you should still abide by our general style rules that the linter would enforce.


10. Bonus/Optional: makeWordSearch(wordList, replaceEmpties) [2.5 pts]
    Write the function makeWordSearch(wordList, replaceEmpties) that takes a possibly-empty list of non-empty lowercase words and a boolean value replaceEmpties (that we will explain later) and returns a wordSearch (a 2d list of lowercase letters) that contains all the given words, according to the algorithm described here.
    
    To start, if the wordList is empty, just return None. Otherwise, start with a 0x0 board. Add each word in the order given to the board according to the rules below, and return the resulting board.
    
    First, if the word is longer than the number of rows in the board (which is guaranteed to happen on the first word), then it cannot possibly fit on the board (right?). In that case, add empty rows and empty columns to the board, keeping the board square, so that the number of rows equals the length of the word. Note that empty cells do not yet contain any letters.
    
    Next, if possible, add the word in the location and direction resulting in the lowest cost, where the cost is the total number of empty cells that must be filled in with a letter to add the word at the given location and direction. If there is a tie, use the first location and direction with the lowest cost, where you should sweep across row0 from left-to-right, then row1, and so on, and where the directions should be ordered in the same way (up-left, up, up-right, left, right, down-left, down, down-right).
    
    It is possible that this process completes with no place to add the word. In that case, add one more row and one more column of empty cells to the board, keeping it square, and then add the word to the bottom row starting at column 0 and heading to the right.
    
    Hint: you should carefully re-read the previous paragraph, as it may not be too intuitive!
    
    After you have added all the words, if the replaceEmpties parameter is False, return the board as-is, with empty cells containing a dash ('-'). However, if replaceEmpties is True, then for each empty cell on the board, replace it with the first lowercase letter that does not appear among its non-empty neighbors. Do this sweeping the usual way, left-to-right across row0, then row1, and so on.
    
    You will surely want to add some well-chosen helper functions here. Also, you may wish to carefully review a few test cases we are providing you, prior to designing your solution:
    def testMakeWordSearch(): print("Testing makeWordSearch()...", end="") board = makeWordSearch([], False) assert(board == None) board = makeWordSearch(["ab"], False) assert(board == [['a', 'b'], ['-', '-'] ]) board = makeWordSearch(["ab"], True) assert(board == [['a', 'b'], ['c', 'd'] ]) board = makeWordSearch(["ab", "bc", "cd"], False) assert(board == [['a', 'b'], ['c', 'd'] ]) board = makeWordSearch(["ab", "bc", "cd", "de"], False) assert(board == [['a', 'b', '-'], ['c', 'd', '-'], ['d', 'e', '-']]) board = makeWordSearch(["ab", "bc", "cd", "de"], True) assert(board == [['a', 'b', 'a'], ['c', 'd', 'c'], ['d', 'e', 'a']]) board = makeWordSearch(["abc"], False) assert(board == [['a', 'b', 'c'], ['-', '-', '-'], ['-', '-', '-']]) board = makeWordSearch(["abc"], True) assert(board == [['a', 'b', 'c'], ['c', 'd', 'a'], ['a', 'b', 'c']]) board = makeWordSearch(["abc", "adc", "bd", "bef", "gfc"], False) assert(board == [['a', 'b', 'c'], ['d', 'e', '-'], ['c', 'f', 'g']]) board = makeWordSearch(["abc", "adc", "bd", "bef", "gfc"], True) assert(board == [['a', 'b', 'c'], ['d', 'e', 'a'], ['c', 'f', 'g']]) print("Passed!")


11. Bonus/Optional: keplersPolygons [1.5 - 2.5 pts] [submitted separately]
    Background: among his lesser-known exploits, the great German mathematician and astronomer Johannes Kepler studied how polygons can tile the plan or portions of the plane.  As part of these studies, he created these interesting figures:
    
    With that, write a program that draws any one of the following 4 figures so that it fills the largest square that fits inside the window, even if the window resizes. Note that the lower-left figure is worth 1.5 pts, and the other 3 figures are worth 2.5 pts. The max bonus is 2.5 points, even if you draw several of these figures.
    
    Note: if you attempt this bonus, it will be submitted in a separate file under the Autolab entry 'hw5-kepler'. There is no starter file for this part (you may want to refer to hw3 for inspiration as to how to set up your file), and there is no linter, but you should still abide by our general style rules that the linter would enforce.
    
    Have fun!!!