# Arup Guha
# 7/16/2026
# Code to Verify COT 3100 H7 Problem 8 result

# Change this flag to True if you want to see all 178 strings...
global PRINTIT
PRINTIT = False

def go(curS, limit):

    # We're done print it and return.
    if len(curS) == limit:

        if PRINTIT:
            print(curS)
        return 1

    # If len less than 2, we can add either letter.
    if len(curS) < 2:
        return go(curS+"H",limit)+go(curS+"T",limit)

    # Need to switch the letter.
    if curS[-1] == curS[-2]:
        if curS[-1] == 'H':
            return go(curS+"T",limit)
        return go(curS+"H",limit)

    # Both will work.
    return go(curS+"H",limit)+go(curS+"T",limit)

# n is the length of the total sequence. We are counting
# the number of binary strings of n bits that do NOT have
# 3 0s or 3 1s in a row.
def bitwise(n):

    res = 0
    
    # Go through all of the bitmasks.
    for mask in range(1<<n):

        ok = True
        
        # Loop through isolating each set of 3 consecutive bits.
        for i in range(n-2):
            tmp = (mask>>i)&7

            # 000 and 111, so 0 and 7 are disallowed.
            if tmp == 0 or tmp == 7:
                ok = False
                break

        # Count it, if it works.
        if ok:
            res+=1

    # Ta da!
    return res

# Run both.
print("recursive result = ",go("", 10))
print("iterative result = ", bitwise(10))