CMU 15-112: Fundamentals of Programming and Computer Science
Week 3: More Lists and Animations

Code Tracing - Debugging
Free Response
  1. foldTypeRun
    Implement the function foldTypeRun(L), which is designed to destructively modify a non-empty mixed-type list L. This list contains both single-digit integers and characters. The goal is to group consecutive equal-type values in L as follows: any run of consecutive integers should be combined into a single integer value whose digits correspond to the run, and all runs of consecutive characters should be transformed into a string with characters representing the run.
    The function should modify L so that any subsequence with two or more occurrences of the same type is replaced with a single occurrence, following the above mentioned rules. Consequently, after calling the function, there should be no consecutive values of the same type (string or integer) in L.
    Your function should be mutating/destructive. For full credit, you are not allowed to empty the input list L.
    Note: the final L may still have repeated types, but they should not appear consecutively.
    For example...
    L = [4, 2] foldTypeRun(L) assert(L == [42]) L = ['b', 'y', 'e'] foldTypeRun(L) assert(L == ['bye']) L = [1, 2, 3, 'h', 'e', 'l', 'l', 'o', 1, 5, 1, 1, 2] foldTypeRun(L) assert(L == [123, 'hello', 15112]) # there were three runs with the same type # 1, 2, 3: become 123 # 'h','e','l','l','o' become 'hello' # 1,5,1,1,2 become 15112 L = ['f', 'a', 'l', 'l', 2, 0, 2, 3, 'y', 'e', 'y'] f oldTypeRun(L) assert(L == ['fall', 2023, 'yey'])

    Alternative: You can solve the problem in a non-destructive way with a penalty. If so, your function must return the result as a new list, and L should not be modified.

  2. wordSearch:
    We have provided the outer and inner functions from the word search case study. Write the missing middle helper function wordSearchFromCell so that wordSearch(board, row) works properly.
    Remember that wordSearch(board, word) takes board (a 2d list of lowercase letters) and word (a non-empty string of lowercase letters) and returns a tuple that contains the word, (startRow, startCol) as a tuple, and a string describing the direction. We may test your code using cases not shown here. You must not modify the helper functions we have provided.
    Note that as long as your code is functional without modifying wordSearch or wordSearchFromCellInDirection, it is fine if your variable names and code do not perfectly match ours. Do not hardcode.
    #Do not modify this function! def wordSearch(board, word): (rows, cols) = (len(board), len(board[0])) for row in range(rows): for col in range(cols): result = wordSearchFromCell(board, word, row, col) if (result != None): return result return None #Write the missing helper function below the supplied test cases def wordSearchFromCell( ): return 42 #Do not modify this function! def wordSearchFromCellInDirection(board, word, startRow, startCol, drow, dcol) : (rows, cols) = (len(board), len(board[0])) dirNames = [ ["up-left" , "up", "up-right"], ["left" , "" , "right" ], ["down-left", "down", "down-right" ] ] for i in range(len(word)): row = startRow + i*drow col = startCol + i*dcol if ((row < 0) or (row >= rows) or (col < 0) or (col >= cols) or (board[row][col] != word[i])): return None return (word, (startRow, startCol), dirNames[drow+1][dcol+1]) def testWordSearch(): print('Testing wordSearch(board, row)...', end='') board = [ [ 'd', 'o', 'g' ], [ 't', 'a', 'c' ], [ 'o', 'a', 't' ], ['u', 'r', 'k' ], ] assert(wordSearch(board, "dog") == ('dog', (0, 0), 'right')) assert(wordSearch(board, "cat") == ('cat', (1, 2), 'left')) assert(wordSearch(board, "tad") == ('tad', (2, 2), 'up-left')) assert(wordSearch(board, "cow") == None) print('Passed!') testWordSearch()

  3. Color Sequences :
    Imagine a game that uses a 2D board of colored squares, where each square is either red, green, or blue. Whenever there are three or more squares of the same color in a vertical line, that line of colored squares is eliminated from the board. Write destructive function blankVerticalSequences(board) which, given a board, finds any vertical sequences of length three or more and replaces all of the color codes with a space. The function is destructive, so it does not return anything. Consider the following example:

    After this code runs, board contains:
    [ ["B", "R", "R", " "], [" ", "R", "G", " "], [" ", "B", "R", " "], [" ", "B", "G", "R"], ["R", "G", "R", "G"], ["G", "R", " ", "B"], [" ", "G", " ", "R"], [" ", "B", " ", "G"], [" ", "B", " ", "B"], [" ", "R", " ", "G"], ]

  4. Numerical Tic-Tac-Toe :
    Numerical Tic-Tac-Toe is a variation of the classic game invented by the mathematician Ronald Graham. The two players take turns marking the spaces in a three-by-three grid with a number. The player who succeeds in making one horizontal, vertical, or diagonal line sum to 15 is the winner. The line may contain both even a nd odd numbers. In this task, you will create a simplified version in which the numbers they play in each turn are predefined and players can only choose where to play. Here are the specifications you need to implement:
    • Game Setup:– The game should display a 3x3 grid with numbers.
      • Initially, all grid cells contain the number 0.
      • The grid should be white on a black background.
      • A countdown timer is displayed at the bottom of the screen.
      • Player One starts, and the countdown timer starts at 20 seconds.
    • Gameplay Rules:
      • Player One plays with odd numbers (1, 3, 5, 7, 9), and Player Two plays with even numbers (2, 4, 6, 8).
      • The sequence of plays is always fixed: Player One places 1, Player Two places 2, Player One places 3, and so on.
      • On each player’s turn, they must select an empty cell on the grid.
      • If the selected cell contains a 0 (empty), the player can make a move (place their predefined number), and the countdown timer resets to 20 seconds.
    • Winning Condition:
      • The player who succeeds in making one horizontal, vertical, or diagonal line of numbers on the grid sum to 15 is the winner. The winning line may contain both even and odd numbers and 0s.
      • If the countdown timer reaches 0 before the current player makes a move, the other player wins.
      • When a player wins, a message appears at the top of the window indicating "Player One Won!" or "Player Two Won!" accordingly.
    • Draw Condition:
      • If the game ends with a draw (all cells are filled without a winning line), the message "It’s a Draw" appears at the top of the window.
      • Your task is to write the Python code using cmu_graphics.
      Here are some helper functions you may use in your solution.
      def resetBoard(app): app.board = [ [0,0,0], [0,0,0], [0,0,0] ] def drawGrid(app): cellSize = (app.width)//3, (app.height)//3 for row in range(3): for col in range(3): # compute coordinates x1 = cellSize[0] * col y1 = cellSize[1] * row # draw the cell and its content drawRect(x1, y1, cellSize[0], cellSize[1], border='white', borderWidth=5) drawLabel(app.board[row][col], x1 + cellSize[0]//2, y1 + cellSize[1]//2, size=60, fill='white')
      Make reasonable assumptions for anything not specified here.

  5. isValidFourNeighborColoring:
    Write the function isValidFourNeighborColoring(L) that takes an arbitrary value L and returns True if L satisfies the criteria of a four neighbor coloring rectangle, and False otherwise. The following conditions define a four neighbor coloring rectangle:
    • L is a non-empty 2D rectangular list.
    • L consists exclusively of single-character strings representing colors, which can be 'G' (green), 'R' (red), 'Y' (yellow), and 'B' (blue).
    • No two adjacent cells within the rectangular list L have the same color. Here, adjacent cells are defined as those located in the up, down, left, and right directions surrounding a given cell.

    Here are some test cases:
    L1 = [['Y', 'G', 'R', 'B'], ['B', 'Y', 'B', 'Y'], ['R', 'G', 'R', 'G'], ['B', 'Y', 'B', 'Y']] L2 = [['B', 'Y', 'B', 'Y']] L3 = [['R', 'G', 'B', 'G'], ['B', 'Y', 'B', 'Y'], ['R', 'G', 'R', 'G'], ['B', 'Y', 'B', 'Y']] L4 = [['R', 'G', 'R', 'G'], ['B', 'Y', 'B'], ['R', 'G', 'R', 'G'], ['B', 'Y', 'B', 'Y']] L5 = [['RED', 'G', 'RED', 'G'], ['B', 'Y', 'B', 'Y'], ['RED', 'G', 'RED', 'G'], ['B', 'Y', 'B', 'Y']] L6 = "Remember the Magic Square?" assert(isValidFourNeighborColoring(L1) == True) # OK assert(isValidFourNeighborColoring(L2) == True) # Also OK assert(isValidFourNeighborColoring(L3) == False) # L[0][2] == L[1][2] assert(isValidFourNeighborColoring(L4) == False) # Not rectangular assert(isValidFourNeighborColoring(L5) == False) # Invalid value (RED) assert(isValidFourNeighborColoring(L6) == False) # Not even a list

  6. zeroRectCount(L) :
    Background: given a 2d list of integers L, we will say that a rectangular region of L is a "zeroRect" (a coined term) if the sum of the values in that region equals 0. For example, consider this list:
    L = [ [ 1, 2, -3, 5, 1 ], [ 3, -6, 4, 0, 1 ] ] [ 3, -6, 4, 0, 1 ] ]
    Here are the rectangular regions of L that sum to 0:
    R1 = [ [ 1, 2, -3 ] ] # 1x3 in top-left of L R2 = [ [ 1, 2 ], [ 3, -6 ] ]# 2x2 in top-left of L R3 = [ [ 0 ] ] # 1x1 near bottom-right of L
    With this in mind, write the function zeroRectCount(L) that takes a rectangular 2d list of integers L, and returns the total number of zeroRects in L. For example, with L as above, zeroRectCount(L) returns 3.
    Hint: while you may solve this any way you wish, our sample solution used a large number of nested 'for' loops to try all possible rectangles (so don't be discouraged if your solution does so as well). You may not import or use any module other than copy. You may not use any method, function, or concept that we have not covered this semester. We may use additional test cases not shown here. Do not hardcode.
    # Note: almostEqual(x, y) and roundHalfUp(n) are both supplied for you. # You must write all other helper functions you wish to use. def almostEqual(d1, d2, epsilon=10**-7): #helper-fn return (abs(d2 - d1) < epsilon) import decimal def roundHalfUp(d): #helper-fn # Round to nearest with ties going away from zero. rounding = decimal.ROUND_HALF_UP return int(decimal.Decimal(d).to_integral_value(rounding=rounding)) import copy #--------------- #Write your function below the supplied test cases def zeroRectCount(L): return 42 def testZeroRectCount(): print('Testing zeroRectCount(L)...', end='') L = [[42]] assert(zeroRectCount(L) == 0) L = [[0]] assert(zeroRectCount(L) == 1) L = [[-3, -1, 2, 3]] assert(zeroRectCount(L) == 0) L = [[-3, -1, 1, 3]] assert(zeroRectCount(L) == 2) L = [ [ 1, 2, -3, 5, 1 ], [3, -6, 4, 0, 1 ] ] assert(zeroRectCount(L) == 3) L = [ [ 1, 2, -3, 5], [3, -6, 4, 0], [-4, 6, 1, -9] ] assert(zeroRectCount(L) == 7) print('Passed!') testZeroRectCount()