Ślepy sumator binarny

10

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

ngn
źródło
Gdybym przetłumaczył to na mój wybrany język (Haskell), mógłbym użyć rekurencji wartości i zadzwonić Ftylko raz. To z pewnością byłoby oszustwo, ale nie jestem pewien, czy byłoby to dobre oszustwo, czy złe.
Christian Sievers
Wiem, że stan globalny nie jest mile widziany w Haskell, ale pozwólcie, że zapytam o to jako eksperyment myślowy: jeśli zwiększę globalny licznik w implementacji F, o ile by to wzrosło na końcu? - tak rozumiem „liczbę połączeń”.
ngn
Mógłbym zrobić dokładnie to, a powiedziałoby to 1. Ale nie można go było przetłumaczyć z powrotem na JavaScript za pomocą twojego kodu. Zasadniczo powiedziałbym y=f(x)i pozwolę xpolegać y.
Christian Sievers
Obawiam się, że nie rozumiem, jak to by działało. Czy mógłbyś pokazać przykładowy kod? Mój Haskell jest kiepski, ale jestem pewien, że mogę to rozgryźć, jeśli będę mógł grać z kodem.
ngn
Być może możemy użyć następujących typów do modelowania tego problemu? data Box = B Int deriving (Show); f :: [[[Box]]] -> [Box]Potrzebuję więcej czasu, aby dowiedzieć się, jak wdrożyć f(Haskell zmusza tu małe litery) - jutro spróbuję.
ngn

Odpowiedzi:

6

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!

Jferard
źródło
Bardzo dobrze :) Znalazłeś dwie łatwe optymalizacje, które celowo pominąłem. „Wątpię, czy można znacznie zmniejszyć liczbę par” - zauważ, że pierwszym kryterium wygranej jest liczba połączeń do F(). Gwarantuję, że istnieje sposób na znaczne ich zmniejszenie (jest to najtrudniejsza część tego wyzwania), a następnie będzie miejsce na optymalizację liczby par, a na końcu oczywiście grę w golfa (ale jest to najmniej ważne kryterium).
ngn
Ok, rozumiem! Prędzej czy później, masz coś takiego: ... + x * y * z + .... Nie możemy go użyć Fdo oceny, ale jeśli dokonaliśmy obliczeń x * yz poprzedniego Fwywołania, musimy tylko: ... + (x * y) * z + ...(pasuje do formatu F). Grając w sympy, udało mi się oszczędzić połączenia (krok 1: oblicz r0, c0, r1; krok 2: oblicz c1 i niektóre wartości Aux; krok 3: oblicz r2, c2, r3, c3), a teraz szukam ogólnego rozwiązanie.
jferard
Tak, innymi słowy: bity wyjściowe są wielomianami stopnia większego niż 2 w bitach wejściowych. Produkt wewnętrzny może łączyć najwyżej wielomian stopnia m i stopnia n z wielomianem stopnia (m + n). Nie spiesz się - za kilka godzin będę mógł założyć nagrodę :)
ngn
Możesz rozważyć skorzystanie z Załącznika 2 powyżej. Albo inaczej: jeśli ktoś skopiuje kod, usunie spację i opublikuje go ponownie, technicznie będę musiał przyznać mu premię.
ngn
2
Dla przypomnienia, nie można użyć mniej niż pięciu połączeń, ponieważ rozwiązanie wymaga wielomianu stopnia 32. (Wielomian odpowiadający dowolnej funkcji bitów wejściowych jest unikalny.)
Nitrodon
2

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

Christian Sievers
źródło
Tu nie ma gniewu :) Więc, jeśli dobrze rozumiem, argumentem fjest leniwa, potencjalnie nieskończona lista, która materializuje się podczas iteracji? Obawiam się, że jest to sprzeczne z duchem wyzwania - pozwala ci odłożyć decyzję o tym, co przekazać jako-pierwszy i+1argument do momentu, gdy uzyskasz wynik odpowiadający i-temu. O wiele bardziej interesujące jest ustalenie, ile połączeń fpotrzebujesz, dzięki w pełni zmaterializowanym, niezmiennym argumentom :)
ngn
Zgadzam się. @jferard wykonał niesamowitą pracę, której taka sztuczka nie powinna unieważnić. Chociaż fmoże pobierać nieskończone dane wejściowe (dodawać nieskończone strumienie bitów, tak!), Nie o to chodzi. Och, a tak naprawdę tracewiadomość zapewnia, że ​​długość jest skończona i znana na początku. Nie powiedziałbym też, że decyzja jest odroczona: wszystko zostało zaplanowane z wyprzedzeniem, zgodnie z żądaniem, ja po prostu ślepo tasuję pudełka. I zauważ, że nie chodzi o kolejność argumentów: mógłbym to zmienić, aby reszawierał najpierw wynik, a następnie bity przenoszenia.
Christian Sievers
„Po prostu ślepo tasuję skrzynki” - Załóżmy, że otrzymałeś skrzynkę z rozmowy f; czy przekazujesz to pole jako kolejny argument w tym samym wywołaniu do f?
ngn
Tak. Na tym właśnie polega rekurencja wartości. Masz rację: używa lenistwa i faktu, że mogę używać argumentów, które nie są w pełni zmaterializowane (podoba mi się ten opis). Biorąc pod uwagę oczywistą atmosferę wyzwania, to - jak zapowiedziano - wyraźnie oszukuje. Jeśli ktoś uważa, że ​​jest pomysłowy lub godny uwagi, może argumentować, że to dobre oszustwo.
Christian Sievers
Z pewnością jest to dobry rodzaj - oczywiście nie masz zamiaru oszukiwać tutaj. Lenistwo w programowaniu funkcjonalnym to piękna koncepcja i ma swoje uzasadnione zastosowanie. Kiedy kilka lat temu próbowałem nauczyć się Haskella, pamiętam, że byłem pod wielkim wrażeniem jednowierszowej, która „wiąże węzeł” z liczbami Fibonacciego.
ngn
0

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