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

扫一扫，分享到微信

微信分享二维码