Ein gewöhnliches N-stelliges Zahlenschloss besteht aus N rotierenden Scheiben. Auf jeder Disc sind die Ziffern 0 bis 9 in der angegebenen Reihenfolge angegeben, und Sie müssen sie auf das richtige Kennwort einstellen, um sie zu öffnen. Wenn Sie das Passwort nicht kennen, müssen Sie es natürlich höchstens 10 N- mal versuchen, bevor Sie es entsperren. Das ist nicht interessant.
Betrachten wir also eine Variante des Zahlenschlosses, nennen wir es abstandsoffenbar.
Bei jedem erfolglosen Versuch, ein abstandsoffenlegendes Schloss zu öffnen, reagiert es auf die Mindestanzahl der zu entsperrenden Bewegungen.
Eine Bewegung ist als Drehung um eine Position definiert, zum Beispiel 1 Bewegung von 890
bis 899
und 9 Bewegungen von 137
bis 952
.
Die Herausforderung
Versuchen Sie bei einem entfernungsabhängigen Schloss mit unbekanntem Kennwort, das Schloss mit einer minimalen Anzahl von Versuchen (keine Bewegungen) zu öffnen , ohne dass das Programm zu lang wird.
Regeln & Scorings
- Sie sollten ein vollständiges Programm schreiben, das Eingaben von stdin und Ausgaben von stdout ausführt. Das Programm sollte die Ein- / Ausgabe wie folgt ausführen:
Start
Input an integer N (number of digits) from stdin
Do
Output a line containing decimal string of length N (your attempt) to stdout
Input an integer K (response of the lock) from stdin
While K not equal 0
End
Ihr Programm sollte bis zu N = 200 verarbeiten und bei jeder Eingabe weniger als 5 Sekunden ausgeführt werden.
Führende Nullen in der Ausgabe sollten nicht ausgelassen werden.
Es gibt 5 Testdaten für jede Länge, sodass die Gesamtzahl der Testdaten 1000 beträgt. Die Testdaten werden zufällig generiert.
Das Endergebnis ist (Gesamtzahl der Vermutungen in allen Testdaten) * ln (Codelänge in Bytes + 50). Die niedrigste Punktzahl gewinnt. (ln ist natürlicher Baumstamm)
Ich werde das Programm für Sie bespielen. Wenn Sie wissen möchten, wie ich Ihr Programm bewerten werde, oder wenn Sie es selbst bewerten möchten, werfen Sie einen Blick auf frühere Änderungen in diesem Beitrag .
Diese Herausforderung endet am 2017/12/07 14:00 UTC. Ich werde dann meine Lösung posten.
Laufendes Beispiel
Zeilen, die mit " >
Eingabe" beginnen, und andere stehen für die Programmausgabe.
Sie können ein Passwort im Kopf haben und mit Ihrem Programm interagieren, um es zu testen.
> 3 # 3-digit lock. The hidden password is 746
000 # 1st guess (by program)
> 11 # response to the 1st guess
555 # 2nd guess
> 4 # ...
755
> 2
735
> 2
744
> 2
746 # finally the correct answer! The program attempts 6 times.
> 0 # this is not necessary
Beispielprogramm
BEARBEITEN: Vielleicht war das Eingabe- / Ausgabeformat oben nicht klar. Hier ist ein Beispielprogramm in Python.
Python, 369 Bytes, Gesamtzahl der Versuche = 1005973, Punktzahl = 6073935
import sys
N = int(input()) # get the lock size
ans = ''
for i in range(N): # for each digit
lst = []
for j in range(10): # try all numbers
print('0' * i + str(j) + '0' * (N - i - 1)) # make a guess
result = int(input()) # receive the response
lst.append(result)
ans += str(lst.index(min(lst)))
print(ans) # output the final answer
Vielen Dank an Jonah für die Vereinfachung der Herausforderung.
quelle
162751*ln(388+50)=989887
.C # (.NET Core) , 617 Byte, Versuche insgesamt = 182255, Punktzahl = 1185166
Hoffentlich funktioniert C # in diesem Format für Sie. Es liegt in Form eines vollständigen Programms vor, daher sollte es eine Möglichkeit geben, eine ausführbare Datei zu kompilieren. Lassen Sie mich wissen, ob ich etwas tun kann, um es einfacher zu machen. Bytes sind Teil der Wertung, obwohl das Code Golf-Tag entfernt wurde, sodass meine offizielle Einreichung alle nicht benötigten Leerzeichen und nützlichen Namen entfernt. Meine folgende Erklärung wird Fragmente des ungolfed Codes verwenden:
Erläuterung
Dieses Programm verwendet nur eine einzige Hilfsmethode:
Dies schreibt die Vermutung auf stdout und liest dann den Abstand von stdin. Es beendet auch sofort das Programm, wenn eine Vermutung die genaue Kombination ist. Ich nenne es viel. Als nächstes die Ersteinrichtung:
Dies ermittelt die Länge der Kombination und beginnt dann mit allen Nullen zu raten. Danach durchläuft es jede Ziffer in einer
for
Schleife.Für jede Ziffer wird 5 erraten, und anschließend wird der nächste Schritt basierend auf der Änderung der Entfernung seit der vorherigen Schätzung (wobei diese Ziffer 0 war) festgelegt.
Wenn der Abstand um 5 erhöht wurde, war 0 für diesen Abstand korrekt. Stellen Sie diese Ziffer auf 0 zurück. Wenn Sie die aufgezeichnete Entfernung manuell ändern, wird eine zusätzliche Vermutung verhindert.
Wenn sich die Distanz um 5 verringert, ist 5 die richtige Ziffer und wir bewegen uns sofort zur nächsten Ziffer.
Danach sind die Dinge schwierig. Die Verwendung von
5
und0
für meine anfänglichen Vermutungen bedeutet, dass die verbleibenden Differenzmöglichkeiten3, 1, -1, -3
mit jeweils 2 Möglichkeiten bestehen, für die 1 zusätzliche Vermutung zur Unterscheidung erforderlich ist. Jeder dieser Fälle hat eine ähnliche FormEinige der Zahlen ändern sich, aber im Wesentlichen versuchen wir eine der beiden Möglichkeiten und prüfen, ob die Änderung für diese Ziffer die richtige war. Wenn dies nicht der Fall ist, ist die andere Ziffer korrekt, sodass wir diese Ziffer festlegen und die Differenz dann manuell anpassen.
Diese Methode bedeutet, dass wir höchstens 1 Vermutung für die anfänglichen Nullen, 2 Vermutungen pro Ziffer und dann 1 endgültige Vermutung benötigen sollten, um sicherzustellen, dass die letzte Ziffer nicht durchfällt.
Es könnte zwar fehlerhaft sein, es funktioniert soweit ich es manuell überprüft habe, aber das ist keine Garantie.Fehler gefunden und gequetscht dank Colera Suquelle
37
. Die Ausgabe ist:00, 50, 30, 75, 75
(ja, zwei 75er).<
mit>
in everyif
inswitch
scheint den Fehler zu beheben. Wenn du das willst, ist deine Punktzahl182255*ln(617+50)=1185166
.Python 2 und 3: 175 Bytes, Gesamtversuche = 1005972, Punktzahl = 5448445
Dieses Programm benötigt maximal (log (n)) * 10 Versuche pro Kombination oder jede einzelne Ziffer benötigt 10 Versuche (also
333
30 Versuche).Vielen Dank an Colera Su, die mir bei der Eingabe / Ausgabe-Funktionalität geholfen hat.
Python-Version von Challenge ( geändert durch OP ).
Ich habe eine Version des Sperrcodes in Python geschrieben. Sie können weitermachen und verwenden, wenn Sie versuchen, dies in Python zu lösen (wie ich). Das Folgende funktioniert in Python 2 und 3. Es war viel sinnvoller, nur Lock als eine Klasse zu implementieren, mit der Sie testen können, und ich habe beschlossen, eine Generatorfunktion zum Erraten der Eingaben zu erstellen.
quelle
LockIO
Klasse falsch geschrieben habe. Ich habe eine Bearbeitungsanfrage gesendet. Zweitens denke ich, dass Sie das Bewertungskriterium falsch verstanden haben. Die Punktzahl wird anhand der vom Generator generierten Testdaten berechnet, nicht beispielsweise (Ich habe Ihr Programm ausgeführt und die Gesamtzahl ist 1005972). Das natürliche Protokoll fehlt ebenfalls. Drittens habe ich angegeben, dass Sie ein vollständiges Programm bereitstellen müssen, daher sollten Sie denLockIO
Teil auch in Ihre Byteanzahl aufnehmen. Zusätzlich müssen Sie das Endergebnis ausgeben, und das wird auch in der Punktzahl gezählt.Lock
undmasterLock
dient nur zum bequemen Testen.LockIO
ist das, was Sie tatsächlich einreichen müssen, da es das erforderliche E / A-Format verwendet.R ,
277 Bytes (Punktzahl = 1175356)258 Bytes, Gesamtversuche = 202999, Punktzahl = 1163205Probieren Sie es online!
Stdin-stdout-Version, wie vom OP gefordert, keine Boilerplates. Vielen Dank an Colera Su für die Behebung eines anfänglichen Fehlers. Dies ist eine geringfügig kürzere Version als die in den Kommentaren.
Hier unter der TIO-Vorlage, um eine Reihe von Tests innerhalb von TIO durchzuführen
R , 189 Bytes
Probieren Sie es online!
Betrachten wir einen Vektor von Nullen als die anfängliche Vermutung. Nennen wir V den Abstand zwischen der aktuellen Vermutung und der Lösung. Für jede Position müssen Sie nur die Änderungen in V überprüfen, wenn Sie 0 durch 5 und 4 ersetzen. Tatsächlich sind die Unterschiede zwischen dem Ändern von 0 durch 5 in meinem Vektor s1 aufgeführt. Die Unterschiede zwischen dem Ändern von 0 mit 4 sind in meinem Vektor s2 aufgeführt. Wie Sie sehen, bilden diese beiden Vektoren die Ziffern der Lösung eindeutig ab.
Die Gesamtzahl der Tests ist also
3 * L2 * L + 1, wobei L die Länge des Codes ist: eine erste Prüfung gegen alle Nullen, dann zwei Prüfungen für jede Ziffer, eine gegen 5 und eine gegen 4.Die Verbesserung von Faktor 3 auf Faktor 2 wurde von Kamil Drakaris Beitrag inspiriert.
Der Rest der TIO-Einreichung ist ein Boilerplate für R. Die TIO-Einreichung zeigt die Laufzeit und die Gesamtanzahl der Vorgänge für 1000 Läufe mit L = 1 ... 200, 5 Wiederholungen für jeden Wert von L.
quelle
Error in scan(n = 1) : scan() expected 'a real', got 'S=rep(0,L)'
bei der Ausführung.scan(file=file("stdin"),n=1)
funktionieren. Dieses Programm (genau wie Ihr, nur korrigierte E / A) erhält eine Punktzahl von202999*ln(277+50)=1175356
.202999*ln(258+50) != 202999*ln(277+50)