# Programming for the Puzzled -- Srini Devadas
# You Will All Conform
# Input is a vector of F's and B's, in terms of forwards and backwards caps
# Output is a set of commands (printed out) to get either all F's or all B's
# Fewest commands are the goal

caps = ['F', 'F', 'B', 'B', 'B', 'F', 'B', 'B', 'B', 'F', 'F', 'B', 'F']
cap2 = ['F', 'F', 'B', 'B', 'B', 'F', 'B', 'B', 'B', 'F', 'F', 'F', 'F']
cap3 = ['F', 'F', 'B', 'H', 'B', 'F', 'B', 'B', 'B', 'F', 'H', 'F', 'F']


def pleaseConform(caps):
    # Initialization
    start = 0
    forward = 0
    backward = 0
    intervals = []

    # Determine intervals where caps are on in the same direction
    for i in range(1, len(caps) + 1):
        if i >= len(caps) or caps[start] != caps[i]:
            if (caps[start] != 'H'):
                # each interval is a tuple with 3 elements (start, end, type)
                intervals.append((start, i - 1, caps[start]))

                if caps[start] == 'F':
                    forward += 1
                elif caps[start] == 'B':
                    backward += 1
            start = i

    flip = 'F' if forward < backward else 'B'
    for t in intervals:
        if t[2] == flip:
            # Exercise: if t[0] == t[1] change the printing!
            if t[0] == t[1]:
                print('Person at position', t[0], 'flip your cap!')
            else:
                print('People in positions', t[0],
                      'through', t[1], 'flip your caps!')


def pleaseConformOnepass(caps):
    if len(caps) <= 0:
        return
    caps = caps + [caps[0]]
    start = None
    for i in range(1, len(caps)):
        if caps[i] != caps[i-1]:
            if caps[i] != caps[0] and caps[i] != 'H':
                start = i
            elif start is not None and caps[start] != 'H':
                if start == i - 1:
                    print('Person at position', start, 'flip your cap!')
                else:
                    print('People in positions', start,
                          'through', i-1, 'flip your caps!')
                start = None


# pleaseConform(caps)
# pleaseConform(cap2)
pleaseConform(cap3)
# pleaseConformOnepass(caps)
# pleaseConformOnepass(cap2)
# pleaseConformOnepass(cap3)
# pleaseConformOnepass([])
