Latar Belakang

Alice dan Bob memainkan permainan yang disebut membangun kata biner . Untuk memainkan game ini, Anda memperbaiki panjang n >= 0, satu set Gdari panjang- nkata biner disebut tujuan set , dan panjang- nstring yang tberisi surat-surat Adan B, yang disebut urutan giliran . Permainan berlangsung nbergantian, dan pada gilirannya i, pemain ditentukan oleh t[i]memilih sedikit w[i]. Ketika permainan berakhir, para pemain melihat kata biner yang wtelah mereka buat. Jika kata ini ditemukan di set tujuan G, Alice memenangkan permainan; kalau tidak, Bob yang menang.

Sebagai contoh, mari kita memperbaiki n = 4, G = [0001,1011,0010]dan t = AABA. Alice mendapat giliran pertama, dan dia memilih w[0] = 0. Giliran kedua juga milik Alice, dan dia memilih w[1] = 0. Bob mendapat giliran ketiga, dan dia memilih w[2] = 0. Pada belokan terakhir, Alice memilih w[3] = 1. Kata yang dihasilkan,, 0001ditemukan di G, jadi Alice memenangkan permainan.

Sekarang, jika Bob memilih w[2] = 1, Alice bisa memilih w[3] = 0pada giliran terakhirnya, dan masih menang. Ini berarti bahwa Alice dapat memenangkan permainan tidak peduli bagaimana Bob bermain. Dalam situasi ini, Alice memiliki strategi kemenangan . Strategi ini dapat divisualisasikan sebagai pohon biner berlabel, yang bercabang pada tingkat yang sesuai dengan belokan Bob, dan yang setiap cabangnya berisi kata dari G:

A A B A

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

Alice bermain dengan hanya mengikuti cabang pada gilirannya; tidak peduli cabang mana yang dipilih Bob, Alice akhirnya menang.

Memasukkan

Anda diberikan sebagai input panjang n, dan set Gsebagai daftar panjang string (mungkin kosong)n .

Keluaran

Output Anda adalah daftar turn order yang mana Alice memiliki strategi kemenangan, yang setara dengan keberadaan pohon biner seperti dijelaskan di atas. Urutan pesanan belokan tidak masalah, tetapi duplikat dilarang.

Aturan rinci

Anda dapat menulis program atau fungsi lengkap. Dalam hal suatu program, Anda dapat memilih pembatas untuk input dan output, tetapi harus sama untuk keduanya. Hitungan byte terpendek menang, dan celah standar tidak diizinkan.

Uji Kasus

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]

Fakta Menarik

Jumlah pesanan belokan dalam output selalu sama dengan jumlah kata dalam set tujuan.

Dyalog APL, 59 byte

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

Algoritma yang sama seperti pada solusi @ 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}

Contoh dijalankan:

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

Ini hanya semacam golf, kebanyakan untuk menunjukkan algoritme. Input dan output adalah serangkaian string. Python tampaknya tidak memiliki fitur yang tepat untuk mengekspresikan bagian-bagian ini secara kompak, jadi akan lebih keren jika seseorang menulis ini dalam bahasa yang lebih cocok.

Inilah cara rekursi dapat diekspresikan secara matematis. Sayangnya, PPCG masih kekurangan rendering matematika, jadi saya harus menggunakan blok kode.

Objek yang menarik adalah set string. Biarkan |mewakili set union dan &mewakili set persimpangan.

Jika ckarakter, biarkan c#Smewakili karakter yang mengawali cdengan semua string di S. Sebaliknya, biarkan kontraksi c\Smenjadi string lebih pendek satu karakter Syang mengikuti karakter awal c, misalnya 0\{001,010,110,111} = {01,10},.

Kita dapat secara unik memisahkan serangkaian string Sdengan karakter 01berdasarkan karakter pertama mereka.

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

Kemudian, kita dapat mengekspresikan fungsi yang diinginkan fsebagai berikut, dengan kasus basis di dua baris pertama dan kaleng rekursif di baris terakhir:

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

Perhatikan bahwa kita tidak perlu menggunakan panjangnya n.

Mengapa ini bekerja? Mari kita pikirkan tentang string-string yang memungkinkan Alice menang untuk serangkaian string S.

Jika karakter pertama adalah A, Alice dapat memilih langkah pertama ('0' atau '1'), membiarkannya memilih untuk mengurangi masalah menjadi S0atau S1. Jadi sekarang string-pindah yang tersisa harus dalam setidaknya satu f(S0)atau f(S1), karenanya kita mengambil penyatuan mereka |.

Demikian pula, jika karakter pertama adalah 'B', Bob dapat memilih, dan ia akan memilih yang lebih buruk untuk Alice, sehingga string-string yang tersisa harus berada di persimpangan ( &).

Kasing dasar hanya memeriksa apakah Skosong atau tidak pada akhirnya. Jika kita melacak panjang string n, dengan mengurangi 1 setiap kali kita berulang, basisnya dapat ditulis:

f(S) = S if n==0

Solusi rekursif juga menjelaskan fakta menyenangkan yang f(S)memiliki ukuran yang sama S. Itu benar untuk kasus dasar, dan untuk kasus induktif

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

kita punya

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)