CMU 15-112: Fundamentals of Programming and Computer Science
Quiz 11

---

This quiz was offered online in two parts -- SA and CT in one part, and FR in the other. Students may not return to SA and CT once they start FR. The BonusCT is in be in part 1, and bonusFR is in part 2.

#######################################################
# PART ONE: 12.5 minutes
#######################################################

################################
# SA
################################

1. When using backtracking to solve N Queens with N==4, here is the board after the second queen is placed in a legal position (not attacked by prior queens):

Q - - - 
- - - - 
- Q - - 
- - - - 

With this in mind, what is the first board that the algorithm will produce that contains exactly 3 queens in legal positions (all not attacking each other)?

2. Assuming that a single solid triangle is drawn in a Level 0 Sierpinski Triangle, how many solid triangles are drawn in a Level 3 Sierpinski Triangle?

3. Recall listFiles() from the course notes, which takes a path to a folder and returns a list of the full paths to all the files in that folder or any folder recursively below it. For example, here is an excerpt of what listFiles('sampleFiles') returns:

    [ 'sampleFiles/emergency.txt',
      'sampleFiles/folderB/restArea.txt',
      'sampleFiles/folderB/folderH/driving.txt',
      ...
    ]

With this in mind, fill in the blank in the following code:

def listFiles(path):
    if os.path.isfile(path):
        return [ path ]
    else:
        files = [ ]
        for filename in os.listdir(path):
            ___________________ # <-- HERE
        return files

################################
# CT
################################

def ct1(n, m):
    if (n > m):
        return ct1(m, n)
    elif (m == n):
        return m
    else:
        return ct1(n, m-1) - 1

print(ct1(8, 5))

def ct2(s, depth=0):
    if (s == ''):
        return s
    else:
        i = len(s)//2
        return (str(depth) +
                s[i] +
                ct2(s[:i], depth+1) +
                ct2(s[i+1:], depth+1))
print(ct2('ABCD'))

#######################################################
# PART TWO: 12.5 minutes
#######################################################

################################
# FR1: hasTwoNines(n)
################################

Without using 'for' or 'while' loops, write the recursive function hasTwoNines(n) that takes a possibly-negative integer n and returns True if it contains the digit 9 exactly twice, and False otherwise. For example:

   assert(hasTwoNines( 139495) == True)
   assert(hasTwoNines(-139495) == True)  # negatives work!
   assert(hasTwoNines(-139499) == False) # too many 9's
   assert(hasTwoNines(-139411) == False) # too few 9's
   assert(hasTwoNines(-139411) == False) # too few 9's

################################
# FR2: sameValues(L, M)
################################

Without using 'for' or 'while' loops, write the recursive function sameValues(L, M) that takes two possibly-empty lists L and M that may not be the same length, and nondestructively returns a set S which contains any value v that occurs at the same index i in both L and M (so L[i] == M[i]).

################################
# BonusCt
################################

def bonusCt(m):
    def f(n):
        return 0 if n==0 else n%2 + f(n//2)
    def g(k, n=0):
        return n if f(n)==k else g(k,n+1)
    def h(m):
        return [ ] if m==0 else [g(m)] + h(m-1)
    return h(m)
print(bonusCt(4))

################################
# BonusFR: longestSubpalindrome(s)
################################

Without using 'for' or 'while' loops, write the recursive function longestSubpalindrome(s) that takes a possibly-empty string s and returns the longest substring t in s such that t is a palindrome. If more than one exists, you may break ties any way you wish. Note that you may use string slicing here. For example:

    assert(longestSubpalindrome('abc') in ['a', 'b', 'c'])
    assert(longestSubpalindrome('abcbd') == 'bcb')
    assert(longestSubpalindrome('abcbddbca') == 'cbddbc')
    assert(longestSubpalindrome('') == '')