Wyobraź sobie, że masz dwa pola B(x)i B(y)każdy z nich zawiera nieznany bit - 0 lub 1 oraz maszynę, Fktóra może je prześwietlić i wytworzyć trzecie pole dla B(x^y)( xor ). Fmoże również obliczyć B(x*y)( i ). W rzeczywistości są to tylko szczególne przypadki pojedynczej operacji, którą może wykonać maszyna - każda z nich to produkt wewnętrzny oznaczony F()poniżej.

Dla dwóch tablic o tej samej długości

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

produkt wewnętrzny jest zdefiniowany jako

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

„ Każdy ” oznacza F()może przetwarzać wiele par x[], y[]za jednym zamachem. Od x[]i y[]od jednej pary muszą być tej samej długości; x[]-s i y[]-s z różnych par niekoniecznie muszą.

Pola są reprezentowane przez unikalne identyfikatory liczb całkowitych.

Może wyglądać implementacja produktu wewnętrznego w JavaScript

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);
  })
}

(Proszę przetłumaczyć powyższe na wybrany język).

Biorąc pod uwagę dostęp do F()implementacji odpowiedniej dla twojego języka (ale nie ma dostępu do Hlub B()) i podane dwie tablice identyfikatorów pól stanowiących 16-bitowe reprezentacje binarne dwóch liczb całkowitych, aa bTwoim zadaniem jest wytworzenie identyfikatorów pól dla 16-bitowej reprezentacji binarnej od a+b(przepełnienie odrzucając) z minimalną liczbą F()połączeń.

Rozwiązanie, które wywołuje F()najmniej czasu, wygrywa. Więzy zostaną zerwane przez policzenie łącznej liczby x[],y[]par, F()z którymi wywołano - mniej znaczy lepiej. Jeśli nadal jest związany, rozmiar twojego kodu (wyłączając implementację F()i jego pomocników) określa zwycięzcę w tradycyjny sposób golfa. Jako odpowiedzi użyj tytułu „MyLang, 123 połączenia, 456 par, 789 bajtów”.

Napisz funkcję lub pełny program. Dane wejściowe / wyjściowe / argumenty / wynik są tablicami int w dowolnym rozsądnym formacie. Reprezentacja binarna może być mała lub duża - wybierz jedną.

Dodatek 1: Aby nieco ułatwić wyzwanie, możesz założyć, że pola o identyfikatorach 0 i 1 zawierają wartości 0 i 1. Daje to stałe, przydatne np. Do negacji ( x^1to „nie”). Oczywiście istniały sposoby obejścia braku stałych, ale reszta wyzwania i tak jest wystarczająco trudna, więc wyeliminujmy to rozproszenie.

Dodatek 2: Aby wygrać nagrodę, musisz wykonać jedną z następujących czynności:

• opublikuj swój wynik (połączenia, pary, bajty) i kod przed upływem terminu

• opublikuj swój wynik i skrót sha256 kodu przed upływem terminu; następnie opublikuj rzeczywisty kod w ciągu 23 godzin po terminie

Python 3 , 5 połączeń, 92 pary, 922 bajty

Python 3 , 5 połączeń, 134 pary, 3120 bajtów

Python 3 , 6 wywołań, 106 par, 2405 bajtów

[JavaScript (Node.js)], 9 wywołań, 91 par, 1405 bajtów

JavaScript (Node.js), 16 wywołań, 31 par, 378 bajtów

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

Wypróbuj online!

PIERWSZA WERSJA Dobra, to nie gra w golfa. To tylko adaptacja kodu @ ngn.

Jedynym pomysłem jest to, że nie musisz obliczać ostatniego przeniesienia, ponieważ odrzucasz przepełnienie. Połączenia Fsą również pogrupowane według dwóch. Być może można je pogrupować w inny sposób, ale wątpię, czy można znacznie zmniejszyć liczbę par ze względu na charakter podstawowego algorytmu dodawania.

EDYCJA : Wciąż nie grałem w golfa. Z pewnością można by zmniejszyć liczbę par, a prawdopodobnie także liczbę połączeń. Zobacz https://gist.github.com/jferard/864f4be6e4b63979da176bff380e6c62 celu uzyskania „dowodu” z sympią.

EDYCJA 2 Przełączono na Python, ponieważ jest dla mnie bardziej czytelny. Teraz mam ogólną formułę, myślę, że mogę osiągnąć limit 5 (może 4) połączeń.

EDYCJA 3 Oto podstawowe cegły:

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

Ogólna formuła to:

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

Rozszerzona wersja to:

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 połączeń wydaje mi się limitem. Teraz mam trochę pracy, aby usunąć pary i zagrać w golfa!

EDYCJA 4 grałem w golfa.

Wersja bez golfa:

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

Wypróbuj online!

Haskell, 1 połączenie (oszustwo?), 32 pary (można poprawić), 283 bajtów (to samo)

Proszę, nie gniewajcie się na mnie, nie chcę z tym wygrywać, ale w uwagach do wyzwania zachęciłem mnie do wyjaśnienia, o czym mówiłem.

Próbowałem użyć monady stanowej do obsługi dodawania pól oraz zliczania połączeń i par i to działało, ale nie udało mi się sprawić, aby moje rozwiązanie działało w tym ustawieniu. Zrobiłem więc to, co zasugerowałem w komentarzach: po prostu ukryj dane za konstruktorem danych i nie zaglądaj. (Czystym sposobem byłoby użycie oddzielnego modułu i nie eksportowanie konstruktora.) Ta wersja ma tę zaletę, że jest znacznie prostsza.

Ponieważ mówimy o pudełkach bitów, umieszczam Boolw nich wartości. Definiuję zerojako dane pole z bitem zerowym - a onenie jest potrzebne.

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

Używamy funkcji debugowania, traceaby zobaczyć, jak często fbyła wywoływana i z iloma parami. &&&przegląda pola według dopasowania wzorca, nierówność /= zastosowana w Boolwartościach wynosi 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)

testFunkcja przyjmuje ślepego binarnego sumatora jako pierwszego argumentu, a następnie dwa numery w którym dodatek jest badane. Zwraca Boolwskazanie, czy test się powiódł. Najpierw tworzone są pola wprowadzania, następnie wywoływany jest sumator, wynik jest rozpakowywany (z unB) i porównywany z oczekiwanym wynikiem.

Zaimplementowałem dwa sumatory, przykładowe rozwiązanie simple, dzięki czemu możemy zobaczyć, że dane wyjściowe debugowania działają poprawnie, a moje rozwiązanie używa rekurencji wartości 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]) ] ]

Widzisz, jak się definiuję respod względem samego siebie? Jest to również znane jako wiązanie węzła .

Teraz możemy zobaczyć, jak fnazywa się to tylko raz:

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

Lub zamień valrecna, simpleaby zobaczyć, jak fjest wywoływany 32 razy.

Wypróbuj online! (wyniki śledzenia są wyświetlane w obszarze „Debugowanie”)

JavaScript, 32 połączenia, 32 pary, 388 bajtów

Dyalog APL, 32 połączenia, 32 pary, 270 bajtów

To naiwne przykładowe rozwiązanie, które może służyć jako szablon.

Zauważ, że liczba bajtów musi obejmować tylko sekcję otoczoną „POCZĄTEK / ROZWIĄZANIE KOŃCOWE”.

Wyjaśnienie:

Wybrałem kolejność bitów little-endian (bit x[0]jest najmniej znaczący).

Zauważ, że mod dodawania 1-bitowego można zrealizować jako F([[[x,y],[x,y]]])(to znaczy: x*x ^ y*y- mnożenie mod 2 jest idempotentne), a mnożenie binarne jakoF([[[x],[y]]]) .

Przechodzimy przez bity od najmniej znaczącego do najbardziej znaczącego i na każdym kroku obliczamy bit wyniku i przeniesienie.

#!/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)

To samo w APL Dyalog (ale przy użyciu losowych identyfikatorów skrzynek):

⎕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)