"""
Authors: Peter Mawhorter
Consulted:
Date: 2021-11-7
Purpose: Solutions for lab 12 part 2 on branching recursion.
"""


def listPowersOfTwo(n):
    """
    Returns a list containing all of the powers of two, up to and
    including 2^n, where each number is represented enough times so that
    it adds up to 2^n. So for example, listPowersOfTwo(3) will return the
    list [1, 1, 2, 1, 1, 2, 4, 1, 1, 2, 1, 1, 2, 4, 8], with 8 ones, 4
    twos, and 2 fours, and 1 eight.
    """
    if n == 0:
        return [1]
    else:
        return (
            listPowersOfTwo(n - 1)
          + listPowersOfTwo(n - 1)
        ) + [ 2**n ]


# Answers to questions in the lab:
# How many function call frames are created when evaluating listPowersOfTwo(2)?
#   Seven: one for n = 2, two for n = 1, and four for n = 0.

# How many of those are base-cases, and how many are recursive?
#   Four are base cases with n = 0, the other three are recursive.

# How does the number of items in the final list relate to the number of
# function call frames? Why?
#   There's one entry in the final list for each function call frame.
#   That's because each frame adds one entry to the list.

# What is the result for listPowersOfTwo(2)?
#   [1, 1, 2, 1, 1, 2, 4]


def printCoinPossibilities(soFar, numFlips):
    """
    Prints strings of 'h' and 't' to represent 'heads' and 'tails' which
    include all possible sequences of coin flip outcomes, starting with
    the soFar results and including exactly numFlips total flips.
    """
    if len(soFar) >= numFlips:
        # Base case: enough flips already so print the result
        print(soFar)
    else:
        # Recursive case: print possibilities for both heads and tails
        printCoinPossibilities(soFar + 'h', numFlips)
        printCoinPossibilities(soFar + 't', numFlips)


def listCoinPossibilities(soFar, numFlips):
    """
    Works like printCoinPossibilities, but returns a list of strings
    instead of printing the possibilities.
    """
    if len(soFar) >= numFlips:
        # Base case: return a list with just the one possibility
        return [ soFar ]
    else:
        # Recursive case: concatenate lists with 'h' and 't' outcomes
        return (
            listCoinPossibilities(soFar + 'h', numFlips)
          + listCoinPossibilities(soFar + 't', numFlips)
        )


def listBetOutcomes(initialBet, numFlips):
    """
    Lists all possible outcomes of a gambling game where the initial
    bet is increased by 30% or decreased by 30% based on the outcome of
    a coin flip, and then this process is repeated a number of times. At
    each step, values are rounded down to whole numbers. initialBet
    specifies the initial bet amount and numFlips specifies how many
    coin flips occur. The number of outcomes in the list will be 2^n,
    where n is the number of flips. With 0 flips, the list will just
    contain the initial bet.
    """
    if numFlips == 0:
        # Base case: zero flips
        return [ initialBet ]
    else:
        # Join possibilities for winning and losing
        return (
            listBetOutcomes(int(initialBet * 0.7), numFlips - 1)
          + listBetOutcomes(int(initialBet * 1.3), numFlips - 1)
        )