9021_TUT_4

Exercise 1

Problem Description

At first, I thought this exercise was about dividing by a modulus, where the modulus would always be incremented by one. But then I realized that in some cases, there’s no “2” in the division sequence. For example, for 12, the answer is 12 6 3 1\n. This indicates that the number is always being divided by 2.

When we look at the examples of these answers, we can see that the format aligns each number to the right, based on the width of the largest number.

%%run_and_test python3 -c "from exercise_4_1 import f1; f1(13)"

'''
 13  6  3  1\n
 12  6  3  1\n
 11  5  2  1\n
 10  5  2  1\n
  9  4  2  1\n
  8  4  2  1\n
  7  3  1\n
  6  3  1\n
  5  2  1\n
  4  2  1\n
  3  1\n
  2  1\n
  1\n
'''

So we have the following solution:

# Assume that the argument n is an integer at least equal to 1.
#
# Each integer is printed out in a field of size equal to
# the number of digits in n plus 1.
#
# The output is printed out, not returned.

def f1(n):
    w = len(str(n)) + 1
    for i in range(n, 0, -1):
        while i:
            print(f'{i:{w}}', end="")
            i = i // 2
        print()
    return

Complexity Analysis

The time complexity of this algorithm is O(n log n), where n is the input number. This is because we are dividing the number by 2 until we reach 1. The space complexity is O(1) because we are not using any additional data structures.

Exercise 2

Problem Description

This exercise asks us to repeatedly remove the maximum number from the set until only one element remains. The line print(“A list of sets:”, all(isinstance(x, set) for x in S)) checks if the return value of f2 is a list of sets.

In my solution:

def f2(S: set[int]):
    ans = []
    s_list = list(S)  # Convert the set to a list
    s_list.sort()  # Sort the list
    while len(s_list) > 0:
        ans.append(set(s_list))  # Append the current set
        s_list.pop()  # Pop the last (largest) element
    return ans

I convert the set to a list because tuples don’t have a sort() method. So I convert it, sort it, and then pop the largest element (which is at the end of the list) while the length is greater than 1.

The standard solution is:

def f2(S):
    U = [set(S)]
    while len(S) > 1:
        S.remove(max(S))  # Remove the maximum element
        U.append(set(S))  # Append the current set
    return U

The standard solution is simpler; it uses max() to find and remove the largest element, then appends the result to the list.

Standard solution is better because it is more concise and uses less memory.

Exercise 3

Problem Description

As per the description of Exercise 4, we need to remove elements that are equal to the mean value of their neighboring elements (i.e., the element is the average of the one just before and the one just after it).
Please pay attention to the special challenge: use only one loop without any break or continue statements, and only one if statement (with no elif nor else statements).

In my solution:

# Assume that the argument L is an increasing list of integers.
#
# Keep removing any member of the list
# that is neither the first one nor the last one
# and that is the average of the one just before and the one just after.
#
# Special challenge: use only one loop without any break or continue statements,
# and only one if statement (with no elif nor else statements).
def f3(L):
    for i in range(len(L) - 2):
        if L[i] + L[i + 2] == 2 * L[i + 1]:  # Check if the middle element is the average
            L.pop(i + 1)  # Remove the element if it satisfies the condition
            return f3(L)  # Recurse to check the rest of the list
    return L

Explanation:

• The function iterates through the list, checking if any element (except the first and last) is the average of its neighbors.

• If an element meets this condition, it’s removed using pop(), and the function calls itself recursively to continue checking the remaining list.

• This approach ensures that all elements satisfying the condition are removed.

• The main reason for using recursion in the original code is to avoid i going beyond the scope of the list, because the length of the list changes each time an element is deleted, so in the original for loop, the index may exceed the length of the list. Recursion avoids this situation by re-calling the function and re-traversing the list from the beginning.

When we use for i in sth. in Python, i is essentially a “view” or a “shallow copy” of the elements in sth.. Modifying i directly will not change sth. itself. Additionally, we cannot modify the value of i, because in each iteration of the loop, i is reset to the next element in the sequence.
This means that if we use a for loop directly in this context, and we remove an element from the list during the loop, the list will get shorter. As a result, i could end up being out of range in subsequent iterations of the loop.

The standard solution is:

def f3(L):
    i = 0
    while (i := i + 1) < len(L) - 1:
        if L[i - 1] + L[i + 1] == L[i] * 2:
            L.pop(i)
            i -= 1
    return L

Explanation:

The while loop version of the code does avoid recursion, and manually manages the value of i to ensure that the index does not exceed the range after the list is deleted. This reduces the complexity of the recursive call while achieving the same effect.

Key points:

• The function uses only one loop and one if statement as required by the challenge.
• Recursion is used to continue processing after each removal.

Exercise 4

Problem Description

You are given an integer n, and the goal is to express n as a sum (or difference) of powers of 2. This should be done by leveraging the binary representation of n.
Specifically, you need to:

1. Convert n to its binary form.
2. Identify which positions in the binary form have a 1.
3. Use these positions to generate the corresponding powers of 2.
4. If n is positive, add the powers of 2 together. If n is negative, subtract the powers of 2.
   The output should be in the form of an equation, displaying the original number as the sum (or difference) of powers of 2.

Example 1:

For n = 13:

The binary representation of 13 is 1101.
This corresponds to 2^3 + 2^2 + 2^0, because the 3rd, 2nd, and 0th positions in the binary number are 1.

Output: 13 = 2^3 + 2^2 + 2^0

Explanation:

The function f4(n) converts an integer n into a sum of powers of 2 based on its binary representation. Let’s go through the code:

1. Handling the case when n is zero:

   if not n:
       print('0 = 0')
       return

   This part checks if n is zero using if not n. If n is zero, the function prints 0 = 0 and returns immediately, since zero doesn’t need further decomposition into powers of 2.

2. Converting the number to binary:

   binary_n = f'{n:b}'

   The f'{n:b}' converts the integer n to its binary form as a string (without the 0b prefix). For example, if n = 13, binary_n will be 1101.

3. Finding the positions of 1s in the binary representation:

   powers = (i for i in range(len(binary_n)) if binary_n[i] == '1')

   This list comprehension creates a list of indices where the binary digit is 1. For 1101, the positions list will be [0, 2, 3].

   • This is a generator expression that finds the positions (indices) in the binary string where there is a 1.
   • range(len(binary_n)) iterates over each character in the binary string, and the condition binary_n[i] == '1'filters out the positions where there is a 1.
   • For example, if n = 13 and binary_n = '1101', the positions of 1s would be (0, 2, 3), because the first, third, and fourth bits from the right are 1.

4. print(operator.join(f’2^{len(binary_n) - i - 1}’ for i in powers))

   print(operator.join(f'2^{len(binary_n) - i - 1}' for i in powers))

   • This is the key part of the function that prints the powers of 2 based on the positions of 1s in the binary representation.
     • f'2^{len(binary_n) - i - 1}' creates strings like 2^3, 2^2, 2^0 by converting each position i into the corresponding exponent for 2. The exponent is calculated as len(binary_n) - i - 1, where i is the position of the 1 in the binary string.
     • operator.join(...) joins all these terms together with either' + 'or' - 'depending on the value of n.

Exercise 5

To solve next problems, lets first understand the zip function in Python.

1. Let’s try:

L1 = [1, 2, 3]
L2 = [4, 5, 6]
print(list(zip(L1, L2)))

Output:

[(1, 4), (2, 5), (3, 6)]

And zip in dictionary:

L1 = [1, 2, 3]
L2 = [4, 5, 6]
print(dict(zip(L1, L2)))

Output:

[(1, 4), (2, 5), (3, 6)]
{1: 4, 2: 5, 3: 6}

The finally we try using zip with *, which is used to unpack the elements of a list or tuple:

L = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
for i in zip(L):
    print(i)

for i in zip(*L):
    print(i)

Output:

([1, 2, 3],)
([4, 5, 6],)
([7, 8, 9],)
(1, 4, 7)
(2, 5, 8)
(3, 6, 9)

Problem Description

In this problem, we can identify the pattern by observing the example: start from the first and last elements of a list and progressively make pairs towards the center of the list.

My initial thought was to use a two-pointer approach: one pointer starts at the beginning of the list, and the other starts at the end, and they move towards each other. However, I missed the specific requirement in the problem: “Return an expression built only from list, reversed, and zip.”

Wrong Solution:

def f5(*L):
    ans = []
    left = 0
    right = len(L) - 1
    while left < len(L):
        ans.append(((L[left], L[right]), (L[right], L[left])))
        left += 1
        right -= 1
    return ans

Correct Solution:

def f5(*L):
    return list(zip(zip(L, reversed(L)), reversed(list(zip(L, reversed(L))))))

The idea behind the correct solution is as follows:

1. zip(L, reversed(L)) creates pairs of elements where the first comes from L and the second comes from reversed(L) (i.e., L reversed).
   Example: If L = (1, 2, 3), then reversed(L) is (3, 2, 1). So, zip(L, reversed(L)) results in [(1, 3), (2, 2), (3, 1)].

2. reversed(list(zip(L, reversed(L)))): Here, we convert the result of zip(L, reversed(L)) into a list and then reverse the entire list.
   Example: If zip(L, reversed(L)) produced [(1, 3), (2, 2), (3, 1)], then reversed(list(zip(L, reversed(L)))) will return [(3, 1), (2, 2), (1, 3)].

3. zip(zip(L, reversed(L)), reversed(list(zip(L, reversed(L))))): This part pairs the result of zip(L, reversed(L)) with its reversed version. It takes corresponding elements from both sequences and forms pairs.
   Example: If zip(L, reversed(L)) is [(1, 3), (2, 2), (3, 1)] and its reverse is [(3, 1), (2, 2), (1, 3)], then zip(zip(L, reversed(L)), reversed(list(zip(L, reversed(L))))) produces pairs of tuples like:

   • ((1, 3), (3, 1))
   • ((2, 2), (2, 2))
   • ((3, 1), (1, 3))

Finally, this expression is wrapped in list() to convert the zip object into a list of tuples.

Exercise 6

Problem Description

Exercise 6 is similar to Exercise 5, requiring us to use zip, *, and list to solve the problem. We are given a variable number of arguments *L, and the goal is to output them in the form of [(...), (...)]. This task is simpler than the previous one, as the pairing only needs to reverse and mirror the elements.

At first, I attempted the following approach:

Wrong Solution:

def f6(*L):
    return list(zip(zip(L, reversed(L)), zip(reversed(L), L)))

I tried using zip to pair elements in forward and reverse order:

zip(L, reversed(L)) pairs the elements of L with the reversed version of L, while zip(reversed(L), L) pairs them in the reverse order.

However, the output of this solution was:

[((0, 1), (1, 0)), ((1, 0), (0, 1))]

This did not meet the requirements, as the pairs (0, 1) and (1, 0) were grouped separately. The correct format should have 0, 1, 1, 0 in the same tuple.

Correct Solution:

def f6(*L):
    return list(zip(*zip(L, reversed(L)), *zip(reversed(L), L)))

Explanation of the Fix:

To achieve the desired output, we need to flatten or “unpack” the pairs created by zip(L, reversed(L)) and zip(reversed(L), L) into individual elements and combine them correctly. This is where the * operator comes in, which unpacks the results from the zip function.

By using * before zip(L, reversed(L)) and zip(reversed(L), L), you effectively unpack the tuples into separate elements, allowing the outer zip function to combine them in the desired form.

• *zip(L, reversed(L)): This unpacks the paired tuples from L and reversed(L). Instead of getting pairs like (0, 1), it unpacks them into 0, 1, 1, 0.

• *zip(reversed(L), L): Similarly, this unpacks the reversed pairs.

The final zip call then combines these unpacked elements into the correct tuple format. The result is:

[(0, 1, 1, 0), (1, 0, 0, 1)]

This ensures that the mirrored pairs are placed together in the same tuple as required by the problem.