"""
Learning Goals:
 - Trace over recursive functions that use multiple recursive calls with Towers of Hanoi
 - Recognize linear search on lists and in recursive contexts
 - Use binary search when reading and writing code to search for items in sorted lists
"""

def moveDiscs(start, tmp, end, numDiscs):
    if numDiscs == 1:
        print("Move 1 disc from", start, "to", end)
        return 1
    else:
        total = 0
        total += moveDiscs(start, end, tmp, numDiscs - 1)
        total += moveDiscs(start, tmp, end, 1)
        total += moveDiscs(tmp, start, end, numDiscs - 1)
        return total

print("Total moves:", moveDiscs("left", "middle", "right", 4))

###

def linearSearch(lst, target):
    if lst == []:
        return False
    elif lst[0] == target:
        return True
    else:
        smallerProblem = lst[1:]
        return linearSearch(smallerProblem, target)

print(linearSearch(["dog", "cat", "rabbit", "mouse"], "rabbit"))
print(linearSearch(["dog", "cat", "rabbit", "mouse"], "horse"))

###

def binarySearch(lst, target):
    if lst == []:
        return False
    else:
        mid = len(lst) // 2
        if target == lst[mid]:
            return True
        elif target < lst[mid]: # left
            return binarySearch(lst[:mid], target)
        else: # right
            return binarySearch(lst[mid+1:], target)

print(binarySearch([2, 5, 10, 20, 42, 56, 67, 76, 89, 95], 100))