完成Python基础算法和数据结构练习。
Longest palindrome substring
def longest_palindrome(text):
—|—
A string is said to be a palindrome if it reads the same both forward and
backward, for example ‘racecar’ . Given text , find and return the longest
consecutive substring inside text that is a palindrome. If there exist
multiple palindromes with the same largest possible length, return the
leftmost one.
Note that since you are looking for the longest palindrome, of course you
should loop through these substrings in descending order of length, and the
substrings of same length should be looped through left to right. This way you
can simply return the first palindrome substring that you find, safe in the
knowledge that the text does not contain any longer palindromic substrings.
| text | Expected result |
|---|---|
| ‘saippuakauppias’ | ‘saippuakauppias’ |
| ‘abaababaaabbabaababababaa’ | ‘aababababaa’ |
| ‘xxzxxracecar’ | ‘racecar’ |
| ‘xyxracecaryxy’ | ‘racecar’ |
| The straightforward implementation of the trivial algorithm “loop through all | |
| possible substrings and check which ones are palindromes, remembering the | |
| longest palindrome that you have seen” should pass the test in a reasonably | |
| short time. However, as a curiosity, the real challenge in this problem is | |
| making this function at least an order of magnitude faster than this, which is | |
| why you might meet this one in a later course on algorithmic techniques. The | |
| students who are already piqued in this kind of algorithmic tweaking might | |
| want to check out the Wikipedia page “ Longest Palindromic Substring “, as the | |
| dynamic programming technique used to solve this problem is a key to solving a | |
| thousand other problems of similar combinatorial nature of overlapping | |
| recursive subproblems. |
All your fractions are belong to base
def group_and_skip(n, out, ins):
—|—
A pile of n identical coins lies on the table. In each move, the remaining
coins are grouped into exactly out coins in each group, where out is
guaranteed to be a positive integer greater than one. The n % out leftover
coins that do not fit into any group are taken aside and recorded. From each
complete group of out coins, exactly ins coins are added back in the pile, and
the rest of the coins of that group are discarded. Repeat this until the
entire pile becomes empty, which must eventually happen whenever out > ins
. Return a list that says how many coins were taken aside in each step.
| n | out | ins | Expected result |
|---|---|---|---|
| 123456789 | 10 | 1 | [9, 8, 7, 6, 5, 4, 3, 2, 1] |
| 987654321 | 1000 | 1 | [321, 654, 987] |
| 255 | 2 | 1 | [1, 1, 1, 1, 1, 1, 1, 1] |
| 81 | 5 | 3 | [1, 3, 2, 0, 4, 3] |
| 10**9 | 13 | 3 | [12, 1, 2, 0, 7, 9, 8, 11, 6, 8, 10, 5, 8, 3] |
| As seen in the first three rows, this method produces the digits of n in base | |||
| out in reverse order. So this entire setup turns out to be the cleverly | |||
| disguised algorithm to construct the representation of integer n in base out . | |||
| However, an improvement over the standard algorithm for the integer base | |||
| conversion is that this version works not only for integer bases, but allows | |||
any fraction out/ins that satisfies out > ins and gcd(out, ins) == 1 |
|||
| to be used as a base! For example, the familiar integer 42 would be written as | |||
| 323122 in base 4/3. | |||
| (Yes, fractional bases are an actual thing. Take a deep breath to think about | |||
| the implications, and then imagine trying to do your real world basic | |||
| arithmetic in such a system. That sure would have been some “New Math” for the | |||
| frustrated parents in the sixties who already found it exasperating enough to | |||
| balance their checkbooks just in our familiar base ten!) |
Last man standing
def josephus(n, k):
—|—
In the ancient times back “ when men were made of iron and their ships were
made of wood “, as seen in “300”, “Spartacus”, “Game of Thrones” and similar
historical docudramas of swords and sandals, a group of zealots (yes,
literally ) was surrounded by the overwhelming Roman enemy. To avoid capture
and slow humiliating death by crucifixion, in their righteous zeal these men
chose to commit mass suicide in a way that prevented any one of them from
changing his mind. The zealots arranged themselves in a circle and used lots
to choose a step size k . Starting from the first man, they repeatedly count k
men ahead and quickly kill that man, removing his corpse from the grim circle.
(Being normal people instead of computer scientists, they always start
counting from one instead of zero, the concept of which didn’t even exist for
them back then anyway!) This continues until only one man remains, expected to
honorably fall on his own sword and join his fallen brothers. Josephus would
very much prefer to be this last man since he has other ideas of surviving.
Help him and his secret confederate survive with a function that, given n and
k , returns the list of the execution order so that these men know which
places let them be the last two survivors to walk away from this grim circle.
| n | k | Expected result |
|---|---|---|
| 4 | 1 | [1, 2, 3, 4] |
| 4 | 2 | [2, 4, 3, 1] |
| 10 | 3 | [3, 6, 9, 2, 7, 1, 8, 5, 10, 4] |
| 8 | 7 | [7, 6, 8, 2, 5, 1, 3, 4] |
Recamn’s sequence
def recaman(n):
—|—
Compute and return the first n terms of the Recamn’s sequence , starting from
the term a1 = 1. See the linked definition for this sequence as it is defined
on Wolfram Mathworld . Note how this definition depends on whether a
particular number is already part of the previously generated part of the
sequence.
To make your function execute in a speedy fashion even when generating a
sequence that contains millions of elements, you should use a set to remember
which values are already part of the previously generated sequence. This way
you can generate each element in constant time instead of having to iterate
through the entire previously generated list like some “ Shlemiel “ would have
done. Your better technique can create this list arbitrarily far in linear
time, and should therefore be blazingly fast even for millions of elements.
| n | Expected result |
|---|---|
| 10 | [1, 3, 6, 2, 7, 13, 20, 12, 21, 11] |
Blocks in pyramid
def pyramid_blocks(n, m, h):
—|—
A solid pyramid structure (although here in the ancient Mesoamerican than the
more famous ancient Egyptian style) is built from layers, each layer
consisting of a rectangle of identical cubic blocks. The top layer of the
pyramid consists of n rows and m columns of such blocks, with n * m blocks in
that layer. The layer immediately below each layer contains one more row and
one more column, all the way to the bottom layer of the pyramid. If the entire
pyramid consists of h such layers, how many blocks does this pyramid contain
in total?
This problem could be solved in a straightforward brute force fashion by
simply looping through the h layers and adding up all the blocks along the way
in each layer. With the current version of the automated tester, solving the
test cases would take roughly one minute to complete, since all of these three
arguments can get pretty big. However, with the application of some sums and
discrete math can come up with an analytical closed form formula for the
result and compute the answers much faster that way. If you have taken such
courses, you might want to derive this formula yourself (note that the correct
formula is necessarily symmetric with respect to n and m ), or use the
resources on the Internet to find out how to solve the summation formula.
| n | m | h | Expected result |
|---|---|---|---|
| 2 | 3 | 1 | 6 |
| 2 | 3 | 10 | 570 |
| 10 | 11 | 12 | 3212 |
| 100 | 100 | 100 | 2318350 |
| 10**6 | 10**6 | 10**6 | 2333331833333500000 |
Count growlers
def count_growlers(animals):
—|—
Let the strings ‘cat’ and ‘dog’ denote that kind of animal facing left, and
‘tac’ and ‘god’ denote that same kind of animal facing right. Each individual
animal, regardless of its own species, growls if it sees more dogs than cats
to the direction that the animal is facing. Given a list of such animals ,
return the count of how many of them are growling.
| animals | Expected result |
|---|---|
| [‘cat’, ‘dog’] | 0 |
| [‘god’, ‘cat’, ‘cat’, ‘tac’, ‘tac’, ‘dog’, ‘cat’, ‘god’] | 2 |
| I admit that I was pretty high when I originally thought up this problem, at | |
| least high enough to perceive the letter ‘t’ as a tail of a happy cat held up | |
| high, and ‘d’ as the snout and stand-up ears of a curious dog, perhaps some | |
| kind of spitz or a similar breed. Yeah, good luck trying to unsee that now. | |
| And yet for some reason, this problem is somehow more tricky than it would | |
| initially seem in a fair, predictable and just world, and does not seem to | |
| conveniently adapt to clean and Pythonic solutions. |
Bulgarian solitaire
def bulgarian_solitaire(piles, k):
—|—
You are given a row of piles of pebbles and a positive integer k so that the
total number of pebbles in these piles equals k*(k+1)//2 , a formula that
just so happens to equal the sum of all positive integers from 1 to k . An apt
metaphor for the bleak daily life behind the Iron Curtain, all pebbles are
identical and you don’t have any choice in the moves. Each move must pick up
exactly one pebble from every pile (even if doing so makes that pile
disappear), and create a new pile from these collected pebbles. For example,
starting with piles = [7, 4, 2, 1, 1] , the first move would turn this into
[6, 3, 1, 5] . The next move turns this into [5, 2, 4, 4] , which then turns
into [4, 1, 3, 3, 4] , and so on.
This function should count how many moves are needed to convert the given
initial piles into the goal state where each number from 1 to k appears as the
size of exactly one pile , and return that count. These numbers from 1 to k
may appear in any order inside the list, not necessarily sorted. Note that
applying the basic move to this goal state simply loops back to that same
configuration. (In mathematical lingo, this goal state is a fixed point of the
transformation function between these configurations of pebbles.)
| piles | k | Expected result |
|---|---|---|
| [1, 4, 3, 2] | 4 | 0 |
| [8, 3, 3, 1] | 5 | 9 |
| [10, 10, 10, 10, 10, 5] | 10 | 74 |
| [3000, 2050] | 100 | 7325 |
| [2*i-1 for i in range(171, 0, -2)] | 171 | 28418 |
| This problem was inspired by Martin Gardner column “Bulgarian Solitaire and | ||
| Other Seemingly Endless Tasks” where it was used as an example of a while-loop | ||
| where it is not immediately obvious that this loop will always eventually | ||
reach its goal and terminate, analogous to the Collatz 3x + 1 problem we |
||
| saw back in the class example mathproblems.py . However, a combinatorial proof | ||
| establishes that this one move can never get stuck, but will reach the goal | ||
state from any starting configuration after at most k(k-1)/2 steps. |
Scylla or Charybdis?
def scylla_or_charybdis(moves, n):
—|—
This problem was inspired by the article “ A Magical Answer to the 80-Year-Old
Puzzle “ in Quanta Magazine . Thanks to your cunning, your nemesis in life is
trapped inside a devious game where, for a refreshing change from the usual
way of things, you get to be the Final Boss. (Everyone is the hero in their
own story until they become a villain in somebody else’s, after all.) This
final level consists of a one-dimensional video game platform that reaches
safely n-1 steps from its center to both directions. Your two new lethal
friends Scylla and Charybdis are waiting in anticipation at each end of this
platform, at the distance n steps away from its center.
Your nemesis starts at the center of this platform, and must immediately
commit to her entire sequence of future moves , given to your function as a
string made of characters ‘+’ (“ just a step to the ri-i-i-i-ight”) and ‘-‘
(move one step to the left). Of course your nemesis will choose some series of
moves that keeps her safely on the platform. Your adversarial task is to find
a positive integer k so that executing every k :th step of moves (so this
subsequence starts from position k-1 and includes every k :th element from
then on) makes your nemesis fall into one of the two possible dooms n steps
away from the center.
This function should find and return the value of k that makes your hated
nemesis fall off the platform in the smallest number of moves, to ensure that
his allies who by now have surely become aware of his predicament won’t have
time to come rescue him. To ensure the existence of some solution, the given
sequence of moves is guaranteed to end with the suffix of 2 n consecutive
steps to the right, so k=1 will always work whenever no larger step size leads
to the faster doom. If several values of k work equally well, your function
should return the smallest such k .
| moves | n | Expected result |
|---|---|---|
| ‘-++–++-++++’ | 2 | 3 |
| ‘–++++—+-++-+++++++++++’ | 5 | 5 |
| ‘+-++—+-+-++-+++—-+++-++-+—+–++++++++++’ | 5 | 7 |
Arithmetic progression
def arithmetic_progression(items):
—|—
An arithmetic progression is a numerical sequence so that the stride between
each two consecutive elements is constant throughout the sequence. For
example, [4, 8, 12, 16, 20] is an arithmetic progression of length 5, starting
from the value 4 with a stride of 4.
Given a non-empty list items of positive integers in strictly ascending order,
find and return the longest arithmetic progression whose all values exist
somewhere in that sequence. Return the answer as a tuple (start, stride, n) of
the values that define the progression. To ensure that the answer is unique
for automated testing, if there exist several progressions of the same length,
return the one with the smallest start . If there exist several progressions
of equal length from the same start , return the progression with the smallest
stride .
| items | Expected result |
|---|---|
| [42] | (42, 0, 1) |
| [2, 4, 6, 7, 8, 12, 17] | (2, 2, 4) |
| [1, 2, 36, 49, 50, 70, 75, 98, 104, 138, 146, 148, 172, 206, 221, 240, 274, | |
| 294, 367, 440] | (2, 34, 9) |
| range(1000000) | (0, 1, 1000000) |
Tukey’s ninther
def tukeys_ninthers(items):
—|—
Back in the day when computers were far slower and had a lot less RAM for our
programs to burrow into, special techniques were necessary to achieve many
things that are trivial today with a couple of lines of code . In this spirit,
“ Tukey’s ninther “ is an approximation algorithm from the seventies to
quickly find something reasonably close to the median element of the given
unsorted list. For the purposes of this problem, the median element of the
list is defined to be the element that would end up in the middle position
after that list is sorted, making this median unique regardless of the
elements and their multiplicities. Note again that your code is not asked to
find the actual median of the list, but find the element that Tukey’s ninther
algorithm would return as the quick approximation of the median.
Tukey’s algorithm splits the list into triplets of three elements, and finds
the median element for each triplet. These medians-of-three are collected into
a new list that this same operation is applied to, until only one element
remains. For simplicity, your function can assume that the length of items is
always some power of three. In the following table, each row contains the list
produced by applying one round of Tukey’s algorithm to the list in the next
row.
| items | Expected result |
|---|---|
| [15] | 15 |
| [42, 7, 15] | 15 |
| [99, 42, 17, 7, 1, 9, 12, 77, 15] | 15 |
| Tukey’s algorithm for approximating the median element is extremely robust , | |
| as can be appreciated by giving it a whole bunch of randomly shuffled lists of | |
| distinct numbers to operate on (these distinct numbers can come from arbitrary | |
| distributions and scales, since this algorithm is comparison-based with no | |
| arithmetic between elements), and plotting the histogram of results to admire | |
| how heavily centered around the actual median this distribution ends up being. | |
| (For example, the median of the last example list in the above table is really | |
| 15, pinky swear for grownup realsies.) Even better, if all items are distinct | |
| and the length of the list is some power of three, the approximate median can | |
| never be from the true top or bottom third of the sorted elements, thus | |
| eliminating all risk of accidentally using some funky outlier as your median. |
