tło

Alice i Bob grają w grę o nazwie binarne słowo . Aby zagrać w grę, ustalamy długość n >= 0, zestaw Gdługości ndwójkowych słów zwanych zestawem bramek oraz nciąg długości tzawierający litery Ai Bnazywany porządkiem tury . Gra trwa przez ntury, a na turę igracz określony przez t[i]wybiera trochę w[i]. Po zakończeniu gry gracze patrzą na binarne słowo w, które skonstruowali. Jeśli to słowo zostanie znalezione w zestawie bramek G, Alice wygrywa grę; w przeciwnym razie Bob wygrywa.

Na przykład, powiedzmy, fix n = 4, G = [0001,1011,0010]i t = AABA. Alice dostaje pierwszą turę, a ona wybiera w[0] = 0. Druga tura należy również do Alicji, a ona wybiera w[1] = 0. Bob ma trzecią turę i wybiera w[2] = 0. W ostatniej turze Alice wybiera w[3] = 1. Wynikowe słowo, 0001znajduje się w G, więc Alice wygrywa.

Teraz, gdyby Bob wybrał w[2] = 1, Alice mogłaby wybrać w[3] = 0w swojej ostatniej turze i nadal wygrywać. Oznacza to, że Alice może wygrać grę bez względu na to, jak gra Bob. W tej sytuacji Alice ma zwycięską strategię . Strategię tę można zwizualizować jako oznaczone drzewo binarne, które rozgałęzia się na poziomach odpowiadających zwrotom Boba i którego każda gałąź zawiera słowo z G:

A A B A

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

Alice gra po prostu śledząc gałęzie w swojej turze; bez względu na to, którą gałąź wybierze Bob, Alice w końcu wygrywa.

Wejście

Jako dane wejściowe podano długość n, a zestaw Gjako (być może pustą) listę ciągów długości n.

Wynik

Twój wynik to lista rozkazów tury, dla których Alice ma strategię wygrywającą, co jest równoważne z istnieniem drzewa binarnego, jak opisano powyżej. Kolejność rozkazów tury nie ma znaczenia, ale duplikaty są zabronione.

Szczegółowe zasady

Możesz napisać pełny program lub funkcję. W przypadku programu możesz wybrać separator dla wejścia i wyjścia, ale musi być taki sam dla obu. Wygrywa najkrótsza liczba bajtów, a standardowe luki są niedozwolone.

Przypadki testowe

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]

Śmieszny fakt

Liczba zleceń skrętu na wyjściu jest zawsze równa liczbie słów w zestawie celów.

Dyalog APL, 59 bajtów

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

Ten sam algorytm jak w rozwiązaniu @ 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}

Przykładowy przebieg:

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

Jest to tylko rodzaj gry w golfa, głównie w celu pokazania algorytmu. Dane wejściowe i wyjściowe są zestawami ciągów. Python nie wydaje się mieć odpowiednich funkcji do wyrażania części tego zwięźle, więc byłoby fajnie, gdyby ktoś napisał to w lepiej dopasowanym języku.

Oto jak rekurencję można wyrazić matematycznie. Niestety PPCG wciąż nie ma renderowania matematycznego, więc będę musiał użyć bloków kodu.

Przedmiotem zainteresowania są zestawy ciągów znaków. Niech |reprezentuje zestaw unii i &reprezentuje zestaw przecięcia.

Jeśli cjest znakiem, niech c#Sreprezentuje wstawianie znaku cdo wszystkich łańcuchów w S. I odwrotnie, niech skurcz c\Sbędzie krótszym o jeden znak ciągiem Snastępującego po znaku początkowym c, np 0\{001,010,110,111} = {01,10}.

Możemy jednoznacznie podzielić zestaw ciągów Sznaków 01ze znakami według ich pierwszej postaci.

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

Następnie możemy wyrazić pożądaną funkcję fw następujący sposób, z przypadkami bazowymi w pierwszych dwóch wierszach, a rekurencyjną w ostatnim wierszu:

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

Pamiętaj, że nie musimy używać długości n.

Dlaczego to działa? Zastanówmy się nad ciągami ruchów, które pozwoliły Alice wygrać dla zestawu ciągów S.

Jeśli pierwszą postacią jest A, Alice może wybrać pierwszy ruch („0” lub „1”), pozwalając jej zredukować problem do S0lub S1. Tak więc teraz pozostały ciąg ruchów musi znajdować się w co najmniej jednym f(S0)lub f(S1), dlatego bierzemy ich związek |.

Podobnie, jeśli pierwszą postacią jest „B”, Bob może wybrać, a on wybierze gorszą dla Alice, więc pozostały ciąg ruchu musi znajdować się na przecięciu ( &).

Podstawy po prostu sprawdzają, czy Sna końcu są puste, czy nie. Jeśli śledzimy długość ciągów n, odejmując 1 za każdym razem, gdy się powtarzamy, zamiast tego można zapisać zasady:

f(S) = S if n==0

Rozwiązanie rekurencyjne wyjaśnia również zabawny fakt, który f(S)ma taki sam rozmiar jak S. Dotyczy to przypadków podstawowych i przypadku indukcyjnego

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

mamy

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)