Part 1: SA

You may not run any code in Part 1. Once you move to Part 2, you may not return to Part 1.

Note: The Free Response Previews are previews of the question you must solve in Part 2, so that you can choose when to move on from Part 1. You will be able to run code in the testing environment in Part 2. Remember, you will not be able to return to Part 1 once you have moved to Part 2.

SA1 [10 pts]

Answer SA1 on your physical quiz paper.

SA2 [5 pts]

In words (not code) describe the functionality of the base case of drawSierpinskyTriangle() from the notes.

Part 2: FR

FR1: distList(n) [85 pts]

Write a recursive backtracking function distList(n) that takes an integer n and returns a list of size 2n which contains all the numbers from 1 to n twice such that if x is in the list then the two xs are separated by exactly x other numbers. If such a list cannot be generated, return None.

Consider the following examples:

distList(3) returns [3, 1, 2, 1, 3, 2]
distList(4) returns [4, 1, 3, 1, 2, 4, 3, 2]
distList(2) returns None

Notes/Hints:

  1. You must use backtracking to solve the problem to receive credit, even if another approach would work.
  2. You may make use of wrapper functions and/or optional arguments.
  3. If you don't understand the problem, look at the examples again. Notice that the 3s always have three other numbers between them, the 2s always have two other numbers between them, etc.
  4. While there are multiple valid approaches to the problem, we start with a list of size 2n and fill it in as we go.
def distList(n):
    return 42

def testDistList():
    print('Testing distList...', end='')

    result1 = distList(3)
    assert(result1 == [3, 1, 2, 1, 3, 2] or
           result1 == reversed([3, 1, 2, 1, 3, 2]))

    result2 = distList(4)
    assert(result2 == [4, 1, 3, 1, 2, 4, 3, 2] or
           result2 == reversed([4, 1, 3, 1, 2, 4, 3, 2]))

    assert(distList(2) is None)
    assert(distList(6) is None)

    print('Passed!')

testDistList()