<jupyter_start><jupyter_text>Chapter 5 - Discussion Questions  1. Draw a call stack for the Tower of Hanoi problem. Assume that you start with a stack of three disks.We can call just call the function with above parameters and at each recursive call we keep track of the parameters passed.<jupyter_code>def move_tower(height, from_pole, to_pole, with_pole, tracing_execution=False, move_verbose=True):
    if height >= 1:
        move_tower(height - 1, from_pole, with_pole, to_pole, tracing_execution, move_verbose)
        if tracing_execution:
            print(f"move_tower({height - 1}, {from_pole}, {with_pole}, {to_pole})")
        move_disk(from_pole, to_pole, move_verbose)
        if tracing_execution:
            print(f"move_disk({from_pole}, {to_pole})")
        move_tower(height - 1, with_pole, to_pole, from_pole, tracing_execution, move_verbose)
        if tracing_execution:
            print(f"move_tower({height - 1}, {with_pole}, {to_pole}, {from_pole})")

def move_disk(from_p, to_p, verbose=True):
    if verbose:
        print("moving disk from", from_p, "to", to_p)

move_tower(3, "A", "B", "C", True, False)<jupyter_output>move_tower(0, A, C, B)
move_disk(A, B)
move_tower(0, C, B, A)
move_tower(1, A, B, C)
move_disk(A, C)
move_tower(0, B, A, C)
move_disk(B, C)
move_tower(0, A, C, B)
move_tower(1, B, C, A)
move_tower(2, A, C, B)
move_disk(A, B)
move_tower(0, C, B, A)
move_disk(C, A)
move_tower(0, B, A, C)
move_tower(1, C, A, B)
move_disk(C, B)
move_tower(0, A, C, B)
move_disk(A, B)
move_tower(0, C, B, A)
move_tower(1, A, B, C)
move_tower(2, C, B, A)<jupyter_text>By reading from the top to the bottom, we have the call stack when calling the tower of Hanoi algorithm with three disks and three poles.  2. Using the recursive rules as described, draw a Sierpinski triangle using paper and pencil.We just describe how to draw it. First off, we need the code.<jupyter_code>import turtle

def draw_triangle(points, color, my_turtle):
    my_turtle.fillcolor(color)
    my_turtle.up()
    my_turtle.goto(points[0][0], points[0][1])
    my_turtle.down()
    my_turtle.begin_fill()
    my_turtle.goto(points[1][0], points[1][1])
    my_turtle.goto(points[2][0], points[2][1])
    my_turtle.goto(points[0][0], points[0][1])
    my_turtle.end_fill()


def get_mid(p1, p2):
    return ((p1[0] + p2[0]) / 2, (p1[1] + p2[1]) / 2)


def sierpinski(points, degree, my_turtle):
    colormap = ["blue", "red", "green", "white", "yellow", "violet", "orange"]
    draw_triangle(points, colormap[degree], my_turtle)
    if degree > 0:
        sierpinski(
            [points[0], get_mid(points[0], points[1]), get_mid(points[0], points[2])],
            degree - 1,
            my_turtle,
        )
        sierpinski(
            [points[1], get_mid(points[0], points[1]), get_mid(points[1], points[2])],
            degree - 1,
            my_turtle,
        )
        sierpinski(
            [points[2], get_mid(points[2], points[1]), get_mid(points[0], points[2])],
            degree - 1,
            my_turtle,
        )<jupyter_output><empty_output><jupyter_text>At each recursive call, `degree` is decreased: degree tells us how many triangles are we going to draw, at each of the three sides. Therefore, we start with the leftmost triangle(s), and after the inner-most triangle is done being drawn (`degree` is zero in this subcall), we proceed to draw the next (righ-most) triangle, from the inside out.  3. Using the dynamic programming algorithm for making change, find the smallest number of coins that you can use to make 33 cents in change. In addition to the usual coins assume that you have an 8 cent coin.<jupyter_code>def coin_change(change, coins_available):
    min_amounts = []

    for i in range(change + 1):
        min_amounts += [[i, []]]

        min_change = i
        min_amount = [[1]] * i

        for coin in [c for c in coins_available if c <= i]:
            if 1 + min_amounts[i - coin][0] < min_change:
                min_change = 1 + min_amounts[i - coin][0]
                min_amount = [coin] + min_amounts[i - coin][1]
        
        min_amounts[i][0] = min_change
        min_amounts[i][1] = min_amount
        
    return min_amounts[change][1]

coin_change(33, [1, 2, 5, 8, 10, 20, 50])<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.12879850397381953, 'fraction_numerical': 0.02244039270687237, 'mean_word_length': 3.406797116374871, 'pattern_counts': {'":': 0, '<': 14, '<?xml version=': 0, '>': 14, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '459245', 'license': 'MIT', 'n_tokens_mistral': 1618, 'n_tokens_neox': 1516, 'n_words': 452, 'path': 'chapter5/chapter5_questions.ipynb', 'repo_name': 'RiccardoMPesce/PythonDS3-Selected-Assignments', 'size': '4278'}