Zwycięskie strategie gry polegającej na budowie strun

14

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.

Zgarb
źródło
5
Jestem raczej zaintrygowany faktem, że dane wejściowe i wyjściowe mają taki sam rozmiar. Czy masz na to dowód lub dowód? Zastanawiam się, czy istnieje sposób na obliczenie tej funkcji, która intuicyjnie zachowuje rozmiar.
xnor
2
Twój przypadek testowy nr 5 przeczy twojemu
zabawnemu
3
@ mbomb007 Przypadek testowy nr 5 wyświetla 11101dwa razy; zabawny fakt wciąż obowiązuje dla zestawów. Zgarb, czy dane wejściowe mogą zawierać powtarzające się elementy, czy był to błąd?
xnor
@xnor To coś, co pojawiło się w moich badaniach jakiś czas temu. Mam dowód w tym przedruku , strona 16, ale jest on zasadniczo taki sam jak twój.
Zgarb
1
@ xnor Intuicyjnie, w dowolnym momencie, jeśli zarówno 0, jak i 1 wygrywają wybory, wtedy Alice lub Bob mogą wybrać następny ruch. Jeśli jest tylko jedna wygrana opcja, Alice musi wybrać następną. Zatem liczba wyborów dla ciągu jest taka sama, jak liczba wyborów wygranej strategii. Mało rygorystyczne, ale przekonujące.
Alchymist

Odpowiedzi:

1

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
ngn
źródło
13

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)
xnor
źródło
Uruchomienie kodu daje TypeError: 'int' object is not subscriptable. Czy masz link do uruchamialnego programu? Właśnie print f([0001,1011,0010],4)
wkleiłem
@ mbomb007 Funkcję należy wywołać jak f({'000','001','010','011','100','101','110','111'},3). Czy w ten sposób pojawia się błąd?
xnor
Ach, nie widziałem, że brakuje mi cytatów, dzięki. Działa również zprint f(['0001','1011','0010'],4)
mbomb007
Jeśli chcesz uruchomić program, wiedząc nniezależnie od parametrów, byłoby ton=len(S[0])if S!=[]else 0
mbomb007,
Uruchom tutaj: repl.it/7yI
mbomb007