完成Python基础算法和数据结构练习。
An unordinary ordering of ordinals
1 | def sort_by_digit_count(items): |
Sorting can be done using arbitrary comparison criteria, as long as they satisfy the mathematical requirements of a total ordering relation. To play around with this concept, let us define a wacky ordering comparison of positive integers so that for any two integers, the one that contains the digit 9 more times than the other is considered to be larger, regardless of the magnitude and other digits of these numbers. For example, 99 > 12345678987654321 > 10^1000 in this ordering. If both integers contain the digit 9 the same number of times, the comparison proceeds to the next lower digit 8, and so on, until the first distinguishing digit has been discovered. If both integers contain every digit from 9 to 0 pairwise the same number of times, the ordinary integer order comparison will determine their mutual ordering.
| items | Expected result |
|---|---|
| [9876, 19, 4321, 99, 73, 241, 111111, 563, 33] | [111111, 33, 241, 4321, 563, 73, 19, 9876, 99] |
| [111, 19, 919, 1199, 911, 999] | [111, 19, 911, 919, 1199, 999] |
| [1234, 4321, 3214, 2413] | [1234, 2413, 3214, 4321] |
As will be explained in the discrete math course, the above relation is transitive and antisymmetric, and therefore a completely legal ordering relation for integers. Outside its entertainment valu it is very nearly useless, though, since it is hard to imagine any useful integer arithmetic operation that would preserve equal values as equals under our wacky equivalence. The ordinary ordering for ordinals (how is that for a name for a hipster indie band?) that we unthinkingly take as some sort of law of nature is useful because it is compatible with useful arithmetic operations in the previous sense, and makes these operations therefore immensely more powerful.
Count divisibles in range
1 | def count_divisibles_in_range(start, end, n): |
Let us take a breather and tackle a problem so simple that its solution needs only a couple of conditions, but not even any loops, let alone anything even more fancy. The difficulty is coming up with the conditions that cover all possible cases of this problem exactly right, including all of the potentially tricksy edge and corner cases , without being off-by-one . Given three integers start , end and n so that start <= end , count and return how many integers between start and end , inclusive, are divisible by n . Sure, you could solve this problem with the list comprehension1
return len([x for x in range(start, end+1) if x % n == 0])
but of course the automated tester is designed so that anybody trying to solve this problem in such a blunt and brutish way will soon run out of both time and space! So you should use no loops but integer arithmetic and conditional statements only, and be careful with various edge cases and off-by-one pitfalls lurking in the bushes. Note that either start or end can be negative or zero, but n is guaranteed to be greater than zero.
| start | end | n | Expected result |
|---|---|---|---|
| 7 | 28 | 4 | 6 |
| -77 | 19 | 10 | 9 |
| -19 | -13 | 10 | 0 |
| 1 | 10**12 - 1 | 5 | 199999999999 |
| 0 | 10**12 - 1 | 5 | 200000000000 |
| 0 | 10**12 | 5 | 200000000001 |
| -10**12 | 10**12 | 12345 | 162008911 |
Bridge hand shape
1 | def bridge_hand_shape(hand): |
In the card game of bridge , each player receives a hand of exactly thirteen cards. The shape of the hand is the distribution of these cards into the four suits in the exact order of spades, hearts, diamonds, and clubs. Given a bridge hand encoded as in the example script cardproblems.py , return the list of these four numbers. For example, given a hand that contains five spades, no hearts, five diamonds and three clubs, this function should return [5, 0, 5, 3] . Note that the cards in hand can be given to your function in any order, since in this question the player has not yet manually sorted his hand. Your answer still has to list all four suits in their canonical order, so that other players will also know what you are talking about.
| hand | Expected result |
|---|---|
| [(‘eight’, ‘spades’), (‘king’, ‘diamonds’), (‘ten’, ‘diamonds’), (‘trey’, ‘diamonds’), (‘seven’, ‘spades’), (‘five’, ‘diamonds’), (‘two’, ‘hearts’), (‘king’, ‘spades’), (‘jack’, ‘spades’), (‘ten’, ‘clubs’), (‘ace’, ‘clubs’), (‘six’, ‘diamonds’), (‘trey’, ‘hearts’)] | [4, 2, 5, 2] |
| [(‘ace’, ‘spades’), (‘six’, ‘hearts’), (‘nine’, ‘spades’), (‘nine’, ‘diamonds’), (‘ace’, ‘diamonds’), (‘trey’, ‘diamonds’), (‘five’, ‘spades’), (‘four’, ‘hearts’), (‘trey’, ‘spades’), (‘seven’, ‘diamonds’), (‘jack’, ‘diamonds’), (‘queen’, ‘spades’), (‘king’, ‘diamonds’)] | [5, 2, 6, 0] |
Milton Work point count
1 | def milton_work_point_count(hand, trump = 'notrump'): |
Playing cards are again represented as tuples of form (rank, suit) as in the cardproblems.py example program. The trick taking power of a bridge hand is estimated with Milton Work point count , of which we shall implement a version that is simple enough for beginners of either Python or the game of bridge. Looking at a bridge hand that consists of thirteen cards, first give it 4 points for each ace, 3 points for each king, 2 points for each queen, and 1 point for each jack. That should be simple enough. This raw point count is then adjusted with the following rules:
- If the hand contains one four-card suit and three three-card suits, subtract one point for being flat . (Flat hands rarely play as well as non-flat hands with the same point count.)
- Add 1 point for every suit that has five cards, 2 points for every suit that has six cards, and 3 points for every suit with seven cards or longer. (Shape is power in offense.)
- If the trump suit is anything other than ‘notrump’ , add 5 points for every void (that is, suit without any cards in it) and 3 points for every singleton (that is, a suit with exactly one card) for any other suit than the trump suit. (Voids and singletons are great when you are playing a suit contract, but very bad when you are playing a notrump contract. Being void in the trump suit is, of course, extremely bad in that suit contract!)
| hand | trump | Expected result |
|---|---|---|
| [(‘four’, ‘spades’), (‘five’, ‘spades’), (‘ten’, ‘hearts’), (‘six’, ‘hearts’), (‘queen’, ‘hearts’), (‘jack’, ‘hearts’), (‘four’, ‘hearts’), (‘two’, ‘hearts’), (‘trey’, ‘diamonds’), (‘seven’, ‘diamonds’), (‘four’, ‘diamonds’), (‘two’, ‘diamonds’), (‘four’, ‘clubs’)] | ‘diamonds’ | 8 |
| [(‘trey’, ‘spades’), (‘queen’, ‘hearts’), (‘jack’, ‘hearts’), (‘eight’, ‘hearts’), (‘six’, ‘diamonds’), (‘nine’, ‘diamonds’), (‘jack’, ‘diamonds’), (‘ace’, ‘diamonds’), (‘nine’, ‘clubs’), (‘king’, ‘clubs’), (‘jack’, ‘clubs’), (‘five’, ‘clubs’), (‘ace’, ‘clubs’)] | ‘clubs’ | 20 |
| [(‘trey’, ‘spades’), (‘seven’, ‘spades’), (‘two’, ‘spades’), (‘trey’, ‘hearts’), (‘queen’, ‘hearts’), (‘nine’, ‘hearts’), (‘ten’, ‘diamonds’), (‘six’, ‘diamonds’), (‘queen’, ‘diamonds’), (‘ace’, ‘diamonds’), (‘nine’, ‘clubs’), (‘four’, ‘clubs’), (‘five’, ‘clubs’)] | ‘notrump’ | 7 |
Next higher zigzag
1 | def next_zigzag(n): |
The definition of zigzag numbers is exactly the same as in the earlier problem that asked you to identify whether the given number is a zigzag number. In this problem, the function is given a positive integer n that is guaranteed to be a zigzag number . This function should return a positive integer m > n that is the next higher zigzag number so that none of the numbers strictly between n and m is a zigzag number.
This problem could in principle be solved by counting up from n+1 and using your earlier is_zigzag function to determine whether you have reached the next higher zigzag number. Unfortunately, as you can see in the table below, the gap between two consecutive zigzag numbers can be arbitrarily large, so you need some more analytical approach based on the digit pattern found at the end of the number. Unfortunately, this digit pattern might also be arbitrarily long before it allows you to decide where the next zigzag number lies…
| n | Expected result |
|---|---|
| 801 | 802 |
| 1082845 | 1082846 |
| 92398 | 92401 |
| 27398 | 27450 |
| 89292523198989898 | 89292523230101010 |
Count consecutive summers
1 | def count_consecutive_summers(n): |
Positive integers can be expressed as sums of consecutive positive integers in various ways. For example, 42 can be expressed as such a sum in four different ways: (a) 3 + 4 + 5 + 6 + 7 + 8 + 9, (b) 9 + 10 + 11 + 12, (c) 13 + 14 + 15 and (d) 42. As the last solution (d) shows, any positive integer can always be trivially expressed as a singleton sum that consists of that integer alone. Given a positive integer n , determine how many different ways it can be expressed as a sum of consecutive positive integers, and return that count.
The count of how many different ways a positive integer n can be represented as a sum of consecutive integers is also called its politeness , and can be alternatively computed by counting how many odd divisors that number has. However, note that the linked Wikipedia definition includes only sums that consist of at least two components, so according to their definition, the politeness of 42 equals 3 due to its odd divisors being 3, 7 and 21.
| n | Expected result |
|---|---|
| 42 | 4 |
| 99 | 6 |
| 92 | 2 |
Powers of two are therefore the least polite of all numbers. How would one characterize the “most polite” numbers that allow more ways to represent as sums of consecutive integers than any number less than them?
Hitting integer powers
1 | def hitting_integer_powers(a, b, tolerance = 100): |
The integer powers of the given base such as 7 in the series 7, 49, 393, 2401, 16807, 117649, … quickly become too large to be useful for our daily lives. Outside time and space, all alone with no human mind to watch over them, these sequences of powers probe through the infinite space of positive integers with exponentially increasing gaps that eventually contain entire universes inside them. Python lets us play around with integer powers whose millions of digits make them unimaginable for us and yet its mechanical binary decisions inerrantly probe through and dissect these behemoths that our minds could not begin to visualize.
Except in cases when the prime factors of a and b fit together nicely such as one of these numbers being some power of the other, the iron hand of the Fundamental Theorem of Arithmetic dictates that never the twain shall meet; the integer powers a**pa and b**pb can never be equal for any integer exponents pa and pb . However, in spirit of “close enough for government work”, we consider such powers to “hit” if their absolute difference abs(a**pa - b**bp) multiplied by the desired tolerance is at most equal to the smaller of those two powers. For example, tolerance=100 requires their difference to be at most 1%. (This definition uses no division to keep it accurate for arbitrarily large integers.)
Given the positive integers a and b and your desired tolerance , find and return the tuple of the smallest integer exponents (p1, p2) that satisfy the above requirement.
| a | b | tolerance | Expected result |
|---|---|---|---|
| 2 | 4 | 100 | (2, 1) |
| 2 | 7 | 100 | (73, 26) |
| 3 | 6 | 100 | (137, 84) |
| 4 | 5 | 1000 | (916, 789) |
| 10 | 11 | 1000 | (1107, 1063) |
| 42 | 99 | 100000 | (33896, 27571) |
(This problem was inspired by the Riddler Express problem in the column “ Can you get another haircut already? “ of Riddler , an excellent source of problems of this kind of general spirit.)
Expand positive integer intervals
1 | def expand_intervals(intervals): |
An interval of consecutive positive integers can be succinctly described as a string that contains its first and last value, inclusive, separated by a minus sign. (This problem is restricted to positive integers so that there can be no ambiguity between the minus sign character used as a separator and an actual unary minus sign in front of an integer.) For example, the interval that contains the numbers 5, 6, 7, 8, 9 could be more concisely described as ‘5-9’ . Multiple intervals can be described together by separating their descriptions with commas. An interval that contains only one value is given as only that value.
Given a string that contains one or more such comma-separated interval descriptions, guaranteed to be given in sorted ascending order and never overlap with each other, create and return the list that contains all the integers contained inside these intervals. In solving this problem the same as any other problems, it is always best not to reinvent the wheel, but check out first whether the string objects have useful methods to make your job easier…
| intervals | Expected result |
|---|---|
| ‘’ | [] |
| ‘42’ | [42] |
| ‘4-6,10-12,16’ | [4, 5, 6, 10, 11, 12, 16] |
| ‘1,3-9,12-14,9999’ | [1, 3, 4, 5, 6, 7, 8, 9, 12, 13, 14, 9999] |
Bridge hand shorthand form
1 | def bridge_hand_shorthand(hand): |
In literature on the game of contract bridge , hands are often given in abbreviated form that makes their relevant aspects easier to visualize at a glance. In this abbreviated shorthand form, suits are always listed in the exact order of spades, hearts, diamonds and clubs , so no special symbols are needed to show which suit is which. The ranks in each suit are listed as letters from ‘AKQJ’ for aces and faces , and all spot cards lower than jack are written out as the same letter ‘x’ to indicate that its exact spot value is irrelevant for the play mechanics of that hand. These letters must be listed in descending order of ranks AKQJx . If some suit is void , that is, the hand contains no cards of that suit, that suit is abbreviated with a single minus sign character ‘-‘ . The shorthand forms for the individual suits are separated using single spaces in the result string, without any trailing whitespace.
| hand | Expected result |
|---|---|
| [(‘four’, ‘spades’), (‘five’, ‘spades’), (‘ten’, ‘hearts’), (‘six’, ‘hearts’), (‘queen’, ‘hearts’), (‘jack’, ‘hearts’), (‘four’, ‘hearts’), (‘two’, ‘hearts’), (‘trey’, ‘diamonds’), (‘seven’, ‘diamonds’), (‘four’, ‘diamonds’), (‘two’, ‘diamonds’), (‘four’, ‘clubs’)] | ‘xx QJxxxx xxxx x’ |
| [(‘trey’, ‘spades’), (‘queen’, ‘hearts’), (‘jack’, ‘hearts’), (‘eight’, ‘hearts’), (‘six’, ‘diamonds’), (‘nine’, ‘diamonds’), (‘jack’, ‘diamonds’), (‘ace’, ‘diamonds’), (‘nine’, ‘clubs’), (‘king’, ‘clubs’), (‘jack’, ‘clubs’), (‘five’, ‘clubs’), (‘ace’, ‘clubs’)] | ‘x QJx AJxx AKJxx’ |
| [(‘trey’, ‘spades’), (‘seven’, ‘spades’), (‘two’, ‘spades’), (‘trey’, ‘hearts’), (‘queen’, ‘hearts’), (‘nine’, ‘hearts’), (‘ten’, ‘diamonds’), (‘six’, ‘diamonds’), (‘queen’, ‘diamonds’), (‘ace’, ‘diamonds’), (‘nine’, ‘clubs’), (‘four’, ‘clubs’), (‘five’, ‘clubs’)] | ‘xxx Qxx AQxx xxx’ |
| [(‘ace’, ‘spades’), (‘king’, ‘spades’), (‘queen’, ‘spades’), (‘jack’, ‘spades’), (‘ten’, ‘spades’), (‘nine’, ‘spades’), (‘eight’, ‘spades’), (seven, ‘spades’), (‘six’, ‘spades’), (‘five’, ‘spades’), (‘four’, ‘spades’), (‘trey’, ‘spades’), (‘two’, ‘diamonds’)] | ‘AKQJxxxxxxxx - x -‘ |
(Then again, the author once saw aplay problem where eight was a relevant rank…)
Losing trick count of a bridge hand
1 | def losing_trick_count(hand): |
The Milton Work point count that we saw in the earlier problem is the first baby step in estimating the playing power of a bridge hand. Once the partnership discovers they have a good trump fit, hand evaluation continues more accurately using some system of losing trick count . For example, a small slam in spades with ‘AKxxxxx - Kxxx xx’ and ‘xxxx xxxxx AQx -‘ is a lock despite possessing only 16 of the 40 high card points in the deck, whereas any slam is hopeless with the hands ‘QJxxx xx AKx QJx’ against ‘AKxxx QJ QJx AKx’ despite the combined powerhouse of “quacky” 33 points with horrendous duplication of useful cards.
In this problem, we compute the basic losing trick count as given in step 1 of “ Methodology “ section of the Wikipedia page “ Losing Trick Count “ without any finer refinements. Keep in mind that no suit can have more losers than it has cards, and never more than three losers even if there were ten cards of that suit in their hand! The following dictionary (composed by student Shu Zhu Su during the Fall 2018 term) might also come handy for the combinations whose losing trick count differs from the string length, once you convert each J of the shorthand form into an x :
1 | {'-':0,'A':0,'x':1,'Q':1,'K':1,'AK':0,'AQ':1,'Ax':1,'KQ':1,'Kx':1,'Qx':2,'xx':2, 'AKQ':0, 'AKx':1, 'AQx':1,'Axx':2, 'Kxx':2, 'KQx':1, 'Qxx':2, 'xxx':3} |
| hand | Expected result |
|---|---|
| [(‘ten’, ‘clubs’), (‘two’, ‘clubs’), (‘five’, ‘clubs’), (‘queen’, ‘hearts’), (‘four’, ‘spades’), (‘trey’, ‘spades’), (‘ten’, ‘diamonds’), (‘king’, ‘spades’), (‘five’, ‘diamonds’), (‘nine’, ‘hearts’), (‘ace’, ‘spades’), (‘queen’, ‘spades’), (‘six’, ‘spades’)] | 7 |
| [(‘eight’, ‘hearts’), (‘queen’, ‘spades’), (‘jack’, ‘hearts’), (‘queen’, ‘hearts’), (‘six’, ‘spades’), (‘ten’, ‘hearts’), (‘five’, ‘clubs’), (‘jack’, ‘spades’), (‘five’, ‘diamonds’), (‘queen’, ‘diamonds’), (‘six’, ‘diamonds’), (‘trey’, ‘spades’), (‘nine’, ‘clubs’)] | 8 |