完成Python基础算法和数据结构练习。
Bulls and cows
def bulls_and_cows(guesses):
—|—
In the old two-player game of “ Bulls and Cows “ (reincarnated in the
seventies with pretty colours under the name “ Mastermind “) the first player
thinks up a four-digit secret number whose each digit must be different, for
example 8723 or 9425. (For simplicity, we will not use the digit zero in this
problem.) The second player tries to guess this secret number by repeatedly
guessing a four-digit number. After each guess, the first player reveals how
many “bulls”, the right digit in the right position, and “cows”, the right
digit but in the wrong position, that guess contains. For example, if the
secret number is 1729 , the guess 5791 contains one bull (the digit 7 ) and
two cows (the digits 9 and 1 ). The guess 4385, on the other hand, contains
zero bulls and zero cows.
Given a list of guesses that have been completed, each individual guess given
as a three-tuple (guess, bulls, cows) , this function should return the list
of all four-digit numbers that are consistent with all these guesses, sorted
in ascending order. Note that it is very much possible for the result list to
be empty, if no four-digit integer is consistent with all of the guesses .
(Hint: start by creating a list of all four-digit numbers that do not contain
any repeated digits. Loop through the individual guesses given, and for each
guess, use a list comprehension to create a list of numbers that were in the
previous list and are still consistent with the current guess. After you have
done all that, jolly well then, old chap, “ When you have eliminated all which
is impossible, then whatever remains, however improbable, must be the truth. “
Sherlock Holmes)
| guesses | Expected result |
|---|---|
| [(1234, 2, 2)] | [1243, 1324, 1432, 2134, 3214, 4231] |
| [(8765, 1, 0), (1234, 2, 1)] | [1245, 1263, 1364, 1435, 1724, 1732, 2734, |
| 3264, 4235, 8134, 8214, 8231] | |
| [(1234, 2, 2), (4321, 1, 3)] | [] |
| [(3127, 0, 1), (5723, 1, 0), (7361, 0, 2), (1236, 1, 0)] | [4786, 4796, |
| 8746, 8796, 9746, 9786] | |
| This problem and its myriad generalizations to an exponentially larger number | |
| of possibilities (for example, otherwise the same game but played with English | |
| words ) can be solved in more clever and efficient ways than the above brute | |
| force enumeration, but that will be a topic for a later, more advanced | |
| algorithms course. |
Sort list by element frequency
def frequency_sort(items):
—|—
Sort the given list of integer items so that its elements end up in the order
of decreasing frequency , that is, the number of times that they appear in
items . If two elements occur with the same frequency, they should end up in
the ascending order of their element values with respect to each other, as is
the standard practice in sorting things.
The best way to solve this problem is to “Let George do it”, or whichever way
you wish to put this concept of passing the buck, by having the Python sort
function perform the sorting against custom sorting criterion, as done in the
example script countries.py . Start by creating a dictionary to keep track of
how many times each element occurs inside the array. Then, use these counts
stored in that dictionary as the sorting key of the actual array elements,
breaking ties on the frequency by using the actual element value.
(If you also happen to remember that the order comparison of Python tuples is
lexicographic , you don’t even have to exhaust yourself with the work needed
to break these ties between two equally frequent values…)
| items | Expected result |
|---|---|
| [4, 6, 2, 2, 6, 4, 4, 4] | [4, 4, 4, 4, 2, 2, 6, 6] |
| [4, 6, 1, 2, 2, 1, 1, 6, 1, 1, 6, 4, 4, 1] | [1, 1, 1, 1, 1, 1, 4, 4, 4, 6, |
| 6, 6, 2, 2] | |
| [17, 99, 42] | [17, 42, 99] |
| [‘bob’,’bob’,’carl’,’alex’,’bob’] | [‘bob’,’bob’,’bob’,’alex’,’carl’] |
Calling all units, B-and-E in progress
def is_perfect_power(n):
—|—
A positive integer n is a perfect power if it can be expressed as the power b**e for some two integers b and e that are both greater than one . (Any
positive integer n can always be expressed as the trivial power n**1 , so
we don’t care about those.) For example, the integers 32, 125 and 441 are
perfect powers since they equal 2**5 , 5**3 and 21**2 ,
respectively.
This function should determine whether the given positive integer n is a
perfect power. Your code needs to somehow iterate through a sufficient number
of possible combinations of b and e that could work, returning True right away
when you find some b and e that satisfy b**e == n , and returning False when
all possibilities for b and e have been tried and found wanting. Since n can
get pretty large, your function should not examine too many combinations of b
and e above and beyond those that are both necessary and sufficient to
reliably determine the answer. Achieving this efficiency is the central
educational point of this problem.
| n | Expected result |
|---|---|
| 42 | False |
| 441 | True |
| 469097433 | True |
| 12**34 | True |
| 12**34 - 1 | False |
| The automated tester for this problem is based on the mathematical theorem | |
| about perfect powers that says that after the special case of two consecutive | |
| perfect powers 8 and 9, whenever the positive integer n is a perfect power, | |
| n-1 cannot be a perfect power. This theorem makes it easy to generate | |
| pseudorandom test cases with known answers, both positive and negative. For | |
| example, we would not need to try out all possible ways to express the number | |
| as an integer power to know right away that the behemoth 1234**5678 - 1 is not | |
| a perfect power. |
The MD problem
def md(a, b, n):
—|—
Consider an infinite series that starts with the value 1 at the first position
0, since in this problem we are again wearing the hats of computer scientists
and our counting from zero, instead of starting counting from one like those
dastardly mathematicians. Let v be the most recent element in the sequence. If
the value of the integer division v // a is nonzero and has not appeared
in the sequence so far, the next element of the sequence equals v // a .
Otherwise the next element equals b * v . For example, when trying out
parameter values a = 2 and b = 3 in spirit of the Collatz sequence, this
sequence would start off as [1, 3, 9, 4, 2, 6, 18, 54] .
Whenever the parameters a and b are positive and have no common factors higher
than 1, this sequence can be proven to produce every positive integer exactly
once, the values bouncing up and down in a chaotic spirit again very much
reminiscent of the Collatz sequence. This function should return the position
in the sequence where n makes its appearance.
| a | b | n | Expected result |
|---|---|---|---|
| 2 | 3 | 1 | 0 |
| 2 | 3 | 18 | 6 |
| 3 | 2 | 18 | 20 |
| 3 | 13 | 231 | 181 |
| 2 | 3 | 100000 | 175221 |
| This problem was taken from the page “ Unsolved Problems and Rewards “ by | |||
| Clark Kimberling. The | |||
| “unsolved” part there was proving that every positive integer will appear | |||
| exactly once, but then some guy proved that back in 2004 so that we all can | |||
| just rely on that fact from now on. The goal of object-oriented design and | |||
| programming is for us to become “mathematicians in spirit” so that no problem | |||
| would ever need to be solved twice . Once some thorny problem has been | |||
| successfully solved by somebody, it is sufficient to reduce your current | |||
| problem into that problem to also declare your problem now solved. | |||
| Furthermore, even the same problem can be solved any number of times, instead | |||
| of merely once, by putting a sufficiently strong for-loop around the code that | |||
| can solve it once… |
Collapse positive integer intervals
def collapse_intervals(items):
—|—
This function is the inverse of the earlier question of expanding positive
integer intervals. Given a nonempty list of positive integers that is
guaranteed to be in sorted ascending order, create and return the unique
description string where every maximal sublist of consecutive integers has
been condensed to the notation first-last . If some maximal sublist consists
of a single integer, it must be included in the result string just by itself
without the minus sign separating it from the now redundant last number. Make
sure that the string returned by your function does not contain any whitespace
characters, and does not have a redundant comma in the end.
| items | Expected result |
|---|---|
| [1, 2, 4, 6, 7, 8, 9, 10, 12, 13] | ‘1-2,4,6-10,12-13’ |
| [42] | ‘42’ |
| [3, 5, 6, 7, 9, 11, 12, 13] | ‘3,5-7,9,11-13’ |
| [] | ‘’ |
| range(1, 1000001) | ‘1-1000000’ |
Distribution of abstract bridge hand shapes
def hand_shape_distribution(hands):
—|—
This is a continuation of the earlier “Bridge hand shape” problem that asked
you to compute the shape of one given bridge hand. In that problem, the shapes
[6, 3, 2, 2] and [2, 3, 6, 2] were considered different, as they very much
would be in the actual bidding and play of the hand. However, in this
combinatorial generalized version of this problem, we shall consider two hand
shapes like these two to be the same abstract shape if they are equal when we
care only about the sorted counts of the suits, but don’t care which
particular suits they happen to be.
Given a list of bridge hands , each hand given as a list of 13 cards encoded
the same way as in all of the previous card problems, create and return a
Python dictionary that contains all abstract shapes that occur within hands ,
each shape mapped to its count of occurrences in hands . Note that Python
dictionary keys cannot be lists (Python lists are mutable, and changing the
contents of a dictionary key would break the internal ordering of the
dictionary) so you need to represent the abstract hand shapes as immutable
tuples that can be used as keys inside your dictionary.
As tabulated on “ Suit distributions “ in “ Durango Bill’s Bridge
Probabilities and Combinatorics “, there exist precisely 39 possible abstract
shapes of thirteen cards, the most common of which is 4-4-3-2, followed by the
shape 5-3-3-2. Contrary to intuition, the most balanced possible hand shape
4-3-3-3 turns out to be surprisingly unlikely, trailing behind even the less
balanced shapes 5-4-3-1 and 5-4-2-2 that one might have intuitively assumed to
be far less frequent. ( Understanding why randomness tends to produce variance
rather than converging to complete uniformity is a great aid in understanding
many other counterintuitive truths about the behaviour of random processes in
computer science and mathematics.)
For example, if it were somehow possible to give to your function the list of
all 635,013,559,600 possible bridge hands and not run out of the heap memory
in the Python virtual machine, the returned dictionary would contain 39
entries for the 39 possible hand shapes, two examples of these entries being
(4,3,3,3):66905856160 and (6,5,1,1):4478821776 . (Our automated tester will
try out your function with a much smaller list of pseudo-randomly generated
bridge hands, but at least for the common hand types that you might expect to
see every day at the daily duplicate of the local bridge club, the percentage
proportions really ought not be that different from the exact answers if
measured over a sufficiently large number of random hands.)
Flip of time
def hourglass_flips(glasses, t):
—|—
An hourglass is given as a tuple (u, l) (the second character is the lowercase
letter L , not the digit one) for the number of minutes in the upper and lower
chamber. After m minutes elapse, the state of that hourglass will be
(u-min(u,m), l+min(u,m)) so that the total amount of sand u+l remains constant
inside the same hourglass and neither chamber can ever become negative.
Flipping the hourglass (u, l) produces the hourglass (l, u) , of course.
Given a list of glasses , each of form (u, 0) so that all sand is initially in
the upper chamber, and the amount of time t to be measured, you can only wait
for the first hourglass to run out of time after its u minutes, since any
eyeball estimation of hourglasses during the measurement is not allowed. Once
the time in the chosen hourglass runs out, you may instantaneously flip any
subset of these glasses (note that you don’t have to flip any glasses, not
even the one that just ran out of sand) to continue to measure the remaining
time t-u .
This function should return the smallest possible number of individual
hourglass flips that can exactly measure t minutes, or None if this task is
impossible. The base cases of recursion are when t equals zero or exactly t
minutes remain in some hourglass (no flips are needed), or when t is smaller
than the time remaining in any hourglass (no solution is possible). Otherwise,
wait for the first hourglass to run out after its u minutes, and loop through
all possible subsets of your hourglasses, recursively trying each flipped
subset to best measure the remaining t-u minutes.
| glasses | t | Expected result |
|---|---|---|
| [(7, 0), (11, 0)] | 15 | 2 |
| [(4, 0), (6, 0)] | 11 | None |
| [(7, 0), (4, 0), (11, 0)] | 20 | 3 |
| [(16, 0), (21, 0)] | 36 | 6 |
| [(5, 0), (8, 0), (13, 0)] | 89 | 7 |
| (Hint: the handy generator itertools.product([0, 1], repeat=n) produces all 2 | ||
| n possible n -element tuples made of [0, 1] to represent the possible subsets | ||
| of n individual glasses that will be flipped for the recursive call.) |
Fibonacci sum
def fibonacci_sum(n):
—|—
Fibonacci numbers are a clich in introductory computer science, especially in
teaching recursion where this famous combinatorial series is mainly used to
reinforce the belief that recursion is silly… but all clichs became clichs in
the first place because they were so good that everyone and their brother kept
using them! Let us therefore rather play around with Zeckendorf’s theorem , a
more amazing property of these famous numbers: every positive integer can be
expressed exactly one way as a sum of distinct non-consecutive Fibonacci
numbers .
Once we have proven that some such sum exists, any consecutive Fibonacci
numbers F i and F i + 1 inside that sum can always be replaced by F i +2
without affecting the total. Performing this replacement from the highest term
down guarantees that the term F i + 2 is unused and can be used to replace F i
and F i +1 . Since each such replacement decreases the number of terms inside
the sum by one, this cleanup is guaranteed to terminate after a finite number
of replacements.
The simple greedy algorithm can be proven to always produce the desired
breakdown of n into a sum of distinct non-consecutive Fibonacci numbers:
always add into the list the largest possible
Fibonacci number f that is at most equal to n . Then convert the rest given by
n-f in this same manner, until nothing remains to be converted. To allow for
automated testing, the list of Fibonacci numbers must be returned sorted in
descending order.
| n | Expected result |
|---|---|
| 10 | [8, 2] |
| 100 | [89, 8, 3] |
| 1234567 | [832040, 317811, 75025, 6765, 2584, 233, 89, 13, 5, 2] |
| 10**10 | [7778742049, 1836311903, 267914296, 102334155, 9227465, 3524578, |
| 1346269, 514229, 75025, 6765, 2584, 610, 55, 13, 3, 1] |
Rooks with friends
def rooks_with_friends(n, friends, enemies):
—|—
Those dastardly rooks have once again gone on a rampage on a generalized n -
by- n chessboard, just like in the earlier problem of counting how many
squares were safe from their occupants being pulverized into dust under the
rolling wrath of these lumbering juggernauts. Each rook is again represented
as a tuple (row, column) of the coordinates of the square that it is standing
on.
However, in this version of the problem, some of these rooks are now your
friends (same colour as you) while the others are your enemies (the opposite
colour from you).
Friendly rooks protect the chess squares by standing between them and any
enemy rooks that might want to threaten those squares. An enemy rook can
attack only those squares in the same row or column that do not enjoy the
protection of any friendly rook standing between them. Given the board size n
and the lists of friends and enemies , count how many empty squares on the
board are safe from the enemy rooks.
| n | friends | enemies | Expected result |
|---|---|---|---|
| 4 | [(2,2), (0,1), (3,1)] | [(3,0), (1,2), (2,3)] | 2 |
| 4 | [(3,0), (1,2), (2,3)] | [(2,2), (0,1), (3,1)] | 2 |
| 8 | [(3,3), (4,4)] | [(3,4), (4,3)] | 48 |
Possible words in Hangman
def possible_words(words, pattern):
—|—
Given a list of possible words , and a pattern string that is guaranteed to
contain only lowercase English letters a to z and asterisk characters * ,
create and return a sorted list of words that match the pattern in the sense
of the famous pen-and-paper guessing game of Hangman .
Any pattern can only match words of the exact same length. In all positions
where the pattern contains some letter, the word must contain that same
letter. In positions where the pattern contains an asterisk, the word
character in that position may not be any of the letters that explicitly occur
inside the pattern. (In the game of Hangman, all occurrences of such a letter
would have already been revealed in the earlier round where that letter was
the current guess.)
For example, the words ‘bridge’ and ‘smudge’ both match the pattern ‘ ***dg* ‘ . However, the words ‘grudge’ and ‘ dredge ‘ would not match that same
pattern, since the first asterisk may not be matched with either of the
letters ‘g’ or ‘d’ that appear inside the pattern .
| pattern | Expected result |
|---|---|
| ‘ t t t ‘ | [‘statute’] |
| ‘a s a’ | [‘acystia’, ‘acushla’, ‘anosmia’] |
| ‘ ikk* ‘ | [‘dikkop’, ‘likker’, ‘nikkud’, ‘tikker’, ‘tikkun’ |
