fundo

Alice e Bob jogam um jogo chamado construir uma palavra binária . Para jogar, você fixa um comprimento n >= 0, um conjunto Gde npalavras binárias chamadas de conjunto de metas e uma nsequência tcontendo as letras Ae Bchamada de ordem do turno . O jogo dura por nturnos e, por sua vez i, o jogador definido por t[i]seleciona um pouco w[i]. Quando o jogo termina, os jogadores olham para a palavra binária que weles construíram. Se essa palavra for encontrada no objetivo definido G, Alice vence o jogo; caso contrário, Bob vence.

Por exemplo, vamos consertar n = 4, G = [0001,1011,0010]e t = AABA. Alice recebe o primeiro turno e escolhe w[0] = 0. O segundo turno também é de Alice, e ela escolhe w[1] = 0. Bob tem o terceiro turno e ele escolhe w[2] = 0. No turno final, Alice escolhe w[3] = 1. A palavra resultante,, 0001é encontrada em G, então Alice vence o jogo.

Agora, se Bob tivesse escolhido w[2] = 1, Alice poderia ter escolhido w[3] = 0em seu turno final e ainda vencer. Isso significa que Alice pode ganhar o jogo, não importa como Bob jogue. Nesta situação, Alice tem uma estratégia vencedora . Essa estratégia pode ser visualizada como uma árvore binária rotulada, que se ramifica nos níveis correspondentes aos turnos de Bob e cuja cada ramificação contém uma palavra de G:

A A B A

-0-0-0-1
    \
     1-0

Alice toca simplesmente seguindo os galhos na sua vez; não importa qual ramo Bob escolher, Alice finalmente vence.

Entrada

Você recebe como entrada o comprimento ne o conjunto Gcomo uma lista (possivelmente vazia) de cadeias de comprimento n.

Resultado

Sua saída é a lista de ordens de turno para as quais Alice possui uma estratégia vencedora, que é equivalente à existência de uma árvore binária, conforme descrito acima. A ordem das ordens de turno não importa, mas duplicatas são proibidas.

Regras detalhadas

Você pode escrever um programa completo ou uma função. No caso de um programa, você pode escolher o delimitador para entrada e saída, mas deve ser o mesmo para ambos. A menor contagem de bytes vence e as brechas padrão não são permitidas.

Casos de teste

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]

Fato engraçado

O número de ordens de turno na saída é sempre igual ao número de palavras no conjunto de metas.

Dyalog APL, 59 bytes

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

O mesmo algoritmo da solução do @ xnor.

(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

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}

Exemplo de execução:

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

Isso é apenas um tipo de jogo de golfe, principalmente para mostrar o algoritmo. As entradas e saídas são conjuntos de strings. O Python não parece ter os recursos certos para expressar partes disso de maneira compacta; portanto, seria legal se alguém escrevesse isso em uma linguagem mais adequada.

Veja como a recursão pode ser expressa matematicamente. Infelizmente, o PPCG ainda carece de renderização matemática, então terei que usar blocos de código.

Os objetos de interesse são conjuntos de strings. Vamos |representar a união do conjunto e &representar a interseção do conjunto.

Se cfor um caractere, vamos c#Srepresentar o prefixo cde todos os caracteres S. Por outro lado, deixe que a contração c\Sseja a sequência mais curta de um caractere Sque segue o caractere inicial c, por exemplo,0\{001,010,110,111} = {01,10} ,.

Podemos dividir exclusivamente um conjunto de strings Scom caracteres 01pelo primeiro caractere.

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

Em seguida, podemos expressar a função desejada da fseguinte forma, com os casos de bases nas duas primeiras linhas e a lata recursiva na última linha:

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

Observe que não precisamos usar o comprimento n.

Por que isso funciona? Vamos pensar nas cordas de movimento que deixaram Alice vencer por um conjunto de cordas S.

Se o primeiro personagem for A, Alice pode escolher o primeiro movimento ('0' ou '1'), permitindo que ela escolha reduzir o problema para S0ou S1. Então agora a seqüência de movimento restante deve estar em pelo menos um de , f(S0)ou f(S1), portanto, tomamos a união deles| .

Da mesma forma, se o primeiro caractere é 'B', Bob escolhe e ele escolhe o pior para Alice, então a sequência de movimento restante deve estar na interseção ( &).

Os casos básicos simplesmente verificam se Sestão vazios ou não no final. Se estivermos acompanhando o comprimento das strings n, subtraindo 1 a cada vez que recorrermos, as bases poderão ser escritas:

f(S) = S if n==0

A solução recursiva também explica o fato divertido que f(S)tem o mesmo tamanho que S. É verdade para os casos base e para o caso indutivo

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

temos

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)