完成Python基础算法和数据结构练习。
Longest palindrome substring
1 | 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
1 | 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
1 | 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
1 | 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
1 | 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
1 | 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
1 | 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?
1 | 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
1 | 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
1 | 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.