We have arranged $$n$$ cards on a table so that only the uppermost side of each card is visible. Each card bears two numbers, one on each side. The numbers range from 1 to $$2n$$, and each number appears exactly once on one of the cards. You must choose any number of cards and flip them over, and then add up the $$n$$ numbers now on top. What's the highest sum you can be sure to reach?
The highest number you can be sure to reach is \[ \left\lceil{\frac{1 + 2 + 3 + \cdots + 2n}{2}}\right\rceil = \left\lceil{\frac{n(2n + 1)}{2}}\right\rceil \] If the sum of the visible numbers on the uppermost side of each card is greater than or equal to this value, you should accept the cards as they are. Otherwise, you should flip all $$n$$ cards.
Since you don't know how the invisible numbers are distributed across the bottom of the cards, worst case this might be the best that you can do. For example, suppose $$n=50$$ and the cards show the numbers 26 to 75, totalling \[ 26 + 27 + \cdots + 75 = 2525 = \frac{1 + 2 + 3 + \cdots + 100}{2} \] Assume that the $$k$$ cards you flip over are the first $$k$$ cards in the sequence $$1, 2, \ldots, 25, 76, 77, \ldots, 100$$. If you flip over fewer than 26 cards, the sum will gradually decrease further below 2525. But if you flip over more than that, the sum will start to rise again from the 26th card onwards, but will reach 2525 only with the 50th card. Either way, you won't beat the total.
A card bearing two numbers — one on each side of the card — is represented as a tuple with two numbers (int): the first is the visible number at the top of the card and the second is the invisible number at the bottom of the card. A sequence of cards is represented as a list of cards (tuple) bearing two numbers.
Your task:
Write a function visible that takes a sequence (list) of cards (tuple). The function must return the sum of all numbers that are visible on top of the cards in the given sequence.
Write a function maximum that takes a sequence (list) of cards (tuple). The function must return the sum obtained by taking, for each card in the given sequence, the largest number on either side of the card.
Write a function flip that takes a sequence (list) of cards (tuple). The function has a second optional parameter selection that may take a sequence (list or tuple) of numbers (int). All numbers in the sequence passed to the parameter selection must be visible at the top of at least one card in the given sequence of cards. If this is not the case, then the function may not modify the sequence of cards and must raise an AssertionError with the message invalid selection. Otherwise, the function must flip all cards in the given sequence for which the number at the top of the card appears in the sequence passed to the parameter selection, without the function returning anything. If no argument is explicitly passed to the parameter selection, the function must flip all cards in the given sequence of cards.
Write a function isvalid that takes a sequence (list) of $$n$$ cards (tuple). The function must return a Boolean value (bool) that indicates if each number in the range from 1 to $$2n$$ (limits included) occurs exactly once on either side of the cards in the given sequence of cards.
Write a function generate_cards that takes an integer $$n \in \mathbb{N}$$ (int). The function must return a sequence (list) with $$n$$ cards (tuple), bearing each number in the range from 1 to $$2n$$ (limits included) exactly once on either side of the cards. The numbers must be arranged randomly across the cards.
>>> cards = [(5, 9), (6, 10), (2, 7), (1, 8), (4, 3)]
>>> visible(cards)
18
>>> maximum(cards)
38
>>> flip(cards)
>>> cards
[(9, 5), (10, 6), (7, 2), (8, 1), (3, 4)]
>>> visible(cards)
37
>>> flip(cards, [3])
>>> cards
[(9, 5), (10, 6), (7, 2), (8, 1), (4, 3)]
>>> visible(cards)
38
>>> flip(cards, [1])
Traceback (most recent call last):
AssertionError: invalid selection
>>> cards
[(9, 5), (10, 6), (7, 2), (8, 1), (4, 3)]
>>> flip(cards, (9, 10, 2))
Traceback (most recent call last):
AssertionError: invalid selection
>>> cards
[(9, 5), (10, 6), (7, 2), (8, 1), (4, 3)]
>>> flip(cards, (4, 7, 9))
>>> cards
[(5, 9), (10, 6), (2, 7), (8, 1), (3, 4)]
>>> visible(cards)
28
>>> isvalid(cards)
True
>>> isvalid([(5, 9), (10, 6), (8, 1), (3, 4)])
False
>>> isvalid([(5, 9), (10, 6), (9, 7), (8, 1), (3, 4)]) # twice 9, no 2
False
>>> generate_cards(5)
[(9, 5), (8, 1), (2, 3), (6, 4), (7, 10)]
>>> generate_cards(5)
[(2, 3), (4, 1), (7, 8), (9, 10), (6, 5)]