14
\$\begingroup\$

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.

\$\endgroup\$
  • 4
    \$\begingroup\$ I'm rather intrigued by the fact that the input and output have equal size. Do you have a proof or citation for this fact? I wonder if there's a way to compute this function that intuitively preserves size. \$\endgroup\$ – xnor Jan 13 '15 at 20:51
  • 2
    \$\begingroup\$ Your test case #5 contradicts your fun fact... \$\endgroup\$ – mbomb007 Jan 13 '15 at 21:55
  • 3
    \$\begingroup\$ @mbomb007 Test case #5 lists 11101 twice; the fun fact still holds for sets. Zgarb, may the input contain repeated elements, or was this an error? \$\endgroup\$ – xnor Jan 13 '15 at 22:56
  • \$\begingroup\$ @xnor This is something that came up in my research a while ago. I have a proof in this preprint, page 16, but it is essentially the same as yours. \$\endgroup\$ – Zgarb Jan 14 '15 at 7:41
  • 1
    \$\begingroup\$ @xnor Intuitively, at any turn, if both 0 and 1 are winning choices, then either Alice or Bob can choose the next move. If there is only one winning option then Alice must choose next. Thus the number of choices for the string is the same as the number of choices of winning strategy. Hardly rigorous, but compelling. \$\endgroup\$ – Alchymist Jan 14 '15 at 10:56
1
\$\begingroup\$

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
\$\endgroup\$
13
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ Running your code gives TypeError: 'int' object is not subscriptable. Do you have a link to a runnable program? I just pasted it and ran it with print f([0001,1011,0010],4) \$\endgroup\$ – mbomb007 Jan 13 '15 at 22:48
  • \$\begingroup\$ @mbomb007 The function needs to be invoked like f({'000','001','010','011','100','101','110','111'},3). Do you get an error this way? \$\endgroup\$ – xnor Jan 13 '15 at 22:51
  • \$\begingroup\$ Ah, I didn't see I was missing quotes, thanks. It also runs with print f(['0001','1011','0010'],4) \$\endgroup\$ – mbomb007 Jan 13 '15 at 22:53
  • \$\begingroup\$ If you want to run the program knowing n independent of parameters it would be n=len(S[0])if S!=[]else 0 \$\endgroup\$ – mbomb007 Jan 13 '15 at 23:01
  • \$\begingroup\$ Run it here: repl.it/7yI \$\endgroup\$ – mbomb007 Jan 13 '15 at 23:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.