RSA 和 Diffie-Hellman 笔记

1. RSA 和 Diffie-Hellman 的数学背景

RSA

• Prime Factorization: 质因数分解问题。
• Diffie-Hellman: 离散对数问题。

令：

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

定义：

$$
a_i \cdot s + e_i
$$

为某种加密形式。

例如：

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

2. RSA 算法步骤

1. 选择两个质数：

   $$
   p = 3, q = 11
   $$

   则：

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

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

   (计算与n互质的数量个数)

   • ∵ p, q为prime, ∴ $\forall a \in \mathbb{Z}^+, \ a < p \implies \gcd(a, p) = 1, \quad \text{其中 } p \text{ 是质数。}$
   • ∴有$(p-1)$和$(q-1)$个 与PQ互质
   • ∴有小于等于n的总数为 $n = p*q$, n能整除为q个, 被p整除为p个
   • ∴与n个不互质的总数为$p+q-1$
   • 所以有$\phi(n) = n-(q+p-1)=pq-q+p-q=(p-1)(q-1)$

2. 选择公钥 $e$：

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

   例如：

   $$
   e = 7
   $$

3. 计算私钥 $d$：

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

   解出：

   $$
   d = 3
   $$

4. 公私钥对：

• 公钥：$(e, n) = (7, 33)$
• 私钥：$(d, n) = (3, 33)$

3. 加解密过程

• 假设明文 $m = 4$，加密后得到密文 $c$：

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

  计算：

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

• 解密得到明文 $m$：

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

  计算：

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

4. 证明解密的正确性

加密和解密的核心是以下等式成立：

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

所以我们有

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

1. 以加密公式为出口：

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

2. 将 $c$ 以解密公式进行计算：

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

3. 将 $c$ 以加密公式代入：

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

4. 统合为指数乘式：

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

5. 与 $e \cdot d = 1 + k \cdot \phi(n)$ 进一步连续：

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

6. 应用质数进度最大公式：

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

7. 分解为无需重复任务：

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

8. 因为 $m^{\phi(n)} \equiv 1$:

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

故证明解密正确。

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}$ 表示以q为Mod的Finite Ring
2. $\chi$ 是$\mathbb{Z}$上的概率分布, 用来生成”小数字”(噪声)

• 均匀分布：如 χ 从区间[**−B,B]（例如 [−5,5]）中随机生成整数值，$B≪q/2B$ 表示生成的噪声范围比模数 q 的一半要小得多。
  $B≪q/2B$的假设确保解密时，噪声 $e_i$不会造成模运算后的结果模糊不清。
• 离散高斯分布：这是另一种更常见的分布类型，记作 $D_{\mathbb{Z}, \sigma}$，具有标准差 σ，用来生成接近 0 的随机噪声值。

$a \gets D$: a 从概率分布 D 中随机抽取（或生成）。
$a \gets S$: 当 S 是一个有限集合时，a 是从 S 中随机、均匀抽取的一个值。

$a_i \in \mathbb{Z}_q^n$: 这是模 𝑞 的 n-维向量空间。它由长度为 𝑛 的向量组成，其中每个分量都来自$\mathbb{Z}_q$

QUESTION：

2241. Design an ATM Machine.md
There is an ATM machine that stores banknotes of 5 denominations: 20, 50, 100, 200, and 500 dollars. Initially the ATM is empty. The user can use the machine to deposit or withdraw any amount of money.

When withdrawing, the machine prioritizes using banknotes of larger values.

For example, if you want to withdraw $300 and there are 2 $50 banknotes, 1 $100 banknote, and 1 $200 banknote, then the machine will use the $100 and $200 banknotes.
However, if you try to withdraw $600 and there are 3 $200 banknotes and 1 $500 banknote, then the withdraw request will be rejected because the machine will first try to use the $500 banknote and then be unable to use banknotes to complete the remaining $100. Note that the machine is not allowed to use the $200 banknotes instead of the $500 banknote.
Implement the ATM class:

ATM() Initializes the ATM object.
void deposit(int[] banknotesCount) Deposits new banknotes in the order $20, $50, $100, $200, and $500.
int[] withdraw(int amount) Returns an array of length 5 of the number of banknotes that will be handed to the user in the order $20, $50, $100, $200, and $500, and update the number of banknotes in the ATM after withdrawing. Returns [-1] if it is not possible (do not withdraw any banknotes in this case).

My Think：

The purpose of this question is to simulate an ATM machine, which returns the amount of money you withdraw, no more and no less. I am greedy, because the second sentence “There are 3 $200 bills and 1 $500 bill in the machine, so the withdrawal request will be rejected”
This shows that we can skip thinking about the knapsack problem in complex dynamic programming and directly consider simple greed.

Because the denominations of the deposited money are only 20, 50, 100, 200, 500, we can store them in the list in advance and wait for traversal.

Then we create a defaultdict() to create a hash table for each denomination in the ATM machine.

deposit() creates a reverse traversal dictionary. Because we need to traverse the dictionary from large denominations to small denominations, the reverse dictionary is very convenient at this time.

Assuming the initial amount is 600, the first denomination traversed is 500, It fits the logic of the question very well

For the withdraw() function, I created a temporary dictionary deep copy storage so that the initial array will not be changed when [-1] is returned. Otherwise, it will be troublesome to backtrack.

Here, Sylvia and I used two different traversal methods. She traversed the list of denominations, while I traversed the dictionary directly (actually traversed the key directly).

1. If the current denomination (600) is greater than the current denomination (500), then try to deduct it. If the bank money is withdrawn directly, then look at the next denomination.

2. If it is not withdrawn, then amount deducts the deductible share and then continues to look at the next denomination.

3. If there is still amount left at the end, return [-1], otherwise calculate how many bills have been consumed in total, which is the answer.

这道题的目的是模拟一台ATM机器, 让你取多少钱, 就返回多少钱, 不能多也不能少. 我是贪心的思想, 因为第二句”机器里有 3 张 $200 的钞票和1 张 $500 的钞票，那么取款请求会被拒绝”
这就说明我们可以跳过思考复杂的动态规划中的背包问题, 而直接考虑简单的贪心.

因为存的钱的面额只有20, 50, 100, 200, 500 这五种面额, 于是我们提前存在列表里面等待遍历即可.
然后我们创建一个defaultdict(), 为ATM机器里面的每种面额创建哈希表.

deposit()创建了一个反向遍历的字典. 因为我们需要从大面额到小面额遍历字典, 在这个时候反向的字典就很方便.

假设初始`amount`为`600`, 遍历到的第一个面额就是`500`, 就很符合题目的逻辑

withdraw()函数, 我之所以创建了一个临时字典深拷贝储存是在返回[-1]的情况下不更改初始数组. 否则还要回溯挺麻烦的.

这里我和Sylvia用了两种不同的遍历方式, 她遍历了面额的列表, 而我是直接遍历的字典(实际上直接遍历的key).

1. 如果当前面额(600)大于了当前面额(500), 那就尝试扣除, 如果直接把银行钱取完了, 那再看下一个面值.
2. 如果没有取完, 那么amount扣除掉能扣除的份额, 再继续看下一个面额即可.
3. 到最后amount还有剩余则返回[-1], 否则计算一共消耗了多少张钞票, 即是答案了.

Code：

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

import copy
from typing import List

from collections import defaultdict


class ATM:

    def __init__(self):
        self.sd = defaultdict(int)
        self.amount = ['20', '50', '100', '200', '500']

    def deposit(self, banknotesCount: List[int]) -> None:
        for i in range(len(banknotesCount) - 1, -1, -1):
            self.sd[self.amount[i]] += banknotesCount[i]



    def withdraw(self, amount: int) -> List[int]:
        tempSd = copy.deepcopy(self.sd)
        # key = 面值, value = 张数
        for key, value in tempSd.items():
            if amount >= int(key) and value > 0:
                # 需要多少张钞票
                howManyPiece = amount // int(key)
                if howManyPiece >= value:
                    # 全部取出来
                    tempSd[key] = 0
                    amount -= value * int(key)
                else:
                    # 取出这么多钞票
                    tempSd[key] -= howManyPiece
                    amount -= int(key) * howManyPiece
        else:
            if amount > 0:
                return [-1]
            else:
                ans = []
                for i in self.sd.keys():
                    ans.append(self.sd[i] - tempSd[i])
                self.sd = copy.deepcopy(tempSd)
                return ans[::-1]

QUESTION：

MyCalendar.md

My Think：

Today we are talking about MyCalendar I II III. The daily questions for these three days are the same, so we will do them together.

今天我们讲MyCalendar I II III, 这三天的每日一题都是一样的,所以一起做了.

I:

We use binary search to find where startTime can be inserted, and return False if it is found in advance. After finding the insertion point, we can check whether there is overlap.

我们用二分查找, 查找 startTime 在哪里可以插入, 如果提前找到了直接返回 False. 找到了插入点后, 再检查是否有重叠即可.

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

class MyCalendar:

    def __init__(self):
         self.date = []

    def book(self, startTime: int, endTime: int) -> bool:
        # Binary Search 二分查找 
        n = len(self.date)
        left, right = 0, n - 1
        while left <= right:
            mid = (left + right) // 2
            if self.date[mid][0] < startTime:
                left = mid + 1  # Move the left pointer 移动左指针
            elif self.date[mid][0] > startTime:
                right = mid - 1  # Move the right pointer 移动右指针
            else:
                return False  # Find the overlap 发现重叠
        # Check for overlap with previous and next intervals 检查与前后区间的重叠
        if left > 0 and self.date[left - 1][1] > startTime:
            return False
        if left < len(self.date) and self.date[left][0] < endTime:
            return False

        # Insert it 插入区间
        self.date.insert(left, (startTime, endTime))
        return True

II:

This question requires us to check whether there will be three reservations under the conditions of the previous question. Although binary search can also be done, it will be much more complicated. We introduce the idea of ​​differential (Line Sweep) in this question.

1. Record the changes at each time point (start and end)
   When a new interval [startTime, endTime) is to be inserted:

   1. At the position corresponding to startTime +1
   2. At the position corresponding to endTime -1
      In this way, we only record “how much the overlap number should be added/subtracted at these two boundary time points”.

2. Count the current maximum overlap when necessary
   Sort all-time points (keys) from small to large, and accumulate their +1/-1 values in turn.
   The result of the accumulation is the number of activities carried out simultaneously at the corresponding time (that is, the “overlap number”).
   If you want to find out whether there is a triple reservation, see whether the maximum of this accumulation process reaches 3 (or higher)

这道题要求我们在上一道题的条件下, 检查是否会出现三次预定. 二分查找虽然也可以做, 但是会复杂很多. 我们在这一题引入差分(Line Sweep)的思想.

1. 记录每个时间点（开始与结束）的变化
   当有新的区间 [startTime, endTime) 要插入时：

   1. 在 startTime 对应的位置 +1
   2. 在 endTime 对应的位置 -1
      这样我们只记录“在这两个边界时间点，重叠数量要加/减多少”。

2. 在需要时统计当前的最大重叠
   把所有的时间点（key）从小到大排序，依次累加其 +1/-1 值。
   累加的结果就是对应时刻同时进行的活动数量（也就是“重叠数量”）。
   如果要查找是否出现三重预定，就看这个累加过程最大是否到达 3（或更高）

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

from sortedcontainers import SortedDict
class MyCalendarTwo:
    def __init__(self):
        self.sd = SortedDict()
    def book(self, startTime: int, endTime: int) -> bool:
        self.sd[startTime] = self.sd.get(startTime, 0) + 1
        self.sd[endTime] = self.sd.get(endTime, 0) - 1
        s = 0
        for v in self.sd.values():
            s += v
            if s > 2:
                self.sd[startTime] -= 1
                self.sd[endTime] += 1
                return False
        return True

III:

This question is even more difficult. It requires us to find the maximum number of multiple reservations. We can just record it based on the previous question.

1. Difference record

   Same as before: +1 at the position corresponding to startTime, -1 at the position corresponding to endTime.

   Store in self.sd: key = time point, value = increase or decrease at that time point.

2. Find the maximum number of overlaps

   Use a rolling variable ongoing to indicate “how many overlaps there are at the current moment”.
   Each time a time point is traversed, the corresponding difference is accumulated to ongoing, and then max_overlap = max(max_overlap, ongoing) is updated.

这道题更加过分, 要求我们找到多重预定中最多有多少重, 我们就在上一道题的基础上记录即可.

1. 差分记录

   与之前一致：在 startTime 对应的位置 +1，在 endTime 对应的位置 -1。
   self.sd 中存储：key=时间点, value=该时间点的增减量。

2. 求最大重叠数

   用一个滚动变量 ongoing 表示“当前时刻有多少重叠”。
   每遍历一个时间点，把对应的差分累加到 ongoing，然后更新 max_overlap = max(max_overlap, ongoing)。

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

from sortedcontainers import SortedDict


class MyCalendarThree:
    def __init__(self):
        self.sd = SortedDict()

        self.max_overlap = 0

    def book(self, startTime: int, endTime: int) -> int:
        # First, record the "plus 1" and "minus 1" of this reservation.先把这次预定的“加1”和“减1”记录下来
        self.sd[startTime] = self.sd.get(startTime, 0) + 1
        self.sd[endTime] = self.sd.get(endTime, 0) - 1

        # Temporary variable, record the number of overlaps 临时变量, 记录几折叠
        ongoing = 0 # Current overlap number
        tmp_max = 0
        for v in self.sd.values():
            ongoing += v
            tmp_max = max(ongoing, tmp_max)
        self.max_overlap = max(self.max_overlap, tmp_max)
        return self.max_overlap

Description:

https://leetcode.cn/problems/minimum-length-of-anagram-concatenation/description/?envType=daily-question&envId=2024-12-20
You are given a string s, which is known to be a concatenation of anagrams of some string t.

Return the minimum possible length of the string t.

An anagram is formed by rearranging the letters of a string. For example, “aab”, “aba”, and, “baa” are anagrams of “aab”.

Example 1:

Input: s = "abba"

Output: 2

Explanation:

One possible string t could be "ba".

Example 2:

Input: s = "cdef"

Output: 4

Explanation:

One possible string t could be "cdef", notice that t can be equal to s.

Thinking:

Since the problem naturally suggests using a counting method (Counter), we need to find the minimum substring for each string. For example, for abba, the result is ab; for cdef, it’s cdef.
We iterate from length 1 (a single character) onwards, slicing the string to get the current substring.

Initially, we compute the character count for the original string using Counter, which gives us a dictionary of character frequencies.
Next, we only need to check if the count of each character in the current substring multiplied by n/k equals the count in the original string (i.e., whether repeating the current substring x times equals the original string).

由于题意很容易联想到这道题要进行计数(Counter). 我们需要找到每个字符串的最小子串，abba为ab, cdef为cdef. 于是我们从长度0（即单个字符）开始遍历，期间通过切片的形式来获取当前子串。
因为最开始我们对原始字符串进行了Counter，得到了字符数量和字符对应的字典。接下来我们只需要判断当前子串的Counter到的某个字符的数值乘以n/k是否等于原始字符串的Counter的值即可（即当前子串乘以x倍是否等于源字符串）。

Code:

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

import collections
class Solution:
    def minAnagramLength(self, s: str) -> int:
        def check(k: int) -> bool:
            # 遍历字符串 s，每次取长度为 k 的子串
            # Iterate over the string `s`, taking substrings of length `k`
            for i in range(0, n, k):
                # 统计每个字符出现的次数
                # Count the occurrences of each character in the current substring
                cnt1 = collections.Counter(s[i: i + k])
                for c, v in cnt.items():
                    # 如果每个字符出现的次数乘以 n/k != cnt[] return False
                    # If the count of any character multiplied by (n // k) != the original count, return False
                    if cnt1[c] * (n // k) != v:
                        return False
            return True

        cnt = collections.Counter(s)
        n = len(s)
        for i in range(1, n+1):
            if n % i == 0 and check(i):
                return i

Description:

You are given an integer array nums of even length. You have to split the array into two parts nums1 and nums2 such that:

nums1.length == nums2.length == nums.length / 2.
nums1 should contain distinct elements.
nums2 should also contain distinct elements.
Return true if it is possible to split the array, and false otherwise.

Example 1:

Input: nums = [1,1,2,2,3,4]
Output: true
Explanation: One of the possible ways to split nums is nums1 = [1,2,3] and nums2 = [1,2,4].
Example 2:

Input: nums = [1,1,1,1]
Output: false
Explanation: The only possible way to split nums is nums1 = [1,1] and nums2 = [1,1]. Both nums1 and nums2 do not contain distinct elements. Therefore, we return false.

Thinking:

题目要求判断是否可以将数组分成两个部分，使得两个部分的元素都是不同的。
最开始考虑的是Counter()记录每个数字是否满足某个条件，如果不满足就返回False。后面发现不需要Counter，普通的字典记录，中途遇到某个数字大于2就返回False即可。

Code:

1
2
3
4
5
6
7
8

class Solution:
    def isPossibleToSplit(self, nums: List[int]) -> bool:
        Counter_nums = Counter(nums)
        for i, j in Counter_nums.items():
            if j > 2:
                return False
        else:
            return True

1
2
3
4
5
6
7
8

class Solution:
    def isPossibleToSplit(self, nums: List[int]) -> bool:
        count = {}
        for num in nums:
            count[num] = count.get(num, 0) + 1
            if count[num] > 2:
                return False
        return True

QUESTION：

1366. Rank Teams by Votes.md
In a special ranking system, each voter gives a rank from highest to lowest to all teams participating in the competition.

The ordering of teams is decided by who received the most position-one votes. If two or more teams tie in the first position, we consider the second position to resolve the conflict, if they tie again, we continue this process until the ties are resolved. If two or more teams are still tied after considering all positions, we rank them alphabetically based on their team letter.

You are given an array of strings votes which is the votes of all voters in the ranking systems. Sort all teams according to the ranking system described above.

Return a string of all teams sorted by the ranking system.

Example 1:

Input: votes = [“ABC”,”ACB”,”ABC”,”ACB”,”ACB”]
Output: “ACB”
Explanation:
Team A was ranked first place by 5 voters. No other team was voted as first place, so team A is the first team.
Team B was ranked second by 2 voters and ranked third by 3 voters.
Team C was ranked second by 3 voters and ranked third by 2 voters.
As most of the voters ranked C second, team C is the second team, and team B is the third.
Example 2:

Input: votes = [“WXYZ”,”XYZW”]
Output: “XWYZ”
Explanation:
X is the winner due to the tie-breaking rule. X has the same votes as W for the first position, but X has one vote in the second position, while W does not have any votes in the second position.
Example 3:

Input: votes = [“ZMNAGUEDSJYLBOPHRQICWFXTVK”]
Output: “ZMNAGUEDSJYLBOPHRQICWFXTVK”
Explanation: Only one voter, so their votes are used for the ranking.

Constraints:

1 <= votes.length <= 1000
1 <= votes[i].length <= 26
votes[i].length == votes[j].length for 0 <= i, j < votes.length.
votes[i][j] is an English uppercase letter.
All characters of votes[i] are unique.
All the characters that occur in votes[0] also occur in votes[j] where 1 <= j < votes.length.

My Think：

This question requires us to count their votes. The first thing that comes to mind is to build a double structure, similar to this:
这道题要求我们统计他们的投票情况. 首先想到的就是构建一个双重结构体, 类似于这样:

1
2
3
4
5
6
7

type struct {
    char A {
        1: 1;
        2: 1;
        3: 1;
    }
}

Then fill in the dictionary in a double loop and sort it. It’s very simple in Python, but I thought it was complicated at first and built the sorting logic manually.
Finally, we can use lambda expression sorted_teams = sorted(rank.keys(), key = lambda x: ([-rank[x][i] for i in range(len(votes[0]))], x))

What needs to be noted in Go is the usage of the standard answer. Use slices.SortedFunc to sort the teams. The sorting rules are defined according to the requirements of the question:

1. Sort in descending order by votes.
2. If the votes are the same, sort in ascending alphabetical order.
   maps.Keys(cnts) gets the keys of all teams (that is, the characters of all teams)
   slices.Compare(cnts[b], cnts[a]): compare the vote slices of two teams and sort in descending order by votes (b comes first).
   cmp.Compare(a, b): when the votes are the same, sort in ascending alphabetical order.
   cmp.Or: execute the first comparison rule. If the return value is not 0 (that is, there is a priority difference), return directly; otherwise execute the next rule.

然后在一个双重循环中填写这个字典, 最后进行排序即可. 在Python中十分简单, 但是我一开始想复杂了, 手动构建了排序逻辑.
最后用lambda表达式即可sorted_teams = sorted(rank.keys(), key = lambda x: ([-rank[x][i] for i in range(len(votes[0]))], x))

Go里需要注意的是标准答案的用法, 使用 slices.SortedFunc 对团队进行排序，排序规则按题目要求定义：

1. 按票数降序排列。
2. 如果票数相同，按字母升序排列。
   maps.Keys(cnts) 获取所有团队的键（即所有团队的字符）
   slices.Compare(cnts[b], cnts[a])：比较两个团队的票数切片，按票数降序排列（b 在前）。
   cmp.Compare(a, b)：当票数相同时，按字母升序排列。
   cmp.Or：执行第一个比较规则，如果返回值非 0（即有优先级差异），直接返回；否则执行下一个规则。

Code：

1
2
3
4
5
6
7
8

class Solution:
    def rankTeams(self, votes: List[str]) -> str:
        rank = defaultdict(lambda: defaultdict(int))
        for value in votes:
            for ind, c in enumerate(value):
                rank[c][ind] += 1
        sorted_teams = sorted(rank.keys(), key = lambda x: ([-rank[x][i] for i in range(len(votes[0]))], x))
        return ''.join(sorted_teams)

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

def rankTeams_Siz(self, votes: List[str]) -> str:
        rank = defaultdict(lambda: defaultdict(int))
        for value in votes:
            for ind, c in enumerate(value):
                rank[c][ind] += 1
        print(rank)
        ans = ''
        for i in range(len(votes[0])):
            temp_ans = ''
            count = 0
            for key, value in rank.items():
                if value[i] > count:
                    temp_ans = key
                    count = value[i]
                else:
                    # 如果并列, 则考虑下一位 If there is a tie, consider the next one
                    while value[i] == count:
                        i += 1 # 这个i是临时变量, 直接用 This i is a temporary variable, use it directly
                        if i > len(votes[0]): # 考虑找到最后都没找到的情况Consider the situation where you find nothing in the end.
                            # 答案值应该是字母顺序 The answer values should be in alphabetical order
                            temp_ans = key
                            break
                        if value[i] > count:
                            temp_ans = key
                            count = value[i]
            ans += temp_ans
        return ans

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

func rankTeams(votes []string) string {
    cnts:=map[rune][]int{}
    for _,ch := range votes[0] {
        cnts[ch]=make([]int,len(votes[0]))
    }

    for _,vote := range votes{
        for i,ch := range vote{
            cnts[ch][i]++
        }
    }

    res := slices.SortedFunc(maps.Keys(cnts),func(a,b rune) int{
        return cmp.Or(slices.Compare(cnts[b],cnts[a]),cmp.Compare(a,b))
    })
    return string(res)
}

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

package main

import "sort"

func rankTeams(votes []string) string {
	rank := make(map[byte]map[int]int)

	for _, vote := range votes {
		for i := 0; i < len(vote); i++ {
			team := vote[i]
			if _, ok := rank[team]; !ok {
				rank[team] = make(map[int]int)
			}
			rank[team][i]++
		}
	}

	teams := make([]byte, 0, len(rank))
	for team := range rank {
		teams = append(teams, team)
	}

	sort.Slice(teams, func(i, j int) bool {
		a, b := teams[i], teams[j]
		for k := 0; k < len(votes[0]); k++ {
			// 比较两队在 k 排位的票数 // Compare the votes of the two teams in position k
			countA, countB := rank[a][k], rank[b][k]
			if countA != countB {
				return countA > countB // 按票数降序 Sort by votes in descending order
			}
		}
		return a < b // 字母升序 Alphabetical ascending
	})
	// 拼接结果
	return string(teams)
}

QUESTION：

3159. Find Occurrences of an Element in an Array.md
You are given an integer array nums, an integer array queries, and an integer x.

For each queries[i], you need to find the index of the queries[i]th occurrence of x in the nums array. If there are fewer than queries[i] occurrences of x, the answer should be -1 for that query.

Return an integer array answer containing the answers to all queries.

Example 1:

Input: nums = [1,3,1,7], queries = [1,3,2,4], x = 1

Output: [0,-1,2,-1]

Explanation:

For the 1st query, the first occurrence of 1 is at index 0.
For the 2nd query, there are only two occurrences of 1 in nums, so the answer is -1.
For the 3rd query, the second occurrence of 1 is at index 2.
For the 4th query, there are only two occurrences of 1 in nums, so the answer is -1.
Example 2:

Input: nums = [1,2,3], queries = [10], x = 5

Output: [-1]

Explanation:

For the 1st query, 5 doesn’t exist in nums, so the answer is -1.

Constraints:

1 <= nums.length, queries.length <= 105
1 <= queries[i] <= 105
1 <= nums[i], x <= 104

My Think：

I haven’t written a solution for a long time. Now that I’m on vacation, I’m starting over. This question requires us to find “all x’s indices” from the given nums, and then return the index address of the queries-th x.
So we can use the list generation formula indices = [i for i, value in enumerate(nums) if value == x] to return a list containing all x’s indices,
and then query them one by one.
First mistake: I didn’t consider the case where indices is empty, so indices[q-1] out of range.
Second mistake: I forgot that the for loop in Golang needs two parameters to receive the value passed by range.

很久没有写题解了,现在放假了于是重新开始了. 这一道题要求我们从给定的nums中找到”所有x的索引”, 然后返回第queries个x的索引地址即可.
于是我们可以用列表生成式indices = [i for i, value in enumerate(nums) if value == x]来返回一个包含所有x索引的列表,
然后依次在其中查询即可.
第一次错误: 没有考虑indices为空的情况, 于是indices[q-1] out of range.
第二次错误: 忘记了Golang里的for循环需要两个参数接收range传来的value.

Code：

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

class Solution:
    def occurrencesOfElement(self, nums: List[int], queries: List[int], x: int) -> List[int]:
        # Find the indices of all elements equal to x
        indices = [i for i, value in enumerate(nums) if value == x]
        # print(indices)
        n = len(indices)
        ans = []
        for q in queries:
            if indices and q-1 < n:
                ans.append(indices[q-1])
            else:
                ans.append(-1)
        return ans

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

func occurrencesOfElement(nums []int, queries []int, x int) []int {
    var indices []int
    for i, value := range nums {
        if value == x {
            indices = append(indices, i)
        }
    }
    var ans []int
    n := len(indices)
    for _, q := range queries { // "_, q"
        if n > 0 && q-1 < n { 
            ans = append(ans, indices[q-1])
        } else {
            ans = append(ans, -1)
        }
    }
    return ans
}

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.

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

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: