Stellen Sie sich vor, Sie haben zwei Boxen B(x)
und B(y)
jeweils ein unbekanntes Bit - 0 oder 1 - und eine Maschine F
, die sie röntgen und eine dritte Box für B(x^y)
( xor ) produzieren kann. F
kann auch berechnen B(x*y)
( und ). Tatsächlich sind dies nur Sonderfälle des einzelnen Vorgangs, den die Maschine ausführen kann - jeweils ein inneres Produkt , das F()
unten angegeben ist.
Für zwei Arrays gleicher Länge
[B(x[0]), B(x[1]), ..., B(x[n-1])]
[B(y[0]), B(y[1]), ..., B(y[n-1])]
inneres Produkt ist definiert als
B(x[0]*y[0] ^ x[1]*y[1] ^ ... ^ x[n-1]*y[n-1])
„ Jede “ Mittel F()
können mehrere Paare von verarbeiten x[]
, y[]
in einem Arbeitsgang. Das x[]
und y[]
von einem Paar muss gleich lang sein; x[]
-s und y[]
-s von verschiedenen Paaren müssen nicht unbedingt.
Boxen werden durch eindeutige Ganzzahl-IDs dargestellt.
Eine Implementierung des inneren Produkts in JavaScript könnte folgendermaßen aussehen
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);
})
}
(Bitte übersetzen Sie das Obige in die Sprache Ihrer Wahl.)
Der Zugang zu einer F()
Implementierung als geeignet für Ihre Sprache (aber keinen Zugang zu H
oder B()
) und bei zwei Anordnungen von Box - IDs , welche die 16-Bit-Darstellungen von zwei ganzen Zahlen a
und b
Ihre Aufgabe ist es , Produkte Box - IDs für die 16-Bit - Binärdarstellung von a+b
(Überlauf verwerfen) mit der Mindestanzahl von F()
Anrufen.
Die Lösung, die F()
am wenigsten anruft, gewinnt. Krawatten werden durch Zählen der Gesamtzahl der x[],y[]
Paare, F()
mit denen aufgerufen wurde , unterbrochen - weniger ist besser. Wenn immer noch gebunden, bestimmt die Größe Ihres Codes (mit Ausnahme der Implementierung von F()
und seiner Helfer) den Gewinner auf herkömmliche Weise. Bitte verwenden Sie einen Titel wie "MyLang, 123 Anrufe, 456 Paare, 789 Bytes" für Ihre Antwort.
Schreiben Sie eine Funktion oder ein komplettes Programm. Eingabe / Ausgabe / Argumente / Ergebnis sind int-Arrays in jedem vernünftigen Format. Die binäre Darstellung kann klein oder groß sein - wählen Sie eine aus.
Anhang 1: Um die Herausforderung etwas zu vereinfachen, können Sie davon ausgehen, dass Felder mit den IDs 0 und 1 die Werte 0 und 1 enthalten. Dies gibt Ihnen Konstanten, die beispielsweise für die Negation nützlich sind ( x^1
ist "nicht"). Es gab natürlich Möglichkeiten, den Mangel an Konstanten zu umgehen, aber der Rest der Herausforderung ist sowieso schwer genug, also lasst uns diese Ablenkung beseitigen.
Anhang 2: Um das Kopfgeld zu gewinnen, müssen Sie einen der folgenden Schritte ausführen:
Veröffentlichen Sie Ihre Punktzahl (Anrufe, Paare, Bytes) und Ihren Code vor Ablauf der Frist
Veröffentlichen Sie Ihre Punktzahl und einen sha256-Hash Ihres Codes vor Ablauf der Frist. Geben Sie dann den tatsächlichen Code innerhalb von 23 Stunden nach Ablauf der Frist ein
F
nur einmal aufrufen . Das wäre sicherlich Betrug, aber ich bin mir nicht sicher, ob es gut oder schlecht wäre.y=f(x)
und davonx
abhängen lasseny
.data Box = B Int deriving (Show); f :: [[[Box]]] -> [Box]
Ich brauche mehr Zeit, um herauszufinden, wie man es implementiertf
(Haskell erzwingt hier Kleinbuchstaben) - ich werde es morgen versuchen.Antworten:
Python 3 , 5 Aufrufe, 92 Paare, 922 Bytes
Python 3 , 5 Aufrufe, 134 Paare, 3120 BytesPython 3 , 6 Aufrufe, 106 Paare, 2405 Bytes[JavaScript (Node.js)], 9 Aufrufe, 91 Paare, 1405 BytesJavaScript (Node.js), 16 Aufrufe, 31 Paare, 378 BytesProbieren Sie es online aus!
ERSTE VERSION Okay, das ist kein Golf. Es ist nur eine Anpassung von @ ngns Code.
Die einzige Idee hier ist, dass Sie den letzten Übertrag nicht berechnen müssen, da Sie den Überlauf verwerfen. Außerdem werden die Anrufe
F
von zu zwei gruppiert. Vielleicht können sie auf andere Weise gruppiert werden, aber ich bezweifle, dass Sie die Anzahl der Paare aufgrund der Art des grundlegenden Additionsalgorithmus erheblich reduzieren können.EDIT : Immer noch nicht Golf gespielt. Die Anzahl der Paare könnte sicherlich reduziert werden, und wahrscheinlich auch die Anzahl der Anrufe. Unter https://gist.github.com/jferard/864f4be6e4b63979da176bff380e6c62 finden Sie einen "Beweis" mit Sympy.
EDIT 2 Zu Python gewechselt, weil es für mich besser lesbar ist. Jetzt habe ich die allgemeine Formel, ich denke, ich kann das Limit von 5 (vielleicht 4) Anrufen erreichen.
EDIT 3 Hier sind die Grundbausteine:
Die allgemeine Formel lautet:
Die erweiterte Version lautet:
5 Anrufe scheinen mir das Limit zu sein. Jetzt habe ich ein wenig Arbeit, um Paare zu entfernen und Golf zu spielen!
EDIT 4 Ich habe diesen Golf gespielt.
Ungolfed Version:
Probieren Sie es online aus!
quelle
F()
. Ich garantiere, dass es eine Möglichkeit gibt, diese erheblich zu reduzieren (das ist der schwierigste Teil dieser Herausforderung), und dann wird es Raum geben, die Anzahl der Paare zu optimieren und schließlich natürlich den Code zu spielen (aber das ist das am wenigsten wichtige Kriterium).... + x * y * z + ...
. Wir können es nicht verwendenF
, um es auszuwerten, aber wenn wirx * y
mit dem vorherigenF
Aufruf berechnet haben, müssen wir nur Folgendes tun:... + (x * y) * z + ...
(es entspricht dem Format vonF
). Als ich mit Sympy spielte, konnte ich einen Anruf ersparen (Schritt 1: Berechne r0, c0, r1; Schritt 2: Berechne c1 und einige Hilfswerte; Schritt 3: Berechne r2, c2, r3, c3) und suche jetzt nach einem General Lösung.Haskell, 1 Aufruf (Betrug ???), 32 Paare (könnte verbessert werden), 283 Bytes (gleich)
Bitte sei mir nicht böse, ich möchte damit nicht gewinnen, aber ich wurde in den Bemerkungen zur Herausforderung ermutigt, zu erklären, wovon ich sprach.
Ich habe versucht, mit der Statusmonade Boxen hinzuzufügen und Anrufe und Paare zu zählen, und das hat funktioniert, aber ich habe es nicht geschafft, meine Lösung in dieser Einstellung zum Laufen zu bringen. Also habe ich getan, was auch in den Kommentaren vorgeschlagen wurde: Verstecke einfach die Daten hinter einem Datenkonstruktor und gucke nicht. (Der saubere Weg wäre, ein separates Modul zu verwenden und den Konstruktor nicht zu exportieren.) Diese Version hat den Vorteil, dass sie viel einfacher ist.
Da es sich um Bitboxen handelt, habe ich
Bool
Werte in sie eingefügt. Ich definierezero
als die angegebene Box mit dem Nullbit - aone
wird nicht benötigt.Wir verwenden die Debugging-Funktion
trace
zu sehen, wie oftf
und mit wie vielen Paaren aufgerufen wurde.&&&
schaut in die Kästchen durch Mustervergleich, die/=
fürBool
Werte verwendete Ungleichung istxor
.Die
test
Funktion verwendet einen blinden binären Addierer als erstes Argument und dann zwei Zahlen, für die die Addition getestet wird. Es wird angezeigtBool
, ob der Test erfolgreich war. Zuerst werden die Eingabefelder erstellt, dann wird der Addierer aufgerufen, das Ergebnis entpackt (mitunB
) und mit dem erwarteten Ergebnis verglichen.Ich habe zwei Addierer implementiert, die Beispiellösung
simple
, damit wir sehen können, dass die Debug-Ausgabe korrekt funktioniert, und meine Lösung mithilfe der Wertrekursionvalrec
.Sehen Sie, wie ich
res
in Bezug auf sich selbst definiere? Das wird auch als Knotenbinden bezeichnet .Jetzt können wir sehen wie
f
nur einmal aufgerufen wird:Oder ersetzen
valrec
durchsimple
, zu sehen,f
dass 32 Mal aufgerufen wird.Probieren Sie es online aus! (Die Tracing-Ausgabe erscheint unter "Debug")
quelle
f
eine faule, möglicherweise unendliche Liste, die sich materialisiert, wenn Sie sie durchlaufen? Ich fürchte , das ist , gegen den Geist der Herausforderung - es lässt Sie die Entscheidung über verschieben , was als das passiereni+1
-st Argument bis nach Sie das Ergebnis erhalten haben an den entsprechendeni
-te. Es ist viel interessanter herauszufinden, wie viele Anrufef
Sie mit vollständig materialisierten, unveränderlichen Argumenten benötigen :)f
könnte zwar unendlich viel Eingabe geben (unendliche Bitströme hinzufügen, yay!), Aber das ist nicht der Punkt. Oh, und tatsächlich stellt dietrace
Nachricht sicher, dass die Länge endlich und am Anfang bekannt ist. Ich würde auch nicht sagen, dass es eine aufgeschobene Entscheidung gibt: Alles wurde im Voraus geplant, wie gefordert, ich mische nur blind Kisten. Und beachten Sie, dass es nicht um die Reihenfolge der Argumente geht: Ich könnte es so ändern, dass esres
zuerst das Ergebnis und dann die Übertragsbits enthält.f
. Geben Sie dieses Feld als weiteres Argument im selben Aufruf an zurückf
?JavaScript, 32 Aufrufe, 32 Paare, 388 Bytes
Dyalog APL, 32 Aufrufe, 32 Paare, 270 Bytes
Dies ist eine naive Beispiellösung, die als Vorlage dienen kann.
Beachten Sie, dass die Byteanzahl nur den Abschnitt enthalten darf, der von "BEGIN / END SOLUTION" umgeben ist.
Erläuterung:
Ich habe die Little-Endian-Bitreihenfolge gewählt (
x[0]
ist das niedrigstwertige Bit).Beachten Sie, dass Einzelbit-Additionsmod 2 als
F([[[x,y],[x,y]]])
(dh:x*x ^ y*y
- Multiplikationsmod 2 ist idempotent) und binäre Multiplikation als realisiert werden kannF([[[x],[y]]])
.Wir durchlaufen die Bits von niedrigstwertig zu höchstwertig und berechnen bei jedem Schritt ein Ergebnisbit und einen Übertrag.
Das gleiche gilt für Dyalog APL (jedoch unter Verwendung randomisierter Box-IDs):
quelle