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.

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

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.

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.

Standard Solution:

1
2
3
4
5
6
7

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

My Solution:

1
2
3
4
5
6
7
8
9

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}")

Lattice-based Cryptography: Basic Example

Introduction to Lattice

In lattice-based cryptography, a lattice is a regularly spaced grid of points in space. It is formed by taking integer linear combinations of a set of vectors, called the “basis”. For this example, let’s use a 2-dimensional lattice, where the lattice points are integer combinations of two vectors.

Why Can Bad Basis Be Used for Encryption, and Good Basis for Decryption?

The core issue lies in lattice-based encryption, where information is mapped to a lattice, encrypted using the public key (Bad Basis), and finally decrypted using the private key (Good Basis). The key point here is the geometric properties of Good Basis and Bad Basis.

Encryption Process (Using Bad Basis as Public Key):

In the encryption process, the dense lattice structure generated by Bad Basis maps the message to a lattice point.
Suppose we want to encrypt a message. First, we choose a random error (noise) and then add some randomness to the message so that the encrypted message can be represented as a point in the lattice. Since the lattice structure of Bad Basis is very dense and hard to manipulate, attackers cannot directly recover the original message from the encrypted one.

Decryption Process (Using Good Basis as Private Key):

During decryption, the private key uses Good Basis. Since the basis vectors of Good Basis are orthogonal, the lattice structure is clearer and easier to manipulate, making it possible to recover the information using Good Basis.
Specifically, using Good Basis, we can find the closest lattice point (i.e., recover the original message using the decryption formula). Because the lattice structure generated by Good Basis is simple, decryption becomes very easy.

Why Can We Use Bad Basis for Encryption and Good Basis for Decryption?

The key lies in the relationship between Bad Basis and Good Basis:

Good Basis and Bad Basis are mathematically related, as they belong to the same lattice. Although the lattice structure generated by Bad Basis is more complex and dense, it is still a different representation of the lattice defined by Good Basis. Through mathematical operations, we can convert Bad Basis into Good Basis and recover information from it.

In fact, the relationship between Bad Basis and Good Basis can be obtained through matrix operations. Using specific algorithms, such as Babai’s rounding algorithm, we can use the information from Bad Basis to find the closest Good Basis point. Since the structure of Good Basis is clearer, it is easy to recover the original message using its basis vectors during decryption.

The security of lattice-based encryption relies on a mathematical problem: recovering the shortest vector (or the correct message) from a dense lattice (defined by Bad Basis) is a very difficult problem. This problem, known as the Shortest Vector Problem (SVP), is currently not efficiently solvable by existing quantum algorithms.

Explanation of Key Points

• Lattice Structure: The lattice is generated by linear combinations of basis vectors $( \mathbf{v_1} )$ and $( \mathbf{v_2} )$. In this example, the vectors are simple, but in real applications, the lattice structure is much more complex.

• Encryption: The message is transformed into a ciphertext through lattice operations, typically involving some noise or error terms (such as in LWE).

• Decryption: The secret key (a vector or some form of trapdoor information) is used to recover the original message by solving lattice-related problems.

This Markdown example is a basic introduction, and in practical lattice-based schemes, the lattice vectors, encryption, and decryption processes are far more intricate. But this should provide a simple framework for understanding the key concepts.

How to solve the problem of UNPROTECTED PRIVATE KEY FILE?

1
2
3
4
5
6
7
8
9

F:\> ssh -i "id_rsa" -p 2251 ??@??.com
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@         WARNING: UNPROTECTED PRIVATE KEY FILE!          @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
Permissions for 'id_rsa' are too open.
It is required that your private key files are NOT accessible by others.
This private key will be ignored.
Load key "id_rsa": bad permissions
??@??.com: Permission denied (publickey).

So I went home and tested it with my old computer:

1. An error message appeared: ssh: The term 'ssh' is not recognized as the name of a cmdlet, function, script file, or operable program

2. Checked whether OpenSSH was installed through Get-WindowsCapability -Online | ? Name -like 'OpenSSH*', and found that Windows7 system does not natively support OpenSSH

3. Tried to solve it by installing Git Bash, but Unable to locate the program input point GetSystemTimePreciseAsFileTime on the dynamic link library KERNEL32.dll

4. Tried Release on the OpenSSH official website, and found that it could not be compiled because the api-ms-win-core-file-l1-1-0.dll file was missing in the computer

5. Cygwin official website found that it supports unsupported Windows version, https://cygwin.com/install.html

6. Win+R->cmd->setup-x86_64.exe --allow-unsupported-windows --site http://ctm.crouchingtigerhiddenfruitbat.org/pub/cygwin/circa/64bit/2024/01/30/231215 --no-verify

7. Successfully run Cygwin, set up the Tsinghua University mirror source, https://mirrors.tuna.tsinghua.edu.cn/cygwin/, select openssh, and install various C++ packages

8. It still failed, and then I found that the key file can be used after it is removed from the USB drive. . .

题目：

思想：

就排序，排完之后，两两比较后merge.

代码：

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

from typing import List

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        # 先按区间的起始位置进行排序
        intervals.sort(key=lambda x: x[0])
        
        merged = []
        for interval in intervals:
            # 如果merged列表为空，或者当前区间不与merged列表中的最后一个区间重叠，直接添加到merged列表
            if not merged or merged[-1][1] < interval[0]:
                merged.append(interval)
            else:
                # 否则我们就合并当前区间和merged列表中的最后一个区间
                merged[-1][1] = max(merged[-1][1], interval[1])
        
        return merged

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.

My Solution

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

Standard Solution

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

while True:
    try:
        x = input('Enter a floating point number between -1 and 1 excluded: ')
        if '.' not in x:
            raise ValueError
        x = float(x)
        if not (-1 < x < 1):
            raise ValueError
        break
    except ValueError:
        print('You got that wrong, try again!\n')
print(f'\nUp to +/-0.005, you input {x:.2f}')

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.

In other words: Modify the sentence to conform to English grammar

Standard Solution

1. Split text into a list of words.
2. Iterate through the words and apply the following rules:
   • If the word is the first word of the sentence (i.e., the first word or follows a sentence-ending punctuation mark), capitalize it.
   • If the word is not the first word of the sentence, make it lowercase.

1
2
3
4
5
6
7

def f2(text):
    words = text.split()
    for i in range(len(words)):
        # Ternary Expression
        words[i] = words[i].title() if i == 0 or words[i - 1][-1] in '.!?'\
            else words[i].lower()
    return ' '.join(words)

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.

Standard Solution:

1
2
3
4
5
6
7

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

My Solution:

1
2
3
4
5
6
7
8
9

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.

Standard Solution:

1
2
3
4
5
6
7
8

def f4(L):
    i = 0
    while i < len(L):
        if L[i] == i:
            L.pop(i)
        else:
            i += 1
    return L

My Solution:

1
2
3
4
5
6
7
8

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.

Standard Solution:

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

def f5(L):
    D = {}
    for i in range(len(L)):
        m = L[i - 1]
        L[i]
        # Treat it as a head-tail circular array
        n = L[(i + 1) % len(L)]
        # we don't care about the order of m and n [0,1,2,4] L[3%4==3]
        if n < m:
            m, n = n, m
        # If L[i] is between m and n, store it in the dictionary:
        if m < L[i] < n:
            D[L[i]] = m, n
    return D

L[i-1] help us to get the previous element of the current element, 0 - 1 is len(L) - 1.
and L[(i+1) % len(L)] help us to get the next element of the current element. The modulo operation (i+1) % len(L) ensures that the index wraps around to the beginning of the list when it reaches the end.

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.

1
2
3
4
5
6
7
8
9
10
11

def f6(n):
    if not n:
        print('0 = 2^k * 0 for all integers k!')
        return
    k = 0
    m = n
    sign = '-' if n < 0 else ''
    while m % 2 == 0:
        m //= 2
        k += 1
    print(f'{n} = {sign}2^{k} * {abs(m)}')

• If n is negative, it keeps track of the sign.
• It repeatedly divides n by 2 while it remains even (n % 2 == 0), counting how many times this happens (k).
• The remaining number, m, must be odd, because we divide out all possible factors of 2.
• Finally, it prints the equation:
  "n = sign * 2^k * m"

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}")

QUESTION：

2270. Number of Ways to Split Array.md

My Think：

2 <= nums.length <= 105, 因此我们可以直接获取到第一个数字, 初始状态就在指针于index0, 正要往index1走的时候.
然后只需要一次For循环就可以搞定

重点是第二个方法, 来自题解.

Code：

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    def waysToSplitArray(self, nums: List[int]) -> int:
        temp_sum = nums[0]
        total_sum = sum(nums) - temp_sum
        ans = 0
        for i in range(1, len(nums)):
            if temp_sum >= total_sum:
                ans += 1
            temp_sum += nums[i]
            total_sum -= nums[i]
        return ans

1
2

t = (sum(nums) + 1) // 2
return sum(s >= t for s in accumulate(nums[:-1]))

Notes on RSA and Diffie-Hellman

1. Mathematical Background of RSA and Diffie-Hellman

RSA

• Prime Factorization: The problem of integer factorization.
• Diffie-Hellman: The discrete logarithm problem.

Let:

$$
s \in \mathbb{Z}_n^2, a_i \in \mathbb{Z}_2^n, e_i \in \mathbb{Z}^n
$$

Define:

$$
a_i \cdot s + e_i
$$

as a certain encryption form.

For example:

$$
\mathbb{Z}_n^2 = {7, 11, 13, 15, 17, 19, 23, 27, 31}
$$

2. RSA Algorithm Steps

1. Choose two prime numbers:

   $$
   p = 3, q = 11
   $$

   Then:

   $$
   n = p \cdot q = 3 \cdot 11 = 33
   $$

   $$
   \phi(n) = (p-1)(q-1) = 2 \cdot 10 = 20
   $$

   (Computing the number of integers coprime to ( n ))

   • Since ( p, q ) are primes, for all ( a \in \mathbb{Z}^+ ), if ( a < p ), then ( \gcd(a, p) = 1 ), where ( p ) is a prime.
   • There are ( (p-1) ) and ( (q-1) ) numbers coprime to ( pq ).
   • The total count of numbers up to ( n ) is ( n = p \cdot q ), and ( n ) is divisible by ( q ) and ( p ).
   • The total count of numbers not coprime to ( n ) is ( p + q - 1 ).
   • Therefore, ( \phi(n) = n - (q + p - 1) = pq - q - p + 1 = (p-1)(q-1) ).

2. Choose a public key ( e ):

   $$
   1 < e < \phi(n), , \text{and} , \gcd(e, \phi(n)) = 1
   $$

   For example:

   $$
   e = 7
   $$

3. Compute the private key ( d ):

   $$
   d \cdot e \equiv 1 , (\text{mod} , \phi(n))
   $$

   Solving:

   $$
   d = 3
   $$

4. Public-private key pair:

   • Public key: ( (e, n) = (7, 33) )
   • Private key: ( (d, n) = (3, 33) )

3. Encryption and Decryption Process

• Suppose the plaintext is ( m = 4 ), the ciphertext ( c ) is:

  $$
  c = m^e , \text{mod} , n
  $$

  Calculation:

  $$
  c = 4^7 , \text{mod} , 33 = 16
  $$

• Decrypting to retrieve ( m ):

  $$
  m = c^d , \text{mod} , n
  $$

  Calculation:

  $$
  m = 16^3 , \text{mod} , 33 = 4
  $$

4. Proof of Correctness of Decryption

The encryption and decryption rely on the following equation:

$$
e \cdot d \equiv 1 ,(\text{mod}, \phi(n))
$$

Thus, we have:

$$
e \cdot d = 1 + k \cdot \phi(n)
$$

1. From the encryption formula:

   $$
   c = m^e ,(\text{mod}, n)
   $$

2. Using the decryption formula:

   $$
   m = c^d ,(\text{mod}, n)
   $$

3. Substituting ( c ) from the encryption equation:

   $$
   m = (m^e)^d ,(\text{mod}, n)
   $$

4. Consolidating the exponent:

   $$
   m = m^{e \cdot d} ,(\text{mod}, n)
   $$

5. Since ( e \cdot d = 1 + k \cdot \phi(n) ):

   $$
   m = m^{1 + k \cdot \phi(n)} ,(\text{mod}, n)
   $$

6. Applying Euler’s theorem:

   $$
   m^{\phi(n)} \equiv 1 ,(\text{mod}, n)
   $$

7. Simplifying:

   $$
   m^{1 + k \cdot \phi(n)} \equiv m^1 \cdot (m^{\phi(n)})^k ,(\text{mod}, n)
   $$

8. Since ( m^{\phi(n)} \equiv 1 ):

   $$
   m^{1 + k \cdot \phi(n)} \equiv m ,(\text{mod}, n)
   $$

Thus, decryption is correct.

LWD:
$$
\left{ \left(a_i, \langle a_i, s \rangle + e_i \right) : s \gets \mathbb{Z}_q^n, a_i \gets \mathbb{Z}q^n, e_i \gets \chi \right}{i=1}^m
$$

1. ( \mathbb{Z} = \mathbb{Z}/q \mathbb{Z} ) represents a finite ring modulo ( q ).
2. ( \chi ) is a probability distribution over ( \mathbb{Z} ), used to generate “small numbers” (noise).

• Uniform Distribution: ( \chi ) randomly generates integer values from the range [−B, B] (e.g., [−5,5]), where ( B \ll q/2 ).
  The assumption ( B \ll q/2 ) ensures that the noise ( e_i ) does not obscure the modulated result during decryption.
• Discrete Gaussian Distribution: Another common distribution, denoted as ( D_{\mathbb{Z}, \sigma} ), with standard deviation ( \sigma ), used to generate near-zero random noise values.

( a \gets D ): a is randomly sampled (or generated) from probability distribution D.
( a \gets S ): When S is a finite set, a is randomly and uniformly selected from S.

( a_i \in \mathbb{Z}_q^n ): This denotes an ( n )-dimensional vector space modulo ( q ), where each component belongs to ( \mathbb{Z}_q ).