Coin Flip Conundrum

flip_coin.py

#!/usr/bin/env python

import random

# 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 step_back(target, step, coin):
    if target[0] != target[1]:
        if step == 1 and target[0] == coin:
            return 1
        else:
            return 0
    else:
        if step == 0 or target[step] == coin:
            return step
        return step_back(target, step - 1, coin)


def flip_until(target, step, count, saved):
    if step >= len(target):
        return count

    coin = flip_coin()
    count += 1

    if saved is not None:
        saved.append(coin)

    if target[step] == coin:
        step += 1
    else:
        step = step_back(target, step, coin)

    return flip_until(target, step, count, saved)


def main():
    target1 = [0, 1]
    target2 = [0, 0]

    total_turns = 10000
    tossed1 = 0
    coins1 = []
    for i in range(total_turns):
        tossed1 += start_flipping_coin(target1, coins1)
        if coins1[-2:] != target1:
            print("Error1!")  # This is a check to make sure the coin set is correct
        coins1 = []

    tossed2 = 0
    coins2 = []
    for i in range(total_turns):
        tossed2 += start_flipping_coin(target2, coins2)
        if coins2[-2:] != target2:
            print("Error2!")
        coins2 = []

    print("Result:")
    print("Target: {} average steps = {}".format(target1, tossed1 / total_turns))
    print("Target: {} average steps = {}".format(target2, tossed2 / total_turns))


main()