티스토리 뷰
Penney Ante is a gambling game in which two players each name a different sequence of outcomes of coin tosses, where both sequences must have the same length. For example heads-heads-tails, or HHT. Then a coin is flipped repeatedly until one of the sequences appears. The player who named that sequence, wins the game.

Is there any strategy that gives one player a higher probability of winning the game than the other player? Strangely, there is. The famous mathematician John Conway even proposed a beautiful algorithm to compute the probability that one chosen sequence will win against another sequence. We will give an initial explanation of the algorithm for triplets (sequences of length three), but Conway's algorithm is very powerful in that it can be used to compute probabilities for sequences of any length, even for sequences of dissimilar length.
First, we put the two triplets one above the other with their letters aligned, as we've done below for the two triplets THHand HHH. Now we compare the two triplets: if they are the same, put a 1 above the first letter of the first triplet, if not put a 0.
0 THH HHH
Next, remove the first letter from the upper triplet and shift the remaining letters to the left, aligning the leading letters of the two triplets. Then, compare the first two letters of the upper sequence to the first two letters in the lower sequence: if they are the same, place a 1 above the leading letter of the upper sequence, or a 0 otherwise.
1 HH HHH
Repeat this procedure through the last letter of the upper sequence, each time comparing the remaining letters in the upper sequence with the same number of leading letters in the lower sequence (if the lower sequence has fewer letters than the upper sequence, we write a 0 by definition).
1 H HHH
Finally we compile all obtained ones an zeros into a single sequence, which we can represented in the following way:
011 THH HHH
The resulting sequence of zeros and ones is called a bit sequence. Such a bit sequence expresses the amount of overlap between the two sequences of consecutive coin tosses, and can be read as a binary number. In the above example we obtained the bit sequence 011, which is equal to the decimal number 3 when interpreted as a binary number.
Now that we have learned how to determine bit sequences, this gives us a way of working out the odds for two given sequences and . We will write the bit sequence obtained when using sequence both as the upper and lower sequence as , the bit sequence obtained when using sequence as the upper sequence and sequence as the lower sequence as , and so on. The odds in a game of Penney Ante where sequences and compete against each other, are given by the following equations:
where the decimal values of the bit sequences are used in the subtractions at the left hand sides of the equations. If we consider the example where = HHH and = THH, we can first determine the bit sequences:
111 000 A:HHH A:HHH A:HHH B:THH 100 011 B:THH B:THH B:THH A:HHH
Converting these four bit sequences to decimal numbers (the sequence 111 in binary equals 7, the sequence 000 equals 0, the sequence 100 equals 4 and the sequence 011 equals 3) and substituting them into the above equations, we have
So the odds for sequence to win against sequence are . Note that it is uncommon to report the odds themselves. Instead we report the normalized odds that are obtained by dividing and by their greatest common divisor. For example, we do not write the odds as , but as .
If we use for the probability that sequence wins and for the probability that sequence wins, we have
Note that in computing these probabilities, it doesn't matter whether we use the odds or the normalized odds.
Assignment
In this assignment we will represent the outcome of a coin toss using an uppercase letter: H for heads and T for tails. This way we can represent a sequence of outcomes of coin tosses as a string that only contains the letters H and T. Your task:
Write a function winner that takes three string arguments. The first two arguments represent the sequences of outcomes of coin tosses chosen by the two players of a Penney Ante game. The third argument is the sequence of outcomes that was obtained when effectively tossing a coin repeatedly. The function must return the value 1 if the first chosen sequence (first argument) wins the game, the value 2 if the second chosen sequence (second argument) wins the game, and the value 0 if none of the sequences wins because none of them was observed in the sequence of coin tosses passed as the third argument. In case the first two arguments are the same, an AssertionError must be raised with the message sequences cannot be equal. In case the first two arguments do not have the same length, an AssertionError must be raised with the message sequences must have equal length.
Write a function bitsequence that takes two sequences of outcomes of coin tosses and . The function must return a string containing the bit sequence .
Write a function odds that takes two sequences of outcomes of coin tosses and . The function must return a tuple containing the normalized odds in a game of Penney Ante where the two given sequences compete against each other, with .
Tip
In Python you can use the built-in function int to convert the string representation of a binary number into its decimal value. This function has a second optional parameter (default value: 10) that takes the base of the number whose string representation is passed as the first argument to the function.
>>> int('011', 2) 3
Write a function probabilities that takes two sequences of outcomes of coin tosses and . The function must return a tuple containing the probabilities in a game of Penney Ante where the two given sequences compete against each other, with .
The two sequences of outcomes of coin tosses that are passed to the functions bitsequence, odds and probabilities should not necessarily have the same length and can also be the same sequence.
Example
>>> winner('HHH', 'THH', 'HTHTHHHHTHHHTTTTHTHH') 2 >>> winner('THT', 'TTH', 'HTHTHHHHTHHHTTTTHTHH') 1 >>> winner('THH', 'HHT', 'HHHHHHHHHHHHHHHHHHHH') 0 >>> winner('THH', 'THH', 'HHHHHHHHHHHHHHHHHHHH') Traceback (most recent call last): AssertionError: sequences cannot be equal >>> winner('THHT', 'THH', 'HHHHHHHHHHHHHHHHHHHH') Traceback (most recent call last): AssertionError: sequences must have equal length >>> bitsequence('HHH', 'THH') '000' >>> bitsequence('THT', 'TTH') '001' >>> bitsequence('THH', 'HHT') '011' >>> odds('HHH', 'THH') (1, 7) >>> odds('THT', 'TTH') (1, 2) >>> odds('THH', 'HHT') (3, 1) >>> probabilities('HHH', 'THH') (0.125, 0.875) >>> probabilities('THT', 'TTH') (0.3333333333333333, 0.6666666666666666) >>> probabilities('THH', 'HHT') (0.75, 0.25)
def check_equal(a, b):
if len(a) <= len(b):
for i in range(len(a)):
if a[i] != b[i]:
return 0
return 1
return 0
def bitsequence(a, b):
result = ""
for _ in range(len(a)):
result += str(check_equal(a, b))
a = a[1:]
return result
def str_to_binary(string):
return int(string, 2)
def get_gcd(a, b):
mod = a % b
while mod > 0:
a = b
b = mod
mod = a % b
return b
def odds(a, b):
ka = str_to_binary(bitsequence(b, b)) - str_to_binary(bitsequence(b, a))
kb = str_to_binary(bitsequence(a, a)) - str_to_binary(bitsequence(a, b))
if kb == 0:
return (1, 0)
gcd = get_gcd(ka, kb)
if not gcd == 1:
ka /= gcd
kb /= gcd
return (int(ka), int(kb))
def probabilities(a, b):
ka, kb = odds(a, b)
sum = ka + kb
return (float(ka/sum), float(kb/sum))
def check_exception(a, b):
assert a != b, 'sequences cannot be equal'
assert len(a) == len(b), 'sequences must have equal length'
def winner(a, b, c):
check_exception(a, b)
idx_a = c.index(a) if a in c else -1
idx_b = c.index(b) if b in c else -1
multiple = idx_a * idx_b
if idx_a < 0 and idx_b < 0:
return 0
if multiple >= 0:
if idx_a < idx_b:
return 1
return 2
else:
if idx_a > idx_b:
return 1
return 2
'python lecture > algorism' 카테고리의 다른 글
[edu] Transitions and transversions (0) | 2018.10.08 |
---|---|
[edu] Word sums (0) | 2018.10.08 |
[edu] Corkscrew (0) | 2018.10.04 |
[eud] Cowsay (0) | 2018.10.02 |
[edu] Wepe speapeak p (0) | 2018.10.02 |
- Total
- Today
- Yesterday
- 이미지 비교
- virtualenv
- 면접정답
- GIT
- 장고
- 면접답변
- 플러스친구 자동응답
- 장고 플러스친구 자동응답
- gitlab
- 모바일 스킨 적용
- chatbot
- django
- 문서 비교
- 장고 카톡 자동응답
- wsgi
- pycrypto
- PuTTYGen
- 문과 코딩
- gitignore
- Python
- 파이썬 입문
- 파이썬 강좌
- Tistory
- admin.py
- 엑셀 비교
- 파이썬
- 파이썬 프로그래밍
- 모바일 테마 적용
- 파이썬 독학
- django chatbot
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 | 29 |
30 | 31 |