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

Counting Stars-Inter-Uni Programming Contest

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

Description:

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

Thinking:

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

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

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

Code:

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

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

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

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

last_y = []

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

print(len(last_y))

show all >>

9021_TUT_4

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

Exercise 1

Problem Description

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
%%run_and_test python3 -c "from exercise_4_1 import f1; f1(13)"

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

So we have the following solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Assume that the argument n is an integer at least equal to 1.
#
# Each integer is printed out in a field of size equal to
# the number of digits in n plus 1.
#
# The output is printed out, not returned.

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

Complexity Analysis

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

Exercise 2

Problem Description

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

In my solution:

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

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

The standard solution is:

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

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

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

Exercise 3

Problem Description

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

In my solution:

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

Explanation:

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

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

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

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

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

The standard solution is:

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

Explanation:

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

Key points:

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

Exercise 4

Problem Description

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

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

Example 1:

For n = 13:

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

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

Explanation:

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

  1. Handling the case when n is zero:

    1
    2
    3
    if not n:
        print('0 = 0')
        return

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

  2. Converting the number to binary:

    1
    binary_n = f'{n:b}'

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

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

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

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

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

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

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

Exercise 5

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

  1. Let’s try:
1
2
3
L1 = [1, 2, 3]
L2 = [4, 5, 6]
print(list(zip(L1, L2)))

Output:

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

And zip in dictionary:

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

Output:

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

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

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

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

Output:

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

Problem Description

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

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

Wrong Solution:

1
2
3
4
5
6
7
8
9
def f5(*L):
    ans = []
    left = 0
    right = len(L) - 1
    while left < len(L):
        ans.append(((L[left], L[right]), (L[right], L[left])))
        left += 1
        right -= 1
    return ans

Correct Solution:

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

The idea behind the correct solution is as follows:

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

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

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

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

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

Exercise 6

Problem Description

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

At first, I attempted the following approach:

Wrong Solution:

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

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

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

However, the output of this solution was:

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

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

Correct Solution:

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

Explanation of the Fix:

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

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

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

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

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

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

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

show all >>

DartsInter-Uni Programming Contest Tasks Leaderboard Contest

字数统计: 1.6k字   |   阅读时长: 9min

Description：

Darts
https://interunia.unswcpmsoc.com/task/Darts/

Thinking：

This contest is harder than I imaged, this is the second task, and I spent a lot of time but when I checked the Leaderboard and no one has solved it yet, I feel a little bit better.
At first, I thought of simply judging whether this point is in the middle of this circle, using Euclidean distance calculation. But later I found that when there are n circles and m darts, the amount of data is surprisingly large. After the brute force cracking timed out, I had to consider a new method.

We can use the gridded Spatial Indexing, the specific steps are as follows:

1. Spatial division: Divide the entire plane into grids of equal size (Grid), and map the target and dart to the corresponding grid.

Purpose:

  • Reduce the number of targets that need to be calculated.
  • For each dart, you only need to check the targets in its grid and adjacent grids.

2. Map Targets to Grids:

  • Calculate the bounding box of each target.
    • Lower-left corner: ( (x_i - r_i, y_i - r_i) )
    • Upper-right corner: ( (x_i + r_i, y_i + r_i) )
  • Record all grid cells covered by this rectangle and add the target index to these grid cells.

3. Map Darts to Grids:

For each dart, calculate the grid coordinates where it is located.

4. Check if the Dart Hits a Target:

  • For each dart, check all targets in its grid and the adjacent 8 grids.
  • Calculate the distance from the dart to the center of each target and determine whether it is less than or equal to the square of the target’s radius, i.e., ( (dx - x_i)^2 + (dy - y_i)^2 \leq r_i^2 ).

Grid Division Parameters

Grid size (GRID_SIZE):

  • Choose an appropriate grid size, such as 500.
  • The choice of grid size requires a trade-off between space and time efficiency.
1
2
3
4
5
auto get_grid_cell = [&](long long x_n, long long y_n) {
    int gx = int((x_n - min_x) / s);
    int gy = int((y_n - min_y) / s);
    return make_pair(gx, gy);
};

Coordinate mapping function:

Maps actual coordinates to grid coordinates.

  • s is the actual length of each grid cell.
  • $min_x$ and $min_y$ are the minimum values among all target and dart coordinates, used to shift the coordinates.

Mapping Targets to Grids

  • Iterate over all targets and calculate their covered grid ranges.
  • In these grids, record the indices of the targets.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
for (int idx = 0; idx < n; ++idx) {
    int x, y, r;
    tie(x, y, r) = circles[idx];
    long long x_min = x - r;
    long long x_max = x + r;
    long long y_min = y - r;
    long long y_max = y + r;
    auto [gx_min, gy_min] = get_grid_cell(x_min, y_min);
    auto [gx_max, gy_max] = get_grid_cell(x_max, y_max);
    for (int gx = gx_min; gx <= gx_max; ++gx) {
        for (int gy = gy_min; gy <= gy_max; ++gy) {
            long long key = get_grid_key(gx, gy);
            grid[key].push_back(idx); // 存储靶子索引
        }
    }
}

Mapping Darts to Grids

  • For each dart, calculate the grid cell it belongs to.
  • No need to store darts in grids; we process them directly.

Checking if Darts Hit Targets

  • For each dart, get its grid coordinates ( (gx, gy) ).
  • Check the dart’s grid cell and its 8 adjacent grid cells.
  • For each target in these grids, calculate the distance to the dart.
  • If the distance squared is less than or equal to the target’s radius squared, increment the counter.
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
for (const auto& p : points) {
    int dx = p.first;
    int dy = p.second;
    auto [gx, gy] = get_grid_cell(dx, dy);
    bool found = false;
    
    // Check the grid and the 8 adjacent grids
    for (int ix = gx - 1; ix <= gx + 1; ++ix) {
        for (int iy = gy - 1; iy <= gy + 1; ++iy) {
            long long key = get_grid_key(ix, iy);
            if (grid.count(key)) {
                const auto& circle_indices = grid[key];
                for (int idx : circle_indices) {
                    int x, y, r;
                    tie(x, y, r) = circles[idx];
                    // caculate the distance
                    long long dx_sq = (long long)(dx - x) * (dx - x);
                    long long dy_sq = (long long)(dy - y) * (dy - y);
                    long long r_sq = (long long)r * r;
                    if (dx_sq + dy_sq <= r_sq) {
                        ans++;
                        found = true;
                        break; // The dart has found the target, check the next dart
                    }
                }
            }
            if (found) break;
        }
        if (found) break;
    }
}

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
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
import math

n, m = map(int, input().split())

circles = []

min_x = min_y = float('inf')
max_x = max_y = float('-inf')

for _ in range(n):
    x, y, r = map(int, input().split())
    circles.append((x, y, r))
    min_x = min(min_x, x - r)
    max_x = max(max_x, x + r)
    min_y = min(min_y, y - r)
    max_y = max(max_y, y + r)

points = []

for _ in range(m):
    dx, dy = map(int, input().split())
    points.append((dx, dy))
    min_x = min(min_x, dx)
    max_x = max(max_x, dx)
    min_y = min(min_y, dy)
    max_y = max(max_y, dy)

GRID_SIZE = 500
delta_x = max_x - min_x
delta_y = max_y - min_y
s = max(delta_x, delta_y) / GRID_SIZE
if s == 0:
    s = 1

# Function that maps coordinates to grid indices
def get_grid_cell(x_n, y_n):
    gx = int((x_n - min_x) / s)
    gy = int((y_n - min_y) / s)
    return gx, gy

grid = {}

# Mapping the targets onto the grid
for idx, (x, y, r) in enumerate(circles):
    x_min = x - r
    x_max = x + r
    y_min = y - r
    y_max = y + r
    gx_min, gy_min = get_grid_cell(x_min, y_min)
    gx_max, gy_max = get_grid_cell(x_max, y_max)
    for gx in range(gx_min, gx_max + 1):
        for gy in range(gy_min, gy_max + 1):
            if (gx, gy) not in grid:
                grid[(gx, gy)] = []
            grid[(gx, gy)].append(idx)  # store the target index

ans = 0

# For each dart, check the target in the grid where it is located
for dx, dy in points:
    gx, gy = get_grid_cell(dx, dy)
    found = False
    if (gx, gy) in grid:
        for idx in grid[(gx, gy)]:
            x, y, r = circles[idx]
            # Determine if the dart is in the target
            if (dx - x) ** 2 + (dy - y) ** 2 <= r ** 2:
                ans += 1
                found = True
                break  # 找到后跳出循环
    # The grids do not overlap and the surrounding grids are not detected?

print(ans)
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
#include <iostream>
#include <vector>
#include <cmath>
#include <unordered_map>
#include <algorithm>
#include <climits>

using namespace std;

int main() {
    // Fast input/output
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    vector<tuple<int, int, int>> circles;
    long long min_x = LLONG_MAX, min_y = LLONG_MAX;
    long long max_x = LLONG_MIN, max_y = LLONG_MIN;

    // Read circles and update bounding box
    for (int i = 0; i < n; ++i) {
        int x, y, r;
        cin >> x >> y >> r;
        circles.emplace_back(x, y, r);
        min_x = min(min_x, (long long)x - r);
        max_x = max(max_x, (long long)x + r);
        min_y = min(min_y, (long long)y - r);
        max_y = max(max_y, (long long)y + r);
    }

    vector<pair<int, int>> points;

    // Read darts and update bounding box
    for (int i = 0; i < m; ++i) {
        int dx, dy;
        cin >> dx >> dy;
        points.emplace_back(dx, dy);
        min_x = min(min_x, (long long)dx);
        max_x = max(max_x, (long long)dx);
        min_y = min(min_y, (long long)dy);
        max_y = max(max_y, (long long)dy);
    }

    const int GRID_SIZE = 500;
    long long delta_x = max_x - min_x;
    long long delta_y = max_y - min_y;
    double s = max(delta_x, delta_y) / (double)GRID_SIZE;
    if (s == 0) {
        s = 1;
    }

    // Function to get grid cell indices
    auto get_grid_cell = [&](long long x_n, long long y_n) {
        int gx = int((x_n - min_x) / s);
        int gy = int((y_n - min_y) / s);
        return make_pair(gx, gy);
    };

    // Function to combine gx and gy into a single key
    auto get_grid_key = [](int gx, int gy) -> long long {
        return ((long long)gx << 32) | (unsigned int)gy;
    };

    // Map from grid cell key to list of circle indices
    unordered_map<long long, vector<int>> grid;

    // Map circles to grid cells
    for (int idx = 0; idx < n; ++idx) {
        int x, y, r;
        tie(x, y, r) = circles[idx];
        long long x_min = x - r;
        long long x_max = x + r;
        long long y_min = y - r;
        long long y_max = y + r;
        auto [gx_min, gy_min] = get_grid_cell(x_min, y_min);
        auto [gx_max, gy_max] = get_grid_cell(x_max, y_max);
        for (int gx = gx_min; gx <= gx_max; ++gx) {
            for (int gy = gy_min; gy <= gy_max; ++gy) {
                long long key = get_grid_key(gx, gy);
                grid[key].push_back(idx); // Store circle index
            }
        }
    }

    int ans = 0;

    // For each dart, check circles in its grid cell and adjacent cells
    for (const auto& p : points) {
        int dx = p.first;
        int dy = p.second;
        auto [gx, gy] = get_grid_cell(dx, dy);
        bool found = false;

        // Check the dart's grid cell and its 8 neighbors
        for (int ix = gx - 1; ix <= gx + 1; ++ix) {
            for (int iy = gy - 1; iy <= gy + 1; ++iy) {
                long long key = get_grid_key(ix, iy);
                if (grid.count(key)) {
                    const auto& circle_indices = grid[key];
                    for (int idx : circle_indices) {
                        int x, y, r;
                        tie(x, y, r) = circles[idx];
                        // Check if the dart is inside the circle
                        long long dx_sq = (long long)(dx - x) * (dx - x);
                        long long dy_sq = (long long)(dy - y) * (dy - y);
                        long long r_sq = (long long)r * r;
                        if (dx_sq + dy_sq <= r_sq) {
                            ans++;
                            found = true;
                            break; // Move to next dart
                        }
                    }
                }
                if (found) break;
            }
            if (found) break;
        }
    }

    cout << ans << '\n';
    return 0;
}

show all >>