Imagina que tienes dos cajas B(x)
y B(y)
, cada una con un bit desconocido: 0 o 1, y una máquina F
que puede radiografiarlas y producir una tercera caja para B(x^y)
( xor ). F
Tambié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 H
ao B()
) y se le dieron dos matrices de identificadores de caja que constituyen las representaciones binarias de 16 bits de dos enteros a
y b
su 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
F
solo una vez. Eso seguramente sería hacer trampa, pero no estoy seguro de si sería una buena trampa o una mala trampa.y=f(x)
y dejaréx
dependery
.data Box = B Int deriving (Show); f :: [[[Box]]] -> [Box]
Necesitaré más tiempo para descubrir cómo implementarf
(Haskell fuerza las minúsculas aquí). Mañana lo intentaré.Respuestas:
Python 3 , 5 llamadas, 92 pares, 922 bytes
Python 3 , 5 llamadas, 134 pares, 3120 bytesPython 3 , 6 llamadas, 106 pares, 2405 bytes[JavaScript (Node.js)], 9 llamadas, 91 pares, 1405 bytesJavaScript (Node.js), 16 llamadas, 31 pares, 378 bytesPrué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
F
se 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:
La fórmula general es:
La versión ampliada es:
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:
Pruébalo en línea!
fuente
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).... + x * y * z + ...
. No podemos usarF
para evaluarlo, pero si hemos calculadox * y
con laF
llamada anterior , solo tenemos que hacer:... + (x * y) * z + ...
(coincide con el formato deF
). 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.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
Bool
valores. Lo definozero
como el cuadro dado con el bit cero: aone
no es necesario.Estamos utilizando la función de depuración
trace
para ver con qué frecuenciaf
se llamó y con cuántos pares.&&&
mira en los cuadros por coincidencia de patrones, la desigualdad/=
utilizada en losBool
valores esxor
.La
test
función toma un sumador binario ciego como primer argumento, y luego dos números para los que se prueba la suma. Devuelve unaBool
indicació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 valoresvalrec
.¿Ves cómo me estoy definiendo
res
en términos de sí mismo? Eso también se conoce como atar el nudo .Ahora podemos ver cómo
f
solo se llama una vez:O sustituir
valrec
porsimple
al verf
que se llama 32 veces.Pruébalo en línea! (la salida de seguimiento aparece en "Depurar")
fuente
f
es 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 eli+1
argumento -st hasta después de que haya obtenido el resultado correspondiente a lai
-ésima. Es mucho más interesante saber cuántas llamadasf
necesitará con argumentos totalmente inmutables y materializados :)f
podría tomar una entrada infinita (agregar flujos de bits infinitos, ¡sí!), Ese no es el punto. Ah, y en realidad eltrace
mensaje 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 queres
contenga primero el resultado y luego los bits de acarreo.f
; ¿Retroalimenta esa casilla como otro argumento en la misma llamadaf
?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 comoF([[[x],[y]]])
.Atravesamos los bits de menos significativo a más significativo y en cada paso calculamos un bit de resultado y un carry.
Lo mismo en Dyalog APL (pero usando identificadores de caja aleatorios):
fuente