Inspiriert von The Great API Easter Egg Hunt!
Zusammenfassung
Ihre Aufgabe ist es, im "Collatz-Raum" (der später erklärt wird) mit möglichst wenigen Schritten nach einer vorgegebenen Ganzzahl zu suchen.
Einführung
Diese Herausforderung basiert auf der berühmten Collatz-Vermutung, von der hoffentlich jeder hier zumindest gehört hat. Hier ist eine Zusammenfassung von Print the Super Collatz-Nummern .
In der Collatz-Sequenz (auch als 3x + 1-Problem bezeichnet) beginnen Sie mit einer positiven Ganzzahl. In diesem Beispiel verwenden wir 10 und wenden diese Schritte darauf an:
if n is even: Divide it by 2 if n is odd: Multiply it by 3 and add 1 repeat until n = 1
Der Collatz-Abstand C(m,n)
zwischen den beiden Zahlen m
und n
für die Zwecke dieser Herausforderung der Abstand zwischen zwei Zahlen im Collatz-Diagramm (Dank an @tsh, um mich über dieses Konzept zu informieren), der wie folgt definiert ist: (anhand 21
und 13
als Beispiele ):
Schreiben Sie die Collatz-Sequenz für m
(in diesem Fall 21
) auf:
21, 64, 32, 16, 8, 4, 2, 1
Schreiben Sie die Collatz-Sequenz für n
(in diesem Fall 13
) auf:
13, 40, 20, 10, 5, 16, 8, 4, 2, 1
Zählen Sie nun, wie viele Zahlen nur in einer der Sequenzen erscheinen. Dies ist definiert als der Collatz-Abstand zwischen m
und n
. In diesem Fall 8
nämlich.
21, 64, 32, 13, 40, 20, 10, 5
Wir haben also Collatz Abstand zwischen 21
und 13
als C(21,13)=8
.
C(m,n)
haben die folgenden schönen Eigenschaften:
C(m,n)=C(n,m)
C(m,n)=0 iff. m=n
Hoffentlich ist die Definition von C(m,n)
jetzt klar. Beginnen wir mit der Eiersuche im Collatz-Raum!
Zu Beginn des Spiels entscheidet ein Controller über die Position eines Ostereies, die durch seine eindimensionale Koordinate ausgedrückt wird: Eine Ganzzahl im Intervall [p,q]
(mit anderen Worten eine Ganzzahl zwischen p
und q
, beide Enden einschließlich).
Die Position des Eies bleibt während des Spiels konstant. Wir bezeichnen diese Koordinate als r
.
Sie können jetzt eine erste Schätzung einer 0 vornehmen , die vom Controller aufgezeichnet wird. Dies ist deine 0. Runde. Wenn Sie so viel Glück haben, dass Sie es auf den ersten Platz richtig gemacht haben (dh eine 0 = r), endet das Spiel und Ihre Punktzahl ist 0
(Je niedriger die Punktzahl, desto besser). Andernfalls betreten Sie die 1. Runde und raten eine neue 1 , dies geht so lange weiter, bis Sie es richtig verstanden haben, dh a n = r, und Ihre Punktzahl wird sein n
.
Für jede Runde nach dem 0. gibt Ihnen der Controller eine der folgenden Rückmeldungen, damit Sie anhand der angegebenen Informationen eine bessere Vermutung anstellen können. Nehmen wir an, Sie befinden sich derzeit in der n
dritten Runde und daher ist Ihre Vermutung ein n
- "Du hast es gefunden!" Wenn a n = r, endet das Spiel und Sie erzielen ein Tor
n
. - "Du bist näher :)" wenn C (a n , r) <C (a n-1 , r)
- "Sie kreisen um das Ei", wenn C (a n , r) = C (a n-1 , r)
- "Du bist weiter weg :(" wenn C (a n , r)> C (a n-1 , r)
Um einige Bytes zu sparen, werde ich die Antworten in der oben angegebenen Reihenfolge als "Richtig", "Näher", "Gleich", "Weiter" bezeichnen.
Hier ist ein Beispielspiel mit p=1,q=15
.
- a 0 = 10
- a 1 = 11, Antwort: "Näher"
- a 2 = 13, Antwort: "Weiter"
- a 3 = 4, Antwort: "Weiter"
- a 4 = 3, Antwort: "Näher"
- a 5 = 5, Antwort: "Same"
- a 6 = 7, Antwort: "Richtig"
Punktzahl : 6
.
Herausforderung
Entwerfen Sie eine deterministische Strategie, um das Spiel p=51, q=562
mit der besten Punktzahl zu spielen.
Die Antworten sollten die Algorithmen im Detail beschreiben. Sie können jeden Code anhängen, der zur Erläuterung des Algorithmus beiträgt. Dies ist kein Codegolf, daher sollten Sie lesbaren Code schreiben.
Die Antworten sollten die schlechteste Punktzahl enthalten, die sie in allen möglichen Fällen erreichen können r
, und diejenige mit der niedrigsten schlechtesten Punktzahl gewinnt. Im Falle eines Unentschieden gewinnen die Algorithmen, die eine bessere durchschnittliche Punktzahl für alle möglichen r
s haben (die auch in den Antworten enthalten sein sollten). Es gibt keine weiteren Tie Breaker und wir haben möglicherweise am Ende mehrere Gewinner.
Technische Daten
- Um es noch einmal zu wiederholen,
r
liegt in der Pause[51,562]
. - Es gelten Standardlücken .
Kopfgeld (hinzugefügt, nachdem die erste Antwort veröffentlicht wurde)
Ich kann persönlich eine Prämie für eine Antwort anbieten, bei der alle Vermutungen innerhalb des Bereichs gemacht werden, [51,562]
während ich immer noch eine einigermaßen niedrige schlechteste Punktzahl habe.
quelle
Antworten:
Ruby, 196
Das war viel schwieriger, als ich ursprünglich gedacht hatte. Ich musste mit vielen obskuren Fällen umgehen und bekam viel hässlichen Code. Aber es hat viel Spaß gemacht! :) :)
Strategie
Jede Collatz-Sequenz endet mit einer Potenzfolge von 2 (Beispiel: [16, 8, 4, 2, 1]). Sobald eine Potenz von 2 angetroffen wird, teilen wir durch 2, bis wir 1 erreichen. Nennen wir die erste Potenz von 2 in einer Sequenz, die pow2 am nächsten kommt (da dies auch die Potenz von 2 ist, die unserer Zahl mit Collatz Distance am nächsten kommt). Für den angegebenen Bereich (51-562) sind alle möglichen nächsten pow2- Zahlen: [16, 64, 128, 256, 512, 1024]
Kurzfassung
Der Algorithmus führt Folgendes aus:
Detaillierte Version
Bei einem Spiel mit der Zielnummer
r
lautet die Strategie wie folgt:r
in so wenigen Schritten wie möglich die Potenz von 2 zu ermitteln, die am nächsten kommt .Die Ergebnisse
Das Ausführen des Algorithmus für alle Zahlen im Bereich 51-562 dauert auf einem normalen PC ungefähr eine Sekunde und die Gesamtpunktzahl beträgt 38665.
Der Code
Probieren Sie es online aus!
quelle
schlechteste Punktzahl: 11, Gesamtpunktzahl: 3986
Alle Vermutungen sind in Reichweite
[51,562]
.Mein Algorithmus:
vals
. Zunächst enthält die Menge alle Zahlen im Bereich[51,562]
.Gehen Sie bei jedem Schritt wie folgt vor:
guess
in Reihe ,[51,562]
so dass, wenn die Werte invals
(ohneguess
selbst) in 3 Sätzen partitioniert ist auf die möglichen Ergebnisse entsprichtCloser
,Same
undFarther
ist die maximale Größe dieser 3 Sätze Minimum.Wenn es mehrere mögliche Werte gibt,
guess
die die oben genannten erfüllen, wählen Sie den kleinsten.guess
.vals
so, dass sie möglicherweise nicht zu diesem Ergebnis führen können.Meine in C ++ und Bash geschriebene Referenzimplementierung läuft auf meinem Computer in ca. 7,6 Sekunden und liefert die schlechteste Punktzahl / Summenpunktzahl, wie im Titel beschrieben.
Das Ausprobieren aller möglichen First-Guess-Werte dauert auf meinem Computer ungefähr 1,5 Stunden. Ich könnte darüber nachdenken, das zu tun.
quelle