CMU 15-112: Fundamentals of Programming and Computer Science
Homework 9 (Due Saturday 28-Mar at 8pm EDT)
(TP-Mentor Meetings Due by Monday 30-Mar)

• As with hw8, this homework is collaborative. You may work with up to 3 other current 15-112 students.
• Collaboration is not strictly required, but is very strongly encouraged.
• This must be earnest collaboration, with each of you genuinely working together the whole time. It is not acceptable for one of you to do the work, or any portion of the work, and for the other to copy any portion of that work. Any collaboration must be earnest collaboration from each of you.
• Be sure to list the names and andrew id's of each of your collaborators at the top of your hw8.py file!
• Do not directly copy any code! That is not collaborating!!!

• If you are doing non-spicy problems, download all of these to that folder:
  • hw9.py
  • cs112_s20_unit9_linter.py
• If you are doing spicy problems, download all of these to that folder:
  • spicy-hw9.py
  • cs112_s20_unit9_spicy_linter.py
• Edit hw9.py or spicy-hw9.py
• When you have completed and fully tested hw9, submit your hw9 file to Autolab. For this hw, you may submit up to 10 times, but only your last submission counts.
• Note: if you are doing the spicy-hw9, you must submit to the spicy-hw9 entry in the etc category. In this case, do not submit to hw9 in the hw category.

---

A few more notes:
• You may (and in fact must) finally use recursion this week.
• Every problem this week requires that you use recursion meaningfully in order to receive the points.
• If you are doing the non-spicy-problems, then you may not use loops -- no for loops or while loops this week!
• If you are doing the spicy problems, however, you may use loops, so long as you use recursion meaningfully (as you will see, there is a way to use iteration in some places, and recursion in others, to write an elegant solution, particularly to the backtracking probelm).
• You may use helper functions, so long as they are recursive and not iterative.
• You may use wrapper functions -- that is, your solution function may itself be a non-recursive wrapper around a recursive helper function.
• You may only use builtin functions or methods if they run in O(1). Basically, this means that you should write the core logic yourself, and not search for some builtin that somehow magically does most of the heavy lifting for you. So in particular, among many other builtins you may not use this week, you may not use sort, sorted, min, or max this week (you can write your own recursive versions of these if you wish, though that is not required, and we did not do that for our sample solutions). Also, note that slicing (L[i:j]) is just fine this week. If you are unsure, ask a TA.


• Do not hardcode the test cases in your solutions.

---

Required Problem (10 pts)



1. Term Project Ideation [10 pts] [manually graded] [due by Monday night]
   This week, you will be receiving your assigned Term Project mentor. They will reach out to you regarding times to meet for 10-15 minutes between now and next Monday (30-Mar). In this meeting, you will be discussing ideas you have regarding what you hope to accomplish in your Term Project. You should bring ideas to the meeting, and even some simple demos if you may have anything demoable.

Mild+Medium Problems (90 pts)



2. Recursion-Only alternatingSum(L) [15 pts] [autograded]
   Write the function alternatingSum(L) that takes a possibly-empty list of numbers, and returns the alternating sum of the list, where every other value is subtracted rather than added. For example: alternatingSum([1,2,3,4,5]) returns 1-2+3-4+5 (that is, 3). If L is empty, return 0. You may not use loops/iteration in this problem.


3. Recursion-Only onlyEvenDigits(L) [15 pts] [autograded]
   Without using iteration and without using strings, write the recursive function onlyEvenDigits(L), that takes a list L of non-negative integers (you may assume that), and returns a new list of the same numbers only without their odd digits (if that leaves no digits, then replace the number with 0). So: onlyEvenDigits([43, 23265, 17, 58344]) returns [4, 226, 0, 844]. Also the function returns the empty list if the original list is empty. You may not use strings nor loops/iteration in this problem.


4. Recursion-Only powersOf3ToN(n) [20 pts] [autograded]
   Write the function powersOf3ToN(n) that takes a possibly-negative float or int n, and returns a list of the positive powers of 3 up to and including n. As an example, powersOf3ToN(10.5) returns [1, 3, 9]. If no such powers of 3 exist, you should return the empty list. You may not use loops/iteration in this problem.


5. Recursion-Only binarySearchValues(L, item) [20 pts] [autograded]
   Recall the Binary Search algorithm which we will discuss on Thursday of this week: start with two indexes, hi and lo, with hi equal to the largest index in L (len(L)-1), and lo to the smallest (0), then set mid to the middle index ((hi+lo)//2) and check if L[mid] equals the item. If so, we're done! If not, then if L[mid] is too small, set lo to mid+1 (not to mid, since we know mid is wrong!), otherwise set hi to mid-1. Continue until we find the element or lo exceeds hi.
   
   With this in mind, write the function binarySearchValues(L, item) that takes a sorted list and a value and returns a list of tuples, (index, value), of the values that Binary Search must check to verify whether or not the item is in the list. You may not use loops/iteration in this problem.
   
   For example, binarySearchValues(['a', 'c', 'f', 'g', 'm', 'q'], 'c') should return [(2, 'f'), (0, 'a'), (1, 'c')]. On the other hand, binarySearchValues(['a', 'c', 'f', 'g', 'm', 'q'], 'n') should return [(2, 'f'), (4, 'm'), (5, 'q')], since 'n' cannot be found.
   
   Hint: our sample solution did not use slicing here (though of course we did use list indexing, as in L[mid]), but rather just kept track of the lo and hi indexes as they changed.


6. Recursion-Only secondLargest(L) [20 pts] [autograded]
   Note: recall that you may not use sort, sorted, min, or max this week! With that in mind, write the function secondLargest(L) that takes a list of integers in any order and returns the second-largest value in the list. To be more precise, it returns the second value from the end if the list was sorted (though you do not need to sort it to solve this problem), so if the largest value occurs twice, you would return that value. Also, if there are fewer than 2 values in the list, return None. Here are some test cases:
   assert(secondLargest([1,2,3,4,5]) == 4) assert(secondLargest([4,3]) == 3) assert(secondLargest([4,4,3]) == 4) assert(secondLargest([-3,-4]) == -4) assert(secondLargest([4]) == None) assert(secondLargest([ ]) == None)
   Again, you do not need to sort the list. We didn't sort it in our sample solution. We just tracked the two largest values as we recursively traversed the list. Also, you may not use loops/iteration in this problem.

Spicy Problems (90 pts)



7. solveABC [70 pts] [autograded]
   Important note: before attempting this problem, first very carefully study the notes and watch the videos from s17's notes on Backtracking in Recursion-part-2 here.
   
   This problem is inspired by the "ABC Path" problems at BrainBashers.com. For more (optional) info, check this out. That said, here's some background: In what we will call an "ABC Puzzle", you are given a 5x5 board like this:
   
   It is an empty board except that it contains a single "A" in an arbitrary cell. Also, the letters from "B" to "Y" are arranged around the outside of the board in an arbitrary order, along with arrows that constrain those letters to a certain row, column, or diagonal. For example, in the image, we see the "H" and "T" are constrained to column 0, "L" and "I" are constrained to row 0, and "C" and "G" are constrained to the diagonal running from (0,0) to (4,4). The goal of this puzzle is to place every letter from "B" to "Y" on the board such that: (1) each letter from "B" to "Y" is placed in the row, column, or diagonal in which it is constrained; and (2) each letter from "B" to "Y" is placed adjacent (including diagonally) to the previous letter (so "B" is adjacent to "A", and "C" is adjacent to "B", and so on).
   
   A solution to the puzzle is here:
   
   Be sure you understand why this solves the puzzle! If you are unsure, go to the link at BrainBashers.com and read more about this kind of puzzle, including this help page, and maybe try to solve a few more of them (the puzzles include a button you can press to get the solutions!).
   
   Now, for us to represent one of these puzzles in Python, we have to represent the constraints. We'll do that by reading them clockwise starting from the top-left corner. Thus, in the given example, the constraints are: constraints = "CHJXBOVLFNURGPEKWTSQDYMI" And we also need to specify the position of the "A", which we will do as a (row,col) tuple, as such: aLocation = (0,4)
   
   With this in mind, write the function solveABC(constraints, aLocation), that takes constraints and the location of the "A", which together define an ABC Puzzle, and returns a completed board which solves the puzzle, or None if no such board exists. Here is a test function that is based on the puzzle used in the example above (notice how the constraints and aLocation match the unsolved puzzle, and the resulting board matches the solved puzzle):
   
   
   def testSolveABC(): print('Testing solveABC()...', end='') constraints = "CHJXBOVLFNURGPEKWTSQDYMI" aLocation = (0,4) board = solveABC(constraints, aLocation) solution = [['I', 'J', 'K', 'L', 'A'], ['H', 'G', 'F', 'B', 'M'], ['T', 'Y', 'C', 'E', 'N'], ['U', 'S', 'X', 'D', 'O'], ['V', 'W', 'R', 'Q', 'P'] ] assert(board == solution) print('Passed!')
   Note: To receive any credit for this problem, you must solve it recursively, even if you could dream up a non-recursive solution!
   Hint #1: This is a backtracking problem. Study nQueens. This is most like that problem.
   Hint #2: Our sample solution required about 50 lines of code. If you are ranging well past that, perhaps you should pause and rethink your approach.


8. flatten(L) [20 pts] [autograded]
   Write the recursive, non-destructive, function flatten(L), which takes a list which may contain lists (which themselves may contain lists, and so on), and returns a single list (which does not contain any other lists) which contains each of the non-lists, in order, from the original list. This is called flattening the list. For example:

   flatten([1,[2]]) returns [1,2]
   flatten([1,2,[3,[4,5],6],7]) returns [1,2,3,4,5,6,7]
   flatten(['wow', [2,[[]]], [True]]) returns ['wow', 2, True]
   flatten([]) returns []
   flatten([[]]) returns []
   flatten(3) returns 3 (not a list)
   

---