Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Flip coin conundrum for any length
#!/usr/bin/env python
import random
import unittest
# 0 = Head, 1 = Tail
def start_flipping_coin(target, saved):
return flip_until(target, 0, 0, saved)
def flip_coin():
return random.randint(0, 1)
# This is curcial part, doesn't mean you just go back one step.
# Because it assumes you are tossing the coin consecutively.
# So, if the your target is {H,T} or {T,H}, then
# If the second toss is not correct, you will still continue with the 2nd toss.
# If the target size is 3, it will be totally different.
def match_saved(target, saved, length):
if length == 0:
return 0
# It should match the maximal length start from beginning of the target
for i in range(len(target), 0, -1):
if target[:i] == saved[len(saved) - i:]:
return i
return match_saved(target, saved, length - 1)
def flip_until(target, step, count, saved):
if step >= len(target):
return count
coin = flip_coin()
count += 1
saved.append(coin)
if target[step] == coin:
step += 1
else:
step = match_saved(target, saved, len(saved))
return flip_until(target, step, count, saved)
def main():
target1 = [0, 1]
target2 = [0, 0]
target3 = [0, 0, 1]
target4 = [0, 1, 0]
total_turns = 10000
tossed1 = 0
coins1 = []
tossed2 = 0
coins2 = []
tossed3 = 0
coins3 = []
tossed4 = 0
coins4 = []
for i in range(total_turns):
tossed1 += start_flipping_coin(target1, coins1)
if coins1[-len(target1):] != target1:
print("Error1!") # This is a check to make sure the coin set is correct
coins1 = []
tossed2 += start_flipping_coin(target2, coins2)
if coins2[-len(target2):] != target2:
print("Error2!")
coins2 = []
tossed3 += start_flipping_coin(target3, coins3)
if coins3[-len(target3):] != target3:
print("Error3!")
coins3 = []
tossed4 += start_flipping_coin(target4, coins4)
if coins4[-len(target4):] != target4:
print("Error4!")
coins4 = []
print("Result:")
print("Target: {} average steps = {}".format(target1, tossed1 / total_turns))
print("Target: {} average steps = {}".format(target2, tossed2 / total_turns))
print("Target: {} average steps = {}".format(target3, tossed3 / total_turns))
print("Target: {} average steps = {}".format(target4, tossed4 / total_turns))
class TestFunction(unittest.TestCase):
def test1(self):
target = [1, 0, 1]
saved = [1, 0, 1]
step = match_saved(target, saved, len(saved))
self.assertEqual(step, 3)
def test2(self):
target = [1, 0, 1]
saved = [1, 0]
step = match_saved(target, saved, len(saved))
self.assertEqual(step, 2)
def test3(self):
target = [1, 0, 1]
saved = [0, 1, 0]
step = match_saved(target, saved, len(saved))
self.assertEqual(step, 2)
def test4(self):
target = [1, 0, 1]
saved = [1, 1]
step = match_saved(target, saved, len(saved))
self.assertEqual(step, 1)
def test5(self):
target = [1, 0, 1]
saved = [0, 1]
step = match_saved(target, saved, len(saved))
self.assertEqual(step, 1)
def test6(self):
target = [1, 0, 1]
saved = [0, 0, 0, 1]
step = match_saved(target, saved, len(saved))
self.assertEqual(step, 1)
def test7(self):
target = [1, 0, 1]
saved = [0, 0, 0, 1, 0]
step = match_saved(target, saved, len(saved))
self.assertEqual(step, 2)
# unittest.main()
main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.