9021_TUT_7

Exercise 1

what is yield in python?

The yield keyword in Python is used to create generator functions. A generator function is a special kind of function that returns a generator iterator, which can be used to iterate over a sequence of values. Unlike a regular function that returns a single value using the return statement, a generator function can yield multiple values, one at a time, pausing its state between each one.

How it works?

When a generator function is called, it doesn’t execute its code immediately. Instead, it returns a generator object that can be iterated over. Each time you request the next item from the generator (using next() or a loop), the generator function resumes execution from where it last left off, runs until it hits a yield statement, and yields the value to the caller.

Problem Description

First, we need to understand the requirements of the problem:

Input: A list of integers L, such as [n1, n2, n3, …]. Output:

• Output n1 lines of rank 1 X, which means X without indentation.
• Between each pair of rank 1 X, output n2 lines of rank 2 X, which are indented with one tab (\t).
• Between each pair of rank 2 X, output n3 lines of rank 3 X, which are indented with two tabs.
• Continue this pattern until all elements in the list L have been processed.

My solution

def f1():
    while True:
        print(" /\\")
        print("/  \\")
        yield
        print("----")
        yield
        print("\\  /")
        print(" \\/")
        yield
        print(" ||")
        print(" ||")
        yield

Standard solution

def f1():
    while True:
        print(' /\\\n/  \\')
        yield
        print('----')
        yield
        print('\\  /\n \\/')
        yield
        print(' ||\n ||')
        yield

Exercise 2

Problem Description

Line:   [1,   3,   3,   1]
           |     |     |
          i=0   i=1   i=2
           ↓     ↓     ↓
Calculate:1+3   3+3   3+1
           ↓     ↓     ↓
Results:   4     6     4

My solution

def f2():
    # initialized
    row = [1]
    while True:
        yield row
        # row[i] + row[i + 1] is the expression in list comprehension
        row = [1] + [row[i] + row[i + 1] for i in range(len(row)-1)] + [1]

Standard solution

def f2():
    L = [1]
    yield L
    while True:
        L = [1] + [L[i] + L[i + 1] for i in range(len(L) - 1)] + [1]
        yield L

Exercise 3

Problem Description

First, we need to understand the requirements of the problem:

Input: A list of integers L, such as [n1, n2, n3, …]. Output:

• Output n1 lines of rank 1 X, which means X without indentation.
• Between each pair of rank 1 X, output n2 lines of rank 2 X, which are indented with one tab (\t).
• Between each pair of rank 2 X, output n3 lines of rank 3 X, which are indented with two tabs.
• Continue this pattern until all elements in the list L have been processed.

My solution

def f3(L):
    def helper(L, rank):
        if not L:
            return
        n = L[0]
        for i in range(n):
            print('\t' * rank + 'X')
            if i < n - 1:
                helper(L[1:], rank + 1)
    helper(L, 0)

We need to write a recursive function to handle this nested structure. Here is the implementation idea:

Define a helper function helper(L, rank), where:

• L is the list currently being processed.
• rank is the current level (indentation level).

In the helper function:

1. If the list is empty, return directly.
2. Get the number of lines to output at the current level, n = L[0].
3. Use a loop to output n lines of the current level’s X, with each line having the corresponding number of tab characters (\t) based on the rank.
4. After each output, if it is not the last element and it is not the last line, recursively call helper to handle the next level of X lines.

Standard solution

def f3(L):
    _f3(L, 0)

def _f3(L, n):
    if n == len(L):
        return
    for _ in range(L[n] - 1):
        print('\t' * n, 'X', sep='')
        _f3(L, n + 1)
    if L[n]:
        print('\t' * n, 'X', sep='')

Exercise 4

Problem Description

Objective: Given a list L of integers, we need to:

• Break it down into sublists of equal length, where the length is maximal.
• This process is recursive: each sublist is further broken down in the same manner.
• The original list should be preserved (i.e., not modified).

Key Points:

• We aim to split the list into the largest possible sublists of equal length (greater than 1) that evenly divide the length of the list.
• The recursion continues until a sublist cannot be broken down further (i.e., its length cannot be divided into equal parts greater than 1).

My solution

from math import sqrt

def f4(L):
    n = len(L)
     # Try to find the maximal sublist length greater than 1
    for sublist_length in range(n // 2, 1, -1):
        if n % sublist_length == 0:
            # Split the list into sublists
            sublists = [f4(L[i:i + sublist_length]) for i in range(0, n, sublist_length)]
            return sublists
    return L.copy()

Standard solution

def f4(L):
    for n in range(2, round(sqrt(len(L))) + 1):
        if len(L) % n == 0:
            w = len(L) // n
            return [f4(L[i : i + w]) for i in range(0, len(L), w)]
    return list(L)

Exercise 5

Problem Description

Objective: Given a special list L (a list whose elements are integers or other special lists), we need to return a dictionary where:

Keys are tuples of indices (i_1, i_2, ..., i_n).
Values are integers e.
The keys represent the path of indices to reach an integer e within the nested list structure.

Interpretation:

• If the key is (i_1,), then L[i_1] is an integer e.
• If the key is (i_1, i_2), then L[i_1][i_2] is an integer e.
• If the key is (i_1, i_2, i_3), then L[i_1][i_2][i_3] is an integer e.
• And so on.

Constraints:

We need to handle any depth of nesting.
Use isinstance() to check if an element is an integer or a list.
The original list should not be modified.

My solution

def f5(L):
    result = {}
    def helper(sublist, path):
        for index, element in enumerate(sublist):
            current_path = path + (index,)
            if isinstance(element, int):
                result[current_path] = element
            elif isinstance(element, list):
                helper(element, current_path)
            else:
                # If there are other types, you might want to handle them or raise an error
                pass
    helper(L, ())
    return result

Standard solution

def f5(L):
    D = {}
    for i in range(len(L)):
        if isinstance(L[i], int):
            D[(i,)] = L[i]
        else:
            E = f5(L[i])
            for s in E:
                D[i, *s] = E[s]
    return D

Difference between my solution and the standard solution

My Solution

• Uses a Helper Function (helper): Your solution defines an inner function helper(sublist, path) to handle the recursion.
• Explicit Path Passing: The path variable, representing the current position in the nested list, is explicitly passed and updated at each recursive call.
• State Encapsulation: By using a nested function, the state (path and result) is encapsulated within the f5 function’s scope.
  Standard Solution
• Direct Recursion: The standard solution directly calls f5(L[i]) recursively without using a helper function.
• Implicit Path Construction: It constructs the path by combining the current index i with the indices from the recursive call (s) using tuple unpacking.
• Dictionary Merging: After each recursive call, it merges the returned dictionary E into the current dictionary D.

Exercise 6

Problem Description

The given problem is not strictly about the Fibonacci sequence, but it generalizes similar principles to a broader set of recursive relationships. In the problem, you’re asked to compute the n-th term of a series, where the series is defined by some initial terms (first_terms) and a set of recurrence factors (factors). The Fibonacci sequence is a special case of such a recurrence relation, where each term is the sum of the two preceding terms.

My solution(Wrong)

def f6(first_terms, factors, n):
    k = len(first_terms) - 1
    sequence = first_terms.copy()
    
    # If n is within the initial terms, return it directly
    if n <= k:
        return sequence[n]
    
    # Compute terms iteratively up to n
    for i in range(k + 1, n + 1):
        xi = 0
        for s in range(k + 1):
            xi += factors[s] * sequence[i - k - 1 + s]
        sequence.append(xi)
    
    return sequence[n]

Standard solution

def f6(first_terms, factors, n):
    series = {i: first_terms[i] for i in range(len(first_terms))}
    _f6(factors, n, series)
    return series[n]
    
def _f6(factors, n, series):
    if n in series:
        return
    x = 0
    for i in range(1, len(factors) + 1):
        _f6(factors, n - i, series)
        x += factors[-i] * series[n - i]
    series[n] = x