Gerrymandering dengan Logic Gates

16

Fungsi mayoritas adalah fungsi boolean yang mengambil tiga input boolean dan mengembalikan yang paling umum. Misalnya jika maj(x,y,z)fungsi mayoritas dan Tmenunjukkan benar dan Fmenunjukkan salah maka:

maj(T,T,T) = T
maj(T,T,F) = T
maj(T,F,F) = F
maj(F,F,F) = F

Pertanyaan ini menyangkut penulisan fungsi boolean sebagai komposisi fungsi mayoritas. Contoh komposisi mayoritas fungsi 5-ary adalah (x1,x2,x3,x4,x5) => maj(x1,x2,maj(x3,x4,x5)). Fungsi ini mengembalikan output berikut pada vektor input sampel ini:

(T,T,F,F,F) => maj(T,T,maj(F,F,F)) = maj(T,T,F) = T
(T,F,T,T,F) => maj(T,F,maj(T,T,F)) = maj(T,F,T) = T
(T,F,T,F,F) => maj(T,F,maj(T,F,F)) = maj(T,F,F) = F
(F,F,F,T,T) => maj(F,F,maj(F,T,T)) = maj(F,F,T) = F

Tugas

Tulis program yang memasukkan bilangan bulat positif dan daftar panjang n vektor boolean dan output pohon gerbang mayoritas yang mengembalikan true pada semua vektor yang diberikan jika memungkinkan. Fungsi dapat mengembalikan benar atau salah pada vektor yang tidak ada dalam daftar kendala.

  • Daftar vektor dapat dimasukkan dalam format apa pun yang Anda suka. Jika Anda suka, alih-alih memasukkan vektor, Anda dapat memasukkan daftar posisi sebenarnya dalam vektor. Jadi misalnya, [TTF,TFT,FTT]atau [[T,T,F],[T,F,T],[F,T,T]]atau [[1,2],[1,3],[2,3]](daftar posisi sebenarnya) semuanya baik-baik saja.

  • Output dapat berupa format pohon apa pun yang valid. Misalnya, maj(maj(x1,x2,x3),x4,x5)berfungsi. Anda mungkin ingin menggunakan angka tunggal sebagai pengganti variabel, seperti pada [[1,2,3],4,5]. Reverse polish 123m45mjuga oke, misalnya.

  • Jika tidak ada fungsi yang berfungsi, program Anda harus menghasilkan kesalahan atau menampilkan nilai falsey.

  • Jika ada beberapa fungsi yang berfungsi, program Anda dapat mengembalikannya. Fungsi tidak perlu disederhanakan. Misalnya, maj(x1,x1,x2)atau x1setara.

Mencetak gol

Ini adalah kode golf: Solusi terpendek dalam byte yang menang.

Kasus uji:

Perhatikan bahwa ada banyak kemungkinan keluaran untuk masing-masing kasus ini, jadi Anda harus menulis skrip checker yang mengubah output Anda menjadi fungsi dan memeriksa apakah fungsi Anda mengembalikan true pada masing-masing vektor input yang ditentukan.

Input: 3, [TFF]
Output: 1 or [1,1,2] or [1,[1,2,2],[1,1,3]] or other equivalent

Input: 3, [TFF,FTF]
Output: Falsey or error (it's not possible)

Input: 3, [TTF,TFT]
Output: [1,2,3] or 1 or other equivalent

Input: 3, [TTF,TFT,FTT]
Output: [1,2,3] or [1,3,2] or other equivalent

Input: 4, [TTFF,TFTF,FFTT]
Output: Falsey or error

Input: 4, [TTTF,TTFT,TFTT,FTTT]
Output: [1, 2, 3] or [2,3,4], or many other options

Input: 5, [TTTFF,FTTFT,TFFFT]
Output: [1,[1,[1,2,5],[2,4,5]],3] or many other options 

Input: 6, [TTTFFF,FTFTTF,TFFTFT]
Output: [1, 2, 4] or [1, [1, 2, 4], [2, 3, 4]] or others

Input: 5, [TTTFF,TTFTF,TTFFT,TFTTF,TFTFT,TFFTT,FTTTF,FTTFT,FTFTT,FFTTT]
Output: [[1, [1, 3, 5], 4], [1, 2, [2, 4, 5]], [2, 3, [3, 4, 5]]] or others

Input: 7, [TTTTFFF,TTTFTFF,TTTFFTF,TTTFFFT,TTFTTFF,TTFTFTF,TTFTFFT,TTFFTTF,TTFFTFT,TTFFFTT,TFTTTFF,TFTTFTF,TFTTFFT,TFTFTTF,TFTFTFT,TFTFFTT,TFFTTTF,TFFTTFT,TFFTFTT,TFFFTTT,FTTTTFF,FTTTFTF,FTTTFFT,FTTFTTF,FTTFTFT,FTTFFTT,FTFTTTF,FTFTTFT,FTFTFTT,FTFFTTT,FFTTTTF,FFTTTFT,FFTTFTT,FFTFTTT,FFFTTTT]
Output: [[[1, [1, [1, 4, 7], 6], 5], [1, [1, 3, [3, 6, 7]], [3, 5, [5, 6, 7]]], [3, 4, [4, [4, 5, 7], 6]]], [[1, [1, [1, 4, 7], 6], 5], [1, 2, [2, [2, 5, 7], 6]], [2, [2, 4, [4, 6, 7]], [4, 5, [5, 6, 7]]]], [[2, [2, [2, 4, 7], 6], 5], [2, 3, [3, [3, 5, 7], 6]], [3, [3, 4, [4, 6, 7]], [4, 5, [5, 6, 7]]]]]
jilbab
sumber
"Komposisi fungsi mayoritas 5-ary adalah (x1, x2, x3, x4, x5) => maj (x1, x2, maj (x3, x4, x5))" bagaimana? Apa jawabannya jika x1 = x2 = F; x3 = x4 = x5 = T; ?
tsh
Saya akan menambahkan tabel kebenaran.
Hood
1
Apa yang dimaksud dengan output 1?
Mhmd
2
Judul yang disarankan: Gerrymandering dengan gerbang logika
Robert Fraser
1
@trichoplax Tidak, output pada semua vektor yang tersisa bisa apa saja. Saya akan memperbarui untuk membuat itu eksplisit.
Hood

Jawaban:

2

JavaScript (ES6), 260 byte

Mengambil input sebagai array array boolean. Mengembalikan pohon gerbang mayoritas 1-diindeks atau melempar kesalahan rekursi (1) jika tidak ada solusi.

Fungsi utama f () secara rekursif berusaha menemukan solusi dengan memanggil pemecah F () dan menambah level bersarang maksimum m pada setiap iterasi.

(1) setelah waktu yang lama , dan mengasumsikan memori tak terbatas

f=(a,m)=>(F=(a,d,I=a[i=0].map(_=>++i),g=(a,b)=>b[1]?b.reduce((s,i)=>s+g(a,i),0)>1:a[b-1])=>I.find(i=>a.every(a=>g(a,i)))||d&&(I.reduce((a,x)=>[...a,...a.map(y=>[...y,x])],[[]]).some(b=>r=b.length==3&&F(a.map(a=>[...a,g(a,b)]),d-1,[...I,b]))&&r))(a,m)||f(a,-~m)

Demo

Contoh

Di bawah ini adalah tabel validasi dari solusi yang ditemukan untuk kasus uji terakhir dari demo.

12345 | [5,[1,2,4],[3,4,[1,2,3]]]
------+-------------------------------------------------------------
TTTFF | [F,[T,T,F],[T,F,[T,T,T]]] --> [F,T,[T,F,T]] -> [F,T,T] --> T
TTFTF | [F,[T,T,T],[F,T,[T,T,F]]] --> [F,T,[F,T,T]] -> [F,T,T] --> T
TTFFT | [T,[T,T,F],[F,F,[T,T,F]]] --> [T,T,[F,F,T]] -> [T,T,F] --> T
TFTTF | [F,[T,F,T],[T,T,[T,F,T]]] --> [F,T,[T,T,T]] -> [F,T,T] --> T
TFTFT | [T,[T,F,F],[T,F,[T,F,T]]] --> [T,F,[T,F,T]] -> [T,F,T] --> T
TFFTT | [T,[T,F,T],[F,T,[T,F,F]]] --> [T,T,[F,T,F]] -> [T,T,F] --> T
FTTTF | [F,[F,T,T],[T,T,[F,T,T]]] --> [F,T,[T,T,T]] -> [F,T,T] --> T
FTTFT | [T,[F,T,F],[T,F,[F,T,T]]] --> [T,F,[T,F,T]] -> [T,F,T] --> T
FTFTT | [T,[F,T,T],[F,T,[F,T,F]]] --> [T,T,[F,T,F]] -> [T,T,F] --> T
FFTTT | [T,[F,F,T],[T,T,[F,F,T]]] --> [T,F,[T,T,F]] -> [T,F,T] --> T
Arnauld
sumber
Ada solusi yang efisien, yang mudah-mudahan seseorang akan menemukannya. Sementara itu, saya kira semacam kekerasan bekerja ...
Hood
2

Mathematica, 121 byte

Fungsi anonim yang mengambil argumen kedua sebagai daftar daftar posisi sebenarnya dalam vektor boolean.

f[n_][s_]:=If[n<3,(Intersection@@s)[[1]],{#/. 2->1,#2/.{2->1,3->2},#3}&@@(1+f[n-1]/@(s-1/.{{0->1},{1->2,0->1},{0->2}}))]

Diformat sedikit lebih bagus:

f[n_][s_] := If[n < 3, (Intersection @@s)[[1]],
   {# /. 2 -> 1, #2 /. {2 -> 1, 3 -> 2}, #3} & @@ 
    (1 + f[n - 1] /@ (s - 1 /. {{0 -> 1}, {1 -> 2, 0 -> 1}, {0 -> 2}}))]

Jika ada kurang dari tiga variabel, memotong vektor kendala untuk melihat apakah ada "Benar" yang sama dalam semua kendala. Jika ada, maka fungsi konstan (x_1, x_2) -> x_i berfungsi, jika tidak maka tidak mungkin (dan akan melempar kesalahan dengan mencoba mengambil elemen pertama dari daftar kosong).

Kalau tidak, gantikan f1=f(x1,x1,x2,x3,,xn1) , f2=f(x1,x2,x2,x3,,xn1) , dan f3=f(x1,x2,x1,x3,,xn1)) , secara rekursif menyelesaikan masing-masing, lalu setf=maj(f1(x1,x3,x4,,xn),f2(x1,x2,x4,,xn),f2(x2,x3,x4,,xn)) .

Penjelasan:

Ini adalah algoritma rekursif yang mengurangi masalah menemukan solusi dari masalah n variabel menjadi menemukan tiga solusi untuk masalah n1 variabel. Pengamatan kunci yang membuat pekerjaan ini adalah bahwa untuk f salah satu fungsi yang kita cari kita miliki: f(x1,,xn)=maj(f(x1,x1,x3,x4,,xn),f(x1,x2,x2,),f(x3,x2,x3,))

Di posisi pertama, kami mengganti x2 dengan x1 , di posisi kedua x3 dengan x2 dan di posisi ketiga x1 dengan x3 .

f(x1,x1,x3,x4,,xn)f(x1,x2,x2,x4,,xn)f(x3,x2,x3,x4,,xn))

Mengapa ini benar? Nah fungsi mayoritas memenuhi dua properti:

  1. !xxmaj(!x,!y,!z)=!maj(x,y,z)

  2. maj(x,y,False)maj(x,y,True)FalseTrue(x1,,xn)(y1,,yn)xiyiif(x1,xn)(y1,,yn)f(x1,xn)f(y1,,yn). Komposisi fungsi monoton adalah monoton sehingga setiap fungsi yang dapat kita bangun dari fungsi mayoritas adalah monoton.

Ternyata fungsi monotonik pelengkap persis kelas fungsi yang dapat dibangun dari gerbang mayoritas.

ff(x1,,xn)=maj(f(x1,x1,x3,x4,,xn),f(x1,x2,x2,x4,,xn),f(x3,x2,x3,x4,,xn))

f1(x1,x2,x3,,xn)=f(x1,x1,x3,x4,,xn)f2(x1,,xn)=f(x1,x2,x2,x4,,xn)f3(x1,,xn)=f(x3,x2,x3,x4,,xn)f=maj(f1,f2,f3)f1f2f3fx1x2x3x1=x2=x3f1=f2=f3=f

x1x2x3fx1=x2x3fx1=x2=Falsex3=True(x1,x1,x3)=(False,False,True)=(x1,x2,x3)(x1,x2,x2)=(False,False,False)(x1,x2,x3) and (x3,x2,x3)=(True,False,True)(x1,x2,x3). By monotonicity we deduce that f2f1=ff3. If f=False then f2False implies f2=False=f and if f=True then f3True implies f3=True. Thus, at least two of f1, f2, and f3 are equal to f in all cases so f=maj(f1,f2,f3).

Hood
sumber