完成Python基础算法和数据结构练习。
Giving back change
1 | def give_change(amount, coins): |
Given the amount of money (expressed as an integer as the total number of cents, one dollar being equal to 100 cents) and the list of available denominations of coins (similarly expressed as cents), create and return a list of coins that add up to amount using the greedy approach where you use as many of the highest denomination coins when possible before moving on to the next lower denomination. The list of coin denominations is guaranteed to be given in descending sorted order, as should your returned result also be.
| amount | coins | Expected result |
|---|---|---|
| 64 | [50, 25, 10, 5, 1] | [50, 10, 1, 1, 1, 1] |
| 123 | [100, 25, 10, 5, 1] | [100, 10, 10, 1, 1, 1] |
| 100 | [42, 17, 11, 6, 1] | [42, 42, 11, 1, 1, 1, 1, 1] |
This particular problem with its countless variations is a classic when modified so that you must minimize the total number of returned coins. The greedy approach will then no longer produce the optimal result for all possible coin denominations. For example, for simple coin denominations of [50, 30, 1] kopecs and the amount of sixty kopecs to be exchanged, the greedy solution [50, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] uses eleven coins, whereas the optimal solution [30, 30] needs only two! A more advanced recursive algorithm would be needed to make the “take it or leave it” decision for each coin and explore which choice leads to a better final outcome. The intermediate results of this recursion would then be memoized to avoid blowing up the running time exponentially.
Rooks on a rampage
1 | def safe_squares_rooks(n, rooks): |
On a generalized n - by- n chessboard, there are some number of rooks , each one represented as a two-tuple (row, column) of the row and the column of the square that the rook is in. (Since we are again being computer programmers instead of normal people, these rows and columns are numbered from 0 to n - 1.) A chess rook covers all squares that are in the same row or in the same column as that rook. Given the board size n and the list of rooks on that board, count the number of empty squares that are safe, that is, are not covered by any rook.
Hint: count separately how many rows and columns on the board are safe from any rook. The result is simply the product of these two counts. (Permuting the rows and columns does not change the answer to this question. We can therefore imagine all the safe rows and columns to have been permuted in a way that has all safe squares form a rectangle at the top left corner of the board, and the area of a rectangle is of course the product of its width and height.)
| n | rooks | Expected result |
|---|---|---|
| 10 | [] | 100 |
| 4 | [(2, 3), (0, 1)] | 4 |
| 8 | [(1, 1), (3, 5), (7, 0), (7, 6)] | 20 |
| 2 | [(1, 1)] | 1 |
| 6 | [(0, 0), (1, 1), (2, 2), (3, 3), (4, 4), (5, 5)] | 0 |
| 100 | [(r, (r*(r-1))%100) for r in range(0, 100, 2)] | 3900 |
| 10**6 | [(r, r) for r in range(10**6)] | 0 |
Try a spatula
1 | def pancake_scramble(text): |
Analogous to flipping a stack of pancakes by sticking a spatula inside the stack and flipping pancakes that rest on top of that spatula, a pancake flip of order k done for the given text string reverses the prefix of first k characters and keeps the rest of the string as it were. For example, the pancake flip of order 2 performed on the string ‘ilkka’ would produce the string ‘likka’ . The pancake flip of order 3 performed on the same string would produce ‘klika’ .
A pancake scramble , as defined in the excellent Wolfram Challenges programming problems site , consists of the sequence of pancake flips of order 2, 3, … , n performed in this exact sequence for the given n -character text string. For example, the pancake scramble done to the string ‘ilkka’ would step through the intermediate results ‘likka’ , ‘kilka’ , ‘klika’ and ‘akilk’ . This function should compute and return the pancake scramble of its parameter text string.
| text | Expected result |
|---|---|
| ‘hello world’ | ‘drwolhel ol’ |
| ‘ilkka’ | ‘akilk’ |
| ‘pancake’ | ‘eanpack’ |
| ‘abcdefghijklmnopqrstuvwxyz’ | ‘zxvtrpnljhfdbacegikmoqsuwy’ |
For those of you who are interested in this sort of stuff, the follow-up question “ How many times you need to pancake scramble the given string to get back the original string? “ is also educational, especially once the strings get so long that the answer needs to be computed analytically (note that the answer depends only on the length of the string but not the content, as long as all characters are distinct) instead of actually performing these scrambles until the original string appears. A more famous problem of pancake sorting asks for the shortest series of pancake flips whose application rearranges the elements of the given list in sorted order.
Words with given shape
1 | def words_with_given_shape(words, shape): |
Let the shape of the given word of length n be a list of n - 1 integers, each one either -1, 0 or +1, indicating whether the next letter following the letter in that position comes later (+1), the same (0) or earlier (-1) in alphabetical order of English letters. For example, the shape of ‘hello’ is [-1, +1, 0, +1] , whereas the shape of ‘world’ is [-1, +1, -1, -1] . Find and return a list of all words that have that particular shape , listed in alphabetical order.
Note that your function, same as all the other functions specified in this document that operate on lists of words, should not itself try to read the wordlist file words_sorted.txt , even when Python makes this possible with just a couple of lines of code. The tester script already reads in the entire wordlist and builds the list of words from there. Your function should use this given list of words without even caring which particular file it came from.
| shape | Expected result (using wordlist words_sorted.txt ) |
|---|---|
| [1, -1, -1, -1, 0, -1] | [‘congeed’, ‘nutseed’, ‘outfeed’, ‘strolld’] |
| [0, 1, -1, 1] | [‘aargh’, ‘eeler’, ‘eemis’, ‘eeten’, ‘oopak’, ‘oozes’, ‘sstor’] |
| [1, 1, 1, 1, 1, 1, 1] | [‘aegilops’] |
Motivated students can take on as an extra challenge for each possible word length n ranging from 3 to 20, find the shape of length n - 1 that matches the largest number of words. Alternatively, try to count how many possible shapes of length n - 1 do not match any words of length n at all. What is the shortest possible shape that does not match any words? How about the shortest such shape that does not contain any zeroes?
Running median of three
1 | def running_median_of_three(items): |
Given a list of items that are all guaranteed to be integers, create and return a new list whose first two elements are the same as they were in original items , after which each element equals the median of the three elements in the original list ending in that position. (If two out of these three elements are equal, then that element is the median of those three.)
| items | Expected result |
|---|---|
| [5, 2, 9, 1, 7, 4, 6, 3, 8] | [5, 2, 5, 2, 7, 4, 6, 4, 6] |
| [1, 2, 3, 4, 5, 6, 7] | [1, 2, 2, 3, 4, 5, 6] |
| [3, 5, 5, 5, 3] | [3, 5, 5, 5, 5] |
| [22, 77] | [22, 77] |
| [42] | [42] |
The card that wins the trick
1 | def winning_card(cards, trump = None): |
Playing cards are again represented as tuples of (rank, suit) as in the cardproblems.py example program. In trick-taking card games such as bridge , the players in turn each play one card from their hand to the trick. The winner of the trick is determined by the following rules:
- If one or more cards of the trump suit have been played to the trick, the trick is won by the highest trump card, regardless of the other cards played.
- If no trump cards have been played to the trick, the trick is won by the highest card of the suit of the first card played to the trick. Cards of any other suits, regardless of their rank, are powerless to win that trick.
- Ace is the highest card in each suit.
Note that the order in which the cards are played to the trick greatly affects the outcome of that trick. Given the list of cards played to the trick, return the card that wins the trick.
| cards | trump | Expected result |
|---|---|---|
| [(‘trey’, ‘spades’), (‘ace’, ‘diamonds’), (‘jack’, ‘spades’), (‘eight’, ‘spades’)] | None | (‘jack’, ‘spades’) |
| [(‘ace’, ‘diamonds’), (‘ace’, ‘hearts’), (‘ace’, |
‘spades’), (‘two’, ‘clubs’)]|’clubs’|(‘two’, ‘clubs’)|
|[(‘two’, ‘clubs’), (‘ace’, ‘diamonds’), (‘ace’, ‘hearts’), (‘ace’, ‘spades’)]|None| (‘two’, ‘clubs’)|
Boustrophedon
1 | def create_zigzag(rows, cols, start = 1): |
This function creates a list of lists that represents a two-dimensional grid with the given number of rows and cols . This grid should contain the integers counting the rows * cols numbers from start in ascending order. However, as in the way that an ox plows a field somewhere back in ancient Greece, the elements of every odd-numbered row must be listed in descending order. However you choose to enforce that discipline is up to you.
In all of the examples of the following table, the keyword parameter start is not given and therefore equals one. But your function must work correctly for arbitrary values of start .
| rows | cols | Expected result |
|---|---|---|
| 3 | 5 | [[1,2,3,4,5], [10,9,8,7,6], [11,12,13,14,15]] |
| 10 | 1 | [[1], [2], [3], [4], [5], [6], [7], [8], [9], [10]] |
| 4 | 2 | [[1,2], [4,3], [5,6], [8,7]] |
Detab
1 | def detab(text, n = 8, sub = ' '): |
In the detabbing process of converting tab characters ‘\t’ to ordinary whitespaces, each tab character is replaced by a suitable number of whitespace characters so that the next character is placed at a position that is exactly divisible by n . However, if the next character is already in a position that is divisible by n , another n whitespace characters are appended to the result so that at least one substitution character will appear to replace any tab character.
For demonstration purposes, since whitespace characters might be difficult to visualize during the debugging stage, the substitution character that fills in the tabs can be freely chosen with the named argument sub that defaults to whitespace. This function should create and return the detabbed version of its parameter text .
| text | n | sub | Expected result |
|---|---|---|---|
| ‘Hello\tthereyou\tworld’ | 8 | ‘$’ | ‘Hello$$$thereyou$$$$$$$$world’ |
| ‘Ilkka\tMarkus\tKokkarinen’ | 4 | ‘-‘ | ‘Ilkka—Markus–Kokkarinen’ |
| ‘Tenser,\tsaid\tthe\ttensor’ | 5 | ‘+’ | ‘Tenser,+++said+the++tensor’ |
People vary greatly on their preference for the value of n , which is why we make it a named argument in this problem. Some people prefer n = 4, others like the wider berth of n = 8, whereas your instructor likes the tight n = 2 best. To each his or her own.
Multidimensional knight moves
1 | def knight_jump(knight, start, end): |
An ordinary chess knight on a two-dimensional board of squares can make an “L-move” into up to eight possible neighbours. However, we can generalize the entire chessboard into k dimensions from our puny two. A natural extension of the knight’s move to keep moves symmetric with respect to these dimensions is to define the possible moves as some k - tuple of strictly decreasing nonnegative integer offsets. Each one of these k offsets must be used for exactly one dimension of your choice during the move, either as a positive or a negative version.
For example, the three-dimensional (4, 3, 1) -knight makes its way by first moving four steps along any one of the three dimensions, then three steps along any other dimension, and then one step along the remaining dimension, whichever of the original three that was. Once the knight has stepped along some dimension, it can no longer step along that same dimension within the same move. These steps are considered to be performed together as a single jump that does not visit or is blocked by any of the intermediate squares. Given the start and end positions as k - tuples of integer coordinates, determine whether the knight can get from start to end in one jump.
| knight | start | end | Expected result |
|---|---|---|---|
| (2, 1) | (12, 10) | (11, 12) | True |
| (7, 5, 1) | (15, 11, 16) | (8, 12, 11) | True |
| (9, 7, 6, 5, 1) | (19, 12, 14, 11, 20) | (24, 3, 20, 11, 13) | False |
A quick combinatorial calculation reveals that exactly k ! 2 k possible neighbours are reachable in a single move, assuming that none of these moves takes the knight outside the board. In this notation, the ordinary chess knight is a (2, 1) -knight that can reach 2! 2 2 = 2 4 = 8 possible neighbouring squares in one jump. A 6-dimensional knight reaches a whopping 6! 2 6 = 46080 different neighbours in one jump. Since the number of moves emanating from each position to its neighbours grows exponentially with respect to k , pretty much everything ends up being close to pretty much everything else in high-dimensional spaces. (Density in general is known to have both advantages and disadvantages in all walks of life.)
Fulcrum
1 | def can_balance(items): |
Each item in the list of items is now considered to be a physical weight, and therefore guaranteed to be a positive integer. Your task is to find and return a fulcrum position in this list so that when balanced on that position, the total torque of the items to the left of that position equals the total torque of the items to the right of that position. The item on the fulcrum is assumed to be centered symmetrically on both sides, and therefore does not participate in the torque calculation.
As taught in any introductory textbook on physics, the torque of an item with respect to the fulcrum equals its weight times its distance from the fulcrum. If a fulcrum position exists, return that position, otherwise return -1 to indicate that the given items cannot be balanced, at least not without rearranging them. That one, by the way, would be an interesting but a more advanced problem normally suitable for a third year computer science course… but in Python, this algorithm could easily be built around this function by using the generator permutations in the module itertools to try out all possible permutations in an outer loop until you find one permutation that works. (In fact, quite a few problems of this style can be solved with this “ generate and test “ approach without needing the fancy backtracking algorithms from third year and up.)
| items | Expected result |
|---|---|
| [6, 1, 10, 5, 4] | 2 |
| [10, 3, 3, 2, 1] | 1 |
| [7, 3, 4, 2, 9, 7, 4] | -1 |
| [42] | 0 |
Yes, I pretty much wrote this problem only to get to say “fulcrum”. What a cool word. And you know what is another really cool word? “ Phalanx “. That one even seems like something that could be turned into an interesting computational problem about lists of lists… and that’s the crux of that matte.