9021_TUT_6

字数统计: 2.7k字   |   阅读时长: 16min

Exercise 1

Problem description

It is hard to find the pattern of the input and output. But through this example:

1
2
3
4
5
6
statements = 'from exercise_6_1 import f1; '\
            'L = [[4, 8], [6, 3, 0], [7]]; print(f1(L))'

%%run_and_test python3 -c "$statements"

'([0, 3, 4, 6, 7, 8], [[0, 3], [4, 6, 7], [8]])\n'

We need to sort the elements into a one-dimensional list and then split them according to the lengths of the sublists in the input.

My Solution

So, the function f1 should be like this:

1
2
3
4
5
6
7
8
9
10
11
12
def f1(L):
    # Calculate the length of each sublist
    lengths = [len(i) for i in L]
    # Split the list into a one-dimensional list
    P = [i for j in L for i in j]
    P.sort()
    ans = []
    flag = 0
    for i in range(len(L)):
        ans.append(P[flag: flag + lengths[i]])
        flag += lengths[i]
    return P, ans

Standard Solution

1
2
3
4
5
6
7
8
def f1(L):
    lengths = [len(L1) for L1 in L]
    F = sorted(e for L1 in L for e in L1)
    R = []
    i = 0
    for n in range(len(L)):
        R.append(F[i : (i := i + lengths[n])])
    return F, R

Explanation

The difference between the two solutions is that the standard solution uses the walrus operator := to simplify the code. The walrus operator is a new feature in Python 3.8. It is used to assign a value to a variable as part of an expression. It is useful when you want to assign a value to a variable and use that value in the same expression.

Exercise 2

Problem description

This exercise ask us to output the sum of diagonal elements of a matrix. Based on the line where i, j are located.
We can use Numpy to solve this problem. It has a function numpy.diagonal() that can return the diagonal elements of a matrix.

My Solution

1
2
3
4
5
6
7
8
9
10
11
12
import numpy as np

def f2(L, i, j, major=True):
    # Convert L to a numpy array for easier indexing
    L = np.array(L)
    i -= 1
    j -= 1
    if major:
        dia = sum(np.diag(L, k= j - i))
    else:
        dia = sum(np.diag(np.fliplr(L), k= (len(L) - 1 - j) - i))
    return dia

Explanation

In a normal matrix, the np.diag() function allows extracting diagonals at different offsets, where the offset k=0 represents the main diagonal.

When we flip the matrix, the coordinates for each cell change in such a way that we need to adjust our calculation of the offset accordingly.

Specifically, for a matrix of size n, flipping it means that the column index j of the original matrix transforms to (n - 1 - j) in the flipped version. Hence, when we want to calculate the offset of the diagonal that passes through (i, j) in the original matrix, we need to determine the offset using (n - 1 - j) - i to correctly represent the position in the flipped version.

Standard Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def f2(L, i, j, major=True):
    i1 = i = i - 1
    j1 = j = j - 1
    the_sum = L[i1][j1]
    if major:
        while (i1 := i1 - 1) >= 0 and (j1 := j1 - 1) >= 0:
            the_sum += L[i1][j1]
        i1, j1 = i, j
        while (i1 := i1 + 1) < len(L) and (j1 := j1 + 1) < len(L):
            the_sum += L[i1][j1]
    else:
        while (i1 := i1 - 1) >= 0 and (j1 := j1 + 1) < len(L):
            the_sum += L[i1][j1]
        i1, j1 = i, j
        while (i1 := i1 + 1) < len(L) and (j1 := j1 - 1) >= 0:
            the_sum += L[i1][j1]
    return the_sum

Explanation

The standard solution uses a while loop to iterate through the elements of the matrix based on the given indices i and j. It calculates the sum of the diagonal elements by moving in the specified direction (major or minor diagonal) and updating the sum accordingly.

Exercise 3

Problem description

This exercise involves swapping elements in a square matrix with an even side length such that each element in a specified half (‘top’, ‘bottom’, ‘left’, or ‘right’) is at least equal to its diagonally opposite element.

If the half is ‘top’ or ‘left’, the element in that half should be at least equal to the diagonally opposite one, otherwise they should be swapped. Conversely, if the half is ‘bottom’ or ‘right’, the element in the other half should be swapped if it is greater.

Standard Solution

The solution is implemented by creating a copy of the matrix and then iterating over the relevant half to determine if swapping is necessary based on the given criteria.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# Assume that the argument L is a list of lists of integers
# that displays as a square with an even side length
# and the argument half is one of
# 'top', 'bottom', 'left' or 'right'.

# Possibly swaps elements that are diagonally opposite
# so that the element in the "half" part of the square is
# at least equal to the other element.

def f3(L, half='top'):
    # Create a copy of the original list to avoid modifying it directly
    L1 = [list(row) for row in L]
    n = len(L)
    
    # Define ranges based on the specified half
    ranges = {
        'top': (range(n // 2), range(n)),
        'bottom': (range(n // 2, n), range(n)),
        'left': (range(n), range(n // 2)),
        'right': (range(n), range(n // 2, n))
    }
    
    # Iterate through the specified half and possibly swap diagonally opposite elements
    for i in ranges[half][0]:
        for j in ranges[half][1]:
            if L[i][j] < L[-i - 1][-j - 1]:
                L1[i][j], L1[-i - 1][-j - 1] = L1[-i - 1][-j - 1], L1[i][j]
    
    return L1

Explanation

The approach in my solution uses a dictionary to define the ranges for each half of the matrix. By iterating over these ranges, it ensures that only the elements in the specified half are considered. If the element in the specified half is smaller than its diagonally opposite counterpart, they are swapped.

The ranges dictionary defines which rows and columns are to be iterated based on the specified half:

  • 'top' considers the top half of the matrix (rows from 0 to n//2)
  • 'bottom' considers the bottom half of the matrix (rows from n//2 to n)
  • 'left' considers the left half of the matrix (columns from 0 to n//2)
  • 'right' considers the right half of the matrix (columns from n//2 to n)

The values are swapped only if they do not meet the condition defined for the given half.

Exercise 4

Problem description

This exercise involves creating a visual pattern on an n x n grid using two different characters to represent black and white cells. The argument n is an integer at least equal to 1, and the argument black_center is either True or False, which influences the color of the center of the grid. The function should use np.full() to create the grid and modify it using simple loops without nested loops.

The function prints the grid instead of returning it.

My Solution

The solution starts by creating an n x n grid initialized entirely to either black or white, depending on whether the center should be black or not. The function then iteratively adjusts concentric squares within the grid, switching the colors as needed.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import numpy as np

def black(i, black_centre):
    return (i % 4 in {1, 2}) ^ (not black_centre)

def f4(n, black_centre=True):
    # Create the initial grid based on the color of the center
    grid = np.full((n, n), '⬛') if black(n, black_centre)\
                                 else np.full((n, n), '⬜')
    # Adjust concentric squares within the grid
    for i in range(1, n // 2 + 1):
        grid[i : n - i, i : n - i] = '⬛' if black(n - 2 * i, black_centre)\
                                           else '⬜'
    # Print the grid row by row
    for row in grid:
        print(*row, sep='')

Explanation

  • The function black(i, black_centre) determines the color of the concentric square based on the current size i and whether the center should be black (black_centre argument).
  • The np.full() function is used to create the grid, either filled with black (‘⬛’) or white (‘⬜’), depending on the value of black(n, black_centre), which determines the color of the center.
  • The for loop iterates through half of the matrix (n // 2), adjusting each concentric square layer by layer.
    • The slicing operation grid[i : n - i, i : n - i] selects the relevant inner square and fills it with either black or white, alternating colors as determined by black(n - 2 * i, black_centre).
  • Finally, the grid is printed row by row, with each character printed consecutively for easy visualization.

Standard Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import numpy as np

def black(i, black_centre):
    return (i % 4 in {1, 2}) ^ (not black_centre)

def f4(n, black_centre=True):
    # Create the grid, starting with the initial color based on the center
    grid = np.full((n, n), '⬛' if black(n, black_centre) else '⬜')
    # Iterate to adjust each concentric layer
    for i in range(1, n // 2 + 1):
        color = '⬛' if black(n - 2 * i, black_centre) else '⬜'
        grid[i:n-i, i:n-i] = color
    # Print the grid
    for row in grid:
        print(''.join(row))

Explanation

The standard solution follows a similar approach to my solution but uses slightly different syntax to achieve the same result:

  • The grid is created using np.full(), just like in my solution.
  • The loop iterates through each concentric layer, updating the color accordingly. The variable color is used to determine what color each inner square should be, making the assignment more readable.
  • The grid is printed in a slightly different way by joining the row’s elements into a single string (print(''.join(row))). This makes the output cleaner by removing the spaces between characters, which is purely aesthetic.

The primary differences between my solution and the standard solution are the use of inline expressions for color selection and minor differences in how the final output is formatted when printed.

Exercise 5

Try it!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import numpy as np

# Define a 2D NumPy array (matrix)
array = np.array([[1, 2, 3],
                  [4, 5, 6],
                  [7, 8, 9]])

# Sum all elements
total_sum = np.sum(array)  # Output: 45

# Sum along rows (axis=1)
row_sums = np.sum(array, axis=1)  # Output: [6, 15, 24]

# Sum along columns (axis=0)
column_sums = np.sum(array, axis=0)  # Output: [12, 15, 18]

print(total_sum, row_sums, column_sums)

Problem description

The exercise is to compute the sum of elements in a given row and column and display a colored square at their intersection based on the sign of the sum:

  • A blue square (‘🟦’) if the sum is 0.
  • A green square (‘🟩’) if the sum is strictly positive.
  • A red square (‘🟥’) if the sum is strictly negative.

For example, given a list of lists representing the matrix:

1
2
3
.  .  2  .  .
2  0 -3  7 -4
.  . -4  .  .

The function should compute the sum for each row and column, and update the intersection elements accordingly.

The function should use np.sum() and np.sign() to simplify calculations, and should use at most loops within loops, avoiding deeper nesting.

The output is printed, not returned.

My Solution

The solution uses NumPy to calculate the sum of each row and column. The function then iterates through the given list and determines the sign of the sum at each intersection, displaying the appropriate color.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import numpy as np

def f5(L):
    # Convert L to a numpy array for easier manipulation
    L = np.array(L)
    n_rows, n_cols = L.shape
    
    # Calculate row and column sums
    row_sums = np.sum(L, axis=1)
    col_sums = np.sum(L, axis=0)
    
    # Iterate through the list and determine the color for each intersection
    for i in range(n_rows):
        row = []
        for j in range(n_cols):
            intersection_sum = row_sums[i] + col_sums[j] - L[i][j]  # Avoid double counting L[i][j]
            if intersection_sum == 0:
                row.append('🟦')  # Blue square
            elif intersection_sum > 0:
                row.append('🟩')  # Green square
            else:
                row.append('🟥')  # Red square
        print(''.join(row))

# Test with the provided statements
statements = 'from exercise_6_5 import f5; '\
             'f5([[4, -6, -5], [6, -7, 6]])'

%%run_and_test python3 -c "$statements"

'🟥🟥🟥\n'
'🟩🟥🟦\n'

Explanation

  • NumPy Conversion: The list L is converted to a NumPy array to take advantage of the efficient np.sum() function for computing sums.
  • Row and Column Sums: The sums for rows and columns are computed separately using np.sum() with the appropriate axis argument.
  • Iteration for Colors: The function then iterates over each element in the matrix to determine the color of the intersection based on the calculated row and column sums. The color is chosen as follows:
    • '🟦' (blue) for a sum of 0.
    • '🟩' (green) for a strictly positive sum.
    • '🟥' (red) for a strictly negative sum.
  • Output: Finally, the grid is printed row by row.

Standard Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import numpy as np

def f5(L):
    L1 = np.array(L)
    for i in range(L1.shape[0]):
        for j in range(L1.shape[1]):
            L[i][j] = { 0: '🟦',
                        1: '🟩',
                       -1: '🟥'
                      }[np.sign(np.sum(L1[i, :])
                                + np.sum(L1[: , j])
                                - L1[i, j]
                               )
                       ]
    for row in L:
        print(*row, sep='')

Explanation

The standard solution follows a similar approach to my solution but uses a dictionary to map the sign of the sum to the corresponding color. The np.sign() function is used to determine the sign of the sum, and the dictionary is used to select the appropriate color based on the sign.

Exercise 6

Problem description

This exercise is similar to Exercise 5, where we compute the sum of elements in a given row and column and display a colored square at their intersection based on the sign of the sum:

  • A blue square (‘🟦’) if the sum is 0.
  • A green square (‘🟩’) if the sum is strictly positive.
  • A red square (‘🟥’) if the sum is strictly negative.

However, the main differences are:

  • Input Structure: The list L must be a square matrix (i.e., the number of rows equals the number of columns).
  • Optimization Requirement: The solution for f6 must avoid manual loops for computation (except for output). Instead, the solution must use vectorized operations in NumPy to enhance computational efficiency.
  • Advanced NumPy Usage: The exercise explicitly suggests using advanced NumPy functions such as np.vectorize(), np.newaxis, and broadcasting.

The output is printed, not returned.

My Solution

The solution for f6 uses advanced NumPy techniques to fully vectorize the computations without using explicit loops (except for printing). It creates the required colored grid by computing the sum for each row and column and then using a vectorized mapping to determine the color.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import numpy as np

def f6(L):
    L1 = np.array(L)
    # Vectorize the color selection based on the sum of row and column
    for row in np.vectorize(lambda e: { 0: '🟦',
                                        1: '🟩',
                                       -1: '🟥'
                                      }[e]
                           )(np.sign(np.sum(L1, axis=1)[:, np.newaxis]
                                     + np.sum(L1.T, axis=1)
                                     - L1
                                    )
                            ):
        print(*row, sep='')

Explanation

  • Vectorization: The solution uses np.vectorize() to apply a function element-wise over an array, effectively mapping each sum to a specific color.
  • Avoiding Loops: Instead of iterating through each element manually, the solution leverages NumPy’s vectorization to calculate row and column sums simultaneously.
  • Broadcasting and np.newaxis: The use of [:, np.newaxis] helps in broadcasting the row sums across the columns to facilitate efficient addition with the column sums. This allows the entire computation to be performed without explicit looping.
  • Output: Finally, each row is printed with the appropriate color, similar to Exercise 5.

Key Differences from Exercise 5

  1. Input Structure: Exercise 5 allows any list of lists, whereas Exercise 6 requires a square matrix.
  2. Loop Usage: Exercise 5 uses explicit loops to calculate intersection sums, whereas Exercise 6 relies entirely on vectorized operations and avoids manual loops (except for printing).
  3. Efficiency: Exercise 6 is more computationally efficient, as it is designed to handle larger datasets using optimized NumPy operations, whereas Exercise 5 uses loops that can be slower for large matrices.

show all >>

9021_TUT_9

字数统计: 3.2k字   |   阅读时长: 19min

My solution didn’t think about the hidden test cases seriously, please refer to the standard solution.

Exercise 1

The doctest module in Python is a tool for testing code by comparing the output of code snippets written in a program’s docstrings to expected results. It allows developers to write simple test cases as part of their documentation and automatically validate that code behaves as documented.

This exercise requires interpreting a pattern where each argument in vertical_bars() represents the number of asterisks (*) to print in a specific “column” position across multiple lines. Here’s a breakdown of the observed pattern and how to implement it:

  1. The biggest number in the input list determines the number of lines to print.
  2. For each row, iterate over the input list and print the number of asterisk.

My Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
# Note that NONE OF THE LINES THAT ARE OUTPUT HAS TRAILING SPACES.
#
# You can assume that vertical_bars() is called with nothing but
# integers at least equal to 0 as arguments (if any).


def vertical_bars(*x):
    '''
    >>> vertical_bars()
    >>> vertical_bars(0, 0, 0)
    >>> vertical_bars(4)
    *
    *
    *
    *
    >>> vertical_bars(4, 4, 4)
    * * *
    * * *
    * * *
    * * *
    >>> vertical_bars(4, 0, 3, 1)
    *
    *   *
    *   *
    *   * *
    >>> vertical_bars(0, 1, 2, 3, 2, 1, 0, 0)
          *
        * * *
      * * * * *
    '''
    # Determine the height (max value of x)
    height = max(x, default=0)

    # Build each line from top to bottom
    for level in range(height-1, -1, -1):
        line = []
        for num_asterisks in x:
            # If the current level is less than the number of asterisks for this column, add '*'
            if level < num_asterisks:
                line.append('*')
            else:
                line.append(' ')

        # Join line with spaces, removing trailing spaces
        line_output = ' '.join(line).rstrip()
        if line_output:  # Print non-empty lines only
            print(line_output)

if __name__ == '__main__':
    import doctest
    doctest.testmod()

Standard Solution:

1
2
3
4
5
6
if x:
    for i in range(max(x), 0, -1):
        print(' '.join('*' if x[j] >= i else ' '
                           for j in range(len(x))
                      ).rstrip()
             )

Exercise 2

This exercise ask us to find the gaps between successive members of a list and output them in a specific format. The gaps are calculated as the difference between two successive elements where the second element is strictly greater than the first. The output should be sorted by gap value and then by the start of the gap.
So in this exercise, we can use:

  • A dictionary to store the gaps and corresponding pairs of numbers.
  • Two pointers to iterate through the list and calculate the gaps.

My Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
# You can assume that the argument L to positive_gaps()
# is a list of integers.
# 
# Records all gaps between two SUCCESSIVE members of L,
# say a and b, such that b is STRICTLY GREATER than a.
#
# Gap values are output from smallest to largest.
#
# For a given gap value, gaps for that value are output
# from smallest to largest starts of gap, without repetition,
# with 2 spaces before "Between".


from collections import defaultdict


def positive_gaps(L):
    '''
    >>> positive_gaps([])
    >>> positive_gaps([2, 2, 2, 1, 1, 0])
    >>> positive_gaps([0, 1, 1, 2, 2, 2])
    Gaps of 1:
      Between 0 and 1
      Between 1 and 2
    >>> positive_gaps([0, 4, 0, 4, 0, 4])
    Gaps of 4:
      Between 0 and 4
    >>> positive_gaps([2, 14, 1, 14, 19, 6, 4, 16, 3, 2])
    Gaps of 5:
      Between 14 and 19
    Gaps of 12:
      Between 2 and 14
      Between 4 and 16
    Gaps of 13:
      Between 1 and 14
    >>> positive_gaps([1, 3, 3, 0, 3, 0, 3, 7, 5, 0, 3, 6, 3, 1, 4])
    Gaps of 2:
      Between 1 and 3
    Gaps of 3:
      Between 0 and 3
      Between 1 and 4
      Between 3 and 6
    Gaps of 4:
      Between 3 and 7
    >>> positive_gaps([11, -10, -9, 11, 15, 8, -5])
    Gaps of 1:
      Between -10 and -9
    Gaps of 4:
      Between 11 and 15
    Gaps of 20:
      Between -9 and 11
    '''
    # Dictionary to store gaps and corresponding pairs
    gaps_dict = defaultdict(list)

    # Loop through the list to find gaps between successive elements
    for i in range(len(L) - 1):
        gap = L[i + 1] - L[i]

        # Only consider gaps where the second number is strictly greater than the first
        if gap > 0:
            pair = (L[i], L[i + 1])

            # Add the pair to the gap list if it's not already there
            if pair not in gaps_dict[gap]:
                gaps_dict[gap].append(pair)

    # Output gaps sorted by gap value and by start of gap
    for gap in sorted(gaps_dict):
        print(f"Gaps of {gap}:")
        for start, end in sorted(gaps_dict[gap]):
            print(f"  Between {start} and {end}")

Optimize Solution:

we can optimize further by skipping over sequences of consecutive identical numbers, as they do not contribute to any positive gaps. Consecutive identical values (like 2, 2, 2) have zero gaps between them, so we can skip ahead to the next distinct value each time we encounter a repeat.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# Dictionary to store gaps and corresponding pairs
gaps_dict = defaultdict(list)
n = len(L)
i = 0  # Start pointer

# Loop through the list with a while loop to skip identical successive values
while i < n - 1:
    j = i + 1  # Successor pointer

    # Skip consecutive identical numbers
    while j < n and L[j] == L[i]:
        j += 1

    # If we have a new distinct successor and the gap is positive
    if j < n:
        gap = L[j] - L[i]
        if gap > 0:
            pair = (L[i], L[j])

            # Add the pair to the gap list if it's not already there
            if pair not in gaps_dict[gap]:
                gaps_dict[gap].append(pair)

    i = j  # Move i to the new distinct value

# Output gaps sorted by gap value and by start of gap
for gap in sorted(gaps_dict):
    print(f"Gaps of {gap}:")
    for start, end in sorted(gaps_dict[gap]):
        print(f"  Between {start} and {end}")

Standard Solution:

1
2
3
4
5
6
7
8
9
10
11
gaps = defaultdict(set)
for i in range(1, len(L)):
    gap = L[i] - L[i - 1]
    if gap > 0:
        if gap not in gaps or L[i - 1] not in gaps[gap]:
            gaps[gap].add(L[i - 1])
for gap in sorted(gaps):
    print(f'Gaps of {gap}:')
    for start in sorted(gaps[gap]):
        print(f'  Between {start} and {start + gap}')

Exercise 3

his problem requires solving equations of the form $x+y=z$, where each part (x, y, and z) consists of a mix of digits and underscores (_). The underscores represent a missing, single-digit number (0–9), and all underscores must be replaced by the same digit across the entire equation.

Standard Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
def solve(equation):
    '''
    >>> solve('1 + 2 = 4')
    No solution!
    >>> solve('123 + 2_4 = 388')
    No solution!
    >>> solve('1+2   =   3')
    1 + 2 = 3
    >>> solve('123 + 2_4 = 387')
    123 + 264 = 387
    >>> solve('_23+234=__257')
    23 + 234 = 257
    >>> solve('   __   +  _____   =     ___    ')
    0 + 0 = 0
    >>> solve('__ + __  = 22')
    11 + 11 = 22
    >>> solve('   012+021   =   00__   ')
    12 + 21 = 33
    >>> solve('_1   +    2   =    __')
    31 + 2 = 33
    >>> solve('0 + _ = _')
    0 + 0 = 0
    0 + 1 = 1
    0 + 2 = 2
    0 + 3 = 3
    0 + 4 = 4
    0 + 5 = 5
    0 + 6 = 6
    0 + 7 = 7
    0 + 8 = 8
    0 + 9 = 9
    '''
    contains_ = '_' in equation
    found_solution = False
    for digit in '0123456789':
        eq = equation.replace('_', digit)
        left, right = eq.split('=')
        left_1, left_2 = left.split('+')
        left_1 = int(left_1)
        left_2 = int(left_2)
        right = int(right)
        if left_1 + left_2 == right:
            if contains_ or not found_solution:
                print(f'{left_1} + {left_2} = {right}')
            found_solution = True
    if not found_solution:
        print('No solution!')
if __name__ == '__main__':
    import doctest
    doctest.testmod()

Explanation:

Explanation of Each Step

  1. Check for Underscores:

    contains_ = '_' in equation: Determines if there are underscores to replace, which helps decide whether to print solutions for cases without underscores.

  2. Iterate Through Possible Digits (0–9):

    for digit in '0123456789':: This loop iterates over each possible digit that can replace _.

  3. Replace Underscores:

    eq = equation.replace('_', digit): Replaces all underscores with the current digit in equation, creating a new equation string without underscores.

  4. Parse Equation Parts:

    1. left, right = eq.split('='): Splits the equation into the left side (x + y) and the right side (z).

    2. left_1, left_2 = left.split('+'): Further splits the left side into x and y.

    3. Each of these parts (left_1, left_2, and right) is converted to integers to perform arithmetic validation.

  5. Validate the Equation:

    1. if left_1 + left_2 == right: Checks if x + y equals z. If so, the equation is valid with this digit replacement.

    2. The solution is printed with print(f’{left_1} + {left_2} = {right}’) if it’s either the first solution or if the equation contains underscores.

  6. No Solution Case:

    If no valid solution is found after testing all digits, print(‘No solution!’) is called.

Exercise 4

My Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
__rectangle = [['' for _ in range(width)] for _ in range(height)]
row = 0
flag = True
while row < width:
    if flag:
        for line in range(height):
            __rectangle[line][row] = starting_from
            starting_from = chr(ord(starting_from) + 1)
            if starting_from > 'Z':
                starting_from = 'A'
    else:
        for line in range(height - 1, -1, -1):
            __rectangle[line][row] = starting_from
            starting_from = chr(ord(starting_from) + 1)
            if starting_from > 'Z':
                starting_from = 'A'
    row += 1
    flag = not flag
for line in __rectangle:
    print(''.join(line))

Standard Solution:

1
2
3
4
5
6
7
start = ord(starting_from) - ord('A')
for i in range(height):
    for j in range(width):
        offset = start + height * j
        offset = offset + height - i - 1 if j % 2 else offset + i
        print(chr(ord('A') + offset % 26), end='')
    print()

Explanation:

  1. Character Offset Calculation:

    It starts by converting the starting_from character to its corresponding numerical position (using ASCII values).

    Then, it calculates an offset for each character, determining which letter should be printed based on the current row (i) and column (j).

  2. Zigzag Filling:

    1. The columns are filled zigzag-style:

      1. Even columns are filled top-down.
      2. Odd columns are filled bottom-up.

    2. This zigzag pattern is achieved through a condition: offset + height - i - 1 if j % 2 else offset + i. This ensures the characters in each column switch directions depending on whether the column index (j) is even or odd.

  3. Efficient Calculation:

    1. Instead of using nested loops to iterate through and assign each character step-by-step, the solution leverages mathematical modular arithmetic (offset % 26) to ensure that character sequences wrap around from ‘Z’ back to ‘A’.
    2. This method allows for the direct printing of characters, making it memory efficient since it doesn’t need to store the whole matrix beforehand.

Exercise 5:

This problem revolves around finding paths in a 10x10 grid (of dimensions dim = 10). The paths are allowed to connect cells in specific directions, and they must start from one value at the top of the grid and end at another value at the bottom. Here’s a breakdown of the question and solution.

  1. Grid Generation
  2. Path Finding
  3. Displaying Results
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
# You can assume that paths() is called with an integer as first
# argument, an integer at least equal to 1 as second argument,
# and integers between 0 and 9 as third and fourth arguments.
#
# A path connects numbers to numbers by moving South,
# South West or South East.
#
# Note that <BLANKLINE> is not output by the program, but
# doctest's way to refer to an empty line
# (here, output by the print() statement in the stub).


from random import seed, randrange
dim = 10


def display(grid):
    print('   ', '-' * (2 * dim + 1))
    for i in range(dim):
        print('   |', ' '.join(str(j) if grid[i][j] else ' '
                                   for j in range(dim)
                              ), end=' |\n'
             )
    print('   ', '-' * (2 * dim + 1))


def paths(for_seed, density, top, bottom):
    '''
    >>> paths(0, 2, 0, 0)
    Here is the grid that has been generated:
        ---------------------
       | 0 1   3 4 5 6 7 8   |
       |   1     4   6     9 |
       | 0   2 3 4   6 7 8   |
       |     2   4 5   7     |
       |       3     6 7   9 |
       | 0   2   4 5   7 8   |
       | 0         5 6       |
       |       3 4     7 8 9 |
       | 0 1   3   5 6       |
       | 0     3   5 6       |
        ---------------------
    <BLANKLINE>
    Here are all paths from 0 at the top to 0 at the bottom:
        ---------------------
       |                     |
       |                     |
       |                     |
       |                     |
       |                     |
       |                     |
       |                     |
       |                     |
       |                     |
       |                     |
        ---------------------
    >>> paths(0, 4, 6, 7)
    Here is the grid that has been generated:
        ---------------------
       | 0 1   3 4 5 6 7 8 9 |
       | 0 1 2   4 5 6     9 |
       | 0   2 3 4 5 6 7 8   |
       |     2   4 5 6 7   9 |
       | 0 1 2 3     6 7   9 |
       | 0   2 3 4 5   7 8 9 |
       | 0 1 2 3   5 6     9 |
       | 0     3 4 5 6 7 8 9 |
       | 0 1   3   5 6 7 8   |
       | 0   2 3 4 5 6     9 |
        ---------------------
    <BLANKLINE>
    Here are all paths from 6 at the top to 7 at the bottom:
        ---------------------
       |                     |
       |                     |
       |                     |
       |                     |
       |                     |
       |                     |
       |                     |
       |                     |
       |                     |
       |                     |
        ---------------------
    >>> paths(0, 4, 6, 6)
    Here is the grid that has been generated:
        ---------------------
       | 0 1   3 4 5 6 7 8 9 |
       | 0 1 2   4 5 6     9 |
       | 0   2 3 4 5 6 7 8   |
       |     2   4 5 6 7   9 |
       | 0 1 2 3     6 7   9 |
       | 0   2 3 4 5   7 8 9 |
       | 0 1 2 3   5 6     9 |
       | 0     3 4 5 6 7 8 9 |
       | 0 1   3   5 6 7 8   |
       | 0   2 3 4 5 6     9 |
        ---------------------
    <BLANKLINE>
    Here are all paths from 6 at the top to 6 at the bottom:
        ---------------------
       |             6       |
       |           5 6       |
       |         4 5 6 7     |
       |         4 5 6 7     |
       |       3     6 7     |
       |     2 3 4 5   7 8   |
       |       3   5 6     9 |
       |         4 5 6 7 8   |
       |           5 6 7     |
       |             6       |
        ---------------------
    >>> paths(0, 4, 0, 2)
    Here is the grid that has been generated:
        ---------------------
       | 0 1   3 4 5 6 7 8 9 |
       | 0 1 2   4 5 6     9 |
       | 0   2 3 4 5 6 7 8   |
       |     2   4 5 6 7   9 |
       | 0 1 2 3     6 7   9 |
       | 0   2 3 4 5   7 8 9 |
       | 0 1 2 3   5 6     9 |
       | 0     3 4 5 6 7 8 9 |
       | 0 1   3   5 6 7 8   |
       | 0   2 3 4 5 6     9 |
        ---------------------
    <BLANKLINE>
    Here are all paths from 0 at the top to 2 at the bottom:
        ---------------------
       | 0                   |
       |   1                 |
       |     2               |
       |     2               |
       |   1 2 3             |
       | 0   2 3 4           |
       | 0 1 2 3   5         |
       | 0     3 4           |
       |   1   3             |
       |     2               |
        ---------------------
    '''
    seed(for_seed)
    grid = [[int(randrange(density) != 0) for _ in range(dim)]
                 for _ in range(dim)
           ]
    print('Here is the grid that has been generated:')
    display(grid)
    new_grid = [[False] * dim for _ in range(dim)]
    paths = _paths(grid, new_grid, 0, top, dim - 1, bottom)
    grid = new_grid
    print()
    print(f'Here are all paths from', top, 'at the top '
          'to', bottom, 'at the bottom:'
         )
    display(grid)
    

def _paths(grid, new_grid, x1, y1, x2, y2):
    if not grid[x1][y1]:
        return False
    if x1 == x2:
        if y1 == y2 and grid[x2][y2]:
            new_grid[x1][y1] = True
            return True
        return False
    extended = False
    if _paths(grid, new_grid, x1 + 1, y1, x2, y2):
        extended = True
    if y1 and _paths(grid, new_grid, x1 + 1, y1 - 1, x2, y2):
        extended = True
    if y1 < dim - 1 and _paths(grid, new_grid, x1 + 1, y1 + 1, x2, y2):
        extended = True
    if extended:
        new_grid[x1][y1] = True
        return True
    return False
                

if __name__ == '__main__':
    import doctest
    doctest.testmod()

Exercise 6:

Problem Description:

The function word_pairs() takes a string of uppercase letters, called available_letters, and outputs all possible pairs of distinct words from the dictionary.txt file that can be formed using all of the available_letters. Here are some key requirements:

  1. Word Pair Requirements:

    • Each word pair should use all of the letters in available_letters without any leftover.
    • Each letter must be used exactly as many times as it appears in available_letters.
    • A word cannot be used more than once in a pair.
    • The second word in each pair should be lexicographically after the first word.

  2. Output Order:

    • Pairs should be printed with the first word in lexicographic order.
    • For each first word, the corresponding second word should also be in lexicographic order.

Standard Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
# You can assume that word_pairs() is called with a string of
# uppercase letters as agument.
#
# dictionary.txt is stored in the working directory.
#
# Outputs all pairs of distinct words in the dictionary file, if any,
# that are made up of all letters in available_letters
# (if a letter in available_letters has n occurrences,
# then there are n occurrences of that letter in the combination
# of both words that make up an output pair).
#
# The second word in a pair comes lexicographically after the first word.
# The first words in the pairs are output in lexicographic order
# and for a given first word, the second words are output in
# lexicographic order.
#
# Hint: If you do not know the imported Counter class,
#       experiment with it, passing a string as argument, and try
#       arithmetic and comparison operators on Counter objects.


from collections import Counter
dictionary_file = 'dictionary.txt'


def word_pairs(available_letters):
    '''
    >>> word_pairs('ABCDEFGHIJK')
    >>> word_pairs('ABCDEF')
    CAB FED
    >>> word_pairs('ABCABC')
    >>> word_pairs('EOZNZOE')
    OOZE ZEN
    ZOE ZONE
    >>> word_pairs('AIRANPDLER')
    ADRENAL RIP
    ANDRE APRIL
    APRIL ARDEN
    ARID PLANER
    ARLEN RAPID
    DANIEL PARR
    DAR PLAINER
    DARER PLAIN
    DARNER PAIL
    DARPA LINER
    DENIAL PARR
    DIRE PLANAR
    DRAIN PALER
    DRAIN PEARL
    DRAINER LAP
    DRAINER PAL
    DRAPER LAIN
    DRAPER NAIL
    ERRAND PAIL
    IRELAND PAR
    IRELAND RAP
    LAIR PANDER
    LAND RAPIER
    LAND REPAIR
    LANDER PAIR
    LARDER PAIN
    LEARN RAPID
    LIAR PANDER
    LINDA RAPER
    NADIR PALER
    NADIR PEARL
    NAILED PARR
    PANDER RAIL
    PLAN RAIDER
    PLANAR REID
    PLANAR RIDE
    PLANER RAID
    RAPID RENAL
    '''
    letters = Counter(available_letters)
    words = []
    word_counters = {}
    with open(dictionary_file) as dictionary:
        for word in dictionary:
            word = word.strip()
            counter = Counter(word)
            if counter < letters:
                words.append(word)
                word_counters[word] = counter
    for i in range(len(words)):
        for j in range(i + 1, len(words)):
            if word_counters[words[i]] + word_counters[words[j]] == letters:
                print(words[i], words[j])
                

if __name__ == '__main__':
    import doctest
    doctest.testmod()

show all >>

9021_TUT_8

字数统计: 3.6k字   |   阅读时长: 22min

Exercise 1

Problem Description

In this exercise, we are asked to create a class named Prime that keeps track of prime numbers, ensuring certain values are considered valid primes and others are not. The class needs to be capable of:

  1. Raising an error when an input is not a valid integer prime.

  2. Tracking previously seen primes to prevent duplicates.

  3. Resetting the state to allow reprocessing of the primes.

The following Python script is used to test the functionality:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
from exercise_8_1 import *

Prime.reset()
try:
    Prime(1)
except PrimeError as e:
    # 1 is not a prime number
    print(e)
try:
    Prime(2.0)
except PrimeError as e:
    # 2.0 is not a prime number
    print(e)
try:
    Prime([1, 2, 3])
except PrimeError as e:
    # [1, 2, 3] is not a prime number
    print(e)
_ = Prime(2)
try:
    Prime(2)
except PrimeError as e:
    # We have seen 2 before
    print(e)
_ = Prime(3)
try:
    Prime(4)
except PrimeError as e:
    # 4 is not a prime number
    print(e)
_ = Prime(5)
_ = Prime(7)
try:
    _ = Prime(2)
except PrimeError as e:
    # We have seen 2 before
    print(e)
_ = Prime(11)
try:
    Prime(5)
except PrimeError as e:
    # We have seen 5 before
    print(e)
Prime.reset()
_ = Prime(2), Prime(3), Prime(5), Prime(7), Prime(11)

The expected output from running the above code is:

1
2
3
4
5
6
7
'1 is not a prime number\n'
'2.0 is not a prime number\n'
'[1, 2, 3] is not a prime number\n'
'We have seen 2 before\n'
'4 is not a prime number\n'
'We have seen 2 before\n'
'We have seen 5 before\n'

My Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# isinstance() is useful.

# DEFINE A CLASS THAT DERIVES FROM EXCEPTION

class PrimeError(Exception):
pass

class Prime:
_seen_primes = set()  # Track primes that have been created

    def __init__(self, num):
        if not isinstance(num, int):
            raise PrimeError(f"{num} is not a prime number")
        if num < 2 or not self._is_prime(num):
            raise PrimeError(f"{num} is not a prime number")
        if num in self._seen_primes:
            raise PrimeError(f"We have seen {num} before")
        
        # Add the prime to the set if validation passes
        self._seen_primes.add(num)
        self.value = num

    @staticmethod
    def _is_prime(num):
        """Helper function to determine if a number is prime."""
        if num < 2:
            return False
        for i in range(2, int(num ** 0.5) + 1):
            if num % i == 0:
                return False
        return True

    @classmethod
    def reset(cls):
        """Clears the record of tracked primes."""
        cls._seen_primes.clear()

Standard Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# isinstance() is useful.

class PrimeError(Exception):
    pass

class Prime:
    primes = set()
    
    def reset():
        Prime.primes = set()

    def __init__(self, p):
        if not isinstance(p, int) or p < 2 \
           or any(p % k == 0 for k in range(2, p // 2 + 1)):
            raise PrimeError(f'{p} is not a prime number')
        if p in Prime.primes:
            raise PrimeError(f'We have seen {p} before')
        Prime.primes.add(p)

Summary

Here’s a comparison of my version with the standard answer, highlighting the main differences and potential advantages:

  1. Prime Checking Method:

    1. My Version: I use sqrt(num) as the upper limit for prime checking, iterating through for i in range(2, int(num ** 0.5) + 1). This approach is more efficient, especially for larger numbers, as it reduces the number of iterations by only checking up to the square root.
    2. Standard Answer: It checks from 2 to p // 2 for factors, which is slightly less efficient for larger numbers because it performs more division operations.

  2. Code Structure:

    1. My Version: Separates the prime-checking logic into a static method _is_prime, making the code more modular and reusable.
    2. Standard Answer: Integrates the prime-checking logic directly into the constructor. This keeps the code concise but might make it less reusable if the prime-checking logic is needed elsewhere.

  3. Reset Method:

    1. My Version: Uses @classmethod for resetting the _seen_primes set, which is more conventional and allows direct calling as a class method.
    2. Standard Answer: Defines reset as a standalone function without decorators. While it works, it may seem less consistent with typical class conventions.

Exercise 2

Problem Description

In this exercise, we need to implement a class named Modulo that represents numbers in modular arithmetic. The class should:

  1. Validate that the modulus is a prime number.

  2. Ensure that both the number and the modulus are integers.

  3. Represent the number in modular form.

The following Python script is used to test the functionality:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
from exercise_8_2 import *

try:
    Modulo(4, 1)
except PrimeError as e:
    # 1 is not a prime number
    print(e)
try:
    # 2.0 is not a prime number
    Modulo(4, 2.0)
except PrimeError as e:
    print(e)
try:
    Modulo({0}, 7)
except IntError as e:
    # {0} is not an integer
    print(e)
x = Modulo(6, 11)
print(repr(x))
print(x)
y = Modulo(11, 7)
print(repr(y))
print(y)
z = Modulo(-100, 29)
print(repr(z))
print(z)

The expected output from running the above code is:

1
2
3
4
5
6
7
8
9
'1 is not a prime number\n'
'2.0 is not a prime number\n'
'{0} is not an integer\n'
'Modulo(6, 11)\n'
'6 (mod 11)\n'
'Modulo(4, 7)\n'
'4 (mod 7)\n'
'Modulo(16, 29)\n'
'16 (mod 29)\n'

Standard Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# isinstance() is useful.

# DEFINE TWO CLASSES THAT DERIVE FROM EXCEPTION

class IntError(Exception):
    pass
    
class PrimeError(Exception):
    pass

class Modulo:
    def __init__(self, k, p):
        if not isinstance(p, int) or p < 2\
           or any(p % k == 0 for k in range(2, p // 2 + 1)):
            raise PrimeError(f'{p} is not a prime number')
        if not isinstance(k, int):
            raise IntError(f'{k} is not an integer')
        self.modulus = p
        self.k = k % p

    def __repr__(self):
        return f'Modulo({self.k}, {self.modulus})'

    def __str__(self):
        return f'{self.k} (mod {self.modulus})'

Summary

The Modulo class validates its inputs and provides a representation for modular arithmetic:

  • Exception Handling:

    • PrimeError is used when the modulus is not a valid prime number.

    • IntError is used when the input is not an integer.

  • Prime Check:

    • The constructor checks if the modulus is a prime number using a similar approach to the one used in Exercise 8.1 (so I use standard solution directly). If not, it raises PrimeError.

  • Representation:

    • The class overrides __repr__ and __str__ to provide appropriate representations for instances of Modulo.

  • Modular Arithmetic:

    • The value of k is stored in its modular form by computing k % p, which ensures it always remains within the bounds of 0 to p - 1.

Exercise 3

Problem Description

In this exercise, we extend the Modulo class from Exercise 8.2 to support arithmetic operations, specifically addition and multiplication between two Modulo objects. The class should:

  1. Support addition (+) and multiplication (*) between Modulo objects with the same modulus.

  2. Raise appropriate errors if operations are attempted with incompatible objects.

The following Python script is used to test the functionality:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
from exercise_8_3 import *

x = Modulo(6, 11)
try:
    x + 20
except ModuloError as e:
    # 20 is not a Modulo object
    print(e)
try:
    y = Modulo(20, 13)
    z = x + y
except ModuloError as e:
    # 6 (mod 11) and 7 (mod 13) do not have the same modulus
    print(e)
print('\nTesting addition\n')
y = Modulo(20, 11)
z = x + y
print(x, y, z, sep='; ')
y = Modulo(20, 11)
x += y
print(x, y, sep='; ')
print('\nTesting mutiplication\n')
y = Modulo(-30, 11)
z = x * y
print(x, y, z, sep='; ')
y = Modulo(-30, 11)
x *= y
print(x, y, sep='; ')

The expected output from running the above code is:

1
2
3
4
5
6
7
8
9
10
11
12
'20 is not a Modulo object\n'
'6 (mod 11) and 7 (mod 13) do not have the same modulus\n'
'\n'
'Testing addition\n'
'\n'
'6 (mod 11); 9 (mod 11); 4 (mod 11)\n'
'4 (mod 11); 9 (mod 11)\n'
'\n'
'Testing multiplication\n'
'\n'
'4 (mod 11); 3 (mod 11); 1 (mod 11)\n'
'1 (mod 11); 3 (mod 11)\n'

My Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
# exercise_8_3.py

class PrimeError(Exception):
    pass

class IntError(Exception):
    pass

class ModuloError(Exception):
    """Exception for invalid Modulo operations."""
    pass

class Modulo:
    def __init__(self, number, modulus):
        if not isinstance(modulus, int):
            raise IntError(f"{modulus} is not an integer")
        if not self._is_prime(modulus):
            raise PrimeError(f"{modulus} is not a prime number")
        if not isinstance(number, int):
            raise IntError(f"{number} is not an integer")

        self.number = number % modulus
        self.modulus = modulus

    @staticmethod
    def _is_prime(num):
        if num < 2:
            return False
        for i in range(2, int(num ** 0.5) + 1):
            if num % i == 0:
                return False
        return True

    def __repr__(self):
        return f"Modulo({self.number}, {self.modulus})"

    def __str__(self):
        return f"{self.number} (mod {self.modulus})"

    def __add__(self, other):
        if not isinstance(other, Modulo):
            raise ModuloError(f"{other} is not a Modulo object")
        if self.modulus != other.modulus:
            raise ModuloError(f"{self} and {other} do not have the same modulus")

        result_number = (self.number + other.number) % self.modulus
        return Modulo(result_number, self.modulus)

    def __mul__(self, other):
        if not isinstance(other, Modulo):
            raise ModuloError("The right operand is not a Modulo object")
        if self.modulus != other.modulus:
            raise ModuloError(f"{self} and {other} do not have the same modulus")

        result_number = (self.number * other.number) % self.modulus
        return Modulo(result_number, self.modulus)

Standard Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class IntError(Exception):
    pass
    
class PrimeError(Exception):
    pass

class ModuloError(Exception):
    pass

class Modulo:
    def __init__(self, k, p):
        if not isinstance(p, int) or p < 2\
           or any(p % k == 0 for k in range(2, p // 2 + 1)):
            raise PrimeError(f'{p} is not a prime number')
        if not isinstance(k, int):
            raise IntError(f'{k} is not an integer')
        self.modulus = p
        self.k = k % p

    def _validate(self, m):
        if not isinstance(m, Modulo):
            raise ModuloError(f'{m} is not a Modulo object')
        if m.modulus != self.modulus:
            raise ModuloError(f'{self} and {m} do not have the same modulus')         

    def __repr__(self):
        return f'Modulo({self.k}, {self.modulus})'

    def __str__(self):
        return f'{self.k} (mod {self.modulus})'

    def __add__(self, m):
        self._validate(m)
        return Modulo(self.k + m.k, self.modulus)
        
    def __iadd__(self, m):
        self._validate(m)
        self.k = (self.k + m.k) % self.modulus
        return self

    def __mul__(self, m):
        self._validate(m)
        return Modulo(self.k * m.k, self.modulus)
        
    def __imul__(self, m):
        self._validate(m)
        self.k = self.k * m.k % self.modulus
        return self

Summary

The differences between the two solutions are as follows:

  1. Validation Method:

    • The standard solution defines a _validate method to handle checks for the operands (Modulo type and modulus equality), improving code reuse.
    • My solution performs these checks directly inside the __add__ and __mul__ methods.

  2. In-Place Operations:

    • The standard solution includes in-place addition (__iadd__) and multiplication (__imul__) methods, which modify the current object directly.

    • My solution does not include these in-place methods, focusing only on returning new Modulo objects.

Exercise 4

Problem Description

In this exercise, we need to create an iterable class Prime that generates prime numbers in a sequence. Each instance of Prime should be able to independently generate the sequence of prime numbers.

The following Python script is used to test the functionality:

1
2
3
4
5
6
7
from exercise_8_4 import *

I = Prime()
print(*(next(I) for _ in range(10)), sep=', ')
print()
J = Prime()
print([next(J) for _ in range(10)])

The expected output from running the above code is:

1
2
3
'2, 3, 5, 7, 11, 13, 17, 19, 23, 29\n'
'\n'
'[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]\n'

My Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Prime:
    def __init__(self):
        self.current = 2  # Start with the first prime number

    def __iter__(self):
        return self  # The class itself is the iterator

    def __next__(self):
        # Find the next prime number
        while True:
            if self._is_prime(self.current):
                prime = self.current
                self.current += 1
                return prime
            self.current += 1

    @staticmethod
    def _is_prime(num):
        """Helper function to determine if num is prime."""
        if num < 2:
            return False
        for i in range(2, int(num ** 0.5) + 1):
            if num % i == 0:
                return False
        return True

Standard Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Prime:
    def __init__(self):
        Prime.p = 2

    def __iter__(self):
        return self

    def __next__(self):
        if Prime.p == 2:
            Prime.p = 1
            return 2
        else:
            while True:
                Prime.p += 2
                if all (Prime.p % k for k in range(3, Prime.p // 2 + 1, 2)):
                    return Prime.p

Exercise 5

Shoelace Formula

The shoelace formula, also known as Gauss’s area formula or the surveyor’s formula, is a mathematical method used to calculate the area of a polygon when given the coordinates of its vertices. This method is especially useful for polygons whose vertices are defined on a Cartesian coordinate system. It is called the “shoelace formula” because of the crisscross pattern formed when calculating the terms.

$ A = \frac{1}{2} \left| \sum_{i=1}^{n} (x_i y_{i+1} - y_i x_{i+1}) \right|$

Example Calculation

Consider a triangle with vertices $(x_1, y_1)=(2,4)$, $(x_2, y_2)=(5,11)$ and $(x_3, y_3)=(12, 8)$:

  1. Write the coordinates as:

    $(2, 4), (5, 11), (12, 8), (2, 4)$

  2. Multiply diagonally from left to right:

    $2 \times 11 + 5 \times 8 + 12 \times 4 = 22 + 40 + 48 = 110$

  3. Multiply diagonally from right to left:

    $4 \times 5 + 11 \times 12 + 8 \times 2 = 20 + 132 + 16 = 168$

  4. Subtract and divide by 2:

    $A = \frac{1}{2} \left| 110 - 168 \right| = \frac{1}{2} \times 58 = 29$

  5. Thus, the area of the triangle is 29.

Problem Description

In this exercise, we need to create a set of classes representing different shapes: Polygon, Rectangle, and Square. Each shape has specific properties and a method to calculate the area. The classes should also provide informative messages when initialized or when calculating the area.

The following Python script is used to test the functionality:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
from exercise_8_5 import *

print('Testing a polygon')
print()
# Printed out as a side effect of following statement:
# I am a polygon
x = Polygon(((-3.3, 3.0), (-2.3, 5.1), (0.2, 3.4), (3.2, 5.3),
             (5.0, 2.8), (2.8, -1.8), (1.7, 0.7), (-2.6, -4.1),
             (-5.7, -2.0), (-0.3, 0.7)))
print(x.nb_of_vertices)
# Printed out as a side effect of following statement:
# Computed using the shoelace formula
print(x.area())
print()
print('Testing a rectangle')
print()
# Printed out as a side effect of following statement:
# I am a polygon
# More precisely, I am a rectangle
y = Rectangle(((5.5, -2.8), (5.5, 4.4), (-3.6, 4.4), (-3.6, -2.8)))
print(y.nb_of_vertices)
# Printed out as a side effect of following statement:
# I could compute it more easily, but well, I leave it to Polygon...
# Computed using the shoelace formula
print(y.area())
print()
print('Testing a square')
print()
# Printed out as a side effect of following statement:
# I am a polygon
# More precisely, I am a rectangle
# Even more precisely, I am a square
z = Square(((-3.5, 3.5), (3.5, 3.5), (3.5, -3.5), (-3.5, -3.5)))
print(z.nb_of_vertices)
# Printed out as a side effect of following statement:
# I compute it myself!
print(z.area())

The expected output from running the above code is:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
'Testing a polygon\n'
'\n'
'I am a polygon\n'
'10\n'
'Computed using the shoelace formula\n'
'42.224999999999994\n'
'\n'
'Testing a rectangle\n'
'\n'
'I am a polygon\n'
'More precisely, I am a rectangle\n'
'4\n'
'I could compute it more easily, but well, I leave it to Polygon...\n'
'Computed using the shoelace formula\n'
'65.52000000000001\n'
'\n'
'Testing a square\n'
'\n'
'I am a polygon\n'
'More precisely, I am a rectangle\n'
'Even more precisely, I am a square\n'
'4\n'
'I compute it myself!\n'
'49.0\n'

My Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# exercise_8_5.py

class Polygon:
    def __init__(self, vertices):
        self.vertices = vertices
        self.nb_of_vertices = len(vertices)
        print("I am a polygon")

    def area(self):
    """In my calculation using the shoelace formula, I initially got an exact value, but since the expected output was a float, I used the method from the standard solution to match the expected output."""
        print("Computed using the shoelace formula")
        x, y = list(zip(*self.vertices))
        return abs(sum(x[i] * y[-self.nb_of_vertices + i + 1]
                       for i in range(self.nb_of_vertices))
                   - sum(y[i] * x[-self.nb_of_vertices + i + 1]
                         for i in range(self.nb_of_vertices))) / 2

class Rectangle(Polygon):
    def __init__(self, vertices):
        super().__init__(vertices)
        print("More precisely, I am a rectangle")

    def area(self):
        print("I could compute it more easily, but well, I leave it to Polygon...")
        return super().area()

class Square(Rectangle):
    def __init__(self, vertices):
        super().__init__(vertices)
        print("Even more precisely, I am a square")

    def area(self):
        print("I compute it myself!")
        side_length = abs(self.vertices[0][0] - self.vertices[1][0])
        return side_length ** 2

Standard Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Polygon:
    def __init__(self, points):
        print('I am a polygon')
        self.points = points
        self.nb_of_vertices = len(points)

    def area(self):
        print('Computed using the shoelace formula')
        x, y = list(zip(*self.points))
        return abs(sum(x[i] * y[-self.nb_of_vertices + i + 1]
                       for i in range(self.nb_of_vertices))
                   - sum(y[i] * x[-self.nb_of_vertices + i + 1]
                         for i in range(self.nb_of_vertices))) / 2

class Rectangle(Polygon):
    def __init__(self, points):
        super().__init__(points)
        print('More precisely, I am a rectangle')

    def area(self):
        print('I could compute it more easily, but well, I leave it to Polygon...')
        return super().area()
        

class Square(Rectangle):
    def __init__(self, points):
        super().__init__(points)
        print('Even more precisely, I am a square')

    def area(self):
        print('I compute it myself!')
        return max(abs(self.points[0][0] - self.points[1][0]),
                   abs(self.points[0][1] - self.points[1][1])) ** 2

Exercise 6

Problem Description

In this exercise, we need to implement a class named CircularTuple that represents an immutable sequence of elements. The class should:

  1. Allow circular indexing, meaning any index (positive or negative) will be wrapped around the length of the tuple using modulo arithmetic.

  2. Be immutable, which means any attempt to modify an element should raise an appropriate error.

The following Python script is used to test the functionality:

1
2
3
4
5
6
7
8
9
10
from exercise_8_6 import *

L = CircularTuple([3, 8, 14, 19])
print(len(L))
# Indices modulo the length of L
print(L[-20], L[-11], L[-5], L[-2], L[2], L[5], L[11], L[20], sep=', ')
try:
    L[2] = 0
except CircularTupleError as e:
    print(e)

The expected output from running the above code is:

1
2
3
'4\n'
'3, 8, 19, 14, 14, 8, 19, 3\n'
"We could make it work, but we shouldn't!\n"

My Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# exercise_8_6.py
from collections.abc import Sequence

class CircularTupleError(Exception):
    """Custom exception for CircularTuple immutability."""
    def __init__(self, message="We could make it work, but we shouldn't!"):
        super().__init__(message)

class CircularTuple(Sequence):
    def __init__(self, data):
        self._data = tuple(data)  # Store the data as an immutable tuple

    def __len__(self):
        return len(self._data)

    def __getitem__(self, index):
        # Implement circular indexing using modulo operation
        return self._data[index % len(self._data)]

    def __setitem__(self, index, value):
        # Prevent assignment and raise the custom error
        raise CircularTupleError()

Standard Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from collections.abc import Sequence

class CircularTupleError(Exception):
    pass

class CircularTuple(Sequence):
    def __init__(self, L):
        self.L = L

    def __len__(self):
        return len(self.L)

    def __getitem__(self, i):
        return self.L[i % len(self)]

    def __setitem__(self, i, x):
        raise CircularTupleError("We could make it work, but we shouldn't!")

Summary

  1. Exception Handling:

    • In my solution, CircularTupleError includes a default error message to provide more descriptive information when an assignment is attempted.

    • The standard solution defines CircularTupleError as a simple exception without additional customization.

  2. Both solutions implement circular indexing using modulo arithmetic (index % len(self)), which allows for indexing beyond the bounds of the tuple, wrapping around as needed.

show all >>

9021_TUT_7

字数统计: 1.4k字   |   阅读时长: 8min

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

1
2
3
4
5
6
7
8
9
10
11
12
13
def f1():
    while True:
        print(" /\\")
        print("/  \\")
        yield
        print("----")
        yield
        print("\\  /")
        print(" \\/")
        yield
        print(" ||")
        print(" ||")
        yield

Standard solution

1
2
3
4
5
6
7
8
9
10
def f1():
    while True:
        print(' /\\\n/  \\')
        yield
        print('----')
        yield
        print('\\  /\n \\/')
        yield
        print(' ||\n ||')
        yield

Exercise 2

Problem Description

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

My solution

1
2
3
4
5
6
7
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

1
2
3
4
5
6
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

1
2
3
4
5
6
7
8
9
10
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

1
2
3
4
5
6
7
8
9
10
11
12

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

1
2
3
4
5
6
7
8
9
10
11
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

1
2
3
4
5
6
7

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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

1
2
3
4
5
6
7
8
9
10
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)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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

1
2
3
4
5
6
7
8
9
10
11
12
13
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

show all >>

9021_TUT_5

字数统计: 2.5k字   |   阅读时长: 15min

Exercise 1

Problem Description

We are given a list L and an integer n. The task is to repeatedly extend the list L a certain number of times (n) by multiplying each element of the list by an increasing factor. The factors start at 2 and increase by 1 for each iteration.

In my solution, I used a while loop to iterate n times. In each iteration, I used a list comprehension to multiply each element of the list L by the current factor and then used the extend() method to add the new elements to the end of the list. Finally, I incremented the factor by 1 and decremented n by 1.
Because of the description: L'' == 3 * L', L' == 2 * L ….

My Solution

1
2
3
4
5
6
7
8
9
10
11
def f1(L: list, n: int):
    # because of the des of L'' == 3 * L', L' == 2 * L ....
    base = 2
    # when n bigger than 0, base will always ++,
    while n:
        # I want use map() again, but list generator is more simple
        # extend() will add all the elements in the list to the end of the list
        L.extend([i * base for i in L])
        base += 1
        n -= 1
    return L

Standard Solution

1
2
3
4
def f1(L, n):
    for i in range(2, n + 2):
        L.extend([e * i for e in L])
    return L

Explanation

  1. My Solution: Uses a while loop where n is manually decremented after each iteration step by step since it can help me understand what we need. I keep track of the current base manually (base += 1).
  2. Standard Solution: Uses a for loop, which automatically increments i in each iteration. The range is explicitly set to go from 2 to n + 2, which avoids the need for manually handling the base.

Exercise 2

Problem Description

We are given a list L and an integer n. The task is to extend the list L such that it becomes the first n members of an infinite list, which is defined as:

  • L, followed by 2 * L, followed by 4 * L, followed by 8 * L, and so on.

This means that:

  • L is initially concatenated with 2 * L (all elements of L multiplied by 2).
  • Then, 4 * L (all elements of L multiplied by 4) is concatenated, followed by 8 * L, and so on, until the length of the list is at least n.

The challenge is to achieve this without using any for or while loops.

We can see the pattern here: L, 2 * L, 4 * L, 8 * L, ... until it reaches the length of n.

At first, I ignored the description that “without using any for or while loops.”

Here is my solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Assume that the argument L is a nonempty list of integers
# and the argument n is an integer at least equal to the
# length of L.
#
# Given an integer x and a list of integers S,
# let x * S denote the list obtained from S
# by multiplying all its elements by x.
#
# L becomes the first n members of the infinite list
# defined as L concatenated with 2 * L concatenated
# with 4 * L concatenated with 8 * L...
#
# Use no for nor while statement.
def f2(L: list, n: int):
    while len(L) < n:
        L.extend([i * 2 for i in L])
    # use the slice to cut the list to reach the length of n
    return L[:n]

Standard Solution

1
2
3
def f2(L, n):
    L.extend(e * 2 for e in L if len(L) < n)
    return L

Exercise 3

Problem Description

The goal of this problem is to process a list L, which contains nonempty lists of nonempty lists of integers, and return a pair of lists. Each of these lists will be filtered based on specific conditions related to the length of the sublists and the values inside them.

Here’s the task broken down:

  1. First List in the Pair:

    • For each sublist L' of L, if the length of L' is at least n, then:
    • For each sublist L'' of L', if the sum of the elements of L'' is strictly positive:
    • Collect all the strictly positive integers from L'' and add them to the first list.

  2. Second List in the Pair:

    • This is similar to the first list but slightly simpler:
    • For each sublist L' of L, if its length is at least n:
    • For each sublist L'' of L', if the sum of its members is strictly positive:
    • Directly collect all the strictly positive integers from L'' and add them to the second list.

The task specifies that we must use list comprehensions only—no loops, functions, or other control structures.

My Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
def f3(L, n):
    # First list comprehension: we process L' for length and filter based on sum
    first = [
        [x for L2 in L1 if sum(L2) > 0 for x in L2 if x > 0]
        for L1 in L if len(L1) >= n
    ]

    # Second list comprehension: similar filtering but simpler output structure
    second = [
        [x for x in L2 if x > 0]
        for L1 in L if len(L1) >= n for L2 in L1 if sum(L2) > 0
    ]
    return first, second

Explanation

  1. First List (first):

    • We first filter out the sublists L1 whose length is at least n (for L1 in L if len(L1) >= n).
    • Inside this, for each valid L1, we process its members L2 (which are sublists of integers). We check if the sum of elements of L2 is strictly positive (if sum(L2) > 0).
    • For each valid L2, we collect the strictly positive integers (for x in L2 if x > 0).
    • This gives us the first list of lists, where each list contains the positive integers from sublists of sublists whose sum is positive.

  2. Second List (second):

    • Similar to the first list, but here we directly collect the strictly positive integers from the valid sublists L2, without additional nesting.
    • We again check that the sum of L2 is strictly positive and that the length of L1 is at least n.
    • The result is a more flattened structure than the first list.

  3. Key Concepts:

    • Filtering: Both lists involve filtering based on the length of L1 and the sum of L2.
    • List Comprehensions: Used extensively to meet the problem’s requirement of not using explicit loops or other control structures.

Standard Solution

1
2
3
4
5
6
7
8
9
10
def f3(L, n):
    return ([[e for L2 in L1 if sum(L2) > 0
                 for e in L2 if e > 0
             ] for L1 in L if len(L1) >= n
            ],
            [[e for e in L2 if e > 0]
                 for L1 in L if len(L1) >= n
                     for L2 in L1 if sum(L2) > 0
            ]
           )

Exercise 4

We are given a list L of integers, and the goal is to return a list of lists that consists of pairs of elements from the beginning and end of the list. Specifically:

  1. The number of pairs n at the beginning and the end should be as large as possible while maintaining symmetry.
  2. If the length of L is odd, the remaining element in the middle (that cannot form a pair) should be included as a single list.
  3. No for or while loops should be used in the implementation.

My Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def f4(L: list[int]) -> list[list[int]]:
    # Calculate the number of pairs we can take from both the beginning and end.
    n = len(L) // 2
    
    # Take pairs from the beginning of the list. These are the first n // 2 pairs.
    start_pairs = [L[i:i + 2] for i in range(0, len(L) //  4 * 2, 2)]
    
    # Take pairs from the end of the list. These are the last n // 2 pairs.
    end_pairs = [L[i:i + 2] for i in range(len(L) - (len(L) // 4 * 2), len(L) - 1, 2)]
    
    # Calculate the remaining part (middle element if the list length is odd).
    remain_part = [L[len(L) //  4 * 2 : len(L) -(len(L) // 4 * 2)]] if len(L) % 4 else []
    
    # Combine the start pairs, the remaining part (if any), and the end pairs.
    return start_pairs + remain_part + end_pairs if remain_part else start_pairs + end_pairs

Standard Solution

1
2
3
4
5
6
def f4(L):
    if len(L) % 2:
        return [L[i : i + 2] for i in range(0, len(L) //  4 * 2, 2)] +\
            [L[len(L) //  4 * 2 : len(L) -(len(L) // 4 * 2)]] +\
            [L[i : i + 2] for i in range(len(L) - (len(L) // 4 * 2), len(L) - 1, 2)]
    return [L[i : i + 2] for i in range(0, len(L) - 1, 2)]

Explanation

The reason of why we use len(L) // 4 * 2 is that we want to get the number of pairs we can take from both the beginning and end.

We have a pair at the beginning and a pair at the end, so we need to divide the length of the list by 4 to get the number of pairs. We then multiply this by 2 to get the total number of elements in these pairs.

Exercise 5

Before E5, let’s do some exercises.

Normal dictionary:

1
2
3
4
5
6
7
8
9
d = {}
for i in ['a','b','c','a','b','c']:
    if i in d:
        d[i] += 1
    else:
        # need to initialize the value of the key
        d[i] = 1

print(d)

defaultdict:

1
2
3
4
5
6
7
8
from collections import defaultdict

d = defaultdict(int)
for i in ['a','b','c','a','b','c']:
    # no need to initialize the value of the key
    d[i] += 1
    
print(d)

Counter:

1
2
3
4
5
6
from collections import Counter

# easy to count the number of each element
d = Counter(['a','b','c','a','b','c'])

print(d)

Problem Description

The task is to count the number of customers from different countries by reading a CSV file and then printing the count per country in alphabetical order.

The provided solutions use Python’s csv module to read the data and a dictionary (from the collections.defaultdict class) to keep track of the count of customers from each country.

My Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import csv
from collections import defaultdict

def f5(filename= 'customers-100.csv') -> None:
    # read the file
    with open(filename, newline='') as csvfile:
        reader = csv.reader(csvfile)
        next(reader)  # skip the header
        
        # count the number of customers per country
        count = defaultdict(int)
        for row in reader:
            count[row[6]] += 1  # country is in the 7th column
            
    # Print the results sorted by country name
    for key, value in sorted(count.items()):
        print(f'{value} from {key}')

Standard Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
import csv
from collections import defaultdict

countries = defaultdict(int)
with open('customers-100.csv') as file:
    _ = next(file)  # skip the header
    csv_file = csv.reader(file)
    for records in csv_file:
        countries[records[6]] += 1  # country data is in the 7th column

# Print the results sorted by country name
for country in sorted(countries):
    print(countries[country], 'from', country)

Additional Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import csv
from collections import Counter

def f5_counter(filename='customers-100.csv') -> None:
    with open(filename, newline='') as csvfile:
        reader = csv.reader(csvfile)
        next(reader)  # skip the header
        
        # Create a Counter from the country column (assumed to be the 7th column)
        country_counter = Counter(row[6] for row in reader)
    
    # Print the results sorted by country name
    for key, value in sorted(country_counter.items()):
        print(f'{value} from {key}')

f5_counter()

Additional Additional Solution (Data Analysis) (NOT Mandatory)

Not Mandatory, but it’s a good way to learn how to use pandas to do data analysis.

1
2
3
4
5
6
7
8
9
10
import pandas as pd

# read file by pandas
df = pd.read_csv("customers-100.csv")

# use pandas' count()
country_counts = df['Country'].value_counts().sort_index()

for country, count in country_counts.items():
    print(f'{count} from {country}')

Explanation

Reading the CSV file:

1
df = pd.read_csv(filename)

Using the read_csv() function, Pandas can directly load a CSV file into a DataFrame object, which is similar to a table structure. Each column becomes an attribute of the DataFrame, and the column names automatically become the labels for the DataFrame.

Counting the number of customers per country:

1
df['Country'].value_counts()

Pandas provides the value_counts() method, which can directly count the frequency of each value in a column. Here, we call value_counts() on the Country column to get the number of customers from each country.

Exercise 6

Problem Description

The task is to create a directory structure where:

2024-10-08.png

  • There is a top-level directory named First_10_words_per_letter.
  • Under this directory, there are two subdirectories:
    • Vowels: Containing files for letters A, E, I, O, U, Y.
    • Consonants: Containing files for the rest of the letters in the alphabet (B, C, D, etc.).
  • Each letter (A to Z) has its own file, and each file contains the first 10 words from a dictionary.txt file that start with that letter.
  • The directory structure and the files should be generated programmatically, without using any existing hierarchy.

My Solution(Not Perfect, it relies on the sort of dictionary.txt )

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

import os
from pathlib import Path
from string import ascii_uppercase

def main():
    # Create the top directory
    top_dir = Path('First_10_words_per_letter')
    # Create the subdirectories
    vowels_dir = top_dir / 'Vowels'
    consonants_dir = top_dir / 'Consonants'
    os.makedirs(vowels_dir)
    os.makedirs(consonants_dir)

    # Create the files for each letter
    with open('dictionary.txt') as f:
        for letter in ascii_uppercase:
            # Read the first 10 words starting with the letter
            count = 0
            # Write the words to the file
            letter_dir = vowels_dir if letter in 'AEIOUY' else consonants_dir
            with open(letter_dir / f'{letter}.txt', 'w') as f2:
                for word in f:
                    if word[0] == letter:
                        f2.write(word)
                        count += 1
                    if count >= 10:
                        break

if __name__ == '__main__':
    main()

Explanation

Explanation of My Solution:

  1. Creating Directories:

    • I use os.makedirs() to create the top directory (First_10_words_per_letter) and its subdirectories (Vowels and Consonants).

  2. Reading the Dictionary File:

    • The program reads from dictionary.txt and processes each letter in the alphabet (ascii_uppercase).
    • For each letter, I decide whether to place the corresponding file in the Vowels or Consonants subdirectory based on whether the letter is a vowel or consonant.

  3. Writing the Words:

    • The program writes the first 10 words starting with the given letter into the corresponding .txt file.

  4. Potential Issue:

    • here is some limitations of this. Say that processing the dictionary on the fly would not be an option if the words in the file were not lexicographically ordered?

Standard Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import os
from pathlib import Path
from string import ascii_uppercase

top_dir = Path('First_10_words_per_letter')
os.mkdir(top_dir)
vowels_dir = top_dir / 'Vowels'
consonants_dir = top_dir / 'Consonants'
os.mkdir(vowels_dir)
os.mkdir(consonants_dir)

with open('dictionary.txt') as dictionary:
    for letter in ascii_uppercase:
        letter_dir = vowels_dir if letter in 'AEIOUY' else consonants_dir
        count = 0
        with open(letter_dir / f'{letter}.txt', 'w') as filename:
            for word in dictionary:
                if word[0] != letter:
                    continue
                if count >= 10:
                    break
                print(word, file=filename, end='')
                count += 1

show all >>

Horse Racing-Inter-Uni Programming Contest

字数统计: 497字   |   阅读时长: 2min

Description:

https://interunia.unswcpmsoc.com/task/Horse%20Racing/

Thinking:

Preprocessing Horse Information:

Combine horse information into a list of tuples, horses, where each tuple contains the horse index, starting position, and velocity.
Sort the horses by starting position in descending order. If two horses have the same starting position, sort them by velocity in descending order. This is because the horse with the highest starting position leads initially.

Constructing the Leading Horse Timeline:

  • Use a stack stack to maintain the horses that could become the leader.
  • For each horse, check if it has the potential to overtake the current leading horse.
    • If the current horse’s speed is less than or equal to the horse at the top of the stack, it can never overtake and is discarded.
    • If the current horse’s speed is greater than the top horse’s, calculate when it will overtake the current leader.
    • If the calculated overtaking time is invalid (e.g., earlier than the previous overtaking time), adjust the stack by removing horses that can no longer lead.

Handling Queries:

Use binary search to handle each query time t in the times list to find the corresponding leading horse.
bisect.bisect_right(times, t) - 1 finds the first time point greater than t, then subtract one to get the corresponding horse index.

Timeline Construction: We build a timeline that records the time points when the leading horse changes and the horse that leads during that period.

Binary Search for Queries: Since the timeline is sorted chronologically, we can efficiently find the leading horse for each query time using binary search.

Codes:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
n, q = map(int, input().split())
s_list = list(map(int, input().split()))
v_list = list(map(int, input().split()))
t_list = list(map(int, input().split()))

horses = list(zip(range(n), s_list, v_list))
# Sort horses by decreasing s_i
horses.sort(key=lambda x: (-x[1], -x[2]))  # (-s_i, -v_i)

stack = []
# 存储每次马匹变化的时间点
times = []
# 存储每次马匹变化的编号
horse_indices = []

for idx, s_i, v_i in horses:
    discard = False
    # 检查是否可以领先
    while stack:
        # 看看顶部
        jdx, s_j, v_j = stack[-1]
        if v_i <= v_j:
            # 如果它的速度小于或等于当前领导者的速度，它永远无法超越并被丢弃。
            discard = True
            break
        else:
            # Compute t_int
            t_prev = times[-1] if times else 0.0
            # 可能超过的时间
            t_int = (s_j - s_i) / (v_i - v_j)
            if t_int <= t_prev:
                stack.pop()
                times.pop()
                horse_indices.pop()
            else:
                break
    if not discard:
        if stack:
            t_int = (s_j - s_i) / (v_i - v_j)
        else:
            t_int = 0.0
        stack.append((idx, s_i, v_i))
        times.append(t_int)
        horse_indices.append(idx)


import bisect

result = []
for t in t_list:
    idx = bisect.bisect_right(times, t) -1
    idx = max(0, idx)
    result.append(horse_indices[idx]+1)  # +1 to convert to 1-based indexing

print(' '.join(map(str, result)))

show all >>

Counting Stars-Inter-Uni Programming Contest

字数统计: 299字   |   阅读时长: 1min

Description:

https://interunia.unswcpmsoc.com/task/Counting%20Stars/

Thinking:

  • Given a set of star positions, we need to calculate the minimum number of stars required to explain these positions.
  • Meteors (i.e., moving stars) move from left to right, and from high to low (x coordinates increase, y coordinates decrease), without moving horizontally or vertically.
  • Each meteor may appear in multiple positions (because it moves), and the final cumulative image will show all the positions it has passed through.
  • The positions of fixed stars remain unchanged.

Therefore, we need to maintain a list of the last y-coordinate of the current chain.

  1. Sort the points: Sort them by increasing x coordinates.
  2. Initialization: Create an empty list last_y to store the last y-coordinate of each chain.
  3. Traverse the set of points:
    • For each point (x, y):
      • Use bisect_right to find the first position in last_y that is greater than the current y.
      • If the index is less than the length of last_y, it means there is an existing chain that can accommodate the current point, so we update the last y-coordinate of that chain to the current y.
      • If the index is equal to the length of last_y, it means no suitable chain is found, so we need to create a new chain and add the current y to last_y.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import bisect

n = int(input())
stars = []

for _ in range(n):
    x, y = map(int, input().split())
    stars.append((x, y))

# 按 x 坐标递增排序
stars.sort(key=lambda x: (x[0],))

last_y = []

for x, y in stars:
    idx = bisect.bisect_right(last_y, y)
    if idx < len(last_y):
        last_y[idx] = y  # 更新链的最后一个 y 坐标
    else:
        last_y.append(y)  # 创建新的链

print(len(last_y))

show all >>

9021_TUT_3

字数统计: 2.2k字   |   阅读时长: 13min

Exercise 1

Problem Description:

You are given two integers, m and n, where:

  • m represents the number of repeated units (patterns).
  • n represents the number of elements (underscores) within each unit.

The goal is to generate a string where:

  • Each unit contains n underscores (_), separated by |.
  • These units are then concatenated together, separated by *.

My Solution:

1
2
3
4
5
def generate_struct(n):
    return '|'.join(n * ['_'])

def f1(m, n):
    return ' * '.join(m * [generate_struct(n)])

My Thought Process:

I think of each unit as a separate structure. So, I decompose the problem by breaking down the smallest unit, which is the structure made of underscores joined by |.
After constructing each unit, I use join() to combine them together using *.

Helper Function generate_struct(n):

This function generates the basic structure.
It creates a list of underscores (_) of length n and joins them with |.
Example: If n = 2, the result will be “_|_“.

Standard Solution:

1
2
def f1(m, n):
    return ' * '.join('|'.join('_' for _ in range(n)) for _ in range(m))

Concise Expression:

The inner join creates a string of n underscores joined by | using a generator expression ('_' for _ in range(n)).
The outer join repeats this process m times and concatenates the units using *.

In summary, my solution focuses on modularity by breaking down the problem into smaller parts (like creating a structural unit), whereas the standard solution compresses everything into one line using list comprehensions.

Exercise 2

Problem Description:

The goal is to generate a pattern based on the digits of a given number n. Specifically:

If a digit is odd, it should be represented by a black square (⬛).
If a digit is even, it should be represented by a white square (⬜).
The program takes a number n as input and prints a string of squares corresponding to the digits of n.

My Solution:

1
2
3
4
5
6
7
8
def f2(n):
    ans = ''
    for i in str(n):
        if int(i) % 2 == 0:
            ans += '⬜'
        else:
            ans += '⬛'
    print(ans)

My Thought Process:

  1. Loop through each digit:
    Convert the number n to a string to iterate over each digit individually.

  2. Check if the digit is even or odd:
    Convert each digit back to an integer and use the modulus operator (% 2) to check if the digit is even or odd.

  3. Append the corresponding square:

    • If the digit is even, append a white square (⬜) to the result string.
    • If the digit is odd, append a black square (⬛).

  4. Print the final string:
    After processing all the digits, print the final string containing black and white squares.

Standard Solution:

1
2
def f2(n):
    print(''.join({0: '\u2b1c', 1: '\u2b1b'}[int(d) % 2] for d in str(n)))

Dr.Martin’s solution is:

  1. More compact and Pythonic.
  2. Uses a dictionary and list comprehension for brevity and efficiency.
  3. The Unicode characters for the squares are referenced directly using their escape sequences (\u2b1c for white, \u2b1b for black).

Exercise 3

Problem Description:

In this task, the number n is treated as a number expressed in different bases (ranging from 2 to 10), and we aim to convert it into its corresponding base 10 value for each of these bases, where the conversion is valid.

For n = 2143:

  • 2143 in base 5 is equivalent to 298 in base 10.
  • 2143 in base 6 is equivalent to 495 in base 10.
  • And so on.

The goal is to iterate over different base systems from 2 to 10, treat the input number n as if it is expressed in each base, and then convert it to base 10.

My Solution:

1
2
3
4
5
6
7
8
def f3(n: int):
    for i in range(2, 11):
        try:
            # Treat n as a number in base i and convert it to base 10
            value = int(str(n), i)
            print(f'{n} is {value} in base {i}')
        except ValueError:
            pass

My Thought Process:

  1. Iterating over Bases (2 to 10):

    • We loop through the base values i ranging from 2 to 10.

  2. Conversion Using int():

    • For each base i, we treat the number n as a number in that base. To do this, we first convert n to a string (str(n)) and then use int() to interpret it as a base i number.
    • If the digits of n are valid for base i, this conversion succeeds, and the result is the base 10 equivalent of n.
    • If the digits of n are not valid for base i (for example, if base 2 is used and n contains digits greater than 1), a ValueError is raised, and we skip the invalid base.

  3. Handling Errors with try-except:

    • The try-except block ensures that invalid bases are skipped, allowing us to handle cases where the digits in n are not valid for a particular base.

Standard Solution:

1
2
3
4
5
def f3(n):
    n_as_string = str(n)
    min_base = max(2, max({int(d) for d in n_as_string}) + 1)
    for b in range(min_base, 11):
        print(f'{n} is {int(n_as_string, b)} in base {b}')

It skips the bases where the digits in n are not valid, and it uses a set comprehension to extract the unique digits from n_as_string. The maximum digit is then used to determine the minimum base to start iterating from.

Exercise 4

Problem Description:

The task is to create a function f4(n, base) that returns a dictionary D, where:

Keys are integers from 0 to n.
Values are tuples that represent the base base representation of each key, converted from base 10.

My Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def convert_to_base(n, base):
    if n == 0:
        return '0'
    digits = []
    while n:
        digits.append(str(n % base))
        n //= base
    return ''.join(digits[::-1])

def f4(n: int, base: int):
    D = {}
    for i in range(0, n + 1):
        D[i] = tuple(map(int, convert_to_base(i, base)))
    return D

My Thought Process:

  1. Helper Function convert_to_base(n, base):

    • This function converts a number n from base 10 to the specified base.
    • We use a while loop to repeatedly take the modulus (n % base) and append the remainder to the list digits.
    • We then divide n by base (n //= base) to reduce it for the next iteration.
    • After collecting all digits, we reverse the list and return it as a string.

  2. Main Function f4(n, base):
    We initialize an empty dictionary D.
    For each number i from 0 to n, we convert i to the given base using convert_to_base().
    The converted base digits are then mapped to integers and stored in a tuple as the value for each key i in the dictionary.

Explanation of Why map() is not Pythonic:

In the function f4, the use of map(int, convert_to_base(i, base)) applies the int function
to each element of the result from convert_to_base, effectively converting each character to an integer.

However, it’s worth noting that the map() function, which originates from functional programming,
has largely been superseded by more Pythonic constructs such as list comprehensions.

These comprehensions are generally considered superior for several reasons:

  • They are more elegant and concise.
  • They tend to be shorter in terms of syntax, making the code easier to read.
  • They are easier to understand for most people, especially those who are more familiar with Python’s
    standard syntax rather than functional programming constructs.
  • In many cases, they are also more efficient in terms of performance.

For example, instead of using map(int, ...), the same functionality could be achieved with a
list comprehension, like so:

D[i] = tuple([int(digit) for digit in convert_to_base(i, base)])

This list comprehension achieves the same result but follows a more modern Pythonic style.

Standard Solution:

1
2
3
4
5
6
7
8
9
10
def f4(n, base):
    D = {0: (0,)}
    for m in range(1, n + 1):
        digits = []
        p = m
        while p:
            digits.append(p % base)
            p //= base
        D[m] = tuple(reversed(digits))
    return D

Both solutions are valid and achieve the same result. My approach uses a helper function for base conversion, which adds modularity,
whereas the standard solution is more concise and directly integrates the conversion logic into the main function.

Exercise 5

At the first, try to run this:

1
print(0.1 + 0.2)

What happened? The result is not 0.3, but 0.30000000000000004. Why?

Problem Description:

The approach we are using in this exercise is designed to expose the limitations of floating-point arithmetic in computers. Let’s break down why this approach leads to precision inaccuracies and why other methods might not reveal these issues as clearly.

This problem can seem complex, and it’s designed to highlight the subtleties of floating-point arithmetic. Let’s walk through the logic using the test cases to figure out what the function does.

Key Concepts:

  • Floating-point numbers: Computers store floating-point numbers using a binary format, which often introduces precision errors.
  • Precision: We’re working with two types of precision in this function—simple precision (same as the length of the fractional part) and double precision (twice that length).

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def f5(integral_part, fractional_part):
    # Calculate the number of digits in the fractional part
    precision = len(str(fractional_part))
    
    # Concatenate the integral and fractional parts as strings, then convert to a float
    a_float = float(str(integral_part) + '.' + str(fractional_part))
    
    # Format the float with precision equal to the number of digits in the fractional part (simple precision)
    simple_precision = f'{a_float:.{precision}f}'
    
    # Append a number of zeros equal to the fractional part length to the simple precision value (extended precision)
    extended_simple_precision = simple_precision + '0' * precision
    
    # Format the float with precision equal to twice the number of fractional digits (double precision)
    double_precision = f'{a_float:.{precision * 2}f}'
    
    # Print the first part of the output
    print('With', precision * 2, 'digits after the decimal point, ', end='')
    
    # Compare if extended precision and double precision values are the same
    if extended_simple_precision == double_precision:
        # If they are the same, it means the float is precise and has trailing zeros
        print(simple_precision, 'prints out with', precision, 'trailing',
              precision == 1 and 'zero,' or 'zeroes,', 'namely, as',
              extended_simple_precision
             )
    else:
        # If not, there is a precision error, and no trailing zeros
        print(simple_precision, 'prints out as', double_precision)

Our function attempts to check and display this floating point error with simple precision (simple_precision) and double precision (double_precision). The error becomes more obvious when we represent floating point numbers with higher precision (double the number of decimal places). So in this way, we show that floating point numbers are not always actually stored as we expect them to be with more precise representation.

Exercise 6

Problem Description:

In this task, we are given:

  • A list L, which contains multiple sub-lists of integers, and all sub-lists have the same length n.
  • A list fields, which is a permutation of {1, ..., n}.

We are required to sort the list L by using a multi-key sorting mechanism, where:

  • First, the elements in L are sorted based on the position given by the first element of fields.
  • If two sub-lists are equal based on the first field, we move to the second field, and so on.
  • Finally, if required, the sorting proceeds up to the last field in fields.

Example of Fields Explanation:

If fields = [2, 1], it means:

  1. First, sort based on the second element of each sublist.
  2. If there are ties (same values in the second position), sort based on the first element.

My Solution:

1
2
def f6(L, fields):
    return sorted(L, key=lambda x: [x[i-1] for i in fields])

  1. Sorting with sorted():
    The sorted() function is used to sort the list L.
    The key parameter defines how the sorting will be performed.

  2. Lambda Function:
    The lambda function defines how the sublists will be sorted. It generates a list of values for each sublist based on the positions specified in fields.
    For example, if fields = [2, 1], the lambda function will extract the second and first elements from each sublist in that order, and sorting will be done based on this new list.

  3. Key Structure:
    The key is a list of elements from each sublist, indexed by the positions specified in fields. We use x[i - 1] because fields is 1-based, and list indexing in Python is 0-based.

  4. What is Lambda Function?

For example:

We have:

1
f = lambda x: x * x

This is equivalent to:

1
2
def f(x):
    return x * x

And lambda function in a sorted function is used to define a custom sorting key.

1
2
3
4
5
L = [(1,2), (3,1), (5,0)]

SortedL = sorted(L, key=lambda x: x[1])

print(SortedL)

The result is: [(5, 0), (3, 1), (1, 2)], it sorts the list based on the second element of each tuple.

Standard Solution:

1
2
def f6(L, fields):
    return sorted(L, key=lambda x: tuple(x[i - 1] for i in fields))

Why Use a Tuple?:

  • Tuples are often preferred for multi-key sorting because they are immutable, and Python’s built-in sorting functions can efficiently compare tuples.
  • Each sublist is transformed into a tuple of its elements based on the order defined by fields. The sorted() function then uses these tuples to sort the list.

show all >>

9021_TUT_2

字数统计: 2.9k字   |   阅读时长: 17min

Exercise 1:

This exercise focuses on input validation and formatting floating-point numbers. The goal is to prompt the user to enter a floating-point number between -1 and 1 (exclusive). If the input is valid, the program rounds the number to two decimal places and prints it. Otherwise, it keeps prompting the user until a valid input is provided.
Key Points:

  • The program uses a try-except block to catch invalid inputs (e.g., strings that cannot be converted to floats).
  • The input() function is wrapped in an infinite while loop to continuously ask for input until the correct condition is met.

In the updated version of Exercise 1, we use the formatting :.2f instead of round(). Here’s the key difference between the two:

  • round(): This is a Python built-in function that rounds a number to a specified number of decimal places. For example, round(1.236, 2) will return 1.24. However, the output of round() is still a float, but it does not guarantee a fixed number of decimal places when printed. For instance, round(1.0001, 2) would return 1.0 and only display one decimal place, not two.
  • :.2f: This is part of Python’s string formatting and ensures the number is displayed with exactly two decimal places, no matter what the number is. It also rounds the number appropriately. For instance, number = 1.0 formatted as f”{number:.2f}” will print 1.00. This makes :.2f particularly useful for consistent display of decimal places, which is important for formatting output for users.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
while True:
    try:
        i = input('Enter a floating point number between -1 and 1 excluded: ')
        number = float(i)
        if '.' not in i:
            raise ValueError
        if -1 < number < 1:
            # not using round() here because it rounds to the nearest even number
            print(f'\nUp to +/-0.005, you input {number:.2f}')
        else:
            raise ValueError
        break
    except ValueError:
        print("You got that wrong, try again!\n")

Exercise 2:

This exercise involves processing a block of text and formatting it into sentences. Each sentence should have its first word capitalized, and the remaining words should be in lowercase. The task is to handle spaces and punctuation properly.

Key Points:

  • A regular expression (re.sub) is used to replace multiple spaces with a single space.
  • Another regular expression (re.split) is used to split the text into sentences while preserving punctuation marks.
  • After splitting, the sentences are processed: the first word is capitalized, and all other words are made lowercase.
  • Finally, the processed sentences are recombined into a single formatted text.

Why use re in Exercise 2, and what is re?

In Exercise 2, we use re (Python’s regular expression module) to process and format the text input. Let’s break down why re is used and what it is:

What is re?

re stands for regular expressions, which are powerful tools for matching patterns in strings. The re module in Python allows you to work with regular expressions to search, split, and manipulate text based on specific patterns. Regular expressions are highly flexible and efficient for handling complex string operations.

Why use re in Exercise 2?

In this exercise, we need to handle several complex text manipulations:

  1. Replace multiple spaces with a single space: Sentences in the text may have irregular spaces between words, so we need to normalize these spaces. Instead of writing loops or conditions to handle each case, we use re.sub() with a pattern r’\s+’ to easily match all occurrences of one or more spaces and replace them with a single space.
  2. Split sentences while preserving punctuation: We need to split the text into individual sentences, where each sentence is followed by punctuation (e.g., ‘.’, ‘!’, or ‘?’). The function re.split(r’([.!?])’, text) allows us to split the text based on punctuation while keeping the punctuation marks, which is crucial for proper sentence reconstruction.

Regular expressions allow us to:

  • Efficiently match patterns like spaces or punctuation.
  • Perform complex text transformations with minimal code.
  • Handle edge cases that would otherwise require more manual handling.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# Assume that the argument text is a string that denotes a text,
# defined as one or more sentences, two successive
# sentences being separated by at least one space,
# the first sentence being possibly preceded with spaces,
# the last sentence being possibly followed by spaces,
# a sentence being defined as at least two words,
# two successive words in a sentence being separated by
# at least one space, a word being defined as a sequence
# of (uppercase or lowercase) letters,
# - possibly followed by a comma for a word that is
#   not the last one in its sentence,
# - definitely followed by a full stop, an exclamation mark
#   or a question mark for a word that is the last one
#   in its sentence.
import re


def f2(text):
    # Use regular expression to replace multiple spaces with a single space
    text = re.sub(r'\s+', ' ', text.strip())

    # Correct way to split sentences while preserving delimiters
    sentences = re.split(r'([.!?])', text)

    # Process sentences and punctuation separately
    new_text = []
    i = 0
    while i < len(sentences)-1:
        sentence = sentences[i].strip()
        if sentence:
            sentence =' '.join(sentence.capitalize().split())
            # Rebuild the sentence and add back the punctuation
            new_text.append(sentence +sentences[i +1])
        i += 2
    return ' '.join(new_text)

Exercise 3:

This exercise works with lists of integers and aims to repeatedly remove the first and last elements of the list as long as they are equal. The list is treated as a double-ended queue (deque) for efficient removal of elements from both ends.

Key Points:

  • The deque data structure is used because it provides O(1) operations for popping elements from both ends, which is more efficient than using lists.
  • The program checks if the first and last elements of the deque are equal and removes them until this condition is no longer met.
  • The deque is converted back to a list before being returned.

Why is deque more efficient than list in Exercise 3?

In Exercise 3, we are frequently removing elements from both the front (left) and the back (right) of the list. This is where using a deque (double-ended queue) from Python’s collections module becomes more efficient compared to using a standard list.

Here’s why:

  • List Behavior: When you use a standard list and call list.pop(0) to remove the first (leftmost) element, it requires shifting all the remaining elements one position to the left. This shift operation takes linear time—O(n), where n is the number of elements in the list. This means that for every removal from the front, the larger the list, the slower the operation becomes.

    • Removing from the right side of a list using list.pop() is an O(1) operation (constant time) because no elements need to be shifted, making it efficient only when working from the end of the list.

  • Deque Behavior: A deque (double-ended queue) is specifically designed to support efficient append and pop operations from both ends. In a deque, both popleft() and pop() operations take constant time—O(1)—because the deque is implemented as a doubly linked list. This means no elements need to be shifted when popping from the left or right.

    • In Exercise 3, where we need to frequently remove elements from both ends of the list, using a deque ensures that both the removal from the left (popleft()) and the right (pop()) are performed in constant time. This makes the entire process much more efficient, especially for large lists where repeated operations would slow down if we used a standard list.

What is a deque?

A deque (short for “double-ended queue”) is a data structure that allows for fast appending and popping of elements from both ends. It is part of the collections module in Python and is optimized for scenarios where you need to efficiently add or remove elements from both ends of the sequence.

Key Features of deque:

  • O(1) time complexity for operations on both ends (append, pop, appendleft, popleft).
  • It is implemented as a doubly linked list, meaning each element contains a reference to both the previous and next elements, allowing efficient traversal in both directions.
  • deque is ideal for scenarios where you need frequent and efficient insertions and removals from both the front and back of a sequence, unlike a standard list where such operations are costly at the front.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Assume that the argument L is a list of integers.
#
# For as long as the list has at least two elements
# and the first and last elements of the list are equal,
# pop out those elements.

# def f3(L):
# # Remove the list as long as it has at least two elements and the first and last elements are equal
#     while len(L) > 1 and L[0] == L[-1]:
#         L.pop(0) # Remove the first element
#         L.pop(-1) # Remove the last element
#     return L


from collections import deque

def f3(L):
    L = deque(L)  # Convert the list to a deque for efficient popping from both ends
    # Continue removing elements while there are at least two elements and the first and last are equal
    while len(L) > 1 and L[0] == L[-1]:
        L.popleft()  # Efficiently remove the first element (O(1) operation)
        L.pop()      # Efficiently remove the last element (O(1) operation)
    return list(L)   # Convert the deque back to a list and return it

Exercise 4:

This exercise deals with lists of integers that are in increasing order. The goal is to remove any element whose value is equal to its index in the list. The program iterates over the list and removes such elements, ensuring the index is correctly adjusted after each removal.

Key Points:

  • The program uses a while loop and checks if the element at index i is equal to i. If true, it removes the element and does not increment i, so that the next element at the same position is checked.
  • The remove() function is used to delete the element, which is appropriate for this task.
  • Care is taken to ensure that index adjustments are handled correctly.

The reason we use remove() instead of pop(0) or popleft() in a deque is that we need to specifically remove the value that matches the number we reached. pop() and popleft() remove elements by position, without considering the value, which isn’t suitable for our case.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# Assume that the argument L is a list of integers
# that forms an increasing sequence.
#
# For as long as some member of the list is equal to its index
# in the list, pop out the leftmost such member of the list.

def f4(L):
    i = 0
    while i < len(L):
        if L[i] == i:
            L.remove(L[i])  # Using remove() here since popleft() removes from the left only
        else:
            i += 1  # Only increment i if no element was removed
    return L

Exercise 5:

This exercise works with a circular list of integers. The task is to identify elements that are both larger than one of their adjacent elements and smaller than the other. The result is returned as a dictionary where each key is such an element, and its value is a pair of the adjacent elements (one smaller and one larger).

Key Points:

  • The list is treated as circular, meaning the first element is considered adjacent to the last element.
  • The program iterates through the list, compares each element with its neighbors, and stores those that meet the criteria.
  • For each valid element, the adjacent smaller and larger elements are stored in a dictionary.

To solve this problem, we need to create a dictionary D where each key is an element in the list L that satisfies a certain condition, and the value is a tuple of two elements. The first element of this tuple is the adjacent element that is smaller than the current key, and the second element is the adjacent element that is larger than the current key.

Steps:

  1. Loop structure: Check each element.
  2. Processing of adjacent elements: Since the list is cyclic, the previous element of the first element is the last element, and the next element of the last element is the first element.
  3. Condition check: Find the adjacent elements that are smaller and larger than the current element, and add them to the result dictionary.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# Assume that the argument L is a list of at least 3 distinct integers.
#
# Returns a dictionary D whose keys are those of the members e of L,
# if any, that are
# - smaller than the element right before or right after, and
# - larger than the element right before or right after.
# It is considered that
# - the first member of L is right after the last member of L, and
# - the last member of L is right before the first member of L
# (as if making a ring out of the list).
# For a key e in D, the associated value is the pair whose
# first element is the member of L that is right before or right after
# e and smaller than e, and whose second element is the member of L
# that is right before or right after e and greater than e.

def f5(L):
    D = {}
    for i in range(len(L)):
        m = L[i - 1]
        n = L[(i + 1) % len(L)]
        if n < m:
            m, n = n, m
        if m < L[i] < n:
            D[L[i]] = m, n
    return D

Exercise 6:

This exercise deals with factorizing an integer n into the form 2^k * m, where m is an odd number. If n is negative, the program adds a negative sign to the output. If n is zero, it prints a special message.

Key Points:

  • The program uses a loop to divide n by 2 until n is no longer divisible by 2, counting the number of divisions (k).
  • The absolute value of n is used to ensure correct handling of negative numbers, and a sign is added to the final result if the original number was negative.
  • The program handles the special case where n = 0 by printing a unique message.

More Details:

  1. You need to express the given integer n as n = 2^k * m.
    • k represents the number of times n can be divided by 2. In other words, it is the power of 2 in the factorization of n.
    • m is the remaining odd part after dividing out all factors of 2.
  2. If n is negative, the output should include a negative sign.
  3. Special case: If n = 0, a specific message should be printed.
  4. The result is printed directly, not returned.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Assume that the argument n is an integer.
#
# The output is printed out, not returned.
#
# You might find the abs() function useful.
def f6(n):
    if n == 0:
        print("0 = 2^k * 0 for all integers k!")
    else:
        k = 0
        ori = n
        if n < 0:
            sign = '-'
            n = -n
        else:
            sign = ''
        while n % 2 == 0:
            n //= 2
            k += 1
        print(f"{ori} = {sign}2^{k} * {n}")
    return

FOR VERY VERY VERY VERY VERY BIG NUMBER:

When dealing with very large integers, the method of continuously dividing the number by 2 to factor out powers of 2 (2^k) can become inefficient. This is because each division can be costly in terms of computational time, especially for very large numbers with millions or billions of digits. Each division involves recalculating the entire integer, which is slow for large integers.
Using Bit Manipulation:

A much more efficient approach is to use bit manipulation to determine how many times a number can be divided by 2 (i.e., how many factors of 2 it has). This method avoids division altogether and instead directly analyzes the binary representation of the number to count the number of trailing zeros, which correspond to the powers of 2 in the factorization.

Why?

  1. Bitwise operations are much faster than arithmetic operations like division, especially for large integers. Counting the trailing zeros in a number’s binary representation can be done in constant time.

  2. Extracting the lowest set bit of a number allows us to quickly find how many times a number can be divided by 2 without having to repeatedly divide the number. This provides the power of 2 (k) directly.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def f6(n):
    if n == 0:
        print("0 = 2^k * 0 for all integers k!")
        return
    
    # Handle negative sign
    sign = '-' if n < 0 else ''
    n = abs(n)
    
    # Using bit manipulation to count how many trailing zeros (powers of 2)
    k = (n & -n).bit_length() - 1  # Count trailing zeros by isolating the lowest set bit
    
    # Remove 2^k factor from n
    m = n >> k  # Equivalent to n // 2^k, shifting right by k bits
    
    # Print the result
    print(f"{sign}{n} = {sign}2^{k} * {m}")

show all >>

9021_TUT_4

字数统计: 2.4k字   |   阅读时长: 14min

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
%%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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 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:

1
2
3
4
5
6
7
8
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:

1
2
3
4
5
6
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 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:

1
2
3
4
5
6
7
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:

    1
    2
    3
    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:

    1
    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:

    1
    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))

    1
    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:
1
2
3
L1 = [1, 2, 3]
L2 = [4, 5, 6]
print(list(zip(L1, L2)))

Output:

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

And zip in dictionary:

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

Output:

1
2
[(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:

1
2
3
4
5
6
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
([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:

1
2
3
4
5
6
7
8
9
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:

1
2
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:

1
2
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:

1
2
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.

show all >>