2241. Design an ATM Machine

字数统计: 1.1k字   |   阅读时长: 5min

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]

show all >>

MyCalendar

字数统计: 1.1k字   |   阅读时长: 5min

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

show all >>

3138. Minimum Length of Anagram Concatenation

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

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

show all >>

3046. Split the Array

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

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:

O(2n)
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
O(n)
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

show all >>

1366. Rank Teams by Votes

字数统计: 1.3k字   |   阅读时长: 7min

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

show all >>

3159. Find Occurrences of an Element in an Array

字数统计: 632字   |   阅读时长: 3min

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
}

show all >>

9021_TUT_9

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

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

Exercise 1

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

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

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

My Solution:

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


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

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

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

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

Standard Solution:

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

Exercise 2

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

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

My Solution:

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


from collections import defaultdict


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

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

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

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

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

Optimize Solution:

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

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

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

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

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

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

    i = j  # Move i to the new distinct value

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

Standard Solution:

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

Exercise 3

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

Standard Solution:

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

Explanation:

Explanation of Each Step

  1. Check for Underscores:

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

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

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

  3. Replace Underscores:

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

  4. Parse Equation Parts:

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

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

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

  5. Validate the Equation:

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

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

  6. No Solution Case:

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

Exercise 4

My Solution:

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

Standard Solution:

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

Explanation:

  1. Character Offset Calculation:

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

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

  2. Zigzag Filling:

    1. The columns are filled zigzag-style:

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

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

  3. Efficient Calculation:

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

Exercise 5:

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

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


from random import seed, randrange
dim = 10


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


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

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

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

Exercise 6:

Problem Description:

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

  1. Word Pair Requirements:

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

  2. Output Order:

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

Standard Solution:

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


from collections import Counter
dictionary_file = 'dictionary.txt'


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

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

show all >>

9021_TUT_8

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

Exercise 1

Problem Description

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

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

  2. Tracking previously seen primes to prevent duplicates.

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

The following Python script is used to test the functionality:

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

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

The expected output from running the above code is:

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

My Solution

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

# DEFINE A CLASS THAT DERIVES FROM EXCEPTION

class PrimeError(Exception):
pass

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

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

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

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

Standard Solution

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

class PrimeError(Exception):
    pass

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

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

Summary

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

  1. Prime Checking Method:

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

  2. Code Structure:

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

  3. Reset Method:

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

Exercise 2

Problem Description

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

  1. Validate that the modulus is a prime number.

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

  3. Represent the number in modular form.

The following Python script is used to test the functionality:

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

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

The expected output from running the above code is:

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

Standard Solution

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

# DEFINE TWO CLASSES THAT DERIVE FROM EXCEPTION

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

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

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

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

Summary

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

  • Exception Handling:

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

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

  • Prime Check:

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

  • Representation:

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

  • Modular Arithmetic:

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

Exercise 3

Problem Description

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

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

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

The following Python script is used to test the functionality:

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

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

The expected output from running the above code is:

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

My Solution

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

class PrimeError(Exception):
    pass

class IntError(Exception):
    pass

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

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

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

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

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

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

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

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

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

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

Standard Solution

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

class ModuloError(Exception):
    pass

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

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

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

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

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

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

Summary

The differences between the two solutions are as follows:

  1. Validation Method:

    • The standard solution defines a _validate method to handle checks for the operands (Modulo type and modulus equality), improving code reuse.

    • My solution performs these checks directly inside the __add__ and __mul__ methods.

  2. In-Place Operations:

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

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

Exercise 4

Problem Description

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

The following Python script is used to test the functionality:

1
2
3
4
5
6
7
from exercise_8_4 import *

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

The expected output from running the above code is:

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

My Solution

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

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

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

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

Standard Solution

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

    def __iter__(self):
        return self

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

Exercise 5

Shoelace Formula

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

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

Example Calculation

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

  1. Write the coordinates as:

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

  2. Multiply diagonally from left to right:

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

  3. Multiply diagonally from right to left:

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

  4. Subtract and divide by 2:

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

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

Problem Description

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

The following Python script is used to test the functionality:

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

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

The expected output from running the above code is:

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

My Solution

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

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

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

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

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

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

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

Standard Solution

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

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

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

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

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

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

Exercise 6

Problem Description

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

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

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

The following Python script is used to test the functionality:

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

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

The expected output from running the above code is:

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

My Solution

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

# exercise_8_6.py
from collections.abc import Sequence

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

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

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

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

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

Standard Solution

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

class CircularTupleError(Exception):
    pass

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

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

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

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

Summary

  1. Exception Handling:

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

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

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

show all >>

9021_TUT_5

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

Exercise 1

Problem Description

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

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

My Solution

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

Standard Solution

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

Explanation

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

Exercise 2

Problem Description

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

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

This means that:

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

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

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

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

Here is my solution:

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

Standard Solution

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

Exercise 3

Problem Description

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

Here’s the task broken down:

  1. First List in the Pair:

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

  2. Second List in the Pair:

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

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

My Solution

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

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

Explanation

  1. First List (first):

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

  2. Second List (second):

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

  3. Key Concepts:

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

Standard Solution

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

Exercise 4

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

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

My Solution

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

Standard Solution

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

Explanation

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

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

Exercise 5

Before E5, let’s do some exercises.

Normal dictionary:

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

print(d)

defaultdict:

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

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

Counter:

1
2
3
4
5
6
from collections import Counter

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

print(d)

Problem Description

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

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

My Solution

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

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

Standard Solution

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

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

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

Additional Solution

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

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

f5_counter()

Additional Additional Solution (Data Analysis) (NOT Mandatory)

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

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

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

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

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

Explanation

Reading the CSV file:

1
df = pd.read_csv(filename)

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

Counting the number of customers per country:

1
df['Country'].value_counts()

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

Exercise 6

Problem Description

The task is to create a directory structure where:

2024-10-08.png

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

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

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

import os
from pathlib import Path
from string import ascii_uppercase

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

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

if __name__ == '__main__':
    main()

Explanation

Explanation of My Solution:

  1. Creating Directories:

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

  2. Reading the Dictionary File:

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

  3. Writing the Words:

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

  4. Potential Issue:

    • here is some limitations of this. Say that processing the dictionary on the fly would not be an option if the words in the file were not lexicographically ordered?
      [//]: # ( - One small mistake is that the file handle f for the dictionary.txt file is shared across iterations, but the file is being processed linearly. Once a word is read, it is not reset for the next letter. This will cause issues because the loop keeps reading until the end of the file and will skip words that should be in earlier letters.)

Standard Solution

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

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

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

show all >>

Horse Racing-Inter-Uni Programming Contest

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

Description:

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

Thinking:

Preprocessing Horse Information:

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

Constructing the Leading Horse Timeline:

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

Handling Queries:

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

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

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

Codes:

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

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

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

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


import bisect

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

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

show all >>