10
\$\begingroup\$

Imagine you have two boxes B(x) and B(y), each containing an unknown bit - 0 or 1, and a machine F that can X-ray them and produce a third box for B(x^y) (xor). F can also compute B(x*y) (and). In fact, those are just special cases of the the single operation the machine can perform - inner product each, denoted with F() below.

For two same-length arrays

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

inner product is defined as

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

"Each" means F() can process multiple pairs of x[], y[] in one go. The x[] and y[] from one pair must be of the same length; x[]-s and y[]-s from different pairs don't necessarily need to.

Boxes are represented by unique integer ids.

An implementation of inner product each in JavaScript might look like

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

(Please translate the above to your language of choice.)

Given access to an F() implementation as appropriate for your language (but no access to H or B()) and given two arrays of box ids constituting the 16-bit binary representations of two integers a and b, your task is to produce box ids for the 16-bit binary representation of a+b (discarding overflow) with the minimum number of F() calls.

The solution that calls F() the fewest times wins. Ties will be broken by counting the total number of x[],y[] pairs F() was called with - fewer is better. If still tied, the size of your code (excluding the implementation of F() and its helpers) determines the winner in the traditional code golf way. Please use a title like "MyLang, 123 calls, 456 pairs, 789 bytes" for your answer.

Write a function or a complete program. Input/output/arguments/result is int arrays in any reasonable format. Binary representation may be little- or big-endian - choose one.


Appendix 1: To make the challenge slightly easier, you can assume that boxes with ids 0 and 1 contain the values 0 and 1. This gives you constants, useful e.g. for negation (x^1 is "not"). There were ways around the lack of constants, of course, but the rest of the challenge is hard enough anyway, so let's eliminate this distraction.


Appendix 2: To win the bounty, you must do one of the following:

  • post your score (calls,pairs,bytes) and your code before the deadline

  • post your score and a sha256 hash of your code before the deadline; then post the actual code within 23 hours after the deadline

\$\endgroup\$
  • \$\begingroup\$ If I translated this into my language of choice (Haskell), I could use value recursion and call F only once. That would surely be cheating, but I'm not sure if it would be good cheating or bad cheating. \$\endgroup\$ – Christian Sievers Aug 29 '17 at 20:18
  • \$\begingroup\$ I know global state isn't welcome in Haskell, but let me ask this as a thought experiment: if I incremented a global counter in the implementation of F, by how much would have it grown at the end? - that is my understanding of "number of calls". \$\endgroup\$ – ngn Aug 29 '17 at 20:53
  • \$\begingroup\$ I could do exactly that, and it would say 1. But it could not be translated back to JavaScript using your code. Essentially I'd say y=f(x) and let x depend on y. \$\endgroup\$ – Christian Sievers Aug 29 '17 at 21:00
  • \$\begingroup\$ I'm afraid I don't understand how that would work. Could you show sample code, please? My Haskell is poor, but I'm sure I can figure it out if I can play with the code. \$\endgroup\$ – ngn Aug 29 '17 at 21:16
  • \$\begingroup\$ Perhaps we can use the following types to model this problem? data Box = B Int deriving (Show); f :: [[[Box]]] -> [Box] I'll need more time to figure out how to implement f (Haskell forces lowercase here) - I'll give it a try tomorrow. \$\endgroup\$ – ngn Aug 29 '17 at 21:51
6
+500
\$\begingroup\$

Python 3, 5 calls, 92 pairs, 922 bytes

Python 3, 5 calls, 134 pairs, 3120 bytes

Python 3, 6 calls, 106 pairs, 2405 bytes

[JavaScript (Node.js)], 9 calls, 91 pairs, 1405 bytes

JavaScript (Node.js), 16 calls, 31 pairs, 378 bytes

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

Try it online!

FIRST VERSION Okay that's not golfed. It's just an adaptation of @ngn's code.

The only idea here is that you don't need to compute the last carry since you discard overflow. Also, the calls of F are grouped by two. Maybe they may be grouped in another way, but I doubt you can reduce significantly the number of pairs, due to the nature of the basic addition algorithm.

EDIT: Still not golfed. The number of pairs could certainly be reduced, and probably the number of calls too. See https://gist.github.com/jferard/864f4be6e4b63979da176bff380e6c62 for a "proof" with sympy.

EDIT 2 Switched to Python because it's more readable for me. Now I have got the general formula, I think I may reach the limit of 5 (maybe 4) calls.

EDIT 3 Here are the basic bricks:

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

The general formula is:

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

The expanded version is:

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 calls seems the limit for me. Now I have a little work to remove pairs and golf it!

EDIT 4 I golfed this one.

Ungolfed version:

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

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Very good :) You found the two easy optimisations I left out on purpose. "I doubt you can reduce significantly the number of pairs" - note that the first criterion for winning is the number of calls to F(). I guarantee there is a way to reduce those significantly (that's the hardest part of this challenge), and then there will be room for optimising the number of pairs, and finally of course golfing the code (but that's the least important criterion). \$\endgroup\$ – ngn Aug 27 '17 at 18:50
  • \$\begingroup\$ Ok I got it! Sooner or later, you got something like that: ... + x * y * z + .... We can't use F to evaluate it, but if we have computed x * y with the previous F call, we just have to do: ... + (x * y) * z + ... (it matches the format of F). Playing with sympy, I managed to spare a call (step1: compute r0,c0,r1; step2: compute c1 and some aux values; step3: compute r2,c2,r3,c3), and I'm now loooking for a general solution. \$\endgroup\$ – jferard Aug 28 '17 at 13:55
  • \$\begingroup\$ Yep, in other words: the output bits are polynomials of degree higher than 2 in the input bits. Inner product can combine an m-degree and n-degree polynomial into an (m+n)-degree polynomial, at most. Don't rush - in a few hours I'll be able to set up a bounty :) \$\endgroup\$ – ngn Aug 28 '17 at 14:11
  • \$\begingroup\$ You might want to consider taking advantage of Appendix 2 above. Or else: if someone copies your code, removes a space, and reposts it, technically I'll have to award the bonus to them. \$\endgroup\$ – ngn Aug 30 '17 at 7:35
  • 2
    \$\begingroup\$ For the record, it is impossible to use fewer than five calls, since the solution requires a degree 32 polynomial. (The polynomial corresponding to any function of the input bits is unique.) \$\endgroup\$ – Nitrodon Aug 31 '17 at 4:26
1
\$\begingroup\$

Haskell, 1 call (cheating???), 32 pairs (could be improved), 283 bytes (same)

Please don't be angry with me, I don't want to win with this, but I was encouraged in the remarks to the challenge to explain what I was talking about.

I tried to use the state monad to handle adding boxes and counting calls and pairs, and that worked, but I didn't manage to make my solution working in that setting. So I did what was also suggested in the comments: just hide the data behind a data constructor and don't peek. (The clean way would be to use a seperate module and not export the constructor.) This version has the advantage of being much simpler.

Since we are talking about boxes of bits, I put Bool values into them. I define zero as the given box with the zero bit - a one is not needed.

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

We're using the debugging function trace to see how often f was called, and with how many pairs. &&& looks into the boxes by pattern matching, the inequality /= used on Bool values is 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 test function takes a blind binary adder as first argument, and then two numbers for which addition is tested. It returns a Bool indicating whether the test was successful. First the input boxes are created, then the adder is called, the result unboxed (with unB) and compared with the expected result.

I implemented two adders, the sample solution simple, so that we can see that the debug output works correctly, and my solution using value recursion 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]) ] ]

See how I'm defining res in terms of itself? That is also known as tying the knot.

Now we can see how f is only called once:

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

Or replace valrec by simple to see f being called 32 times.

Try it online! (the tracing output appears under "Debug")

\$\endgroup\$
  • \$\begingroup\$ No anger here :) So, if I understand correctly, the argument to f is a lazy, potentially infinite list that materialises as you iterate through it? I'm afraid that's against the spirit of the challenge - it lets you to defer the decision about what to pass as the i+1-st argument til after you've obtained the result corresponding to the i-th. It's much more interesting to find out how many calls to f you'll need with fully materialised, immutable arguments :) \$\endgroup\$ – ngn Aug 30 '17 at 9:01
  • \$\begingroup\$ I agree. @jferard has done amazing work that shouldn't be invalidated by such a trick. While f could take infinite input (add infinite bit streams,yay!), that is not the point. Oh, and actually the trace message ensures that the length is finite and known at the beginning. Also, I wouldn't say that there is a deferred decision: everything was planned ahead of time, as demanded I am just blindly shuffling boxes. And note it's not about order of arguments: I could change it so that res contains first the result and then the carry bits. \$\endgroup\$ – Christian Sievers Aug 30 '17 at 10:33
  • \$\begingroup\$ "I am just blindly shuffling boxes" - Suppose you've obtained a box from calling f; do you feed back that box as another argument in the same call to f? \$\endgroup\$ – ngn Aug 30 '17 at 10:43
  • \$\begingroup\$ Yes, I do. That is what value recursion is all about. You had that right: it's using lazyness and the fact that I can use arguments that are not fully materialized (I like that description). Given the obvious spirit of the challenge, that's - as announced - clearly cheating. If one thinks it's inventive or noteworthy, one may argue that it's good cheating. \$\endgroup\$ – Christian Sievers Aug 30 '17 at 10:59
  • \$\begingroup\$ It's certainly of the good kind - obviously you have no intention to deceive here. Laziness in functional programming is a beautiful concept and it has its valid uses. When I tried to learn some Haskell a few years ago, I remember being very impressed with a one-liner that "ties the knot" for the Fibonacci numbers. \$\endgroup\$ – ngn Aug 30 '17 at 11:16
0
\$\begingroup\$

JavaScript, 32 calls, 32 pairs, 388 bytes

Dyalog APL, 32 calls, 32 pairs, 270 bytes

This is a naïve sample solution that can serve as a template.

Note that the byte count must include only the section surrounded with "BEGIN/END SOLUTION".

Explanation:

I chose little-endian bit order (x[0] is the least significant bit).

Observe that single-bit addition mod 2 can be realised as F([[[x,y],[x,y]]]) (that is: x*x ^ y*y - multiplication mod 2 is idempotent) and binary multiplication as F([[[x],[y]]]).

We traverse the bits from least significant to most significant and at each step compute a result bit and a 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)

The same in Dyalog APL (but using randomised box ids):

⎕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)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.