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?*
(This same puzzle also appeared in The Riddler on 21 June 2019, with the role of the devil played by a banker. I'm not sure which is scarier.)
{HHHH}
(meaning that 4 heads is the only possibility).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'
.Move
: a set of positions to flip, such as {0, 2}
.Strategy
: an ordered list of moves. Ablindfolded player has no feedback, thus there are no decision points in the strategy.
I take the coin sequence 'HTTT'
to mean there is an 'H'
at the 12 o'clock position, then 3, , 6, and 9 o'clock in that order are 'T'
.
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 = tuple # A sequence 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.def all_moves() -> (Move,):
"List of all possible moves."
return tuple(map(Move, 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:
all_moves()
(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})
all_coins()
frozenset({'HHHH', 'HHHT', 'HHTH', 'HHTT', 'HTHH', 'HTHT', 'HTTH', 'HTTT', 'THHH', 'THHT', 'THTH', 'THTT', 'TTHH', 'TTHT', 'TTTH', 'TTTT'})
rotations('HHHT')
{'HHHT', 'HHTH', 'HTHH', 'THHH'}
flip('HHHT', {0, 2})
'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 (because if there had been 4 heads, you would have already won), leaving 15 possible coin sequences:
update(all_coins(), {0, 1, 2, 3})
frozenset({'HHHH', 'HHHT', 'HHTH', 'HHTT', 'HTHH', 'HTHT', 'HTTH', 'HTTT', 'THHH', 'THHT', 'THTH', 'THTT', 'TTHH', 'TTHT', 'TTTH'})
list(powerset([1,2,3]))
[(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]
Everything looks good so far.
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.
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: # Entries in queue are (move_sequence, end_state) pairs
(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:
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()
({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 ...
I don't have a proof, but I have some evidence that this strategy is the answer:
probably_wins
test below.The call probably_wins(strategy, k)
plays the strategy k times against each possible starting position, assuming a Devil that chooses rotations at random. Note this is dealing with concrete, individual states of the world, like HTHH
, not belief states. If probably_wins
returns False
, then the strategy is definitely flawed. If it returns True
, then the strategy is probably good, but that does not prove it will win every time (and either way probably_wins
makes no claims about being a shortest strategy).
def probably_wins(strategy, k=100) -> bool:
"Is this a winning strategy? A probabilistic algorithm."
return all('T' not in play(strategy, coins)
for coins in all_coins()
for _ in range(k))
def play(strategy, coins) -> Coins:
"Play strategy for one game against a random Devil, starting with coins; return final state of coins."
for move in strategy:
if 'T' not in coins: return coins
coins = random.choice(list(rotations(coins)))
coins = flip(coins, move)
return coins
probably_wins(strategy=coin_search())
True
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 still 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 resulting string and (arbitraily) choose the one that comes first in alphabetical order (which would be 'HHHT'
for the four coin sequences mentioned here).
def Coins(coins) -> str:
"The canonical representation (after rotation) of the 'H'/'T' sequence."
return min(rotations(''.join(coins)))
assert Coins('HHHT') == Coins('HHTH') == Coins('HTHH') == Coins('THHH') == 'HHHT'
With Coins
redefined, the result of all_coins()
is different:
all_coins()
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.
Now for canonical 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.)
def all_moves() -> [Move]:
"All canonical moves."
return [Move(i for i in range(4) if coins[i] == 'H')
for coins in sorted(all_coins())]
all_moves()
[{0, 1, 2, 3}, {0, 1, 2}, {0, 1}, {0, 2}, {0}, set()]
So again we've gone down from 16 to 6.
Let's make sure we didn't break anything and that we still get the same 15-step solution:
coin_search()
({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})
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
, as well as probably_wins
. In each case the chage is trivial.
def all_moves(N=4) -> [Move]:
"All canonical moves for a sequence of N coins."
return [Move(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)
def probably_wins(strategy, N=4, k=1000) -> bool:
"Is this a winning strategy? A probabilistic algorithm."
return all('T' not in play(strategy, coins)
for coins in all_coins(N)
for _ in range(k))
Let's test the new definitions:
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'})
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?
{N: len(all_coins(N))
for N in range(1, 13)}
{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 12, 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 2352 belief states, which is more than a googol. However, we should be able to easily handle up to N=7, because 220 is only a million.
{N: coin_search(N) for N in range(1, 8)}
{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. Hmmm. That suggests ...
For N = 8, there are 236 = 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 less than a second, but this one should take more than a minute. Let's see:
%time strategy8 = coin_search(8)
CPU times: user 1min 11s, sys: 122 ms, total: 1min 11s Wall time: 1min 11s
probably_wins(strategy8, N=8)
True
len(strategy8)
255
Eureka! That's evidence in favor of the conjecture. But not proof. And it leaves many questions unanswered:
coin_search(9)
should take about 20 million minutes.John Lamping came up with this proof of the conjecture:
First, consider n = 3. If the three coins start out different, the devil can guarantee that they are still different after any flip you call for. If you ask for 1 flip, the devil makes the flip apply to one of the two matching coins. If you ask for 2 flips, the devil makes the flip apply to a pair of non-matching coins. If you ask for all 3 flips, they will still disagree, as well. So there is no strategy for 3 coins.
We can generalize this to any prime number of coins, p, different from 2. If the p coins start out different, the devil can still make sure that any flip will leave the coins not matching. If the flip is of all coins, they will still disagree. Suppose it is not of all coins. The devil tries the flip on the current orientation of the table. If that leaves coins different, good. If not, the devil rotates the table by one position. We show that in that position, the coins will disagree after the flip. We know that there are at least two coins that the player asked to be flipped differently. With an odd number of coins, (LFFLF, for example) we also know there must be two adjacent coins that the player asked to be flipped the same. So there must be a subsequence that is either LFF or FLL. We know that the coins initially agreed on the last two positions, because the flip led to all the coins matching. After the rotation, those two positions will be flipped differently, leading to different coins.
Now, consider any multiple of p (say 12, for example, 3 × 4). We can pick out p equally spaced points on the table (every 4th coin in the example), and apply the devil's strategy for p coins to those p coins: If those p start out different, the devil can always make sure they stay different.
So for any number of coins that has a factor other than 2, the devil wins.
Now we have to show that for any number that is a power of 2, the devil loses. We proceed by induction. Suppose that we have a sequence of flip operations that guarantees a win for $2^n$ coins. We assume that there are $2^n - 1$ of them, $o_1, ... o_{2^n-1}$. Each operation specifies, for each of the n coins, whether to flip it or to leave alone, like LFFF. We create two new sequences, also of $2^n-1$ operations, but operating on $2^{n+1}$ coins. The first, called $d$ for double, does $o$ on the first $2^n$ coins, and then repeats the same pattern on the second $2^n$ coins. So if $o_i$ is LFFF, $d_i$ is LFFFLFFF. The second, for single, does $o$ on the first $2^n$ coins, and leaves the second $2^n$ coins alone. So if $o_i$ is LFFF, $s_i$ is LFFFLLLL. Then the following sequence of operations guarantees a win on $2^(n+1)$ coins:
$d_1, ... d_{2^n-1}, s_1, d_1, ... d_{2^n-1}, s_2, .... d_1, ... d_{2^n-1}, s_{2^n-1}, d_1, ... d_{2^n-1}$
That is, we do each operation of $s$, with a complete copy of $d$ between each $s$ operation, as well as at the beginning and at the end. The total number of operations is $2^n×(2^n - 1) + 2^n - 1 = 2^{n+1} -1.$
Before explaining why this works, lets use it to generate the sequences we know. For one coin, we win with a sequence of a single operation, F. For two coins, d is the single operation FF, while s is the single operation FL. Combining them according to the procedure gives FF, FL, FF. For four coins, d is FFFF, FLFL, FFFF, while s is FFLL, FLLL, FFLL, combining them gives FFFF, FLFL, FFFF, FFLL, FFFF, FLFL, FFFF, FLLL, FFFF, FLFL, FFFF, FFLL, FFFF, FLFL, FFFF. That is the answer that we all came up with.
To see why it works, consider all pairs of opposite coins on the table with $2^{n+1}$ coins, and consider the XOR of each pair of opposite coins. There are $2^n$ of these XORs, and there is a natural correspondence between each XOR pair and a single coin in the original game. Now, s complements the XOR of a pair exactly when o flips the corresponding coin in the original game. Meanwhile, every operation in d leaves the XOR of each pair unchanged. So, since the sequence of o operations explores all coins positions, the sequence of s operations explores all XOR states. And the interposed d operations don't interfere with that exploration. In one of those states, the XORs will all be 0, meaning that each pair of opposite coins will agree. But in that state, when opposite pairs of coins agree, d is equivalent to o, just operating on pairs of coins, rather than single coins. So it explores all possible combinations of heads and tails, given that opposites agree. That will include the state where all coins are heads.
Can I understand what is going on by showing how belief states are whittled down?
def show(moves, N=4):
"For each move, print the move number, move, and belief state."
belief = all_coins(N)
order = sorted(belief)
print('Move| Flips | Belief State')
print('----+----------+-------------')
def show(i, move, order=sorted(belief)):
print(f'{i:3} | {movestr(move, N):8} | {beliefstr(belief, order)}')
show(0, set())
for (i, move) in enumerate(moves, 1):
belief = update(belief, move)
show(i, move)
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:
show(coin_search(2), 2)
Move| Flips | Belief State ----+----------+------------- 0 | | HH HT TT 1 | 01 | HH HT 2 | 0 | HH TT 3 | 01 | HH
show(coin_search(4))
Move| Flips | Belief State ----+----------+------------- 0 | | HHHH HHHT HHTT HTHT HTTT TTTT 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:
def play(strategy, coins, verbose=False):
"Play strategy for one game against a random Devil, starting with coins; 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(f'{i:4d}: {coins0} | rot: {coins1} | flip: {movestr(move, N)} {coins}')
return coins
play(coin_search(4), 'HHTH', True)
1: HHTH | rot: THHH | flip: 0123 HTTT 2: HTTT | rot: THTT | flip: 0 2 HHHT 3: HHHT | rot: THHH | flip: 0123 HTTT 4: HTTT | rot: THTT | flip: 01 HTTT 5: HTTT | rot: THTT | flip: 0123 HHHT 6: HHHT | rot: HHHT | flip: 0 2 HTTT 7: HTTT | rot: THTT | flip: 0123 HHHT 8: HHHT | rot: THHH | flip: 012 HHTT 9: HHTT | rot: TTHH | flip: 0123 HHTT 10: HHTT | rot: HTTH | flip: 0 2 HHTT 11: HHTT | rot: TTHH | flip: 0123 HHTT 12: HHTT | rot: THHT | flip: 01 HTHT 13: HTHT | rot: HTHT | flip: 0123 HTHT 14: HTHT | rot: THTH | flip: 0 2 HHHH
'HHHH'
play(strategy8, 'HTTHTTHT', True)
1: HTTHTTHT | rot: TTHTTHTH | flip: 01234567 HHTHHTHT 2: HHTHHTHT | rot: THHTHTHH | flip: 0 2 4 6 HHHTTTTT 3: HHHTTTTT | rot: HTTTTTHH | flip: 01234567 HHHHHTTT 4: HHHHHTTT | rot: HTTTHHHH | flip: 01 45 HHTHTTTT 5: HHTHTTTT | rot: TTHHTHTT | flip: 01234567 HHHHTTHT 6: HHHHTTHT | rot: THHHHTTH | flip: 0 2 4 6 HHHHTHTT 7: HHHHTHTT | rot: TTHHHHTH | flip: 01234567 HHTTTTHT 8: HHTTTTHT | rot: HTTTTHTH | flip: 012 456 HHTHHTHT 9: HHTHHTHT | rot: THHTHHTH | flip: 01234567 HTHTTHTT 10: HTHTTHTT | rot: HTHTTHTT | flip: 0 2 4 6 HHHTTTTT 11: HHHTTTTT | rot: TTTHHHTT | flip: 01234567 HHHHHTTT 12: HHHHHTTT | rot: HHHHTTTH | flip: 01 45 HHHHTHTT 13: HHHHTHTT | rot: THHHHTHT | flip: 01234567 HHTTTTHT 14: HHTTTTHT | rot: TTHTHHTT | flip: 0 2 4 6 HHTHTTTT 15: HHTHTTTT | rot: TTHHTHTT | flip: 01234567 HHHHTTHT 16: HHHHTTHT | rot: THTHHHHT | flip: 0123 HHHTHTHT 17: HHHTHTHT | rot: HTHTHTHH | flip: 01234567 HTHTHTTT 18: HTHTHTTT | rot: HTHTTTHT | flip: 0 2 4 6 HTTTTTTT 19: HTTTTTTT | rot: THTTTTTT | flip: 01234567 HHHHHHHT 20: HHHHHHHT | rot: HHHTHHHH | flip: 01 45 HHTTHTTT 21: HHTTHTTT | rot: THHTTHTT | flip: 01234567 HHHTTHHT 22: HHHTTHHT | rot: TTHHTHHH | flip: 0 2 4 6 HHHTHHTT 23: HHHTHHTT | rot: HHTTHHHT | flip: 01234567 HHTTTHTT 24: HHTTTHTT | rot: HHTTTHTT | flip: 012 456 HTHTHTTT 25: HTHTHTTT | rot: TTTHTHTH | flip: 01234567 HHHTHTHT 26: HHHTHTHT | rot: HHTHTHTH | flip: 0 2 4 6 HHHHHHHT 27: HHHHHHHT | rot: HHHHHTHH | flip: 01234567 HTTTTTTT 28: HTTTTTTT | rot: TTTTTHTT | flip: 01 45 HHTTHTTT 29: HHTTHTTT | rot: HTTTHHTT | flip: 01234567 HHHTTHHT 30: HHHTTHHT | rot: HTTHHTHH | flip: 0 2 4 6 HHTTTHTT 31: HHTTTHTT | rot: HTTHHTTT | flip: 01234567 HHHTHHTT 32: HHHTHHTT | rot: HHTHHTTH | flip: 01234 6 HHTTHTTT 33: HHTTHTTT | rot: TTHTTTHH | flip: 01234567 HHHTTHHT 34: HHHTTHHT | rot: THHHTTHH | flip: 0 2 4 6 HHHTHHTT 35: HHHTHHTT | rot: THHTTHHH | flip: 01234567 HHTTTHTT 36: HHTTTHTT | rot: THTTHHTT | flip: 01 45 HTTTTTTT 37: HTTTTTTT | rot: TTTTTHTT | flip: 01234567 HHHHHHHT 38: HHHHHHHT | rot: HHHHHHTH | flip: 0 2 4 6 HHHTHTHT 39: HHHTHTHT | rot: HTHTHTHH | flip: 01234567 HTHTHTTT 40: HTHTHTTT | rot: HTHTTTHT | flip: 012 456 HHTTTHTT 41: HHTTTHTT | rot: HHTTTHTT | flip: 01234567 HHHTHHTT 42: HHHTHHTT | rot: THHHTHHT | flip: 0 2 4 6 HHHTTHHT 43: HHHTTHHT | rot: TTHHTHHH | flip: 01234567 HHTTHTTT 44: HHTTHTTT | rot: TTHHTTHT | flip: 01 45 HHHHHHHT 45: HHHHHHHT | rot: HHHHTHHH | flip: 01234567 HTTTTTTT 46: HTTTTTTT | rot: TTHTTTTT | flip: 0 2 4 6 HTHTHTTT 47: HTHTHTTT | rot: THTTTHTH | flip: 01234567 HHHTHTHT 48: HHHTHTHT | rot: HTHTHHHT | flip: 0123 HHHHTTHT 49: HHHHTTHT | rot: TTHTHHHH | flip: 01234567 HHTHTTTT 50: HHTHTTTT | rot: TTHHTHTT | flip: 0 2 4 6 HHHHTHTT 51: HHHHTHTT | rot: HHTHTTHH | flip: 01234567 HHTTTTHT 52: HHTTTTHT | rot: THTHHTTT | flip: 01 45 HTHTTHTT 53: HTHTTHTT | rot: THTTHTTH | flip: 01234567 HHTHHTHT 54: HHTHHTHT | rot: HHTHHTHT | flip: 0 2 4 6 HHHTTTTT 55: HHHTTTTT | rot: TTTTTHHH | flip: 01234567 HHHHHTTT 56: HHHHHTTT | rot: THHHHHTT | flip: 012 456 HTHTTHTT 57: HTHTTHTT | rot: THTHTTHT | flip: 01234567 HHTHHTHT 58: HHTHHTHT | rot: HTHHTHHT | flip: 0 2 4 6 HHHTTTTT 59: HHHTTTTT | rot: HHTTTTTH | flip: 01234567 HHHHHTTT 60: HHHHHTTT | rot: HHHHHTTT | flip: 01 45 HHTHTTTT 61: HHTHTTTT | rot: THTTTTHH | flip: 01234567 HHHHTTHT 62: HHHHTTHT | rot: THTHHHHT | flip: 0 2 4 6 HHHHTHTT 63: HHHHTHTT | rot: HHHTHTTH | flip: 01234567 HHTTTTHT 64: HHTTTTHT | rot: TTTHTHHT | flip: 012345 HHHTHTHT 65: HHHTHTHT | rot: THTHTHHH | flip: 01234567 HTHTHTTT 66: HTHTHTTT | rot: HTHTHTTT | flip: 0 2 4 6 HTTTTTTT 67: HTTTTTTT | rot: TTTTTTTH | flip: 01234567 HHHHHHHT 68: HHHHHHHT | rot: HHHHTHHH | flip: 01 45 HHHTHHTT 69: HHHTHHTT | rot: HHHTHHTT | flip: 01234567 HHTTTHTT 70: HHTTTHTT | rot: TTHHTTTH | flip: 0 2 4 6 HHHTTHHT 71: HHHTTHHT | rot: HTHHHTTH | flip: 01234567 HHTTHTTT 72: HHTTHTTT | rot: THTTTHHT | flip: 012 456 HTHTHTTT 73: HTHTHTTT | rot: TTHTHTHT | flip: 01234567 HHHTHTHT 74: HHHTHTHT | rot: THHHTHTH | flip: 0 2 4 6 HHHHHHHT 75: HHHHHHHT | rot: HHHTHHHH | flip: 01234567 HTTTTTTT 76: HTTTTTTT | rot: TTTTTHTT | flip: 01 45 HHTTHTTT 77: HHTTHTTT | rot: HHTTHTTT | flip: 01234567 HHHTTHHT 78: HHHTTHHT | rot: TTHHTHHH | flip: 0 2 4 6 HHHTHHTT 79: HHHTHHTT | rot: HHTHHTTH | flip: 01234567 HHTTTHTT 80: HHTTTHTT | rot: THTTHHTT | flip: 0123 HHHHTTHT 81: HHHHTTHT | rot: TTHTHHHH | flip: 01234567 HHTHTTTT 82: HHTHTTTT | rot: HTTTTHHT | flip: 0 2 4 6 HHTTTTHT 83: HHTTTTHT | rot: HTHHTTTT | flip: 01234567 HHHHTHTT 84: HHHHTHTT | rot: HHHHTHTT | flip: 01 45 HHHTTTTT 85: HHHTTTTT | rot: THHHTTTT | flip: 01234567 HHHHHTTT 86: HHHHHTTT | rot: HHHHHTTT | flip: 0 2 4 6 HTHTTHTT 87: HTHTTHTT | rot: TTHTTHTH | flip: 01234567 HHTHHTHT 88: HHTHHTHT | rot: THHTHTHH | flip: 012 456 HHTTTTHT 89: HHTTTTHT | rot: THHTTTTH | flip: 01234567 HHHHTHTT 90: HHHHTHTT | rot: HHTHTTHH | flip: 0 2 4 6 HHHHTTHT 91: HHHHTTHT | rot: HTTHTHHH | flip: 01234567 HHTHTTTT 92: HHTHTTTT | rot: HTTTTHHT | flip: 01 45 HTHTTHTT 93: HTHTTHTT | rot: THTTHTHT | flip: 01234567 HHTHHTHT 94: HHTHHTHT | rot: HTHTHHTH | flip: 0 2 4 6 HHHTTTTT 95: HHHTTTTT | rot: TTHHHTTT | flip: 01234567 HHHHHTTT 96: HHHHHTTT | rot: HHTTTHHH | flip: 01234 6 HHHHTHTT 97: HHHHTHTT | rot: TTHHHHTH | flip: 01234567 HHTTTTHT 98: HHTTTTHT | rot: TTHTHHTT | flip: 0 2 4 6 HHTHTTTT 99: HHTHTTTT | rot: TTTHHTHT | flip: 01234567 HHHHTTHT 100: HHHHTTHT | rot: HHTTHTHH | flip: 01 45 HHHTTTTT 101: HHHTTTTT | rot: HHTTTTTH | flip: 01234567 HHHHHTTT 102: HHHHHTTT | rot: HHHHTTTH | flip: 0 2 4 6 HHTHHTHT 103: HHTHHTHT | rot: HTHHTHHT | flip: 01234567 HTHTTHTT 104: HTHTTHTT | rot: HTTHTTHT | flip: 012 456 HHHHHTTT 105: HHHHHTTT | rot: TTHHHHHT | flip: 01234567 HHHTTTTT 106: HHHTTTTT | rot: HHTTTTTH | flip: 0 2 4 6 HHTHHTHT 107: HHTHHTHT | rot: THHTHHTH | flip: 01234567 HTHTTHTT 108: HTHTTHTT | rot: THTTHTTH | flip: 01 45 HHTTTTHT 109: HHTTTTHT | rot: HTTTTHTH | flip: 01234567 HHHHTHTT 110: HHHHTHTT | rot: TTHHHHTH | flip: 0 2 4 6 HHHHTTHT 111: HHHHTTHT | rot: THHHHTTH | flip: 01234567 HHTHTTTT 112: HHTHTTTT | rot: HTTTTHHT | flip: 0123 HHHTHHTT 113: HHHTHHTT | rot: HHTTHHHT | flip: 01234567 HHTTTHTT 114: HHTTTHTT | rot: TTHHTTTH | flip: 0 2 4 6 HHHTTHHT 115: HHHTTHHT | rot: HHHTTHHT | flip: 01234567 HHTTHTTT 116: HHTTHTTT | rot: THHTTHTT | flip: 01 45 HTHTHTTT 117: HTHTHTTT | rot: TTTHTHTH | flip: 01234567 HHHTHTHT 118: HHHTHTHT | rot: THTHTHHH | flip: 0 2 4 6 HHHHHHHT 119: HHHHHHHT | rot: HHHHTHHH | flip: 01234567 HTTTTTTT 120: HTTTTTTT | rot: TTHTTTTT | flip: 012 456 HHHTHHTT 121: HHHTHHTT | rot: HTHHTTHH | flip: 01234567 HHTTTHTT 122: HHTTTHTT | rot: TTHHTTTH | flip: 0 2 4 6 HHHTTHHT 123: HHHTTHHT | rot: THHHTTHH | flip: 01234567 HHTTHTTT 124: HHTTHTTT | rot: TTTHHTTH | flip: 01 45 HHHTHTHT 125: HHHTHTHT | rot: HHTHTHTH | flip: 01234567 HTHTHTTT 126: HTHTHTTT | rot: TTTHTHTH | flip: 0 2 4 6 HHHHHHHT 127: HHHHHHHT | rot: HTHHHHHH | flip: 01234567 HTTTTTTT 128: HTTTTTTT | rot: THTTTTTT | flip: 0123456 HHHHHTHT 129: HHHHHTHT | rot: HHHHHTHT | flip: 01234567 HTHTTTTT 130: HTHTTTTT | rot: TTTHTHTT | flip: 0 2 4 6 HHHHHTHT 131: HHHHHTHT | rot: HTHHHHHT | flip: 01234567 HTHTTTTT 132: HTHTTTTT | rot: TTTHTHTT | flip: 01 45 HHTHHTTT 133: HHTHHTTT | rot: THHTTTHH | flip: 01234567 HHHTTHTT 134: HHHTTHTT | rot: HHHTTHTT | flip: 0 2 4 6 HHHTTHTT 135: HHHTTHTT | rot: THTTHHHT | flip: 01234567 HHTHHTTT 136: HHTHHTTT | rot: HTTTHHTH | flip: 012 456 HHTHHTTT 137: HHTHHTTT | rot: HHTTTHHT | flip: 01234567 HHHTTHTT 138: HHHTTHTT | rot: TTHTTHHH | flip: 0 2 4 6 HHTHHTTT 139: HHTHHTTT | rot: TTHHTHHT | flip: 01234567 HHHTTHTT 140: HHHTTHTT | rot: HHHTTHTT | flip: 01 45 HTHTTTTT 141: HTHTTTTT | rot: TTTHTHTT | flip: 01234567 HHHHHTHT 142: HHHHHTHT | rot: HHTHTHHH | flip: 0 2 4 6 HHHHHTHT 143: HHHHHTHT | rot: HHHHTHTH | flip: 01234567 HTHTTTTT 144: HTHTTTTT | rot: TTHTHTTT | flip: 0123 HHTHHTTT 145: HHTHHTTT | rot: TTHHTHHT | flip: 01234567 HHHTTHTT 146: HHHTTHTT | rot: HTTHHHTT | flip: 0 2 4 6 HHTHHTTT 147: HHTHHTTT | rot: TTTHHTHH | flip: 01234567 HHHTTHTT 148: HHHTTHTT | rot: HHHTTHTT | flip: 01 45 HTHTTTTT 149: HTHTTTTT | rot: THTTTTTH | flip: 01234567 HHHHHTHT 150: HHHHHTHT | rot: THHHHHTH | flip: 0 2 4 6 HHHHHTHT 151: HHHHHTHT | rot: HHHTHTHH | flip: 01234567 HTHTTTTT 152: HTHTTTTT | rot: HTHTTTTT | flip: 012 456 HHHTTHTT 153: HHHTTHTT | rot: HHHTTHTT | flip: 01234567 HHTHHTTT 154: HHTHHTTT | rot: TTTHHTHH | flip: 0 2 4 6 HHTHHTTT 155: HHTHHTTT | rot: THHTTTHH | flip: 01234567 HHHTTHTT 156: HHHTTHTT | rot: TTHHHTTH | flip: 01 45 HHHHHTHT 157: HHHHHTHT | rot: THTHHHHH | flip: 01234567 HTHTTTTT 158: HTHTTTTT | rot: TTHTHTTT | flip: 0 2 4 6 HTHTTTTT 159: HTHTTTTT | rot: THTTTTTH | flip: 01234567 HHHHHTHT 160: HHHHHTHT | rot: THTHHHHH | flip: 01234 6 HHTHTTHT 161: HHTHTTHT | rot: TTHTHHTH | flip: 01234567 HHTHTTHT 162: HHTHTTHT | rot: THTTHTHH | flip: 0 2 4 6 HHHHTTTT 163: HHHHTTTT | rot: THHHHTTT | flip: 01234567 HHHHTTTT 164: HHHHTTTT | rot: HHHTTTTH | flip: 01 45 HHTHTTHT 165: HHTHTTHT | rot: HHTHTTHT | flip: 01234567 HHTHTTHT 166: HHTHTTHT | rot: TTHTHHTH | flip: 0 2 4 6 HHHHTTTT 167: HHHHTTTT | rot: TTTHHHHT | flip: 01234567 HHHHTTTT 168: HHHHTTTT | rot: HHHHTTTT | flip: 012 456 HHHHTTTT 169: HHHHTTTT | rot: TTHHHHTT | flip: 01234567 HHHHTTTT 170: HHHHTTTT | rot: TTTHHHHT | flip: 0 2 4 6 HHTHTTHT 171: HHTHTTHT | rot: TTHTHHTH | flip: 01234567 HHTHTTHT 172: HHTHTTHT | rot: TTHTHHTH | flip: 01 45 HHHHTTTT 173: HHHHTTTT | rot: HTTTTHHH | flip: 01234567 HHHHTTTT 174: HHHHTTTT | rot: HTTTTHHH | flip: 0 2 4 6 HHTHTTHT 175: HHTHTTHT | rot: THHTHTTH | flip: 01234567 HHTHTTHT 176: HHTHTTHT | rot: TTHTHHTH | flip: 0123 HHHTHHHT 177: HHHTHHHT | rot: HTHHHTHH | flip: 01234567 HTTTHTTT 178: HTTTHTTT | rot: TTTHTTTH | flip: 0 2 4 6 HHHTHHHT 179: HHHTHHHT | rot: HHHTHHHT | flip: 01234567 HTTTHTTT 180: HTTTHTTT | rot: TTHTTTHT | flip: 01 45 HHHTHHHT 181: HHHTHHHT | rot: HHHTHHHT | flip: 01234567 HTTTHTTT 182: HTTTHTTT | rot: THTTTHTT | flip: 0 2 4 6 HHHTHHHT 183: HHHTHHHT | rot: HHTHHHTH | flip: 01234567 HTTTHTTT 184: HTTTHTTT | rot: TTTHTTTH | flip: 012 456 HHHHHHHH
'HHHHHHHH'