CMU 15-112: Fundamentals of Programming and Computer Science
Collab 12 (Due Monday 23-Nov at 8pm ET (Pittsburgh-time))
...but submit at the end of your collab section!

This assignment is collaborative. No solo work allowed!.
Even though this is collaborative, you must each fully understand your solutions and show your work, and you should be able to explain your team's work by yourself to your group and your TA.
To start:
1. Note: there is no starter file.
  1. Instead, create your own python file called collab12.py in your week11 folder.
2. Don't forget to submit!
Work collaboratively to solve each problem. Do not do any work by yourself except as instructed!
Do not hardcode the test cases in your solutions.
Follow all TA instructions!

Important: Like in previous collabs, you will be graded on demonstrated effort and collaboration rather than completion. Your participation in discussions is much more important than the completeness of the code you submit, so make sure to actively participate at all times. Your submission just needs to make it obvious that you tried hard (during your three hour time). Your grade also depends on you being courteous to your groupmates, and attentive at all times.

Ask your TA if you have any questions!

Note from the profs: Your TAs put today's collab together to help you prepare for Midterm 3! Be sure to tell them thanks! And remember, don't leave all your studying to the last minute, don't try to cram, eat well, and get plenty of sleep! Trust us on this; you'll do better and feel better.

Efficiency review
1. What is the Big-O of: elem in set? Why?
2. What is the Big-O of L.pop()? Why? What about L.pop(0)?
3. What is the Big-O of set(L)? Why?
4. What is the Big-O of merge sort? Why?
5. What is the Big-O of selection sort? Why?
6. Why don't we care about constants?
7. What is the Big-O of binary search? Why? What must be true for us to use binary search?
8. What is the Big-O of fasterIsPrime? Why?
9. What's an example of a problem with exponential Big-O? Why is it exponential?

Recursion review
1. Answer these questions:
  - What are the two parts of a recursive problem?
  - What is the base case in file recursion? The recursive case?
  - If you want to add an extra parameter to your recursive function, what is the best way to do that?
  - If these are a level 0 and level 1 tree fractal, draw a level 2 tree fractal.
2. Discuss the three guiding questions for writing recursive functions
  - How do I make the problem smaller?
  - What is my base case? I.e. What is the smallest version of my input?
  - If I assume the recursive case returns the right thing, what do I do with it?

hasConsecutiveDigits(n)
Without using iteration, write the recursive function hasConsecutiveDigits(n) that takes a possibly-negative int value n and returns True if that number contains two consecutive digits that are the same, and False otherwise.

def testHasConsecutiveDigits():
  print("Beginning hasConsecutiveDigits test cases...")
  assert(hasConsecutiveDigits(1123) == True)
  assert(hasConsecutiveDigits(-1123) == True)
  assert(hasConsecutiveDigits(1234) == False)
  assert(hasConsecutiveDigits(0) == False)
  assert(hasConsecutiveDigits(1233) == True)
  print("Passed!")

wordCounter(path, word)
Without using .count or any loops, write the function wordCounter(path, word) which takes in a path to a directory, as well as a single-word string, and searches all text files in that directory and any subdirectories, returning the number of times that word across all of the text files.
Get some sample files here!

def testWordCounter():
    print("Testing wordCounter...", end="")
    assert(wordCounter("Files", "class") == 5)
    assert(wordCounter("Files", "recursion") == 1)
    assert(wordCounter("Files", "case") == 3)
    assert(wordCounter("Files", "kosbie") == 0)
    assert(wordCounter("Files", "fox") == 1)
    assert(wordCounter("Files", "the") == 25)
    assert(wordCounter("Files", "a") == 20)
    assert(wordCounter("Files", "time") == 4)
    assert(wordCounter("Files", "lorem") == 4)
    assert(wordCounter("Files", "and") == 19)
    assert(wordCounter("Files", "style") == 5)
    assert(wordCounter("Files", "solve") == 2)
    print("Passed!")

Recursion CT

def h(x, y, depth = 0):
    # This uses depth-based indentation as in the course notes
    print("-" * depth, f"h({x}, {y})")

    if  (x + y <= 5):
        result = x + y
    else:
        result = h(x-2, y-2, depth+1) + 2*h(x//2, y//2, depth+1)

    print("-" * depth, "-->",  result)
    return result

print(h(4,6))

increasingPath(board)
Background: We will say that a board is a square 2d list of integers. As with mazes, a solution is a path from the left-top to the right-bottom, only here we will only allow moves that are up, down, left and right (no diagonals). A solution is an "increasing path" (a coined term) if each value on the solution path is strictly larger than the one before it on that path. Consider this board:
```
board   =   [[   1,  3,  2,  4   ],
             [   0,  4,  0,  3   ],
             [   5,  6,  8,  9   ],
             [   0,  7,  8,  9   ]]
```
This board has an increasing path: right to 3, down to 4, down to 6, down to 7, right to 8, right to 9. With this in mind, write the function increasingPath(board) that takes such a board and returns True if there is an increasing path and False otherwise. Similarly, consider this board:
```
board   =   [[3, 5],
             [4, 7]]
```
For this board, your function would also return true (right, down). For full credit, you need to use backtracking, so that you do not explore every possible path, but instead you backtrack once you know a subpath cannot lead to a solution.

OOP review
1. What is the purpose of OOP?
2. What's the difference between an instance of a class vs. a class definition? Give an example of each.
3. How do you create an instance of a class?
4. What does self refer to in method definition?
5. What is the difference between an attribute and a method? How do you distinguish them in test cases?
6. What is the purpose of rewriting repr, hash, and eq?
7. What's the difference between a static method and a local method?
8. What's the difference between a class attribute and a local attribute?
9. How do you overwrite a method inherited from a superclass?

SquadMate and MountainDew Classes
Write the SquadMate and MountainDew classes to pass the following test cases:

print("Beginning OOP test cases...")
# SquadMates have names and at the beginning, have no swag
kyra = SquadMate("Kyra")
katherine = SquadMate("Katherine")
assert(kyra.swag == katherine.swag == 0)

# SquadMates can obtain or lose swag by dancing
kyra.floss()
assert(kyra.swag == -1)
for i in range(10):
    katherine.dab()
assert(katherine.swag == 10)
assert(str(katherine) == "SquadMate named Katherine has swag = 10")

# You can get the total number of mates
assert(SquadMate.numSquadMates() == 2)

# SquadMates can drink Mountain Dew, each gives a swag boost
baja = MountainDew("Baja Blast", 1)
lightning = MountainDew("Sweet Lightning", 12)

# Mountain Dew starts out at 16 oz
assert(baja.volume == lightning.volume == 16)

kyra.giveDrink(baja)
kyra.giveDrink(lightning)
assert(kyra.drinks == [baja, lightning])

# Sipping is drinking from your first drink. It increases your swag by its boost
# and decreases the volume of the drink by 4 oz.
kyra.sip()
assert(kyra.swag == 0) # Since it was at -1 from kyra.floss()
assert(baja.volume == 16 - 4)

# Once the drink is finished, it is put in the recycling bin :)
while baja.volume > 0:
    kyra.sip()
assert(kyra.swag == 3)
assert(kyra.drinks == [lightning])

# Now Kyra drinks Sweet Lightning
kyra.sip()
assert(kyra.swag == 3 + 12)
assert(lightning.volume == 12)
print("Passed!")

CMU 15-112: Fundamentals of Programming and Computer Science Collab 12 (Due Monday 23-Nov at 8pm ET (Pittsburgh-time)) ...but submit at the end of your collab section!

CMU 15-112: Fundamentals of Programming and Computer Science
Collab 12 (Due Monday 23-Nov at 8pm ET (Pittsburgh-time))
...but submit at the end of your collab section!