Hintergrund

Alice und Bob spielen ein Spiel namens Konstruieren eines binären Wortes . Um das Spiel zu spielen, fixieren Sie eine Länge n >= 0, eine Reihe Gvon längs- nbinären Worten des angerufene Zielsatz , und eine längs- nZeichenfolge , tdie Buchstaben enthält , Aund Bdie gerufene reihum . Das Spiel dauert einige Runden n, und in ider Runde t[i]wählt der Spieler, der durch definiert ist, ein Bit aus w[i]. Wenn das Spiel vorbei ist, schauen sich die Spieler das Binärwort an, das wsie konstruiert haben. Wenn dieses Wort im Zielsatz gefunden wird G, gewinnt Alice das Spiel. ansonsten gewinnt Bob.

Zum Beispiel, lassen Sie uns fix n = 4, G = [0001,1011,0010]und t = AABA. Alice bekommt die erste Runde und sie wählt w[0] = 0. Die zweite Runde gehört ebenfalls Alice und sie wählt w[1] = 0. Bob hat den dritten Zug und wählt w[2] = 0. In der letzten Runde wählt Alice w[3] = 1. Das resultierende Wort 0001wird in gefunden G, also gewinnt Alice das Spiel.

Wenn Bob gewählt hätte w[2] = 1, hätte Alice w[3] = 0in ihrem letzten Zug wählen und trotzdem gewinnen können. Dies bedeutet, dass Alice das Spiel gewinnen kann, egal wie Bob spielt. In dieser Situation hat Alice eine Gewinnstrategie . Diese Strategie kann als beschrifteter Binärbaum dargestellt werden, der auf den Ebenen verzweigt, die Bobs Umdrehungen entsprechen, und dessen jeder Zweig ein Wort enthält von G:

A A B A

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

Alice spielt, indem sie einfach den Zweigen folgt, wenn sie an der Reihe ist. egal welchen Zweig Bob wählt, Alice gewinnt schließlich.

Eingang

Sie erhalten als Eingabe die Länge nund die Menge Gals (möglicherweise leere) Liste von Zeichenketten mit Länge n.

Ausgabe

Ihre Ausgabe ist die Liste der Zugreihenfolgen, für die Alice eine Gewinnstrategie hat, die der Existenz eines Binärbaums wie oben beschrieben entspricht. Die Reihenfolge der Zugaufträge spielt keine Rolle, Duplikate sind jedoch verboten.

Detaillierte Regeln

Sie können ein vollständiges Programm oder eine Funktion schreiben. Bei einem Programm können Sie das Trennzeichen für die Ein- und Ausgabe auswählen, es muss jedoch für beide gleich sein. Die kürzeste Byteanzahl gewinnt, und Standardlücken sind nicht zulässig.

Testfälle

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

Die Anzahl der Zugreihenfolgen in der Ausgabe entspricht immer der Anzahl der Wörter im Zielsatz.

Dyalog APL, 59 Bytes

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

Gleicher Algorithmus wie in @ xnors Lösung.

(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}

Beispiellauf:

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

Dies ist nur eine Art Golf, hauptsächlich um den Algorithmus zu zeigen. Die Ein- und Ausgänge sind Sätze von Strings. Python scheint nicht die richtigen Funktionen zu haben, um Teile davon kompakt auszudrücken. Es wäre also cool, wenn jemand dies in einer besser geeigneten Sprache geschrieben hätte.

Hier ist, wie die Rekursion mathematisch ausgedrückt werden kann. Leider fehlt PPCG immer noch die mathematische Darstellung, so dass ich Codeblöcke verwenden muss.

Die Objekte von Interesse sind Sätze von Zeichenfolgen. Stellen Sie |die Mengenvereinigung dar und &stellen Sie die Schnittmenge dar.

Wenn ces sich um ein Zeichen handelt, geben Sie an c#S, dass das Zeichen cvor allen Zeichenfolgen in steht S. Umgekehrt sei die Kontraktion c\Sdie um ein Zeichen kürzere Zeichenfolge S, die auf das Anfangszeichen folgt c, z 0\{001,010,110,111} = {01,10}.

Wir können eine Reihe von Zeichenketten Smit Zeichen 01nach ihrem ersten Zeichen eindeutig aufteilen .

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

Dann können wir die gewünschte Funktion fwie folgt ausdrücken , wobei die Basisfälle in den ersten beiden Zeilen und die rekursive in der letzten Zeile stehen:

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

Beachten Sie, dass wir die Länge nicht verwenden müssen n.

Warum funktioniert das? Lassen Sie uns überlegen, mit welchen Saiten Alice für eine Reihe von Saiten gewinnen kann S.

Wenn das erste Zeichen ist A, kann Alice den ersten Zug auswählen ('0' oder '1') und das Problem auf S0oder reduzieren S1. Der verbleibende Zug muss sich also in mindestens einem von f(S0)oder befinden f(S1), daher nehmen wir ihre Vereinigung |.

Wenn das erste Zeichen 'B' ist, wählt Bob das schlechtere für Alice aus, also muss sich der verbleibende Zugstring in der Kreuzung ( &) befinden.

Die Basisfälle prüfen einfach, ob Sam Ende leer ist oder nicht. Wenn wir die Länge der Zeichenfolgen nverfolgen, können Sie stattdessen die Basen schreiben, indem Sie bei jeder Rekursion 1 subtrahieren:

f(S) = S if n==0

Die rekursive Lösung erklärt auch die lustige Tatsache, f(S)die die gleiche Größe wie hat S. Dies gilt für die Basisfälle und für den induktiven Fall

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

wir haben

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)