Bayangkan Anda memiliki dua kotak B(x)dan B(y), masing-masing berisi bit yang tidak diketahui - 0 atau 1, dan sebuah mesin Fyang dapat melakukan rontgen dan menghasilkan kotak ketiga untuk B(x^y)( xor ). Fjuga dapat menghitung B(x*y)( dan ). Bahkan, itu hanya kasus-kasus khusus dari operasi tunggal yang dapat dilakukan mesin - masing-masing produk dalam , dilambangkan dengan di F()bawah ini.

Untuk dua array dengan panjang yang sama

[B(x[0]), B(x[1]), ..., B(x[n-1])]
[B(y[0]), B(y[1]), ..., B(y[n-1])]

produk dalam didefinisikan sebagai

B(x[0]*y[0] ^ x[1]*y[1] ^ ... ^ x[n-1]*y[n-1])

" Setiap " berarti F()dapat memproses beberapa pasang x[], y[]dalam satu pergi. Pasangan dari x[]dan y[]harus memiliki panjang yang sama; x[]-s dan y[]-s dari pasangan yang berbeda tidak perlu.

Kotak diwakili oleh id integer unik.

Implementasi produk dalam masing-masing dalam JavaScript mungkin terlihat seperti

var H=[0,1];          // hidden values, indexed by boxId
function B(x) {       // seal x in a new box and return the box id
  return H.push(x)-1;
}
function F(pairs) {   // "inner product each"
  return pairs.map(function (pair) {
    var r = 0, x = pair[0], y = pair[1];
    for (var i = 0; i < x.length; i++) r ^= H[x[i]] * H[y[i]];
    return B(r);
  })
}

(Silakan terjemahkan di atas ke bahasa pilihan Anda.)

Diberikan akses ke F()implementasi yang sesuai untuk bahasa Anda (tetapi tidak ada akses ke Hatau B()) dan diberi dua larik kotak id yang merupakan representasi biner 16-bit dari dua bilangan bulat adan b, tugas Anda adalah menghasilkan id kotak untuk representasi biner 16-bit of a+b(discarding overflow) dengan jumlah F()panggilan minimum .

Solusi yang memanggil F()waktu paling sedikit menang. Ikatan akan rusak dengan menghitung jumlah total x[],y[]pasangan F()yang dipanggil - lebih sedikit lebih baik. Jika masih terikat, ukuran kode Anda (tidak termasuk implementasi F()dan pembantunya) menentukan pemenang dengan cara golf kode tradisional. Silakan gunakan judul seperti "MyLang, 123 panggilan, 456 pasangan, 789 byte" untuk jawaban Anda.

Tulis fungsi atau program lengkap. Input / output / argumen / hasil adalah array int dalam format apa pun yang masuk akal. Representasi biner mungkin sedikit atau big-endian - pilih satu.

Lampiran 1: Untuk membuat tantangan sedikit lebih mudah, Anda dapat mengasumsikan bahwa kotak dengan id 0 dan 1 berisi nilai 0 dan 1. Ini memberi Anda konstanta, misalnya berguna untuk negasi ( x^1"tidak"). Tentu saja ada beberapa cara untuk mengatasi kekurangan konstanta, tetapi tantangan lainnya cukup sulit, jadi mari kita hilangkan gangguan ini.

Lampiran 2: Untuk memenangkan hadiah, Anda harus melakukan salah satu dari yang berikut:

• memposting skor Anda (panggilan, pasangan, byte) dan kode Anda sebelum batas waktu

• memposting skor Anda dan hash kode Anda sha256 sebelum batas waktu; kemudian posting kode aktual dalam waktu 23 jam setelah batas waktu

Python 3 , 5 panggilan, 92 pasangan, 922 byte

Python 3 , 5 panggilan, 134 pasangan, 3120 byte

Python 3 , 6 panggilan, 106 pasangan, 2405 byte

[JavaScript (Node.js)], 9 panggilan, 91 pasangan, 1405 byte

JavaScript (Node.js), 16 panggilan, 31 pasangan, 378 byte

def add(F,a,b):r=[];p=lambda x:(x,x);q=lambda u,v,t:([u,v]+t[0],[u,v]+t[1]);s=lambda c,k,n:([e[j][n]for j in range(k,-1,-1)]+[f[n]],[c]+f[n-k:n+1]);t=lambda c,k,n:q(a[n],b[n],s(c,k,n-1));z=F([p([a[i],b[i]])for i in range(16)]+[([a[i]],[b[i]])for i in range(16)]);e=[z[0:16]];f=z[16:32];r+=[e[0][0]];c=f[0];z=F([p([a[1],b[1],c]),([e[0][1],f[1]],[c,f[1]])]+[([e[0][i]],[e[0][i-1]])for i in range(3,16)]);r+=[z[0]];c=z[1];e+=[[0]*3+z[2:15]];z=F([p([a[2],b[2],c]),t(c,0,3),s(c,1,3)]+[([e[j][i]],[e[1][i-j-1]])for j in range(2)for i in range(6+j,16)]);r+=z[0:2];c=z[2];e+=u(2,4,z[3:]);z=F([p([a[4],b[4],c])]+[t(c,i,i+5)for i in range(0,3)]+[s(c,3,7)]+[([e[j][i]],[e[3][i-j-1]])for j in range(4)for i in range(12+j,16)]);r+=z[0:4];c=z[4];e+=u(4,8,z[5:]);z=F([p([a[8],b[8],c])]+[t(c,i,i+9) for i in range(0,7)]);return r+z
def u(b,e,z):
	j=0;w=[0]*(e-b)
	for i in range(b,e):w[i-b]=[0]*(i+e)+z[j:j+16-(i+e)];j+=16-(i+e)
	return w

Cobalah online!

VERSI PERTAMA Oke itu bukan golf. Itu hanya adaptasi dari kode @ ngn.

Satu-satunya ide di sini adalah bahwa Anda tidak perlu menghitung carry terakhir karena Anda membuang overflow. Juga, panggilan Fdikelompokkan berdasarkan dua. Mungkin mereka dapat dikelompokkan dengan cara lain, tetapi saya ragu Anda dapat mengurangi jumlah pasangan secara signifikan, karena sifat dari algoritma penambahan dasar.

EDIT : Masih tidak golf. Jumlah pasangan pasti dapat dikurangi, dan mungkin jumlah panggilan juga. Lihat https://gist.github.com/jferard/864f4be6e4b63979da176bff380e6c62 untuk "bukti" dengan sympy.

EDIT 2 Beralih ke Python karena lebih mudah dibaca untuk saya. Sekarang saya sudah mendapatkan formula umum, saya pikir saya dapat mencapai batas 5 (mungkin 4) panggilan.

EDIT 3 Berikut adalah batu bata dasar:

alpha[i] = a[i] ^ b[i]
beta[i] = a[i] * b[i]
c[0] = beta[0]
r[0] = alpha[0]

Rumus umum adalah:

c[i] = alpha[i]*c[i-1] ^ beta[i]
r[i] = a[i] ^ b[i] ^ c[i-1]

Versi yang diperluas adalah:

c[0] = beta[0]
c[1] = alpha[1]*beta[0] ^ beta[1]
c[2] = alpha[2]*alpha[1]*beta[0] ^ alpha[2]*beta[1] ^ beta[2]
c[3] = alpha[3]*alpha[2]*alpha[1]*beta[0] ^ alpha[3]*alpha[2]*beta[1] ^ alpha[3]*beta[2] ^ beta[3]
...
c[i] = alpha[i]*...*alpha[1]*beta[0] ^ alpha[i]*...*alpha[2]*beta[1] ^ .... ^ alpha[i]*beta[i-1] ^ beta[i]

5 panggilan sepertinya batas bagi saya. Sekarang saya punya sedikit pekerjaan untuk menghilangkan pasangan dan golf itu!

EDIT 4 Saya bermain golf yang ini.

Versi tidak disatukan:

def add(F, a, b):
    r=[]
    # p is a convenient way to express x1^x2^...x^n
    p = lambda x:(x,x)
    # q is a convenient way to express a[i]^b[i]^carry[i-1]
    q = lambda u,v,t:([u,v]+t[0],[u,v]+t[1])

    # step1: the basic bricks
    z=F([p([a[i],b[i]]) for i in range(16)]+[([a[i]],[b[i]]) for i in range(16)])
    alpha=z[0:16];beta=z[16:32]
    r.append(alpha[0])
    c = beta[0]

    # step 2
    z=F([
        p([a[1],b[1],c]),
        ([alpha[1],beta[1]],[c,beta[1]])
        ]+[([alpha[i]],[alpha[i-1]]) for i in range(3,16)])
    r.append(z[0])
    c = z[1] # c[1]
    alpha2=[0]*3+z[2:15]
    assert len(z)==15, len(z)

    # step 3
    t0=([alpha[2],beta[2]],[c,beta[2]])
    t1=([alpha2[3],alpha[3],beta[3]],[c,beta[2],beta[3]])
    z=F([
        p([a[2],b[2],c]),
        q(a[3],b[3],t0),
        t1]+
        [([alpha[i]],[alpha2[i-1]]) for i in range(6,16)]+
        [([alpha2[i]],[alpha2[i-2]]) for i in range(7,16)])
    r.extend(z[0:2])
    c = z[2] # c[3]
    alpha3=[0]*6+z[3:13]
    alpha4=[0]*7+z[13:22]
    assert len(z)==22, len(z)

    # step 4
    t0=([alpha[4],beta[4]],[c,beta[4]])
    t1=([alpha2[5],alpha[5],beta[5]],[c,beta[4],beta[5]])
    t2=([alpha3[6],alpha2[6],alpha[6],beta[6]],[c,beta[4],beta[5],beta[6]])
    t3=([alpha4[7],alpha3[7],alpha2[7],alpha[7],beta[7]],[c,beta[4],beta[5],beta[6],beta[7]])
    z=F([
        p([a[4],b[4],c]),
        q(a[5],b[5],t0),
        q(a[6],b[6],t1),
        q(a[7],b[7],t2),
        t3]+
        [([alpha[i]],[alpha4[i-1]]) for i in range(12,16)]+
        [([alpha2[i]],[alpha4[i-2]]) for i in range(13,16)]+
        [([alpha3[i]],[alpha4[i-3]]) for i in range(14,16)]+
        [([alpha4[i]],[alpha4[i-4]]) for i in range(15,16)])
    r.extend(z[0:4])
    c = z[4] # c[7]
    alpha5 = [0]*12+z[5:9]
    alpha6 = [0]*13+z[9:12]
    alpha7 = [0]*14+z[12:14]
    alpha8 = [0]*15+z[14:15]
    assert len(z) == 15, len(z)

    # step 5
    t0=([alpha[8],beta[8]],[c,beta[8]])
    t1=([alpha2[9],alpha[9],beta[9]],[c,beta[8],beta[9]])
    t2=([alpha3[10],alpha2[10],alpha[10],beta[10]],[c,beta[8],beta[9],beta[10]])
    t3=([alpha4[11],alpha3[11],alpha2[11],alpha[11],beta[11]],[c,beta[8],beta[9],beta[10],beta[11]])
    t4=([alpha5[12],alpha4[12],alpha3[12],alpha2[12],alpha[12],beta[12]],[c,beta[8],beta[9],beta[10],beta[11],beta[12]])
    t5=([alpha6[13],alpha5[13],alpha4[13],alpha3[13],alpha2[13],alpha[13],beta[13]],[c,beta[8],beta[9],beta[10],beta[11],beta[12],beta[13]])
    t6=([alpha7[14],alpha6[14],alpha5[14],alpha4[14],alpha3[14],alpha2[14],alpha[14],beta[14]],[c,beta[8],beta[9],beta[10],beta[11],beta[12],beta[13],beta[14]])
    t7=([alpha8[15],alpha7[15],alpha6[15],alpha5[15],alpha4[15],alpha3[15],alpha2[15],alpha[15],beta[15]],[c,beta[8],beta[9],beta[10],beta[11],beta[12],beta[13],beta[14],beta[15]])

    z=F([
        p([a[8],b[8],c]),
        q(a[9],b[9],t0),
        q(a[10],b[10],t1),
        q(a[11],b[11],t2),
        q(a[12],b[12],t3),
        q(a[13],b[13],t4),
        q(a[14],b[14],t5),
        q(a[15],b[15],t6)
    ])
    r.extend(z)
    return r

Cobalah online!

Haskell, 1 panggilan (selingkuh ???), 32 pasang (dapat ditingkatkan), 283 byte (sama)

Tolong jangan marah dengan saya, saya tidak ingin menang dengan ini, tetapi saya didorong dalam komentar untuk tantangan untuk menjelaskan apa yang saya bicarakan.

Saya mencoba menggunakan monad negara untuk menangani menambahkan kotak dan menghitung panggilan dan pasangan, dan itu berhasil, tetapi saya tidak berhasil membuat solusi saya bekerja di pengaturan itu. Jadi saya melakukan apa yang disarankan dalam komentar: sembunyikan saja data di belakang konstruktor data dan jangan mengintip. (Cara bersihnya adalah dengan menggunakan modul terpisah dan tidak mengekspor konstruktor.) Versi ini memiliki keuntungan menjadi lebih sederhana.

Karena kita berbicara tentang kotak bit, saya memberikan Boolnilai ke dalamnya. Saya mendefinisikan zerosebagai kotak yang diberikan dengan bit nol - a onetidak diperlukan.

import Debug.Trace

data B = B { unB :: Bool }

zero :: B
zero = B False

f :: [([B],[B])] -> [B]
f pairs =  trace ("f was called with " ++ show (length pairs) ++ " pairs") $
           let (B i) &&& (B j) = i && j
           in map (\(x,y) ->  B ( foldl1 (/=) (zipWith (&&&) x y))) pairs

Kami menggunakan fungsi debugging traceuntuk melihat seberapa sering fdipanggil, dan dengan berapa pasangan. &&&melihat ke dalam kotak dengan pencocokan pola, ketidaksetaraan yang /= digunakan pada Boolnilai adalah xor.

bits :: Int -> [Bool]
bits n = bitsh n 16
  where bitsh _ 0 = []
        bitsh n k = odd n : bitsh (n `div` 2) (k-1)

test :: ( [B] -> [B] -> [B] ) -> Int -> Int -> Bool
test bba n m = let x = map B (bits n)
                   y = map B (bits m)
                   r = bba x y
                   res = map unB r
               in res==bits(n+m)

The testfungsi mengambil penambah biner buta sebagai argumen pertama, dan kemudian dua angka yang Selain diuji. Ini mengembalikan yang Boolmenunjukkan apakah tes berhasil. Pertama, kotak input dibuat, kemudian penambah dipanggil, hasilnya tanpa kotak (dengan unB) dan dibandingkan dengan hasil yang diharapkan.

Saya menerapkan dua adders, solusi sampel simple, sehingga kita dapat melihat bahwa output debug berfungsi dengan benar, dan solusi saya menggunakan rekursi nilai valrec.

simple a b = let [r0] = f [([a!!0,b!!0],[a!!0,b!!0])]
                 [c]  = f [([a!!0],[b!!0])]
             in loop 1 [r0] c
             where loop 16 rs _ = rs
                   loop i  rs c = let [ri] = f [([a!!i,b!!i,c],[a!!i,b!!i,c])]
                                      [c'] = f [([a!!i,b!!i,c],[b!!i,c,a!!i])]
                                  in loop (i+1) (rs++[ri]) c'

valrec a b =
    let res = f (pairs res a b)
    in [ res!!i | i<-[0,2..30] ]
  where pairs res a b =
           let ts = zipWith3 (\x y z -> [x,y,z])
                             a b (zero : [ res!!i | i<-[1,3..29] ]) in
           [ p | t@(h:r) <- ts, p <- [ (t,t), (t,r++[h]) ] ]

Lihat bagaimana saya mendefinisikannya ressendiri? Itu juga dikenal sebagai ikatan .

Sekarang kita dapat melihat bagaimana fhanya dipanggil sekali:

*Main> test valrec 123 456
f was called with 32 pairs
True

Atau ganti valrecdengan simpleuntuk melihat fdipanggil 32 kali.

Cobalah online! (output penelusuran muncul di bawah "Debug")

JavaScript, 32 panggilan, 32 pasangan, 388 byte

Dyalog APL, 32 panggilan, 32 pasangan, 270 byte

Ini adalah solusi sampel naif yang dapat berfungsi sebagai templat.

Perhatikan bahwa jumlah byte hanya mencakup bagian yang dikelilingi dengan "BEGIN / END SOLUTION".

Penjelasan:

Saya memilih urutan bit little-endian ( x[0]adalah bit paling signifikan).

Amati bahwa penambahan 2-bit mod 2 dapat direalisasikan sebagai F([[[x,y],[x,y]]])(yaitu: x*x ^ y*y- perkalian mod 2 idempoten) dan perkalian biner sebagai F([[[x],[y]]]).

Kami melintasi bit dari paling tidak signifikan ke paling signifikan dan pada setiap langkah menghitung bit hasil dan carry.

#!/usr/bin/env node
'use strict'
let H=[0,1]
,B=x=>H.push(x)-1
,nCalls=0
,nPairs=0
,F=pairs=>{
  nCalls++;nPairs+=pairs.length
  return pairs.map(([x,y])=>{let s=0;for(let i=0;i<x.length;i++)s^=H[x[i]]*H[y[i]];return B(s)})
}

// -----BEGIN SOLUTION-----
var f=(a,b)=>{
  var r=[], c // r:result bits (as box ids), c:carry (as a box id)
  r[0]=F([[[a[0],b[0]],[a[0],b[0]]]])          // r0 = a0 ^ b0
  c=F([[[a[0]],[b[0]]]])                       // c = a0*b0
  for(var i=1;i<16;i++){
    r.push(F([[[a[i],b[i],c],[a[i],b[i],c]]])) // ri = ai ^ bi ^ c
    c=F([[[a[i],b[i],c],[b[i],c,a[i]]]])       // c = ai*bi ^ bi*c ^ c*ai
  }
  return r
}
// -----END SOLUTION-----

// tests
let bits=x=>{let r=[];for(let i=0;i<16;i++){r.push(x&1);x>>=1}return r}
,test=(a,b)=>{
  console.info(bits(a))
  console.info(bits(b))
  nCalls=nPairs=0
  let r=f(bits(a).map(B),bits(b).map(B))
  console.info(r.map(x=>H[x]))
  console.info('calls:'+nCalls+',pairs:'+nPairs)
  console.assert(bits(a+b).every((x,i)=>x===H[r[i]]))
}

test(12345,6789)
test(12,3)
test(35342,36789)

Hal yang sama di Dyalog APL (tetapi menggunakan id kotak acak):

⎕io←0⋄K←(V←⍳2),2+?⍨1e6⋄B←{(V,←⍵)⊢K[≢V]}⋄S←0⋄F←{S+←1,≢⍵⋄B¨2|+/×/V[K⍳↑⍉∘↑¨⍵]}
⍝ -----BEGIN SOLUTION-----
f←{
  r←F,⊂2⍴⊂⊃¨⍺⍵        ⍝ r0 = a0 ^ b0
  c←⊃F,⊂,¨⊃¨⍺⍵        ⍝ c = a0*b0
  r,⊃{
    ri←⊃F,⊂2⍴⊂⍺⍵c     ⍝ ri = ai ^ bi ^ c
    c⊢←⊃F,⊂(⍺⍵c)(⍵c⍺) ⍝ c = ai*bi ^ bi*c ^ c*ai
    ri
  }¨/1↓¨⍺⍵
}
⍝ -----END SOLUTION-----
bits←{⌽(16⍴2)⊤⍵}
test←{S⊢←0⋄r←⊃f/B¨¨bits¨⍺⍵
      ⎕←(↑bits¨⍺⍵)⍪V[K⍳r]⋄⎕←'calls:' 'pairs:',¨S
      (bits⍺+⍵)≢V[K⍳r]:⎕←'wrong!'}
test/¨(12345 6789)(12 3)(35342 36789)