CMU 15-112: Fundamentals of Programming and Computer Science
Quiz8 version A


Quiz8 Version A


See the quiz8 frontmatter. 30 minutes total..


PART 1


CT1 (10 points):
Indicate what this code prints.

def ct1(M):
    P = [M[i][i] for i in range(len(M[0]))]
    Q = [L[-1] for L in M]
    return [ P, Q ]
print(ct1([ [1, 2], [3, 4], [5, 6] ]))





CT2 (10 points):
Indicate what this code prints.

def ct2(n):
    L = [n+1]
    M = [L, L]
    P = copy.deepcopy(M)
    M[0] = n+2
    Q = copy.copy(M)
    Q.reverse()
    M[1][0] = n+3
    return [M, P, Q]
print(ct2(3))





RC1 (10 points):
Find a value for L such that rc1(L) returns True. Put your answer in the blank below, and nothing else.
(HINTS: L can be a rectangular 2D list! Also, consider what the list comprehension returns, and what M is, in simple terms.)

def rc1(L):
    if len(L)!=4: return False
    j = 0
    while L[0][j] >= 0:
        M = [L[i][j] for i in range(len(L))]
        if (M.count(j) != j):
            return False
        j += 1
    return j==3



PART 2

Free Response: makeEdits(M, E) [70] points]

Background: say we have this 2d list M:
M = [ [ 1, 2, 3 ],
      [ 4, 5, 6 ],
      [ 7, 8, 9 ] ]

Also, we have this list of strings describing non-destructive edits to make on M:
E = [ 'swap row 0 and row 1' ,
      'swap col 1 and col 2' ,
      'swap row 0 and row 2'  ]

To make the first edit, we swap row 0 and row 1 on the original list, to get:
    [ [ 4, 5, 6 ],
      [ 1, 2, 3 ],
      [ 7, 8, 9 ] ]

To make the second edit, we swap col 1 and col 2 on that list, to get:
    [ [ 4, 6, 5 ],
      [ 1, 3, 2 ],
      [ 7, 9, 8 ] ]

Finally, to make the last edit, we swap row 0 and row 2 on that list, to get:
    [ [ 7, 9, 8 ],
      [ 1, 3, 2 ],
      [ 4, 6, 5 ] ]

With this in mind, write the function makeEdits(M, E) that takes a rectangular (but not necessarily square) 2d list M and a 1d list of edits E, and nondestructively returns the 2d list that results from making the edits in E on M.

You can assume that all the edits are of the form described above, and always contain legal indexes.

We will grade using additional test cases, so do not hardcode! You may want to add your own test cases, or at least try some lists with different shapes/sizes/edits.

Note: M can be larger than 10x10. Hint: You may want to use s.split() in your answer. Hint: you may want to use copy.deepcopy(M) in your answer.


import copy

def makeEdits(M, E):
    return 42

def testMakeEdits():
    print('Testing makeEdits()...', end='')
    M = [ [ 1, 2, 3 ], #Original list
          [ 4, 5, 6 ],
          [ 7, 8, 9 ] ]
    E = [ 'swap row 0 and row 1' ,
          'swap col 1 and col 2' ,
          'swap row 0 and row 2'  ]
    N = copy.deepcopy(M) #Make a deepcopy to preserve original list
    R = [ [ 7, 9, 8 ],
          [ 1, 3, 2 ],
          [ 4, 6, 5 ] ]
    assert(makeEdits(M, E) == R)
    assert(M == N) # so we are non-destructive

    #Extra test cases (These were not provided in the quiz, 
    #      but may help you pratice!)
    
    # Testing non-square 2D lists and swaps where the indices are backwards
    M = [ [  1,  2,  3,  4,  5],
        [  6,  7,  8,  9, 10],
        [ 11, 12, 13, 14, 15],
        [ 16, 17, 18, 19, 20]]
    E = ['swap row 0 and row 3',
       'swap row 2 and row 1',
       'swap col 3 and col 1']
    N = copy.deepcopy(M)
    R = [ [ 16, 19, 18, 17, 20],
          [ 11, 14, 13, 12, 15],
        [  6,  9,  8,  7, 10],
        [  1,  4,  3,  2,  5]]
    assert(makeEdits(M, E) == R)
    assert(M == N)

    # Testing a lot of edits, some of which undo each other
    M = [ [  1,  2,  3,  4,  5],
        [  6,  7,  8,  9, 10],
        [ 11, 12, 13, 14, 15],
        [ 16, 17, 18, 19, 20]]
    E = ['swap row 0 and row 1',
       'swap row 1 and row 2',
       'swap row 2 and row 3',
       'swap row 0 and row 1',
       'swap row 1 and row 2',
       'swap row 2 and row 3',
       'swap row 2 and row 3',
       'swap row 1 and row 0',
       'swap col 1 and col 3',
       'swap col 2 and col 4',
       'swap col 4 and col 3',
       'swap col 2 and col 3']
    N = copy.deepcopy(M)
    R = [ [ 16, 19, 18, 20, 17],
        [ 11, 14, 13, 15, 12],
        [  6,  9,  8, 10,  7],
        [  1,  4,  3,  5,  2]]
    assert(makeEdits(M, E) == R)
    assert(M == N)

    # Testing lists at least 10 x 10
    M = [['A0', 'B0', 'C0', 'D0', 'E0', 'F0', 'G0', 'H0', 'I0', 'J0', 'K0'],
         ['A1', 'B1', 'C1', 'D1', 'E1', 'F1', 'G1', 'H1', 'I1', 'J1', 'K1'], 
       ['A2', 'B2', 'C2', 'D2', 'E2', 'F2', 'G2', 'H2', 'I2', 'J2', 'K2'], 
       ['A3', 'B3', 'C3', 'D3', 'E3', 'F3', 'G3', 'H3', 'I3', 'J3', 'K3'], 
       ['A4', 'B4', 'C4', 'D4', 'E4', 'F4', 'G4', 'H4', 'I4', 'J4', 'K4'], 
       ['A5', 'B5', 'C5', 'D5', 'E5', 'F5', 'G5', 'H5', 'I5', 'J5', 'K5'], 
       ['A6', 'B6', 'C6', 'D6', 'E6', 'F6', 'G6', 'H6', 'I6', 'J6', 'K6'], 
       ['A7', 'B7', 'C7', 'D7', 'E7', 'F7', 'G7', 'H7', 'I7', 'J7', 'K7'], 
       ['A8', 'B8', 'C8', 'D8', 'E8', 'F8', 'G8', 'H8', 'I8', 'J8', 'K8'], 
       ['A9', 'B9', 'C9', 'D9', 'E9', 'F9', 'G9', 'H9', 'I9', 'J9', 'K9'], 
       ['AA', 'BA', 'CA', 'DA', 'EA', 'FA', 'GA', 'HA', 'IA', 'JA', 'KA'], 
       ['AB', 'BB', 'CB', 'DB', 'EB', 'FB', 'GB', 'HB', 'IB', 'JB', 'KB'], 
       ['AC', 'BC', 'CC', 'DC', 'EC', 'FC', 'GC', 'HC', 'IC', 'JC', 'KC'], 
       ['AD', 'BD', 'CD', 'DD', 'ED', 'FD', 'GD', 'HD', 'ID', 'JD', 'KD'], 
       ['AE', 'BE', 'CE', 'DE', 'EE', 'FE', 'GE', 'HE', 'IE', 'JE', 'KE']]
    E = [
        'swap row 5 and row 10',
        'swap row 12 and row 14',
        'swap col 9 and col 10',
        'swap row 1 and row 0',
        'swap col 10 and col 1',
    ]
    N = copy.deepcopy(M)
    R = [
         ['A1', 'J1', 'C1', 'D1', 'E1', 'F1', 'G1', 'H1', 'I1', 'K1', 'B1'], 
       ['A0', 'J0', 'C0', 'D0', 'E0', 'F0', 'G0', 'H0', 'I0', 'K0', 'B0'],
       ['A2', 'J2', 'C2', 'D2', 'E2', 'F2', 'G2', 'H2', 'I2', 'K2', 'B2'], 
       ['A3', 'J3', 'C3', 'D3', 'E3', 'F3', 'G3', 'H3', 'I3', 'K3', 'B3'], 
       ['A4', 'J4', 'C4', 'D4', 'E4', 'F4', 'G4', 'H4', 'I4', 'K4', 'B4'], 
       ['AA', 'JA', 'CA', 'DA', 'EA', 'FA', 'GA', 'HA', 'IA', 'KA', 'BA'], 
       ['A6', 'J6', 'C6', 'D6', 'E6', 'F6', 'G6', 'H6', 'I6', 'K6', 'B6'], 
       ['A7', 'J7', 'C7', 'D7', 'E7', 'F7', 'G7', 'H7', 'I7', 'K7', 'B7'], 
       ['A8', 'J8', 'C8', 'D8', 'E8', 'F8', 'G8', 'H8', 'I8', 'K8', 'B8'], 
       ['A9', 'J9', 'C9', 'D9', 'E9', 'F9', 'G9', 'H9', 'I9', 'K9', 'B9'], 
       ['A5', 'J5', 'C5', 'D5', 'E5', 'F5', 'G5', 'H5', 'I5', 'K5', 'B5'], 
       ['AB', 'JB', 'CB', 'DB', 'EB', 'FB', 'GB', 'HB', 'IB', 'KB', 'BB'], 
       ['AE', 'JE', 'CE', 'DE', 'EE', 'FE', 'GE', 'HE', 'IE', 'KE', 'BE'],
       ['AD', 'JD', 'CD', 'DD', 'ED', 'FD', 'GD', 'HD', 'ID', 'KD', 'BD'], 
       ['AC', 'JC', 'CC', 'DC', 'EC', 'FC', 'GC', 'HC', 'IC', 'KC', 'BC'], 
       ]
    assert(makeEdits(M, E) == R)
    assert(M == N)

    print('Passed')

testMakeEdits()



PART 3

BonusCT1 [+2 points]

This is an optional bonus problem. Indicate what this code prints.
def bonusCt1(m):
    N = [ 0 ]
    while N[-1] < m:
        n = len(N)+1
        M = [list(range(0, n*(k+1), k+1)) for k in range(n)]
        N = [sum([M[r][c] for r in range(n)]) for c in range(n)]
    return N[-1]
print(bonusCt1(50))



BonusCT2 [+2 points]

This is an optional bonus problem. Indicate what this code prints.
def bonusCt2(s):
  M, t, k = list(), list(s), 0
  for i in range(2):
      M.append([])
      for j in range(len(s)//2):
          M[-1].append(t.pop(k))
          k = -1-k
  s = ''
  for i in range(-1, 1):
      for j in range(-1, 1):
          s += M[i][j]
  return s
print(bonusCt2('abcdefgh'))