Víbora binaria ciega

10

Imagina que tienes dos cajas B(x)y B(y), cada una con un bit desconocido: 0 o 1, y una máquina Fque puede radiografiarlas y producir una tercera caja para B(x^y)( xor ). FTambién puede calcular B(x*y)( y ). De hecho, esos son solo casos especiales de la operación única que la máquina puede realizar: producto interno de cada uno , indicado a F()continuación.

Para dos matrices de la misma longitud

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

producto interno se define como

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

" Cada " medio F()puede procesar múltiples pares de x[], y[]de una sola vez. El x[]y y[]de un par debe ser de la misma longitud; x[]-s y y[]-s de diferentes pares no necesariamente lo necesitan.

Las cajas están representadas por identificadores enteros únicos.

Una implementación de producto interno cada uno en JavaScript podría verse como

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

(Por favor, traduzca lo anterior a su idioma de elección).

Se le dio acceso a una F()implementación según sea apropiado para su idioma (pero sin acceso Hao B()) y se le dieron dos matrices de identificadores de caja que constituyen las representaciones binarias de 16 bits de dos enteros ay bsu tarea es producir identificadores de caja para la representación binaria de 16 bits de a+b(descartar desbordamiento) con el número mínimo de F()llamadas.

La solución que llama F()la menor cantidad de veces gana. Los lazos se romperán contando el número total de x[],y[]pares con los que F()se llamó: menos es mejor. Si aún está empatado, el tamaño de su código (excluyendo la implementación de F()y sus ayudantes) determina el ganador en la forma tradicional de golf de código. Utilice su título como "MyLang, 123 llamadas, 456 pares, 789 bytes" para su respuesta.

Escribe una función o un programa completo. Entrada / salida / argumentos / resultado son matrices int en cualquier formato razonable. La representación binaria puede ser little-o big-endian: elija una.


Apéndice 1: para facilitar un poco el desafío, puede suponer que los cuadros con ID 0 y 1 contienen los valores 0 y 1. Esto le da constantes, útiles, por ejemplo, para la negación ( x^1"no"). Había maneras de evitar la falta de constantes, por supuesto, pero el resto del desafío es bastante difícil de todos modos, así que eliminemos esta distracción.


Apéndice 2: Para ganar la recompensa, debe hacer uno de los siguientes:

  • publique su puntaje (llamadas, pares, bytes) y su código antes de la fecha límite

  • publique su puntaje y un hash sha256 de su código antes de la fecha límite; luego publique el código real dentro de las 23 horas posteriores a la fecha límite

ngn
fuente
Si traduje esto a mi idioma de elección (Haskell), podría usar la recurrencia de valor y llamar Fsolo una vez. Eso seguramente sería hacer trampa, pero no estoy seguro de si sería una buena trampa o una mala trampa.
Christian Sievers
Sé que el estado global no es bienvenido en Haskell, pero permítanme preguntar esto como un experimento mental: si incrementara un contador global en la implementación de F, ¿cuánto crecería al final? - ese es mi entendimiento de "número de llamadas".
ngn
Podría hacer exactamente eso, y diría 1. Pero no se pudo traducir a JavaScript usando su código. Esencialmente diría y=f(x)y dejaré xdepender y.
Christian Sievers
Me temo que no entiendo cómo funcionaría eso. ¿Podría mostrar un código de muestra, por favor? Mi Haskell es pobre, pero estoy seguro de que puedo resolverlo si puedo jugar con el código.
ngn
¿Quizás podamos usar los siguientes tipos para modelar este problema? data Box = B Int deriving (Show); f :: [[[Box]]] -> [Box]Necesitaré más tiempo para descubrir cómo implementar f(Haskell fuerza las minúsculas aquí). Mañana lo intentaré.
ngn

Respuestas:

6

Python 3 , 5 llamadas, 92 pares, 922 bytes

Python 3 , 5 llamadas, 134 pares, 3120 bytes

Python 3 , 6 llamadas, 106 pares, 2405 bytes

[JavaScript (Node.js)], 9 llamadas, 91 pares, 1405 bytes

JavaScript (Node.js), 16 llamadas, 31 pares, 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

Pruébalo en línea!

PRIMERA VERSIÓN Bueno, eso no es golf. Es solo una adaptación del código de @ ngn.

La única idea aquí es que no necesita calcular el último acarreo ya que descarta el desbordamiento. Además, las llamadas de Fse agrupan por dos. Tal vez puedan agruparse de otra manera, pero dudo que pueda reducir significativamente el número de pares, debido a la naturaleza del algoritmo de suma básico.

EDITAR : Todavía no golf. El número de pares ciertamente podría reducirse, y probablemente también el número de llamadas. Ver https://gist.github.com/jferard/864f4be6e4b63979da176bff380e6c62 para una "prueba" con sympy.

EDITAR 2 Cambió a Python porque es más legible para mí. Ahora que tengo la fórmula general, creo que puedo alcanzar el límite de 5 (quizás 4) llamadas.

EDITAR 3 Aquí están los ladrillos básicos:

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

La fórmula general es:

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

La versión ampliada es:

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 llamadas me parecen el límite. ¡Ahora tengo un poco de trabajo para eliminar pares y jugar golf!

EDITAR 4 Golfé este.

Versión sin golf:

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

Pruébalo en línea!

jferard
fuente
Muy bien :) Encontraste las dos optimizaciones fáciles que dejé a propósito. "Dudo que pueda reducir significativamente el número de pares". Tenga en cuenta que el primer criterio para ganar es el número de llamadas a F(). Le garantizo que hay una manera de reducirlos significativamente (esa es la parte más difícil de este desafío), y luego habrá espacio para optimizar el número de pares, y finalmente, por supuesto, jugar el código (pero ese es el criterio menos importante).
ngn
Ok lo tengo! Más pronto o más tarde, ha obtenido como resultado que: ... + x * y * z + .... No podemos usar Fpara evaluarlo, pero si hemos calculado x * ycon la Fllamada anterior , solo tenemos que hacer: ... + (x * y) * z + ...(coincide con el formato de F). Jugando con sympy, logré ahorrar una llamada (paso1: calcular r0, c0, r1; paso2: calcular c1 y algunos valores auxiliares; paso3: calcular r2, c2, r3, c3), y ahora estoy buscando un general solución.
jferard
Sí, en otras palabras: los bits de salida son polinomios de grado superior a 2 en los bits de entrada. El producto interno puede combinar un polinomio de grado m y grado n en un polinomio de (m + n) grados, como máximo. No se apresure: en unas horas podré establecer una recompensa :)
partir del
Es posible que desee considerar aprovechar el Apéndice 2 anterior. O bien: si alguien copia su código, elimina un espacio y lo vuelve a publicar, técnicamente tendré que otorgarle el bono.
ngn
2
Para el registro, es imposible usar menos de cinco llamadas, ya que la solución requiere un polinomio de grado 32. (El polinomio correspondiente a cualquier función de los bits de entrada es único.)
Nitrodon el
2

Haskell, 1 llamada (trampa ???), 32 pares (podría mejorarse), 283 bytes (igual)

Por favor, no te enfades conmigo, no quiero ganar con esto, pero en las observaciones al desafío me animaron a explicar de qué estaba hablando.

Traté de usar la mónada estatal para manejar agregar cuadros y contar llamadas y pares, y funcionó, pero no pude hacer que mi solución funcionara en ese entorno. Así que hice lo que también se sugirió en los comentarios: solo esconder los datos detrás de un constructor de datos y no mirar. (La manera limpia sería usar un módulo separado y no exportar el constructor). Esta versión tiene la ventaja de ser mucho más simple.

Como estamos hablando de cajas de bits, les pongo Boolvalores. Lo defino zerocomo el cuadro dado con el bit cero: a oneno es necesario.

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

Estamos utilizando la función de depuración tracepara ver con qué frecuencia fse llamó y con cuántos pares. &&&mira en los cuadros por coincidencia de patrones, la desigualdad /= utilizada en los Boolvalores es 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 testfunción toma un sumador binario ciego como primer argumento, y luego dos números para los que se prueba la suma. Devuelve una Boolindicación de si la prueba fue exitosa. Primero se crean los cuadros de entrada, luego se llama al sumador, el resultado sin caja (conunB ) y se compara con el resultado esperado.

Implementé dos sumadores, la solución de muestra simple, para que podamos ver que la salida de depuración funciona correctamente, y mi solución utiliza la recursividad de valores 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]) ] ]

¿Ves cómo me estoy definiendo resen términos de sí mismo? Eso también se conoce como atar el nudo .

Ahora podemos ver cómo fsolo se llama una vez:

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

O sustituir valrecpor simpleal ver fque se llama 32 veces.

Pruébalo en línea! (la salida de seguimiento aparece en "Depurar")

Christian Sievers
fuente
No hay enojo aquí :) Entonces, si entiendo correctamente, ¿el argumento fes una lista perezosa y potencialmente infinita que se materializa a medida que la iteras? Me temo que va contra el espíritu del desafío - que le permite aplazar la decisión sobre lo que debe pasar por el i+1argumento -st hasta después de que haya obtenido el resultado correspondiente a la i-ésima. Es mucho más interesante saber cuántas llamadas fnecesitará con argumentos totalmente inmutables y materializados :)
ngn
Estoy de acuerdo. @jferard ha hecho un trabajo increíble que no debería ser invalidado por tal truco. Si bien fpodría tomar una entrada infinita (agregar flujos de bits infinitos, ¡sí!), Ese no es el punto. Ah, y en realidad el tracemensaje asegura que la longitud es finita y conocida al principio. Además, no diría que hay una decisión diferida: todo fue planeado con anticipación, ya que exigía que solo estuviese barajando ciegamente las cajas. Y tenga en cuenta que no se trata del orden de los argumentos: podría cambiarlo para que rescontenga primero el resultado y luego los bits de acarreo.
Christian Sievers
"Solo estoy barajando a ciegas cajas" - Supongamos que ha obtenido una caja al llamar f; ¿Retroalimenta esa casilla como otro argumento en la misma llamada f?
ngn
Sí. De eso se trata la recursividad de valor. Tenías ese derecho: está usando la pereza y el hecho de que puedo usar argumentos que no están completamente materializados (me gusta esa descripción). Dado el obvio espíritu del desafío, eso es, como se anunció, claramente hacer trampa. Si uno piensa que es inventivo o digno de mención, puede argumentar que es un buen engaño.
Christian Sievers
Ciertamente es del tipo bueno, obviamente no tienes intención de engañar aquí. La pereza en la programación funcional es un concepto hermoso y tiene sus usos válidos. Cuando intenté aprender algo de Haskell hace unos años, recuerdo estar muy impresionado con una frase que "ata el nudo" de los números de Fibonacci.
ngn
0

JavaScript, 32 llamadas, 32 pares, 388 bytes

Dyalog APL, 32 llamadas, 32 pares, 270 bytes

Esta es una solución de muestra ingenua que puede servir como plantilla.

Tenga en cuenta que el recuento de bytes debe incluir solo la sección rodeada por "COMENZAR / FINALIZAR SOLUCIÓN".

Explicación:

Elegí el orden de bits little-endian (x[0] es el bit menos significativo).

Observe que el mod 2 de suma de un solo bit puede realizarse como F([[[x,y],[x,y]]])(es decir: x*x ^ y*y- el mod 2 de multiplicación es idempotente) y la multiplicación binaria como F([[[x],[y]]]).

Atravesamos los bits de menos significativo a más significativo y en cada paso calculamos un bit de resultado y un 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)

Lo mismo en Dyalog APL (pero usando identificadores de caja aleatorios):

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