Winning Strategies for a String Construction Game

Question

Background

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-n string t containing the letters A and 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] = 0. The second turn is also Alice's, and she chooses w[1] = 0. Bob has the third turn, and he chooses w[2] = 0. On the final turn, Alice chooses w[3] = 1. The resulting word, 0001, is found in G, so Alice wins the game.

Now, if Bob had chosen w[2] = 1, Alice could have chosen w[3] = 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 G:

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.

Input

You are given as input the length n, and the set G as a (possibly empty) list of strings of length n.

Output

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.

Detailed Rules

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.

Test Cases

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]

Fun Fact

The number of turn orders in the output is always equal to the number of words in the goal set.

Answer 1

Python, 132

def f(S,n):
 if n<1:return S
 a,b=[f({x[1:]for x in S if x[0]==c},n-1)for c in'01']
 return{'A'+y for y in a|b}|{'B'+y for y in a&b}

Example run:

f({'000','001','010','011','100','101','110','111'},3) == 
{'ABA', 'ABB', 'AAA', 'AAB', 'BBB', 'BBA', 'BAB', 'BAA'}

This is only kind-of golfed, mostly to show the algorithm. The inputs and output are sets of strings. Python doesn't seem to have the right features to express parts of this compactly, so it would be cool if someone wrote this in a better-suited language.

Here's how the recursion can be expressed mathematically. Unfortunately, PPCG still lacks math rendering, so I'll have to use code blocks.

The objects of interest are sets of strings. Let | represent set union and & represent set intersection.

If c is a character, let c#S represent prepending the character c to all strings in S. Conversely, let the contraction c\S be the one-character-shorter strings of S that follow initial character c, e.g., 0\{001,010,110,111} = {01,10}.

We can uniquely split a set of strings S with chars in 01 by their first character.

S = 0#(0\S) | 1#(1\S)

Then, we can express the desired function f as follows, with the bases cases in the first two lines and the recursive can in the last line:

f({})   = {}
f({''}) = {''}
f(S)    = A#(f(0\S)|f(1\S)) | B#(f(0\S)&f(1\S))

Note that we don't need to use the length n.

Why does this work? Let's think about the move-strings that let Alice win for a set of strings S.

If the first character is A, Alice can pick the first move ('0' or '1'), letting her choose to reduce the problem to S0 or S1. So now the remaining move-string has to be in at least one of f(S0) or f(S1), hence we take their union |.

Similarly, if the first character is 'B', Bob gets to pick, and he'll pick the worse one for Alice, so the remaining move-string must be in the intersection (&).

The base cases simply check if S is empty or not at the end. If we're tracking the length of the strings n, by subtracting 1 each time we recurse, the bases can instead be written:

f(S) = S if n==0

The recursive solution also explains the fun fact that f(S) has the same size as S. It's true for the base cases, and for the inductive case

f(S) = A#(f(0\S)|f(1\S)) | B#(f(0\S)&f(1\S))

we have

size(f(S)) = size(A#(f(0\S)|f(1\S)) | B#(f(0\S)&f(1\S)))
           = size(A#(f(0\S)|f(1\S))) + size(B#(f(0\S)&f(1\S))))
           = size((f(0\S)|f(1\S))) + size((f(0\S)&f(1\S))))
           = size(f(0\S)) + size(f(1\S))  [since size(X|Y) + size(X&Y) = size(X) + size(Y)]
           = size(0\S) + size(1\S)
           = size(S)

Answer 2

Dyalog APL, 59 bytes

{(a≡,⊂⍬)∨0=⍴a←∪⍵:a⋄(∇h/t)(('A',¨∪),'B',¨∩)∇(~h←⊃¨a)/t←1↓¨a}

Same algorithm as in @xnor's solution.

(a≡,⊂⍬)∨0=⍴a←∪⍵:a
           a←∪⍵    ⍝ "a" is the unique items of the argument
        0=⍴a       ⍝ is it empty?
 a≡,⊂⍬             ⍝ is it a vector that contains the empty vector?
       ∨       :a  ⍝ if any of the above, return "a"

(∇h/t)(('A',¨∪),'B',¨∩)∇(~h←⊃¨a)/t←1↓¨a
                                 t←1↓¨a  ⍝ drop an item from each of "a" and call that "t"
                         ~h←⊃¨a          ⍝ first of each of "a", call that "h", then negate it
                                /        ⍝ use "~h" as a boolean mask to select from "t"
                       ∇                 ⍝ apply a recursive call
(∇h/t)                                   ⍝ use "h" as a boolean mask on "t", then a recursive call
      (('A',¨∪),'B',¨∩)                  ⍝ apply a fork on the results from the two recursive calls:
       ('A',¨∪)                          ⍝   prepend 'A' to each of the intersection
               ,                         ⍝   concatenated with
                'B',¨∪                   ⍝   prepend 'B' to each of the union