Imaginez que vous avez deux boîtes B(x)et B(y)chacune contenant un bit inconnu - 0 ou 1, et une machine Fqui peut les radiographier et produire une troisième boîte pour B(x^y)( xor ). Fpeut également calculer B(x*y)( et ). En fait, ce ne sont que des cas particuliers de l'opération unique que la machine peut effectuer - produit intérieur chacun , noté F()ci-dessous.

Pour deux tableaux de même longueur

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

le produit intérieur est défini comme

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

« Chaque » signifie F()peut traiter de multiples paires de x[], y[]en une seule fois. Le x[]et y[]d'une paire doivent être de la même longueur; x[]-s et y[]-s de différentes paires n'en ont pas nécessairement besoin.

Les boîtes sont représentées par des identifiants entiers uniques.

Une implémentation de produit interne chacun en JavaScript pourrait ressembler

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

(Veuillez traduire ce qui précède dans la langue de votre choix.)

Étant donné l'accès à une F()implémentation appropriée à votre langue (mais pas d'accès à Hou B()) et compte tenu de deux tableaux d'ID de boîte constituant les représentations binaires 16 bits de deux entiers aet b, votre tâche consiste à produire des ID de boîte pour la représentation binaire 16 bits de a+b(rejet du débordement) avec le nombre minimum d' F()appels.

La solution qui appelle F()le moins de fois gagne. Les égalités seront brisées en comptant le nombre total de x[],y[]paires F()appelées - moins c'est mieux. S'il est toujours lié, la taille de votre code (à l'exclusion de l'implémentation de F()et de ses assistants) détermine le gagnant de la manière traditionnelle du golf de code. Veuillez utiliser un titre comme "MyLang, 123 appels, 456 paires, 789 octets" pour votre réponse.

Écrivez une fonction ou un programme complet. Les entrées / sorties / arguments / résultats sont des tableaux int dans n'importe quel format raisonnable. La représentation binaire peut être en petit ou en gros - choisissez-en une.

Annexe 1: Pour rendre le défi un peu plus facile, vous pouvez supposer que les cases avec les identifiants 0 et 1 contiennent les valeurs 0 et 1. Cela vous donne des constantes, utiles par exemple pour la négation ( x^1n'est "pas"). Il y avait bien sûr des moyens de contourner le manque de constantes, mais le reste du défi est assez difficile de toute façon, alors éliminons cette distraction.

Annexe 2: Pour gagner la prime, vous devez effectuer l'une des actions suivantes:

• publier votre score (appels, paires, octets) et votre code avant la date limite

• publier votre score et un hachage sha256 de votre code avant la date limite; puis affichez le code réel dans les 23 heures après la date limite

Python 3 , 5 appels, 92 paires, 922 octets

Python 3 , 5 appels, 134 paires, 3120 octets

Python 3 , 6 appels, 106 paires, 2405 octets

[JavaScript (Node.js)], 9 appels, 91 paires, 1405 octets

JavaScript (Node.js), 16 appels, 31 paires, 378 octets

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

Essayez-le en ligne!

PREMIÈRE VERSION D'accord, ce n'est pas du golf. C'est juste une adaptation du code de @ ngn.

La seule idée ici est que vous n'avez pas besoin de calculer le dernier report puisque vous jetez le débordement. De plus, les appels de Fsont regroupés par deux. Peut-être qu'ils peuvent être regroupés d'une autre manière, mais je doute que vous puissiez réduire considérablement le nombre de paires, en raison de la nature de l'algorithme d'addition de base.

EDIT : Toujours pas joué au golf. Le nombre de paires pourrait certainement être réduit, et probablement aussi le nombre d'appels. Voir https://gist.github.com/jferard/864f4be6e4b63979da176bff380e6c62 pour une "preuve" avec sympy.

EDIT 2 Passé à Python car il est plus lisible pour moi. Maintenant que j'ai la formule générale, je pense que je peux atteindre la limite de 5 (peut-être 4) appels.

EDIT 3 Voici les briques de base:

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

La formule générale est la suivante:

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

La version étendue est:

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 appels me semble la limite. Maintenant, j'ai un peu de travail pour retirer les paires et jouer au golf!

EDIT 4 J'ai joué à celui-ci.

Version non golfée:

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

Essayez-le en ligne!

Haskell, 1 appel (triche ???), 32 paires (pourrait être amélioré), 283 octets (même)

S'il vous plaît, ne vous fâchez pas contre moi, je ne veux pas gagner avec ça, mais j'ai été encouragé dans les remarques au défi d'expliquer de quoi je parlais.

J'ai essayé d'utiliser la monade d'état pour gérer l'ajout de boîtes et le comptage des appels et des paires, et cela a fonctionné, mais je n'ai pas réussi à faire fonctionner ma solution dans ce paramètre. J'ai donc fait ce qui était également suggéré dans les commentaires: il suffit de cacher les données derrière un constructeur de données et de ne pas jeter un œil. (La meilleure façon serait d'utiliser un module séparé et de ne pas exporter le constructeur.) Cette version a l'avantage d'être beaucoup plus simple.

Puisque nous parlons de boîtes de bits, je leur mets des Boolvaleurs. Je définis zerocomme la case donnée avec le bit zéro - un onen'est pas nécessaire.

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

Nous utilisons la fonction de débogage trace pour voir à quelle fréquence a fété appelée et avec combien de paires. &&&examine les cases par correspondance de motifs, l'inégalité /= utilisée sur les Boolvaleurs est 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)

La testfonction prend un additionneur binaire aveugle comme premier argument, puis deux nombres pour lesquels l'addition est testée. Il renvoie un Boolindiquant si le test a réussi. Les boîtes de saisie sont d'abord créées, puis l'additionneur est appelé, le résultat non encadré (avec unB) et comparé au résultat attendu.

J'ai implémenté deux additionneurs, l'exemple de solution simple, afin que nous puissions voir que la sortie de débogage fonctionne correctement, et ma solution en utilisant la récursion de valeur 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]) ] ]

Vous voyez comment je me définis resen termes de lui-même? Cela est également connu sous le nom de faire le nœud .

Maintenant, nous pouvons voir comment fest appelé une seule fois:

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

Ou remplacer valrec par simplepour voir fêtre appelé 32 fois.

Essayez-le en ligne! (la sortie de suivi apparaît sous "Debug")

JavaScript, 32 appels, 32 paires, 388 octets

Dyalog APL, 32 appels, 32 paires, 270 octets

Il s'agit d'un exemple de solution naïve qui peut servir de modèle.

Notez que le nombre d'octets ne doit inclure que la section entourée de "BEGIN / END SOLUTION".

Explication:

J'ai choisi l'ordre des bits en petit bout ( x[0]c'est le bit le moins significatif).

Observez que l'addition sur un seul bit mod 2 peut être réalisée comme F([[[x,y],[x,y]]])(c'est-à-dire: x*x ^ y*y- la multiplication mod 2 est idempotente) et la multiplication binaire comme F([[[x],[y]]]).

Nous parcourons les bits du moins significatif au plus significatif et calculons à chaque étape un bit de résultat et un report.

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

La même chose dans Dyalog APL (mais en utilisant des identifiants de boîte aléatoires):

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