Flip coin conundrum for any length

robust_flip_coin.py

#!/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()