Notebook

The Devil and the Coin Flip Game¶

If the Devil ever challenges me to a fiddle contest, I'm going down. But here is a contest where I'd have a better chance:

You're playing a game with the Devil, with your soul at stake. You're sitting at a circular table which has 4 coins, arranged in a diamond, at the 12, 3, 6, and 9 o'clock positions. You are blindfolded, and can never see the coins or the table.

Your goal is to get all 4 coins showing heads, by telling the devil the position(s) of some coins to flip. We call this a "move" on your part. The Devil must faithfully perform the requested flips, but may first sneakily rotate the table any number of quarter-turns, so that the coins are in different positions. You keep making moves, and the Devil keeps rotating and flipping, until all 4 coins show heads.

Example: You tell the Devil to flip the 12 o'clock and 6 o'clock positions. The devil might rotate the table a quarter turn clockwiae, and then flip the coins that have moved into the 12 o'clock and 6 o'clock positions (which were formerly at 3 o'clock and 9 o'clock). Or the Devil could have made any other rotation before flipping.

What is a shortest sequence of moves that is guaranteed* to win, no matter what the initial state of the coins, and no matter what rotations the Devil applies?*

Analysis¶

We're looking for a "shortest sequence of moves" that reaches a goal. That's a shortest path search problem. I've done that before.
Since the Devil gets to make moves too, you might think that this is a minimax problem: that we should choose the move that leads to the shortest path, given that the Devil has the option of making moves that lead to the longest path.
But minimax only works when you know what moves the opponent is making: he did that, so I'll do this. In this problem the player is blinfolded; that makes it a partially observable problem (in this case, not observable at all, but we still say "partially").
In such problems, we don't know for sure the true state of the world before or after any move. So we should represent what is known: the set of states that we believe to be possible. We call this a belief state. At the start of the game, each of the four coins could be either heads or tails, so that's 2⁴ = 16 possibilities in the initial belief state: {HHHH, HHHT, HHTH, HHTT, HTHH, HTHT, HTTH, HTTT, THHH, THHT, THTH, THTT, TTHH, TTHT, TTTH, TTTT}
So we have a single-agent shortest path search in the space of belief states (not the space of physical states of the coins). We search for a path from the inital belief state to the goal belief state, which is {HHHH}.
A move updates the belief state as follows: for every four-coin sequence in the current belief state, rotate it in every possible way, and then flip the coins specified by the position(s) in the move. Collect all these results together to form the new belief state. The search space is small (just 2¹⁶ possible belief states), so run time will be fast.
I'll Keep It Simple, and not worry about rotational symmetry (although we'll come back to that later).

Basic Data Structures and Functions¶

What data structures will I be dealing with?

Coins: a coin sequence (four coins, in order, on the table) is represented as a str of four characters, such as 'HTTT'.
Belief: a belief state is a frozenset of Coins (frozen so it can be hashed), like {'HHHT', 'TTTH'}.
Position: an integer index into the coin sequence; position 0 selects the H in 'HTTT'

and corresponds to the 12 o'clock position; position 1 corresponds to 3 o'clock, and so on.

Move: a set of positions to flip, such as {0, 2}.
Strategy: an ordered list of moves. A

blindfolded player has no feedback, there thus no decision points in the strategy.

In [1]:

from collections import deque
from itertools   import product, combinations, chain
import random

Coins     = ''.join   # A coin sequence; a str: 'HHHT'.
Belief    = frozenset # A set of possible coin sequences: {'HHHT', 'TTTH'}.
Position  = int       # An index into a coin sequence.
Move      = set       # A set of positions to flip: {0, 2}
Strategy  = list      # A list of Moves: [{0, 1, 2, 3}, {0, 2}, ...]

What basic functions do I need to manipulate these data structures?

all_moves(): returns a list of every possible move a player can make.
all_coins(): returns a belief state consisting of the set of all 16 possible coin sequences: {'HHHH', 'HHHT', ...}.
rotations(coins): returns a belief set of all 4 rotations of the coin sequence.
flip(coins, move): flips the specified positions within the coin sequence.

(But leave 'HHHH' alone, because it ends the game.)

update(belief, move): returns an updated belief state: all the coin sequences that could result from any rotation followed by the specified flips.

In [2]:

def all_moves() -> [Move]: 
    "List of all possible moves."
    return [set(m) for m in powerset(range(4))]

def all_coins() -> Belief:
    "The belief set consisting of all possible coin sequences."
    return Belief(map(Coins, product('HT', repeat=4)))

def rotations(coins) -> {Coins}: 
    "A set of all possible rotations of a coin sequence."
    return {coins[r:] + coins[:r] for r in range(4)}

def flip(coins, move) -> Coins:
    "Flip the coins in the positions specified by the move (but leave 'HHHH' alone)."
    if 'T' not in coins: return coins # Don't flip 'HHHH'
    coins = list(coins) # Need a mutable sequence
    for i in move:
        coins[i] = ('H' if coins[i] == 'T' else 'T')
    return Coins(coins)

def update(belief, move) -> Belief:
    "Update belief: consider all possible rotations, then flip."
    return Belief(flip(c, move)
                  for coins in belief
                  for c in rotations(coins))

flatten = chain.from_iterable

def powerset(iterable): 
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    # https://docs.python.org/3/library/itertools.html#itertools-recipes
    s = list(iterable)
    return flatten(combinations(s, r) for r in range(len(s) + 1))

Let's try out these functions:

In [3]:

all_moves()

Out[3]:

[set(),
 {0},
 {1},
 {2},
 {3},
 {0, 1},
 {0, 2},
 {0, 3},
 {1, 2},
 {1, 3},
 {2, 3},
 {0, 1, 2},
 {0, 1, 3},
 {0, 2, 3},
 {1, 2, 3},
 {0, 1, 2, 3}]

In [4]:

all_coins()

Out[4]:

frozenset({'HHHH',
           'HHHT',
           'HHTH',
           'HHTT',
           'HTHH',
           'HTHT',
           'HTTH',
           'HTTT',
           'THHH',
           'THHT',
           'THTH',
           'THTT',
           'TTHH',
           'TTHT',
           'TTTH',
           'TTTT'})

In [5]:

rotations('HHHT')

Out[5]:

{'HHHT', 'HHTH', 'HTHH', 'THHH'}

In [6]:

flip('HHHT', {0, 2})

Out[6]:

'THTT'

There are 16 coin sequences in the all_coins belief state. If we update this belief state by flipping all 4 positions, we should get a new belief state where we have eliminated the possibility of 4 tails, leaving 15 possible coin sequences:

In [7]:

update(all_coins(), {0, 1, 2, 3})

Out[7]:

frozenset({'HHHH',
           'HHHT',
           'HHTH',
           'HHTT',
           'HTHH',
           'HTHT',
           'HTTH',
           'HTTT',
           'THHH',
           'THHT',
           'THTH',
           'THTT',
           'TTHH',
           'TTHT',
           'TTTH'})

In [8]:

list(powerset([1,2,3]))

Out[8]:

[(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]

Everything looks good so far.

Search for a Winning Strategy¶

The generic function search does a breadth-first search starting from a start state, looking for a goal state, considering possible actions at each turn, and computing the result of each action (result is a function such that result(state, action) returns the new state that results from executing the action in the current state). search works by keeping a queue of unexplored possibilities, where each entry in the queue is a pair consisting of a strategy (sequence of moves) and a state that that strategy leads to. We also keep track of a set of explored states, so that we don't repeat ourselves. I've defined this function (or one just like it) multiple times before, for use in different search problems.

In [9]:

def search(start, goal, actions, result) -> Strategy:
    "Breadth-first search from start state to goal; return strategy to get to goal."
    explored = set()
    queue = deque([(Strategy(), start)])
    while queue:
        (strategy, state) = queue.popleft()
        if state == goal:
            return strategy
        for action in actions:
            state2 = result(state, action)
            if state2 not in explored:
                queue.append((strategy + [action], state2))
                explored.add(state2)

Note that search doesn't know anything about belief states—it is designed to work on plain-old physical states of the world. But amazingly, we can still use it to search over belief states: it just works, as long as we properly specify the start state, the goal state, and the means of moving between states.

The coin_search function calls search to solve our specific problem:

In [10]:

def coin_search() -> Strategy: 
    "Use `search` to solve the Coin Flip problem."
    return search(start=all_coins(), goal={'HHHH'}, actions=all_moves(), result=update)

coin_search()

Out[10]:

[{0, 1, 2, 3},
 {0, 2},
 {0, 1, 2, 3},
 {0, 1},
 {0, 1, 2, 3},
 {0, 2},
 {0, 1, 2, 3},
 {0},
 {0, 1, 2, 3},
 {0, 2},
 {0, 1, 2, 3},
 {0, 1},
 {0, 1, 2, 3},
 {0, 2},
 {0, 1, 2, 3}]

That's a 15-move strategy that is guaranteed to lead to a win. Stop here if all you want is the answer to the puzzle.

Or you can continue on ...

Verifying the Winning Strategy¶

I don't have a proof, but I have some evidence that this strategy works:

Exploring with paper and pencil, it looks good.
A colleague did the puzzle and got the same answer.
It passes the winning test below.

The call winning(strategy, k) plays the strategy k times against a Devil that chooses starting positions and rotations at random. Note this is dealing with concrete, individual states of the world, like HTHH, not belief states. If winning returns False, then the strategy is definitely flawed. If it returns True, then the strategy is probably good—it won k times in a row—but that does not prove it will win every time (and either way winning makes no claims about being a shortest strategy).

In [11]:

def winning(strategy, k=100000) -> bool:
    "Is this a winning strategy? A probabilistic algorithm."
    return all(play(strategy) == 'HHHH'
               for _ in range(k))

def play(strategy, starting_coins=list(all_coins())) -> Coins:
    "Play strategy for one game against a random Devil; return final state of coins."
    coins = random.choice(starting_coins)
    for move in strategy:
        if 'T' not in coins: return coins
        coins = random.choice(list(rotations(coins)))
        coins = flip(coins, move)
    return coins

winning(strategy=coin_search())

Out[11]:

True

Canonical Coin Sequences¶

Consider these coin sequences: {'HHHT', 'HHTH', 'HTHH', 'THHH'}. In a sense, these are all the same: they all denote the same sequence of coins with the table rotated to different degrees. Since the devil is free to rotate the table any amount at any time, we could be justified in treating all four of these as equivalent, and collapsing them into one representative member. I will redefine Coins so that is stil takes an iterable of 'H' or 'T' characters and joins them into a str, but I will make it consider all possible rotations of the string and (arbitraily) choose the one that comes first in alphabetical order (which would be 'HHHT' for the four coin sequences mentioned here).

In [12]:

def Coins(coins) -> str: 
    "The canonical representation (after rotation) of the 'H'/'T' sequence."
    return min(rotations(''.join(coins)))

In [13]:

assert Coins('HHHT') == Coins('HHTH') == Coins('HTHH') == Coins('THHH') == 'HHHT'

With Coins redefined, the result of all_coins() is different:

In [14]:

all_coins()

Out[14]:

frozenset({'HHHH', 'HHHT', 'HHTT', 'HTHT', 'HTTT', 'TTTT'})

The starting belief set is down from 16 to 6, namely 4 heads, 3 heads, 2 adjacent heads, 2 opposite heads, 1 head, and no heads, respectively.

Let's make sure we didn't break anything:

In [15]:

coin_search()

Out[15]:

[{0, 1, 2, 3},
 {0, 2},
 {0, 1, 2, 3},
 {0, 1},
 {0, 1, 2, 3},
 {0, 2},
 {0, 1, 2, 3},
 {0},
 {0, 1, 2, 3},
 {0, 2},
 {0, 1, 2, 3},
 {0, 1},
 {0, 1, 2, 3},
 {0, 2},
 {0, 1, 2, 3}]

Winning Strategies for N Coins¶

What if there are 3 coins on the table arranged in a triangle? Or 6 coins in a hexagon? To answer that, I'll generalize all the functions that have a "4" in them: all_moves, all_coins, rotations and coin_search.

Computing all_coins(N) is easy; just take the product, and canonicalize each one with the new definition of Coins. For all_moves(N) I want canonicalized moves: the moves {0} and {1} should be considered the same, since they both say "flip one coin." To get that, look at the canonicalized set of all_coins(N), and for each one pull out the set of positions that have an H in them and flip those positions. (The positions with a T should be symmetric, so we don't need them as well.)

In [16]:

def all_moves(N=4) -> [Move]:
    "All canonical moves for a sequence of N coins."
    return [set(i for i in range(N) if coins[i] == 'H')
            for coins in sorted(all_coins(N))]

def all_coins(N=4) -> Belief:
    "Return the belief set consisting of all possible coin sequences."
    return Belief(map(Coins, product('HT', repeat=N)))

def rotations(coins) -> {Coins}: 
    "A list of all possible rotations of a coin sequence."
    return {coins[r:] + coins[:r] for r in range(len(coins))}

def coin_search(N=4) -> Strategy: 
    "Use the generic `search` function to solve the Coin Flip problem."
    return search(start=all_coins(N), goal={'H' * N}, actions=all_moves(N), result=update)

Let's test the new definitions and make sure we haven't broken update and coin_search:

In [17]:

assert all_moves(3) == [{0, 1, 2}, {0, 1}, {0}, set()]
assert all_moves(4) == [{0, 1, 2, 3}, {0, 1, 2}, {0, 1}, {0, 2}, {0}, set()]

assert all_coins(4) == {'HHHH', 'HHHT', 'HHTT', 'HTHT', 'HTTT', 'TTTT'}
assert all_coins(5) == {'HHHHH','HHHHT', 'HHHTT','HHTHT','HHTTT', 'HTHTT', 'HTTTT', 'TTTTT'}

assert rotations('HHHHHT') == {'HHHHHT', 'HHHHTH', 'HHHTHH', 'HHTHHH', 'HTHHHH', 'THHHHH'}
assert update({'TTTTTTT'}, {3}) == {'HTTTTTT'}
assert (update(rotations('HHHHHT'), {0}) == update({'HHTHHH'}, {1}) == update({'THHHHH'}, {2})
        == {'HHHHHH', 'HHHHTT', 'HHHTHT', 'HHTHHT'})

assert coin_search(4) == [
 {0, 1, 2, 3},
 {0, 2},
 {0, 1, 2, 3},
 {0, 1},
 {0, 1, 2, 3},
 {0, 2},
 {0, 1, 2, 3},
 {0, 1, 2},
 {0, 1, 2, 3},
 {0, 2},
 {0, 1, 2, 3},
 {0, 1},
 {0, 1, 2, 3},
 {0, 2},
 {0, 1, 2, 3}]

How many distinct canonical coin sequences are there for up to a dozen coins?

In [18]:

{N: len(all_coins(N))
 for N in range(1, 13)}

Out[18]:

{1: 2,
 2: 3,
 3: 4,
 4: 6,
 5: 8,
 6: 14,
 7: 20,
 8: 36,
 9: 60,
 10: 108,
 11: 188,
 12: 352}

On the one hand this is encouraging; there are only 352 canonical coin sequences of length 10, far less than the 4,096 non-canonical squences. On the other hand, it is discouraging; since we are searching over belief states, that would be 2³⁵² belief states, which is nore than a googol. However, we should be able to easily handle up to N=7, because 2²⁰ is only a million.

Winning Strategies for 1 to 7 Coins¶

In [19]:

{N: coin_search(N) for N in range(1, 8)}

Out[19]:

{1: [{0}],
 2: [{0, 1}, {0}, {0, 1}],
 3: None,
 4: [{0, 1, 2, 3},
  {0, 2},
  {0, 1, 2, 3},
  {0, 1},
  {0, 1, 2, 3},
  {0, 2},
  {0, 1, 2, 3},
  {0, 1, 2},
  {0, 1, 2, 3},
  {0, 2},
  {0, 1, 2, 3},
  {0, 1},
  {0, 1, 2, 3},
  {0, 2},
  {0, 1, 2, 3}],
 5: None,
 6: None,
 7: None}

Too bad; there are no winning strategies for N = 3, 5, 6, or 7.

There are winning strategies for N = 1, 2, 4; they have lengths 1, 3, 15, respectively. Hmm. That suggests ...

A Conjecture¶

For every N that is a power of 2, there will be a shortest winning strategy of length 2^N - 1.

For every N that is not a power of 2, there will be no winning strategy.

Winning Strategy for 8 Coins¶

For N = 8, there are 2³⁶ = 69 billion belief states and if the conjecture is true there will be a shortest winning strategy with 255 steps. All the computations up to now have been instantaneous, but this one should take a few minutes. Let's see:

In [20]:

%time strategy = coin_search(8)

CPU times: user 1min 18s, sys: 118 ms, total: 1min 18s
Wall time: 1min 18s

In [21]:

len(strategy)

Out[21]:

Eureka! That's evidence in favor of the conjecture. But not proof. And it leaves many questions unanswered:

Can you show there are no winning strategies for N = 9, 10, 11, ...?
Can you prove there are no winning strategies for any N that is not a power of 2?
Can you find a winning strategy of length 65,535 for N = 16 and verify that it works?
Can you generate a winning strategy for any power of 2 (without proving it is shortest)?
Can you prove there are no shorter winning strategies for N = 16?
Can you prove the conjecture in general?
Can you understand and explain how the strategy works, rather than just listing the moves?

Visualizing Strategies¶

In [22]:

def show(moves, N=4):
    "For each move, print the move number, move, and belief state."
    belief = all_coins(N)
    order = sorted(belief)
    for (i, move) in enumerate(moves, 1):
        belief = update(belief, move)
        print('{:3} | {:8} | {}'.format(
              i, movestr(move, N), beliefstr(belief, order)))

def beliefstr(belief, order) -> str: 
    return join(((coins if coins in belief else ' ' * len(coins))
                 for coins in order), ' ')

def movestr(move, N) -> str: 
    return join((i if i in move else ' ') 
                for i in range(N))
    
def join(items, sep='') -> str: 
    return sep.join(map(str, items))

The following tables shows how moves change the belief state:

In [23]:

show(coin_search(2), 2)

  1 | 01       | HH HT   
  2 | 0        | HH    TT
  3 | 01       | HH

In [24]:

show(coin_search(4))

  1 | 0123     | HHHH HHHT HHTT HTHT HTTT     
  2 | 0 2      | HHHH HHHT HHTT      HTTT TTTT
  3 | 0123     | HHHH HHHT HHTT      HTTT     
  4 | 01       | HHHH HHHT      HTHT HTTT TTTT
  5 | 0123     | HHHH HHHT      HTHT HTTT     
  6 | 0 2      | HHHH HHHT           HTTT TTTT
  7 | 0123     | HHHH HHHT           HTTT     
  8 | 012      | HHHH      HHTT HTHT      TTTT
  9 | 0123     | HHHH      HHTT HTHT          
 10 | 0 2      | HHHH      HHTT           TTTT
 11 | 0123     | HHHH      HHTT               
 12 | 01       | HHHH           HTHT      TTTT
 13 | 0123     | HHHH           HTHT          
 14 | 0 2      | HHHH                     TTTT
 15 | 0123     | HHHH

We can see that every odd-numbered move flips all four coins to eliminate the possibility of TTTT, flipping it to HHHH. We can also see that moves 2, 4, and 6 flip two coins and have the effect of eventually eliminating the two "two heads" sequences from the belief state, and then move 8 eliminates the "three heads" and "one heads" sequences, while bringing back the "two heads" possibilities. Repeating moves 2, 4, and 6 in moves 10, 12, and 14 then re-eliminates the "two heads", and move 15 gets the belief state down to {'HHHH'}.

You could call show(strategy, 8), but the results look bad unless you have a very wide (345 characters) screen to view it on. So instead I'll add a verbose parameter to play and play out some games with a trace of each move:

In [25]:

def play(coins, strategy, verbose=False):
    "Play strategy against a random Devil; return final state of coins."
    N = len(coins)
    for i, move in enumerate(strategy, 1):
        if 'T' not in coins: return coins
        coins0 = coins
        coins1 = random.choice(list(rotations(coins)))
        coins  = flip(coins1, move)
        if verbose: 
            print('{:4d}: {} rot: {}  flip: {} => {}'.format(
                  i, coins0, coins1, movestr(move, N), coins))
    return coins

play('HHTH', coin_search(4), True)

   1: HHTH rot: HHHT  flip: 0123 => HTTT
   2: HTTT rot: TTTH  flip: 0 2  => HHHT
   3: HHHT rot: HTHH  flip: 0123 => HTTT
   4: HTTT rot: HTTT  flip: 01   => HTTT
   5: HTTT rot: TTHT  flip: 0123 => HHHT
   6: HHHT rot: THHH  flip: 0 2  => HHHT
   7: HHHT rot: THHH  flip: 0123 => HTTT
   8: HTTT rot: TTTH  flip: 012  => HHHH

Out[25]:

'HHHH'

In [26]:

play('HTTHTTHT', strategy, True)

   1: HTTHTTHT rot: TTHTHTTH  flip: 01234567 => HHTHHTHT
   2: HHTHHTHT rot: HHTHTHHT  flip: 0 2 4 6  => HHHHHTTT
   3: HHHHHTTT rot: TTHHHHHT  flip: 01234567 => HHHTTTTT
   4: HHHTTTTT rot: HTTTTTHH  flip: 01  45   => HHHHTHTT
   5: HHHHTHTT rot: HTHTTHHH  flip: 01234567 => HHTTTTHT
   6: HHTTTTHT rot: TTTHTHHT  flip: 0 2 4 6  => HHHHTTHT
   7: HHHHTTHT rot: TTHTHHHH  flip: 01234567 => HHTHTTTT
   8: HHTHTTTT rot: THHTHTTT  flip: 012 456  => HHTHTTTT
   9: HHTHTTTT rot: THHTHTTT  flip: 01234567 => HHHHTTHT
  10: HHHHTTHT rot: TTHTHHHH  flip: 0 2 4 6  => HHTTTTHT
  11: HHTTTTHT rot: HTHHTTTT  flip: 01234567 => HHHHTHTT
  12: HHHHTHTT rot: HTTHHHHT  flip: 01  45   => HTHTTHTT
  13: HTHTTHTT rot: THTTHTTH  flip: 01234567 => HHTHHTHT
  14: HHTHHTHT rot: THHTHTHH  flip: 0 2 4 6  => HHHTTTTT
  15: HHHTTTTT rot: TTTTTHHH  flip: 01234567 => HHHHHTTT
  16: HHHHHTTT rot: HHHTTTHH  flip: 0123     => HHTTTHTT
  17: HHTTTHTT rot: HHTTTHTT  flip: 01234567 => HHHTHHTT
  18: HHHTHHTT rot: HHHTHHTT  flip: 0 2 4 6  => HHTTHTTT
  19: HHTTHTTT rot: TTHTTTHH  flip: 01234567 => HHHTTHHT
  20: HHHTTHHT rot: HHHTTHHT  flip: 01  45   => HTHTHTTT
  21: HTHTHTTT rot: TTHTHTHT  flip: 01234567 => HHHTHTHT
  22: HHHTHTHT rot: HHHTHTHT  flip: 0 2 4 6  => HTTTTTTT
  23: HTTTTTTT rot: TTTTTTTH  flip: 01234567 => HHHHHHHT
  24: HHHHHHHT rot: HHHHHHHT  flip: 012 456  => HTTTTTTT
  25: HTTTTTTT rot: TTTTTHTT  flip: 01234567 => HHHHHHHT
  26: HHHHHHHT rot: HHHHHHHT  flip: 0 2 4 6  => HTHTHTTT
  27: HTHTHTTT rot: THTTTHTH  flip: 01234567 => HHHTHTHT
  28: HHHTHTHT rot: HHHTHTHT  flip: 01  45   => HHTTTHTT
  29: HHTTTHTT rot: TTHHTTTH  flip: 01234567 => HHHTHHTT
  30: HHHTHHTT rot: TTHHHTHH  flip: 0 2 4 6  => HHTTHTTT
  31: HHTTHTTT rot: HTTHTTTH  flip: 01234567 => HHHTTHHT
  32: HHHTTHHT rot: TTHHTHHH  flip: 01234 6  => HHHTTHHT
  33: HHHTTHHT rot: THHHTTHH  flip: 01234567 => HHTTHTTT
  34: HHTTHTTT rot: TTTHHTTH  flip: 0 2 4 6  => HHHTHHTT
  35: HHHTHHTT rot: HTTHHHTH  flip: 01234567 => HHTTTHTT
  36: HHTTTHTT rot: TTHHTTTH  flip: 01  45   => HHHHHHHT
  37: HHHHHHHT rot: HTHHHHHH  flip: 01234567 => HTTTTTTT
  38: HTTTTTTT rot: HTTTTTTT  flip: 0 2 4 6  => HTHTHTTT
  39: HTHTHTTT rot: THTHTTTH  flip: 01234567 => HHHTHTHT
  40: HHHTHTHT rot: HHHTHTHT  flip: 012 456  => HTTTTTTT
  41: HTTTTTTT rot: TTTTTTTH  flip: 01234567 => HHHHHHHT
  42: HHHHHHHT rot: HHTHHHHH  flip: 0 2 4 6  => HHHTHTHT
  43: HHHTHTHT rot: HTHHHTHT  flip: 01234567 => HTHTHTTT
  44: HTHTHTTT rot: HTHTHTTT  flip: 01  45   => HHTTHTTT
  45: HHTTHTTT rot: TTHTTTHH  flip: 01234567 => HHHTTHHT
  46: HHHTTHHT rot: HTTHHTHH  flip: 0 2 4 6  => HHTTTHTT
  47: HHTTTHTT rot: THTTHHTT  flip: 01234567 => HHHTHHTT
  48: HHHTHHTT rot: HHTHHTTH  flip: 0123     => HTHTTHTT
  49: HTHTTHTT rot: TTHTTHTH  flip: 01234567 => HHTHHTHT
  50: HHTHHTHT rot: THTHHTHH  flip: 0 2 4 6  => HHHHHTTT
  51: HHHHHTTT rot: HTTTHHHH  flip: 01234567 => HHHTTTTT
  52: HHHTTTTT rot: TTHHHTTT  flip: 01  45   => HHHHTHTT
  53: HHHHTHTT rot: HHHHTHTT  flip: 01234567 => HHTTTTHT
  54: HHTTTTHT rot: TTTTHTHH  flip: 0 2 4 6  => HHTHTTTT
  55: HHTHTTTT rot: THTTTTHH  flip: 01234567 => HHHHTTHT
  56: HHHHTTHT rot: HHTTHTHH  flip: 012 456  => HTHTTHTT
  57: HTHTTHTT rot: THTTHTTH  flip: 01234567 => HHTHHTHT
  58: HHTHHTHT rot: HHTHTHHT  flip: 0 2 4 6  => HHHHHTTT
  59: HHHHHTTT rot: HHTTTHHH  flip: 01234567 => HHHTTTTT
  60: HHHTTTTT rot: TTTTHHHT  flip: 01  45   => HHTTTTHT
  61: HHTTTTHT rot: HTTTTHTH  flip: 01234567 => HHHHTHTT
  62: HHHHTHTT rot: THHHHTHT  flip: 0 2 4 6  => HHTHTTTT
  63: HHTHTTTT rot: THTTTTHH  flip: 01234567 => HHHHTTHT
  64: HHHHTTHT rot: HHHTTHTH  flip: 012345   => HHTTHTTT
  65: HHTTHTTT rot: HTTHTTTH  flip: 01234567 => HHHTTHHT
  66: HHHTTHHT rot: TTHHTHHH  flip: 0 2 4 6  => HHHTHHTT
  67: HHHTHHTT rot: HHTHHTTH  flip: 01234567 => HHTTTHTT
  68: HHTTTHTT rot: THTTHHTT  flip: 01  45   => HTTTTTTT
  69: HTTTTTTT rot: TTTTTTHT  flip: 01234567 => HHHHHHHT
  70: HHHHHHHT rot: HHHTHHHH  flip: 0 2 4 6  => HTHTHTTT
  71: HTHTHTTT rot: TTHTHTHT  flip: 01234567 => HHHTHTHT
  72: HHHTHTHT rot: HTHHHTHT  flip: 012 456  => HTHTHTTT
  73: HTHTHTTT rot: TTHTHTHT  flip: 01234567 => HHHTHTHT
  74: HHHTHTHT rot: HTHTHTHH  flip: 0 2 4 6  => HTTTTTTT
  75: HTTTTTTT rot: TTTTHTTT  flip: 01234567 => HHHHHHHT
  76: HHHHHHHT rot: HHTHHHHH  flip: 01  45   => HHTTTHTT
  77: HHTTTHTT rot: HTTTHTTH  flip: 01234567 => HHHTHHTT
  78: HHHTHHTT rot: HHTTHHHT  flip: 0 2 4 6  => HHTTHTTT
  79: HHTTHTTT rot: HHTTHTTT  flip: 01234567 => HHHTTHHT
  80: HHHTTHHT rot: HTHHHTTH  flip: 0123     => HTHTTHTT
  81: HTHTTHTT rot: THTTHTTH  flip: 01234567 => HHTHHTHT
  82: HHTHHTHT rot: HHTHHTHT  flip: 0 2 4 6  => HHHTTTTT
  83: HHHTTTTT rot: TTHHHTTT  flip: 01234567 => HHHHHTTT
  84: HHHHHTTT rot: TTHHHHHT  flip: 01  45   => HHHHTTHT
  85: HHHHTTHT rot: HTTHTHHH  flip: 01234567 => HHTHTTTT
  86: HHTHTTTT rot: HTTTTHHT  flip: 0 2 4 6  => HHTTTTHT
  87: HHTTTTHT rot: TTTTHTHH  flip: 01234567 => HHHHTHTT
  88: HHHHTHTT rot: THHHHTHT  flip: 012 456  => HTHTTHTT
  89: HTHTTHTT rot: THTTHTTH  flip: 01234567 => HHTHHTHT
  90: HHTHHTHT rot: THTHHTHH  flip: 0 2 4 6  => HHHHHTTT
  91: HHHHHTTT rot: TTTHHHHH  flip: 01234567 => HHHTTTTT
  92: HHHTTTTT rot: HHHTTTTT  flip: 01  45   => HHTTTTHT
  93: HHTTTTHT rot: TTHTHHTT  flip: 01234567 => HHHHTHTT
  94: HHHHTHTT rot: HHTHTTHH  flip: 0 2 4 6  => HHHHTTHT
  95: HHHHTTHT rot: TTHTHHHH  flip: 01234567 => HHTHTTTT
  96: HHTHTTTT rot: TTHHTHTT  flip: 01234 6  => HHHTHHTT
  97: HHHTHHTT rot: TTHHHTHH  flip: 01234567 => HHTTTHTT
  98: HHTTTHTT rot: TTHTTHHT  flip: 0 2 4 6  => HHTTHTTT
  99: HHTTHTTT rot: THTTTHHT  flip: 01234567 => HHHTTHHT
 100: HHHTTHHT rot: THHTHHHT  flip: 01  45   => HTHTHTTT
 101: HTHTHTTT rot: THTHTTTH  flip: 01234567 => HHHTHTHT
 102: HHHTHTHT rot: HTHTHTHH  flip: 0 2 4 6  => HTTTTTTT
 103: HTTTTTTT rot: TTTTTHTT  flip: 01234567 => HHHHHHHT
 104: HHHHHHHT rot: HHHHHHHT  flip: 012 456  => HTTTTTTT
 105: HTTTTTTT rot: TTTHTTTT  flip: 01234567 => HHHHHHHT
 106: HHHHHHHT rot: HHHHHHHT  flip: 0 2 4 6  => HTHTHTTT
 107: HTHTHTTT rot: THTHTHTT  flip: 01234567 => HHHTHTHT
 108: HHHTHTHT rot: HTHTHTHH  flip: 01  45   => HHHTHHTT
 109: HHHTHHTT rot: TTHHHTHH  flip: 01234567 => HHTTTHTT
 110: HHTTTHTT rot: HTTTHTTH  flip: 0 2 4 6  => HHTTHTTT
 111: HHTTHTTT rot: TTTHHTTH  flip: 01234567 => HHHTTHHT
 112: HHHTTHHT rot: HHHTTHHT  flip: 0123     => HHTTTTHT
 113: HHTTTTHT rot: TTHTHHTT  flip: 01234567 => HHHHTHTT
 114: HHHHTHTT rot: HHTHTTHH  flip: 0 2 4 6  => HHHHTTHT
 115: HHHHTTHT rot: HHHHTTHT  flip: 01234567 => HHTHTTTT
 116: HHTHTTTT rot: HTTTTHHT  flip: 01  45   => HTHTTHTT
 117: HTHTTHTT rot: THTHTTHT  flip: 01234567 => HHTHHTHT
 118: HHTHHTHT rot: HHTHHTHT  flip: 0 2 4 6  => HHHTTTTT
 119: HHHTTTTT rot: HHTTTTTH  flip: 01234567 => HHHHHTTT
 120: HHHHHTTT rot: TTTHHHHH  flip: 012 456  => HHHHHTTT
 121: HHHHHTTT rot: HTTTHHHH  flip: 01234567 => HHHTTTTT
 122: HHHTTTTT rot: HHHTTTTT  flip: 0 2 4 6  => HTHTTHTT
 123: HTHTTHTT rot: THTTHTHT  flip: 01234567 => HHTHHTHT
 124: HHTHHTHT rot: THHTHHTH  flip: 01  45   => HHTHTTTT
 125: HHTHTTTT rot: HHTHTTTT  flip: 01234567 => HHHHTTHT
 126: HHHHTTHT rot: THHHHTTH  flip: 0 2 4 6  => HHHHTHTT
 127: HHHHTHTT rot: THHHHTHT  flip: 01234567 => HHTTTTHT
 128: HHTTTTHT rot: HTTTTHTH  flip: 0123456  => HHHHTHHT
 129: HHHHTHHT rot: THHTHHHH  flip: 01234567 => HTTHTTTT
 130: HTTHTTTT rot: TTHTTTTH  flip: 0 2 4 6  => HHHTTTHT
 131: HHHTTTHT rot: THHHTTTH  flip: 01234567 => HHHTHTTT
 132: HHHTHTTT rot: THHHTHTT  flip: 01  45   => HHHTTTHT
 133: HHHTTTHT rot: TTTHTHHH  flip: 01234567 => HHHTHTTT
 134: HHHTHTTT rot: HTTTHHHT  flip: 0 2 4 6  => HTTHTTTT
 135: HTTHTTTT rot: TTTTHTTH  flip: 01234567 => HHHHTHHT
 136: HHHHTHHT rot: HHHTHHTH  flip: 012 456  => HHTTTTTT
 137: HHTTTTTT rot: TTHHTTTT  flip: 01234567 => HHHHHHTT
 138: HHHHHHTT rot: HHTTHHHH  flip: 0 2 4 6  => HHTTHTHT
 139: HHTTHTHT rot: HTHTHHTT  flip: 01234567 => HHTHTHTT
 140: HHTHTHTT rot: THTTHHTH  flip: 01  45   => HHTTTTTT
 141: HHTTTTTT rot: TTTHHTTT  flip: 01234567 => HHHHHHTT
 142: HHHHHHTT rot: TTHHHHHH  flip: 0 2 4 6  => HHTTHTHT
 143: HHTTHTHT rot: TTHTHTHH  flip: 01234567 => HHTHTHTT
 144: HHTHTHTT rot: HTTHHTHT  flip: 0123     => HHTHTHTT
 145: HHTHTHTT rot: TTHHTHTH  flip: 01234567 => HHTTHTHT
 146: HHTTHTHT rot: HHTTHTHT  flip: 0 2 4 6  => HHTTTTTT
 147: HHTTTTTT rot: TTHHTTTT  flip: 01234567 => HHHHHHTT
 148: HHHHHHTT rot: HHHHHHTT  flip: 01  45   => HHTTTTTT
 149: HHTTTTTT rot: TTTTHHTT  flip: 01234567 => HHHHHHTT
 150: HHHHHHTT rot: HHHHTTHH  flip: 0 2 4 6  => HHTTHTHT
 151: HHTTHTHT rot: THTHHTTH  flip: 01234567 => HHTHTHTT
 152: HHTHTHTT rot: HHTHTHTT  flip: 012 456  => HHHTHTTT
 153: HHHTHTTT rot: THTTTHHH  flip: 01234567 => HHHTTTHT
 154: HHHTTTHT rot: HHTTTHTH  flip: 0 2 4 6  => HHHHTHHT
 155: HHHHTHHT rot: THHTHHHH  flip: 01234567 => HTTHTTTT
 156: HTTHTTTT rot: TTHTTTTH  flip: 01  45   => HHHHTHHT
 157: HHHHTHHT rot: HHTHHHHT  flip: 01234567 => HTTHTTTT
 158: HTTHTTTT rot: TTTHTTHT  flip: 0 2 4 6  => HHHTTTHT
 159: HHHTTTHT rot: HHHTTTHT  flip: 01234567 => HHHTHTTT
 160: HHHTHTTT rot: TTHHHTHT  flip: 01234 6  => HHTTTTTT
 161: HHTTTTTT rot: TTHHTTTT  flip: 01234567 => HHHHHHTT
 162: HHHHHHTT rot: HHHHHTTH  flip: 0 2 4 6  => HHTHTHTT
 163: HHTHTHTT rot: THTTHHTH  flip: 01234567 => HHTTHTHT
 164: HHTTHTHT rot: TTHTHTHH  flip: 01  45   => HHHHHHTT
 165: HHHHHHTT rot: HHTTHHHH  flip: 01234567 => HHTTTTTT
 166: HHTTTTTT rot: HHTTTTTT  flip: 0 2 4 6  => HHTHTHTT
 167: HHTHTHTT rot: THTHTTHH  flip: 01234567 => HHTTHTHT
 168: HHTTHTHT rot: HTHHTTHT  flip: 012 456  => HHHTTTHT
 169: HHHTTTHT rot: TTTHTHHH  flip: 01234567 => HHHTHTTT
 170: HHHTHTTT rot: TTHHHTHT  flip: 0 2 4 6  => HTTHTTTT
 171: HTTHTTTT rot: TTTTHTTH  flip: 01234567 => HHHHTHHT
 172: HHHHTHHT rot: HTHHTHHH  flip: 01  45   => HHHHTHHT
 173: HHHHTHHT rot: THHTHHHH  flip: 01234567 => HTTHTTTT
 174: HTTHTTTT rot: TTHTTHTT  flip: 0 2 4 6  => HHHTHTTT
 175: HHHTHTTT rot: THTTTHHH  flip: 01234567 => HHHTTTHT
 176: HHHTTTHT rot: HHHTTTHT  flip: 0123     => HTTHTTTT
 177: HTTHTTTT rot: TTHTTTTH  flip: 01234567 => HHHHTHHT
 178: HHHHTHHT rot: HHTHHTHH  flip: 0 2 4 6  => HHHTTTHT
 179: HHHTTTHT rot: HHHTTTHT  flip: 01234567 => HHHTHTTT
 180: HHHTHTTT rot: TTTHHHTH  flip: 01  45   => HHHTHTTT
 181: HHHTHTTT rot: HTTTHHHT  flip: 01234567 => HHHTTTHT
 182: HHHTTTHT rot: HHTTTHTH  flip: 0 2 4 6  => HHHHTHHT
 183: HHHHTHHT rot: THHHHTHH  flip: 01234567 => HTTHTTTT
 184: HTTHTTTT rot: HTTTTHTT  flip: 012 456  => HHTHTHTT
 185: HHTHTHTT rot: THHTHTHT  flip: 01234567 => HHTTHTHT
 186: HHTTHTHT rot: HTTHTHTH  flip: 0 2 4 6  => HHHHHHTT
 187: HHHHHHTT rot: TTHHHHHH  flip: 01234567 => HHTTTTTT
 188: HHTTTTTT rot: TTTTTTHH  flip: 01  45   => HHHHHHTT
 189: HHHHHHTT rot: HHHHHTTH  flip: 01234567 => HHTTTTTT
 190: HHTTTTTT rot: HHTTTTTT  flip: 0 2 4 6  => HHTHTHTT
 191: HHTHTHTT rot: HTHTTHHT  flip: 01234567 => HHTTHTHT
 192: HHTTHTHT rot: HTHTHHTT  flip: 012345   => HTHTTTTT
 193: HTHTTTTT rot: HTHTTTTT  flip: 01234567 => HHHHHTHT
 194: HHHHHTHT rot: THHHHHTH  flip: 0 2 4 6  => HHHHHTHT
 195: HHHHHTHT rot: HTHTHHHH  flip: 01234567 => HTHTTTTT
 196: HTHTTTTT rot: TTTTHTHT  flip: 01  45   => HHTHHTTT
 197: HHTHHTTT rot: HTHHTTTH  flip: 01234567 => HHHTTHTT
 198: HHHTTHTT rot: HTTHHHTT  flip: 0 2 4 6  => HHTHHTTT
 199: HHTHHTTT rot: THHTHHTT  flip: 01234567 => HHHTTHTT
 200: HHHTTHTT rot: HTTHHHTT  flip: 012 456  => HHHTTHTT
 201: HHHTTHTT rot: HHHTTHTT  flip: 01234567 => HHTHHTTT
 202: HHTHHTTT rot: HTHHTTTH  flip: 0 2 4 6  => HHTHHTTT
 203: HHTHHTTT rot: TTTHHTHH  flip: 01234567 => HHHTTHTT
 204: HHHTTHTT rot: TTHTTHHH  flip: 01  45   => HHHHHTHT
 205: HHHHHTHT rot: HHHHHTHT  flip: 01234567 => HTHTTTTT
 206: HTHTTTTT rot: TTHTHTTT  flip: 0 2 4 6  => HTHTTTTT
 207: HTHTTTTT rot: TTTHTHTT  flip: 01234567 => HHHHHTHT
 208: HHHHHTHT rot: THHHHHTH  flip: 0123     => HHTHHTTT
 209: HHTHHTTT rot: HTTTHHTH  flip: 01234567 => HHHTTHTT
 210: HHHTTHTT rot: TTHHHTTH  flip: 0 2 4 6  => HHHTTHTT
 211: HHHTTHTT rot: HTTHHHTT  flip: 01234567 => HHTHHTTT
 212: HHTHHTTT rot: TTTHHTHH  flip: 01  45   => HHHHHTHT
 213: HHHHHTHT rot: HHHHHTHT  flip: 01234567 => HTHTTTTT
 214: HTHTTTTT rot: THTHTTTT  flip: 0 2 4 6  => HHHHHTHT
 215: HHHHHTHT rot: THTHHHHH  flip: 01234567 => HTHTTTTT
 216: HTHTTTTT rot: HTTTTTHT  flip: 012 456  => HHTHHTTT
 217: HHTHHTTT rot: THHTTTHH  flip: 01234567 => HHHTTHTT
 218: HHHTTHTT rot: THTTHHHT  flip: 0 2 4 6  => HHHTTHTT
 219: HHHTTHTT rot: TTHTTHHH  flip: 01234567 => HHTHHTTT
 220: HHTHHTTT rot: THHTHHTT  flip: 01  45   => HTHTTTTT
 221: HTHTTTTT rot: TTHTHTTT  flip: 01234567 => HHHHHTHT
 222: HHHHHTHT rot: HHHTHTHH  flip: 0 2 4 6  => HTHTTTTT
 223: HTHTTTTT rot: TTTTHTHT  flip: 01234567 => HHHHHTHT
 224: HHHHHTHT rot: THTHHHHH  flip: 01234 6  => HHTHTTHT
 225: HHTHTTHT rot: HTHTTHTH  flip: 01234567 => HHTHTTHT
 226: HHTHTTHT rot: HTTHTHHT  flip: 0 2 4 6  => HHHHTTTT
 227: HHHHTTTT rot: HHTTTTHH  flip: 01234567 => HHHHTTTT
 228: HHHHTTTT rot: TTHHHHTT  flip: 01  45   => HHHHTTTT
 229: HHHHTTTT rot: TTHHHHTT  flip: 01234567 => HHHHTTTT
 230: HHHHTTTT rot: TTHHHHTT  flip: 0 2 4 6  => HHTHTTHT
 231: HHTHTTHT rot: HHTHTTHT  flip: 01234567 => HHTHTTHT
 232: HHTHTTHT rot: HHTHTTHT  flip: 012 456  => HHHHTTTT
 233: HHHHTTTT rot: TTHHHHTT  flip: 01234567 => HHHHTTTT
 234: HHHHTTTT rot: TTHHHHTT  flip: 0 2 4 6  => HHTHTTHT
 235: HHTHTTHT rot: TTHTHHTH  flip: 01234567 => HHTHTTHT
 236: HHTHTTHT rot: THTHHTHT  flip: 01  45   => HHTHTTHT
 237: HHTHTTHT rot: THTHHTHT  flip: 01234567 => HHTHTTHT
 238: HHTHTTHT rot: TTHTHHTH  flip: 0 2 4 6  => HHHHTTTT
 239: HHHHTTTT rot: TTTHHHHT  flip: 01234567 => HHHHTTTT
 240: HHHHTTTT rot: TTTHHHHT  flip: 0123     => HHHTHHHT
 241: HHHTHHHT rot: HHHTHHHT  flip: 01234567 => HTTTHTTT
 242: HTTTHTTT rot: TTHTTTHT  flip: 0 2 4 6  => HTTTHTTT
 243: HTTTHTTT rot: HTTTHTTT  flip: 01234567 => HHHTHHHT
 244: HHHTHHHT rot: HHTHHHTH  flip: 01  45   => HTTTHTTT
 245: HTTTHTTT rot: TTHTTTHT  flip: 01234567 => HHHTHHHT
 246: HHHTHHHT rot: HHHTHHHT  flip: 0 2 4 6  => HTTTHTTT
 247: HTTTHTTT rot: THTTTHTT  flip: 01234567 => HHHTHHHT
 248: HHHTHHHT rot: HHTHHHTH  flip: 012 456  => HHTTHHTT
 249: HHTTHHTT rot: HHTTHHTT  flip: 01234567 => HHTTHHTT
 250: HHTTHHTT rot: HHTTHHTT  flip: 0 2 4 6  => HHTTHHTT
 251: HHTTHHTT rot: HHTTHHTT  flip: 01234567 => HHTTHHTT
 252: HHTTHHTT rot: THHTTHHT  flip: 01  45   => HTHTHTHT
 253: HTHTHTHT rot: HTHTHTHT  flip: 01234567 => HTHTHTHT
 254: HTHTHTHT rot: HTHTHTHT  flip: 0 2 4 6  => TTTTTTTT
 255: TTTTTTTT rot: TTTTTTTT  flip: 01234567 => HHHHHHHH

Out[26]:

'HHHHHHHH'