Bulls and cows

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

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

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

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

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

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

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

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

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

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
ttt [‘statute’]
‘asa’ [‘acystia’, ‘acushla’, ‘anosmia’]
ikk* [‘dikkop’, ‘likker’, ‘nikkud’, ‘tikker’, ‘tikkun’