Alice and Bob play a game called construct a binary word. To play the game, you fix a length
n >= 0, a set
G of length-
n binary words called the goal set, and a length-
t containing the letters
B, called the turn order. The game lasts for
n turns, and on turn
i, the player defined by
t[i] selects a bit
w[i]. When the game is over, the players look at the binary word
w they have constructed. If this word is found in the goal set
G, Alice wins the game; otherwise, Bob wins.
For example, let's fix
n = 4,
G = [0001,1011,0010], and
t = AABA. Alice gets the first turn, and she chooses
w = 0. The second turn is also Alice's, and she chooses
w = 0. Bob has the third turn, and he chooses
w = 0. On the final turn, Alice chooses
w = 1. The resulting word,
0001, is found in
G, so Alice wins the game.
Now, if Bob had chosen
w = 1, Alice could have chosen
w = 0 in her final turn, and still win. This means that Alice can win the game no matter how Bob plays. In this situation, Alice has a winning strategy. This strategy can be visualized as a labeled binary tree, which branches at the levels corresponding to Bob's turns, and whose every branch contains a word from
A A B A -0-0-0-1 \ 1-0
Alice plays by simply following the branches on her turn; no matter which branch Bob chooses, Alice eventually wins.
You are given as input the length
n, and the set
G as a (possibly empty) list of strings of length
Your output is the list of turn orders for which Alice has a winning strategy, which is equivalent to the existence of a binary tree as described above. The order of the turn orders does not matter, but duplicates are forbidden.
You can write a full program or a function. In the case of a program, you can choose the delimiter for the input and output, but it must be the same for both. The shortest byte count wins, and standard loopholes are disallowed.
3  ->  3 [000,001,010,011,100,101,110,111] -> [AAA,AAB,ABA,ABB,BAA,BAB,BBA,BBB] 4 [0001,1011,0010] -> [AAAA,BAAA,AABA] 4 [0001,1011,0010,0110,1111,0000] -> [AAAA,BAAA,ABAA,BBAA,AABA,AAAB] 5 [00011,00110,00111,11110,00001,11101,10101,01010,00010] -> [AAAAA,BAAAA,ABAAA,BBAAA,AABAA,AAABA,BAABA,AAAAB,AABAB]
The number of turn orders in the output is always equal to the number of words in the goal set.