Über die Serie
Zunächst einmal können Sie dies wie jede andere Code-Golf-Herausforderung behandeln und beantworten, ohne sich Gedanken über die Serie zu machen. Es gibt jedoch eine Rangliste für alle Herausforderungen. Sie finden die Rangliste zusammen mit einigen weiteren Informationen über die Serie im ersten Beitrag .
Obwohl ich eine Menge Ideen für die Serie habe, sind die zukünftigen Herausforderungen noch nicht in Stein gemeißelt. Wenn Sie Vorschläge haben, teilen Sie mir dies bitte auf dem entsprechenden Sandbox-Post mit .
Loch 6: Wirf einen W20
Ein sehr häufiger Würfel in RPGs mit Tischplatte ist der zwanzigseitige Würfel (ein Ikosaeder , allgemein bekannt als d20 ). Es ist deine Aufgabe, einen solchen Würfel zu werfen. Wenn Sie jedoch nur eine Zufallszahl zwischen 1 und 20 zurückgeben würden, wäre dies ein bisschen trivial. Deine Aufgabe ist es also, ein zufälliges Netz für einen bestimmten Würfel zu generieren.
Wir werden das folgende Netz verwenden:
Es ist ein Dreiecksstreifen, so dass es leicht als Liste von ganzen Zahlen dargestellt werden kann. ZB wenn Sie die Eingabe erhalten:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
Das würde dem folgenden Würfel entsprechen (lustige Tatsache: Dies ist das von Magic verwendete Netz : die Lebensmarken der Sammlung / Spin-down-Würfel).
Dies ist jedoch nicht das einzige Netz, das diesen Würfel darstellt. Je nachdem, wie wir die Gesichter abrollen, gibt es 60 verschiedene Netze. Hier sind zwei weitere:
[1, 8, 9, 10, 2, 3, 4, 5, 6, 7, 17, 18, 19, 11, 12, 13, 14, 15, 16, 20]
[10, 9, 18, 19, 11, 12, 3, 2, 1, 8, 7, 17, 16, 20, 13, 14, 4, 5, 6, 15]
Oder grafisch (der Einfachheit halber habe ich die Gesichtsbeschriftungen nicht gedreht):
Die Herausforderung
Ausgehend von einer Liste von Ganzzahlen, die einen Würfel (wie oben beschrieben) darstellen, und einer Ganzzahl N
werden N
unabhängig voneinander einheitlich zufällige d20-Netze ausgegeben , die dem gegebenen Würfel entsprechen. (Das heißt, jedes der 60 möglichen Netze sollte die gleiche Wahrscheinlichkeit haben, generiert zu werden.)
Aufgrund der technischen Einschränkungen von PRNGs ist eine perfekte Gleichmäßigkeit natürlich nicht möglich. Um die Gleichmäßigkeit Ihrer Einreichung zu beurteilen, werden die folgenden Vorgänge als perfekt gleichmäßige Verteilungen ergebend angesehen:
- Beziehen einer Nummer von einem PRNG (über einen beliebigen Bereich), von dem dokumentiert wird, dass sie (ungefähr) einheitlich ist.
- Abbildung einer gleichmäßigen Verteilung über eine größere Menge von Zahlen auf eine kleinere Menge durch Modulo oder Multiplikation (oder eine andere Operation, die Werte gleichmäßig verteilt). Die größere Menge muss mindestens das 1024-fache der möglichen Werte der kleineren Menge enthalten.
Unter diesen Voraussetzungen muss Ihr Algorithmus eine vollkommen gleichmäßige Verteilung ergeben.
Ihr Programm sollte in der Lage sein, 100 Netze in weniger als einer Sekunde zu generieren (versuchen Sie also nicht, zufällige Netze zu generieren, bis eines dem oben angegebenen Würfel entspricht).
Sie können ein Programm oder eine Funktion schreiben, indem Sie eine Eingabe über STDIN (oder die nächstgelegene Alternative), ein Befehlszeilenargument oder ein Funktionsargument vornehmen und das Ergebnis über STDOUT (oder die nächstgelegene Alternative), einen Funktionsrückgabewert oder einen Funktionsparameter (out) ausgeben.
Die Ein- und Ausgabe kann in einem beliebigen praktischen, eindeutigen, flachen Listenformat erfolgen. Sie können davon ausgehen, dass es sich bei den Nennwerten des d20 um eindeutige positive Ganzzahlen handelt, die zum natürlichen Ganzzahltyp Ihrer Sprache passen.
Dies ist Codegolf, daher gewinnt die kürzeste Übermittlung (in Byte). Und natürlich wird die kürzeste Einreichung pro Benutzer auch in die Gesamt-Bestenliste der Serie aufgenommen.
Beispielausgaben
Für die Eingabe
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
Die 60 möglichen Netze (vorausgesetzt, ich habe keinen Fehler gemacht) sind in keiner bestimmten Reihenfolge:
[11, 10, 9, 18, 19, 20, 13, 12, 3, 2, 1, 8, 7, 17, 16, 15, 14, 4, 5, 6]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
[8, 7, 17, 18, 9, 10, 2, 1, 5, 6, 15, 16, 20, 19, 11, 12, 3, 4, 14, 13]
[3, 12, 13, 14, 4, 5, 1, 2, 10, 11, 19, 20, 16, 15, 6, 7, 8, 9, 18, 17]
[3, 4, 5, 1, 2, 10, 11, 12, 13, 14, 15, 6, 7, 8, 9, 18, 19, 20, 16, 17]
[11, 19, 20, 13, 12, 3, 2, 10, 9, 18, 17, 16, 15, 14, 4, 5, 1, 8, 7, 6]
[4, 14, 15, 6, 5, 1, 2, 3, 12, 13, 20, 16, 17, 7, 8, 9, 10, 11, 19, 18]
[2, 10, 11, 12, 3, 4, 5, 1, 8, 9, 18, 19, 20, 13, 14, 15, 6, 7, 17, 16]
[4, 5, 1, 2, 3, 12, 13, 14, 15, 6, 7, 8, 9, 10, 11, 19, 20, 16, 17, 18]
[10, 2, 1, 8, 9, 18, 19, 11, 12, 3, 4, 5, 6, 7, 17, 16, 20, 13, 14, 15]
[3, 2, 10, 11, 12, 13, 14, 4, 5, 1, 8, 9, 18, 19, 20, 16, 15, 6, 7, 17]
[7, 8, 1, 5, 6, 15, 16, 17, 18, 9, 10, 2, 3, 4, 14, 13, 20, 19, 11, 12]
[13, 12, 11, 19, 20, 16, 15, 14, 4, 3, 2, 10, 9, 18, 17, 7, 6, 5, 1, 8]
[16, 15, 14, 13, 20, 19, 18, 17, 7, 6, 5, 4, 3, 12, 11, 10, 9, 8, 1, 2]
[15, 16, 17, 7, 6, 5, 4, 14, 13, 20, 19, 18, 9, 8, 1, 2, 3, 12, 11, 10]
[20, 13, 12, 11, 19, 18, 17, 16, 15, 14, 4, 3, 2, 10, 9, 8, 7, 6, 5, 1]
[5, 4, 14, 15, 6, 7, 8, 1, 2, 3, 12, 13, 20, 16, 17, 18, 9, 10, 11, 19]
[10, 11, 12, 3, 2, 1, 8, 9, 18, 19, 20, 13, 14, 4, 5, 6, 7, 17, 16, 15]
[4, 3, 12, 13, 14, 15, 6, 5, 1, 2, 10, 11, 19, 20, 16, 17, 7, 8, 9, 18]
[19, 20, 13, 12, 11, 10, 9, 18, 17, 16, 15, 14, 4, 3, 2, 1, 8, 7, 6, 5]
[1, 8, 9, 10, 2, 3, 4, 5, 6, 7, 17, 18, 19, 11, 12, 13, 14, 15, 16, 20]
[8, 1, 5, 6, 7, 17, 18, 9, 10, 2, 3, 4, 14, 15, 16, 20, 19, 11, 12, 13]
[18, 9, 8, 7, 17, 16, 20, 19, 11, 10, 2, 1, 5, 6, 15, 14, 13, 12, 3, 4]
[12, 3, 2, 10, 11, 19, 20, 13, 14, 4, 5, 1, 8, 9, 18, 17, 16, 15, 6, 7]
[2, 3, 4, 5, 1, 8, 9, 10, 11, 12, 13, 14, 15, 6, 7, 17, 18, 19, 20, 16]
[10, 9, 18, 19, 11, 12, 3, 2, 1, 8, 7, 17, 16, 20, 13, 14, 4, 5, 6, 15]
[9, 8, 7, 17, 18, 19, 11, 10, 2, 1, 5, 6, 15, 16, 20, 13, 12, 3, 4, 14]
[16, 17, 7, 6, 15, 14, 13, 20, 19, 18, 9, 8, 1, 5, 4, 3, 12, 11, 10, 2]
[17, 7, 6, 15, 16, 20, 19, 18, 9, 8, 1, 5, 4, 14, 13, 12, 11, 10, 2, 3]
[1, 5, 6, 7, 8, 9, 10, 2, 3, 4, 14, 15, 16, 17, 18, 19, 11, 12, 13, 20]
[9, 18, 19, 11, 10, 2, 1, 8, 7, 17, 16, 20, 13, 12, 3, 4, 5, 6, 15, 14]
[16, 20, 19, 18, 17, 7, 6, 15, 14, 13, 12, 11, 10, 9, 8, 1, 5, 4, 3, 2]
[5, 1, 2, 3, 4, 14, 15, 6, 7, 8, 9, 10, 11, 12, 13, 20, 16, 17, 18, 19]
[8, 9, 10, 2, 1, 5, 6, 7, 17, 18, 19, 11, 12, 3, 4, 14, 15, 16, 20, 13]
[13, 20, 16, 15, 14, 4, 3, 12, 11, 19, 18, 17, 7, 6, 5, 1, 2, 10, 9, 8]
[6, 15, 16, 17, 7, 8, 1, 5, 4, 14, 13, 20, 19, 18, 9, 10, 2, 3, 12, 11]
[6, 5, 4, 14, 15, 16, 17, 7, 8, 1, 2, 3, 12, 13, 20, 19, 18, 9, 10, 11]
[7, 6, 15, 16, 17, 18, 9, 8, 1, 5, 4, 14, 13, 20, 19, 11, 10, 2, 3, 12]
[19, 18, 17, 16, 20, 13, 12, 11, 10, 9, 8, 7, 6, 15, 14, 4, 3, 2, 1, 5]
[14, 15, 6, 5, 4, 3, 12, 13, 20, 16, 17, 7, 8, 1, 2, 10, 11, 19, 18, 9]
[17, 18, 9, 8, 7, 6, 15, 16, 20, 19, 11, 10, 2, 1, 5, 4, 14, 13, 12, 3]
[6, 7, 8, 1, 5, 4, 14, 15, 16, 17, 18, 9, 10, 2, 3, 12, 13, 20, 19, 11]
[14, 13, 20, 16, 15, 6, 5, 4, 3, 12, 11, 19, 18, 17, 7, 8, 1, 2, 10, 9]
[20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
[7, 17, 18, 9, 8, 1, 5, 6, 15, 16, 20, 19, 11, 10, 2, 3, 4, 14, 13, 12]
[15, 6, 5, 4, 14, 13, 20, 16, 17, 7, 8, 1, 2, 3, 12, 11, 19, 18, 9, 10]
[9, 10, 2, 1, 8, 7, 17, 18, 19, 11, 12, 3, 4, 5, 6, 15, 16, 20, 13, 14]
[2, 1, 8, 9, 10, 11, 12, 3, 4, 5, 6, 7, 17, 18, 19, 20, 13, 14, 15, 16]
[12, 13, 14, 4, 3, 2, 10, 11, 19, 20, 16, 15, 6, 5, 1, 8, 9, 18, 17, 7]
[17, 16, 20, 19, 18, 9, 8, 7, 6, 15, 14, 13, 12, 11, 10, 2, 1, 5, 4, 3]
[18, 17, 16, 20, 19, 11, 10, 9, 8, 7, 6, 15, 14, 13, 12, 3, 2, 1, 5, 4]
[18, 19, 11, 10, 9, 8, 7, 17, 16, 20, 13, 12, 3, 2, 1, 5, 6, 15, 14, 4]
[11, 12, 3, 2, 10, 9, 18, 19, 20, 13, 14, 4, 5, 1, 8, 7, 17, 16, 15, 6]
[15, 14, 13, 20, 16, 17, 7, 6, 5, 4, 3, 12, 11, 19, 18, 9, 8, 1, 2, 10]
[19, 11, 10, 9, 18, 17, 16, 20, 13, 12, 3, 2, 1, 8, 7, 6, 15, 14, 4, 5]
[12, 11, 19, 20, 13, 14, 4, 3, 2, 10, 9, 18, 17, 16, 15, 6, 5, 1, 8, 7]
[20, 16, 15, 14, 13, 12, 11, 19, 18, 17, 7, 6, 5, 4, 3, 2, 10, 9, 8, 1]
[13, 14, 4, 3, 12, 11, 19, 20, 16, 15, 6, 5, 1, 2, 10, 9, 18, 17, 7, 8]
[5, 6, 7, 8, 1, 2, 3, 4, 14, 15, 16, 17, 18, 9, 10, 11, 12, 13, 20, 19]
[14, 4, 3, 12, 13, 20, 16, 15, 6, 5, 1, 2, 10, 11, 19, 18, 17, 7, 8, 9]
Ersetzen Sie für jedes andere Netz einfach jedes Vorkommen von i
durch die i
th-Zahl in der Eingabe (wobei i
1-basiert ist).
Verwandte Herausforderungen
Bestenliste
Der erste Beitrag der Serie generiert eine Rangliste.
Um sicherzustellen, dass Ihre Antworten angezeigt werden, beginnen Sie jede Antwort mit einer Überschrift. Verwenden Sie dazu die folgende Markdown-Vorlage:
## Language Name, N bytes
Wo N
ist die Größe Ihres Beitrags? Wenn Sie Ihren Score zu verbessern, Sie können alte Rechnungen in der Überschrift halten, indem man sich durch das Anschlagen. Zum Beispiel:
## Ruby, <s>104</s> <s>101</s> 96 bytes
(Die Sprache wird derzeit nicht angezeigt, aber das Snippet erfordert und analysiert sie. In Zukunft werde ich möglicherweise eine Bestenliste nach Sprachen hinzufügen.)
quelle
Antworten:
Ruby, 160 Bytes (Rev. B)
17 Bytes gespart dank Vorschlägen von Martin Büttner.
Ruby, 177 Bytes (Rev. A)
Erläuterung
Es ist möglich, alle möglichen Orientierungen durch Rotationen um eine Fläche (3-fach), einen Scheitelpunkt (5-fach) und zwei Kanten (2-fach) zu erzeugen. Aber nicht irgendein Gesicht und Kanten. Die Achsen müssen die richtige Beziehung haben und die Rotationen müssen in der richtigen Reihenfolge ausgeführt werden, sonst können seltsame Dinge passieren.
So habe ich es gemacht (obwohl ich verstehe, dass Martin es anders gemacht hat.)
Alle Orientierungen eines Tetraeders können durch Kombinationen der folgenden drei Symmetrieoperationen erzeugt werden:
a) Drehung um zwei 2-fache Achsen rechts durch die Mittelpunkte der Kanten (diese stehen im rechten Winkel zueinander. Wenn wir sie miteinander multiplizieren, entdecken wir eine dritte 2-fache Achse durch das verbleibende Kantenpaar.)
b) Drehung um eine 3-fache Achse diagonal zu den 2-fachen Achsen, die durch einen Scheitelpunkt und eine Fläche verläuft.
Die Symmetrie des Ikosaeders ist eine Obermenge der des Tetraeders. In der folgenden Abbildung von https://en.wikipedia.org/wiki/Icosahedron definieren die gelben und roten Flächen zwei verschiedene Tetraeder (oder alternativ ein einzelnes Oktaeder), während die beiden blauen Flächen gemeinsame Kanten in drei Paaren bei sind rechte Winkel (und auf den Flächen eines Würfels liegen.)
Alle Ausrichtungen des Ikosaeders können durch die oben erwähnten Symmetrieoperationen plus einer zusätzlichen 5-fachen Operation erzeugt werden.
Die Rotationen um drei der vier oben genannten Achsen werden durch die magischen Ketten zwischen den
''
Markierungen dargestellt. Die Drehung um die zweite 2-fache Achse ist unterschiedlich und kann einfach durch Umkehren des Arrays erfolgena[]
.Ungolfed im Testprogramm:
Alternative Lösung 131 Bytes (Ungültig aufgrund des binären Random-Walk-Ansatzes, ergibt nur eine annähernd korrekte Verteilung.)
Dies ist ein Scramble (ähnlich wie die Programme, die zum Scramble von Rubiks Cube verwendet werden.)
Die spezifischen Rotationen, die ich benutze, sind zwei der offensichtlichsten:
-Eine Drehung um 120 Grad (um die Flächen 1 und 20 gemäß dem ersten Diagramm)
-Eine 72-Grad-Drehung (um die Eckpunkte, die 1,2,3,4,5 und 16,17,18,19,20 gemäß dem ersten Diagramm gemeinsam haben.)
Wir werfen 99 Mal eine Münze und führen jedes Mal eine dieser beiden Umdrehungen durch, je nachdem, ob es sich um Kopf oder Zahl handelt.
Beachten Sie, dass ein Wechsel dieser deterministisch zu ziemlich kurzen Sequenzen führt. Beispielsweise kann mit den richtigen Rotationssensoren eine 180-Grad-Rotation mit einer Periode von nur 2 erzeugt werden.
quelle
b.map
funktioniert nicht direkt, ich mussb.chars.map
es funktionieren lassen (BTW, das auf meinem Computer nicht funktioniert, da ich Ruby 1.9.3 habe, aber es funktioniert auf Ideone.) Es ist eine faire Einsparung. Ich glaube nicht, dass das Ändern der magischen Zeichenfolgen für nicht druckbare Zeichen-64
funktioniert , um den Willen zu retten :%w{}
Interpretationen\n
(sowie Leerzeichen) als Trennzeichen zwischen den generierten Zeichenfolgen im Array. Ich habe keine Ahnung, was es mit anderen nicht druckbaren ASCII-Zeichen tun wird.IA-32 Maschinencode, 118 Bytes
Hexdump:
Es ist ein bisschen lang, deshalb gehen einige Erklärungen zuerst. Früher habe ich fast den gleichen Algorithmus wie die vorhandenen Antwort von Stufe River St . Um meine Antwort zu ändern, habe ich andere grundlegende Permutationen verwendet, die nicht unbedingt eine intuitive geometrische Bedeutung haben, aber irgendwie bequemer sind.
Der Code muss grundsätzlich eine Permutation generieren, die eine sequentielle Anwendung der folgenden ist:
p3
, hat 0 ... 2 mal angewendetq2
, hat 0 oder 1 Mal angewendetp5
, hat 0 ... 4 mal angewendetp2
, hat 0 oder 1 Mal angewendetFür diese Permutationen gibt es viele Möglichkeiten. Einer von ihnen ist wie folgt:
Diese Wahl ist besser als andere, da die Permutationen hier lange Reihen von sequentiellen Indizes aufweisen, die durch Lauflängencodierung komprimiert werden können - nur 29 Bytes für die 4 Permutationen.
Um die Erzeugung von Zufallszahlen zu vereinfachen, habe ich für alle die Potenzen (wie oft jede Permutation angewendet wird) im Bereich von 1 ... 30 gewählt. Dies führt zu viel zusätzlicher Arbeit im Code, da z. B.
p3
jedes Mal eine Identitätspermutation entsteht, wenn sie dreimal mit sich selbst multipliziert wird. Auf diese Weise ist der Code jedoch kleiner. Solange der Bereich durch 30 teilbar ist, wird die Ausgabe gleichmäßig verteilt.Außerdem sollten die Leistungen positiv sein, damit die Lauflängendecodierungsoperation mindestens einmal ausgeführt wird.
Der Code hat 4 verschachtelte Schleifen; Die Gliederung ist wie folgt:
Ich hoffe, dieser Pseudocode ist klarer als der folgende Inline-Assembler-Code.
Einige unterhaltsame Implementierungsdetails:
call
und greife anschließendpop
auf Daten (codierte Permutationen) zu, die im Code gespeichert sindjecxz
Befehl kann ich bequemerweise ein Null-Byte als Abschluss für den Lauflängendecodierungsprozess verwendenGlücklicherweise ist die Zahl 30 (2 * 3 * 5) fast eine Zweierpotenz. Dadurch kann ich mithilfe eines Kurzcodes eine Zahl im Bereich 1 ... 30 generieren:
Ich verwende einen "Allzweck-Divisions" -Befehl (
aam
), um ein Byte in Bitfelder (3-Bit-Länge und 5-Bit-Index) zu trennen. Zum Glück an dieser Stelle im Code,cl = 0
so profitiere ich von beiden "Seiten"xchg
quelle