10
2
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
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. – Christian Sievers – 2017-08-29T20:18:41.473I 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". – ngn – 2017-08-29T20:53:08.317
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 letx
depend ony
. – Christian Sievers – 2017-08-29T21:00:34.703I'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. – ngn – 2017-08-29T21:16:21.063
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 implementf
(Haskell forces lowercase here) - I'll give it a try tomorrow. – ngn – 2017-08-29T21:51:57.837I think this should work:
data Box=B Int deriving(Show);add(B x)(B y)=B(x+y);iprd[][]=B 0;iprd(B x:xs)(B y:ys)=add(B$x*y)(iprd xs ys);f[]=[];f([x,y]:ps)=(iprd x y):f ps;main=do print$f[[[B 2,B 3],[B 4,B 5]],[[B 6],[B 7]]]
Of course, on condition you never peek behind the tagB
:) Sorry about my horrible un-Haskell-like coding style. – ngn – 2017-08-29T23:00:03.380I really... don't understand what is being asked. in your example code for
F
,pairs
is a list of tuples of.. what? it seems like they are box ids (aka, index inH
) but yourH
is mostly empty. Am I supposed to hidea
andb
inside myH
before callingF(pairs)
in brilliant ways to geta+b
? so then the challenge is about using the results of "inner product each" to do addition – JoshRagem – 2017-08-30T02:14:36.750@JoshRagem "
pairs
is a list of tuples of.. what?" - ..of arrays of box ids. "but yourH
is mostly empty" - In the JS versionB()
appends toH
and returns its old length as a box id. In Haskell it may be better to haveB
as a data constructor and not haveH
at all, like in my previous comment (by the way, I realised I've made a mistake there - addition should be mod 2). Or you may come up with some clever construct that does it in a better way. – ngn – 2017-08-30T07:32:03.410