完成Python基础算法和数据结构练习。
An unordinary ordering of ordinals
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
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 comprehension
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
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
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
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
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
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 apa and bpb 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
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
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
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 :
{‘-‘: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 |
